IJPAM: Volume 103, No. 4 (2015)

SUBGRADIENT OPTIMIZATION PRIOR TO COLUMN
GENERATION -- A MEANS FOR PREDICTING
OPTIMAL COLUMNS

Andreas Westerlund$^1$, Maud Göthe-Lundgren$^2$,
Torbjörn Larsson$^3$, Di Yuan$^4$
$^1$Jeppesen Systems AB
Gothenburg, SWEDEN
$^{2,4}$Department of Science and Technology
Linköping University, SWEDEN
$^3$Department of Mathematics
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.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).