A generalization of column generation to accelerate convergence

This paper proposes a generalization of column generation, reformulating the master problem with fewer variables at the expense of adding more constraints; the sub-problem structure does not change. It shows both analytically and computationally that the reformulation promotes faster convergence to...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2010-04, Vol.122 (2), p.349-378
Main Authors: Liang, Dong, Wilhelm, Wilbert E.
Format: Article
Language:English
Subjects:
Applied sciences
Calculus of variations and optimal control
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Commodities
Cutting stock problem
Exact sciences and technology
Flows in networks. Combinatorial problems
Full Length Paper
Integer programming
Inventory control, production control. Distribution
Linear programming
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Operational research and scientific management
Operational research. Management science
Polytopes
Sciences and techniques of general use
Studies
Theoretical
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:This paper proposes a generalization of column generation, reformulating the master problem with fewer variables at the expense of adding more constraints; the sub-problem structure does not change. It shows both analytically and computationally that the reformulation promotes faster convergence to an optimal solution in application to a linear program and to the relaxation of an integer program at each node in the branch-and-bound tree. Further, it shows that this reformulation subsumes and generalizes prior approaches that have been shown to improve the rate of convergence in special cases.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-008-0251-8