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 (Solving Constraint Integer Programming).