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

Matthias Miltenberger (), Ted Ralphs () and Daniel E. Steffy ()
Additional contact information
Matthias Miltenberger: Zuse Institute Berlin
Ted Ralphs: Lehigh University
Daniel E. Steffy: Oakland University

A chapter in Operations Research Proceedings 2017, 2018, pp 151-157 from Springer

Abstract: 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.

Keywords: Mixed Integer Programming; Linear Programming; Algorithm Analysis (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-89920-6_21

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_21

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().