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.
Citation
Lehrstuhl für Operations Research, RWTH Aachen University, February 2019