1233
eng
reportzib
0
2011-03-10
2011-03-10
--
Valid Linear Programming Bounds for Exact Mixed-Integer Programming
Fast computation of valid linear programming (LP) bounds serves as an
important subroutine for solving mixed-integer programming problems
exactly. We introduce a new method for computing valid LP bounds designed
for this application. The algorithm corrects approximate LP dual solutions
to be exactly feasible, giving a valid bound. Solutions are repaired by
performing a projection and a shift to ensure all constraints are
satisfied; bound computations are accelerated by reusing structural
information through the branch-and-bound tree. We demonstrate this method
to be widely applicable and faster than solving a sequence of exact LPs.
Several variations of the algorithm are described and computationally
evaluated in an exact branch-and-bound algorithm within the mixed-integer
programming framework SCIP.
11-08
urn:nbn:de:0297-zib-12332
Daniel Steffy
-empty- (Opus4 user: )
Kati Wolter
Kati Wolter
ZIB-Report
11-08
deu
uncontrolled
linear programming bounds
deu
uncontrolled
mixed integer programming
deu
uncontrolled
branch-and-bound
deu
uncontrolled
exact computation
Mathematical programming methods [See also 90Cxx]
Computational methods
Mixed integer programming
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1233/ZR-11-08.pdf