Dual-Optimal Inequalities for Stabilized Column Generation

Hatem Ben Amor (), Jacques Desrosiers () and José Manuel Valério de Carvalho ()
Additional contact information
Hatem Ben Amor: GERAD and École Polytechnique de Montréal, C.P. 6079, succ. Centre-ville, Montréal, Quebec, Canada H3C 3A7
Jacques Desrosiers: HEC Montréeal and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Quebec, Canada H3T 2A7
José Manuel Valério de Carvalho: Departamento de Produção e Sistemas, Universidade do Minho, Campus de Gualtar, 4710-057 Braga, Portugal

Operations Research, 2006, vol. 54, issue 3, 454-463

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

Keywords: production/scheduling; cutting-stock problems; programming; linear large-scale systems; column generation; stabilization; dual cuts (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (43)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0278 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:54:y:2006:i:3:p:454-463

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().