Optimization Online


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

Marco E. Luebbecke(marco.luebbecke***at***rwth-aachen.de)
Stephen J. Maher(s.maher3***at***lancaster.ac.uk)
Jonas T. Witt(jonas.witt***at***rwth-aachen.de)

Abstract: 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.

Keywords: Benders decomposition, Dantzig-Wolfe reformulation, domain reduction, column generation

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Lehrstuhl für Operations Research, RWTH Aachen University, February 2019

Download: [PDF]

Entry Submitted: 02/28/2019
Entry Accepted: 02/28/2019
Entry Last Modified: 02/28/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society