Safe bounds in linear and mixed-integer programming
Arnold Neumaier (Arnold.Neumaierunivie.ac.at)
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 )
Entry Submitted: 06/18/2002
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|