Dual-Optimal Inequalities for Stabilized Column Generation

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

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2006-05, Vol.54 (3), p.454-463
Main Authors: Ben Amor, Hatem, Desrosiers, Jacques, Valerio de Carvalho, Jose Manuel
Format: Article
Language:English
Subjects:
Aggregation
Algorithms
Analysis
Applied sciences
column generation
Computers
Cutting stock problem
cutting-stock problems
dual cuts
Dynamic programming
Exact sciences and technology
Flows in networks. Combinatorial problems
Integers
linear large-scale systems
Linear programming
Mathematical optimization
Mathematical vectors
Methods
Minimization of cost
Operational research and scientific management
Operational research. Management science
Operations research
Optimal solutions
Optimization
Preprocessing
Production scheduling
programming
Scalars
Scheduling, sequencing
stabilization
Studies
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.1060.0278