This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ben Amor, H. Articles by Valério de Carvalho, J. M. Search for Related Content

Dual-Optimal Inequalities for Stabilized Column Generation

GERAD and École Polytechnique de Montréal, C.P. 6079, succ. Centre-ville, Montréal, Quebec, Canada H3C 3A7
HEC Montréeal and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Quebec, Canada H3T 2A7
Departamento de Produção e Sistemas, Universidade do Minho, Campus de Gualtar, 4710-057 Braga, Portugal
hatem.ben.amor{at}gerad.ca
jacques.desrosiers{at}hec.ca
vc{at}dps.uminho.pt

Column generation is one of the most successful approaches for solving large-scale linear programming problems. However, degeneracy difficulties and long-tail effects are known to occur as problems become larger. In recent years, several stabilization techniques of the dual variables have proven to be effective. We study the use of two types of dual-optimal inequalities to accelerate and stabilize the whole convergence process. Added to the dual formulation, these constraints are satisfied by all or a subset of the dual-optimal solutions. Therefore, the optimal objective function value of the augmented dual problem is identical to the original one. Adding constraints to the dual problem leads to adding columns to the primal problem, and feasibility of the solution may be lost. We propose two methods for recovering primal feasibility and optimality, depending on the type of inequalities that are used. Our computational experiments on the binary and the classical cutting-stock problems, and more specifically on the so-called triplet instances, show that the use of relevant dual information has a tremendous effect on the reduction of the number of column generation iterations.

Subject classifications: production/scheduling; cutting-stock problems; programming; linear large-scale systems; column generation; stabilization; dual cuts.
History: Received April 2003; revision received May 2004; accepted March 2005.

This article has been cited by other articles:

				A. Ceselli, G. Righini, and M. Salani A Column Generation Algorithm for a Rich Vehicle-Routing Problem Transportation Science, February 1, 2009; 43(1): 56 - 69. [Abstract] [PDF]

				S. Subramanian and H. D. Sherali An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems INFORMS Journal on Computing, September 1, 2008; 20(4): 565 - 578. [Abstract] [PDF]