Andreas Westerlund, Maud Göthe-Lundgren,
Torbjörn Larsson, Di Yuan
Jeppesen Systems AB
Gothenburg, SWEDEN
Department of Science and Technology
Linköping University, SWEDEN
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.

Google Scholar; DOI (International DOI Foundation); WorldCAT.

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