Optimization Online


Improved Column Generation for Highly Degenerate Master Problems

Jacques Desrosiers (jacques.desrosiers***at***hec.ca)
Jean-Bertrand Gauthier (jean-bertrand.gauthier***at***hec.ca)
Marco Lübbecke (marco.luebbecke***at***rwth-aachen.de)

Abstract: Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation method that may take advantage of degenerate solutions. The idea is to reduce the number of constraints to the number of strictly positive basic variables in the current master problem solution. The advantage of this row-reduction is a smaller working basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem that needs to generate weighted subsets of variables that are compatible with the row-reduction, if possible. Such a compatible subset of variables gives rise to a strict improvement in the objective function value if the weighted combination of the reduced costs is negative. We thus state, as a by-product, a necessary and sufficient optimality condition for linear programming. This methodological paper generalizes the improved primal simplex and dynamic constraints aggregation methods. On highly degenerate linear programs, recent computational experiments with these two algorithms show that the row-reduction of a problem might have a large impact on the solution time. We conclude with a few algorithmic and implementation issues.

Keywords: Column generation, degeneracy, dynamic row-reduction

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

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

Citation: Les Cahiers du GERAD G-2011-66

Download: [PDF]

Entry Submitted: 12/01/2011
Entry Accepted: 12/01/2011
Entry Last Modified: 02/06/2013

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