Safe bounds in linear and mixed-integer linear programming

Publication date: 1 July 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

linear programming interval arithmetic lower bounds branch-and-cut mixed-integer programming rounding errors directed rounding mixed-integer rounding certificate of infeasibility generalized Gomory cut safe cuts safe presolve

Mathematics Subject Classification ID

Mixed integer programming (90C11) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Algorithms with automatic result verification (65G20)

Related Items

A hybrid LP/NLP paradigm for global optimization relaxations, Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects, Exploiting verified neural networks via floating point numerical error, On verified numerical computations in convex programming, A general framework for convexity analysis in deterministic global optimization, An efficient and safe framework for solving optimization problems, A review of computation of mathematically rigorous bounds on optima of linear programs, On strong optimality of interval linear programming, Enhancing interval constraint propagation by identifying and filtering \(n\)-ary subsystems, (Global) optimization: historical notes and recent developments, Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates, Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem, Domain reduction techniques for global NLP and MINLP optimization, Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework, The small octagons of maximal width, Certifying feasibility and objective value of linear programs, Rigorous filtering using linear relaxations, Maximal inner boxes in parametric \textit{AE}-solution sets with linear shape, A reliable affine relaxation method for global optimization, An Exact Rational Mixed-Integer Programming Solver, Exact solutions to linear programming problems, A cut and branch approach for the capacitated \(p\)-median problem based on Fenchel cutting planes, Safe and tight linear estimators for global optimization, A rigorous global filtering algorithm for quadratic constraints, A comparison of complete global optimization solvers, Computational experience with rigorous error bounds for the Netlib linear programming library, A survey of safety and trustworthiness of deep neural networks: verification, testing, adversarial attack and defence, and interpretability, Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations, Testing cut generators for mixed-integer linear programming, Transfer Function Synthesis without Quantifier Elimination, A computational status update for exact rational mixed integer programming, A computational status update for exact rational mixed integer programming, On the safety of Gomory cut generators, A hybrid branch-and-bound approach for exact rational mixed-integer programming, Enhancing robustness verification for deep neural networks via symbolic propagation, Fast construction of constant bound functions for sparse polynomials, Iterative Refinement for Linear Programming, Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work, Towards an Accurate Solution of Wireless Network Design Problems, Enhancing numerical constraint propagation using multiple inclusion representations, Validated constraints solving --- practicalities, pitfalls, and new developments

Uses Software