Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

Marco E. Lübbecke, Stephen J. Maher, Jonas T. Witt

When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are not generated. We introduce a sufficient condition for strong redundancy that can be checked by solving a compact LP. Using a dual solution of this compact LP we generate classical Benders cuts for the subproblem so that the generation of strongly redundant columns can be avoided. The potential of these cuts to improve the dual bound of the column generation master problem is evaluated computationally using an implementation in the branch-price-and-cut solver GCG. While their efficacy is limited on classical problems, the cuts’ usefulness is significantly demonstrated on structured models, when a temporal decomposition can be applied.

Discrete Optimization 39:100626, 2021.

Download: Journal Article