Tighter LP Relaxations for Configuration Knapsacks Using Extended Formulations

Abstract

Knapsack inequalities frequently occur in many practical MIP applications. Since their LP relaxation can be weak, modern solvers tighten the formulation incrementally using different separation techniques such as (GUB) cover inequalities. A fundamentally different approach has been introduced in the context of standard line planning (SLP) optimization by Hoppmann, Borndörfer, and Karbstein, who propose an explicit extended formulation, comparable to a Dantzig-Wolfe reformulation of the problem, which implies several important classes of inequalities. The size of the reformulation is tractable because SLP has only knapsack constraints with a bounded number of distinct weights, so-called “configuration knapsacks”. We present a generalization of this approach to arbitrary MIPs involving configuration knapsacks, which we implemented in the MIP solver SCIP. We compare the obtained LP relaxations of this reformulation against standard cutting planes, and discuss the computational benefits and limitations in order to use this extended formulation in practice.

Date
Location
Bordeaux, France