Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization

DOI10.1007/978-3-319-89920-6_21zbMATH Open1397.90283arXiv1803.03455OpenAlexW2962679072MaRDI QIDQ4685751FDOQ4685751

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

Publication date: 9 October 2018

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

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.

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

zbMATH Keywords

linear programmingmixed integer programmingalgorithm analysis

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• An algorithm-independent measure of progress for linear constraint propagation
• Title not available (Why is that?)

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)