IJPAM: Volume 103, No. 4 (2015)
GENERATION -- A MEANS FOR PREDICTING
OPTIMAL COLUMNS


Torbjörn Larsson



Gothenburg, SWEDEN

Linköping University, SWEDEN

Linköping University, SWEDEN
Abstract. We propose a two-phase combination of two
optimization techniques, Lagrangian relaxation and column generation,
with the aim of overcoming their respective drawbacks.
In a prediction phase, subgradient
optimization is used and the Lagrangian relaxed solutions found are used to
initialize a master problem. In a solution phase,
column generation is performed. We provide a
validation of this two-phase method through an asymptotic
result for the prediction phase and give guidelines for its truncated usage.
The two-phase method is assessed on a multicommodity
network flow problem, for which it performs significantly better than
a pure column generation method.
We conclude that the subgradient optimization
prediction phase can accelerate a column generation method
considerably.
Received: August 16, 2015
AMS Subject Classification: 90C05, 90C08, 90C06, 90-08
Key Words and Phrases: linear programming, integer linear programming, subgradient optimization, column generation, Dantzig-Wolfe decomposition, multicommodity network flows
Download paper from here.
DOI: 10.12732/ijpam.v103i4.14 How to cite this paper?
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2015
Volume: 103
Issue: 4
Pages: 797 - 818
Google Scholar; DOI (International DOI Foundation); WorldCAT.
This work is licensed under the Creative Commons Attribution International License (CC BY).