Optimization Online


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

Matthias Miltenberger (miltenberger***at***zib.de)
Ted Ralphs (tkralphs***at***lehigh.edu)
Dan Steffy (steffy***at***oakland.edu)

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: Algorithm Analysis; Linear Programming; Mixed Integer Programming

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Optimization Software and Modeling Systems

Citation: ZIB-Report (17-43), Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany, 07/2017

Download: [PDF]

Entry Submitted: 03/06/2018
Entry Accepted: 03/06/2018
Entry Last Modified: 02/08/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society