Exploring the numerics of branch-and-cut for mixed integer linear optimization

DOI10.1007/978-3-319-89920-6_21MaRDI QIDQ4685751zbMATH OpenOpenAlexFDO

Authors Matthias Miltenberger, Ted K. Ralphs, Daniel E. Steffy

Publication date 9 October 2018

Published in Operations Research Proceedings (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.03455

zbMATH Keywords

algorithm analysislinear programmingmixed integer programming

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct.

Recommendations

• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• Improving branch-and-cut performance by random sampling
• scientific article; zbMATH DE number 2084777
• Computational Integer Programming and Cutting Planes
• Improved strategies for branching on general disjunctions

Cites work

• A relax-and-cut framework for Gomory mixed-integer cuts
• Accuracy and Stability of Numerical Algorithms
• Condition. The geometry of numerical algorithms
• Integer Programming
• Lexicography and degeneracy: Can a pure cutting plane algorithm work?
• MIPLIB 2003

Cited in

(5)

• An algorithm-independent measure of progress for linear constraint propagation
• Improving branch-and-cut performance by random sampling
• scientific article; zbMATH DE number 2084777 (Why is no real title available?)
• \(\mathcal{V}\)-polyhedral disjunctive cuts
• The strength of root cuts in an extended abstract branch-and-cut model

Describes a project that uses

Uses Software

• SCIP
• MIPLIB
• MIPLIB2003

This page was built for publication: Exploring the numerics of branch-and-cut for mixed integer linear optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4685751)