Safe bounds in linear and mixed-integer programming

Arnold Neumaier (Arnold.Neumaierunivie.ac.at)
Oleg Shcherbina (soa7yandex.ru)

Abstract: Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size.

Keywords: Linear programming, mixed-integer programming, rounding errors, directed rounding, interval arithmetic, branch-and-cut, lower bounds, mixed-integer rounding, generalized Gomory cut, safe cuts, safe presolve, certificate of infeasibility.

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

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: http://www.mat.univie.ac.at/+AH4-neum/papers.html#mip

Download: [Compressed Postscript][PDF]

Entry Submitted: 06/18/2002
Entry Accepted: 06/18/2002
Entry Last Modified: 06/18/2002

Modify/Update this entry