TY - GEN A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Valid Linear Programming Bounds for Exact Mixed-Integer Programming N2 - 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. T3 - ZIB-Report - 11-08 KW - linear programming bounds KW - mixed integer programming KW - branch-and-bound KW - exact computation Y1 - 2011 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1233 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-12332 ER -