Issue |
RAIRO-Oper. Res.
Volume 49, Number 3, July-September 2015
|
|
---|---|---|
Page(s) | 527 - 554 | |
DOI | https://doi.org/10.1051/ro/2014054 | |
Published online | 06 February 2015 |
Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems
1 CNRS, LAAS, 7 avenue du colonel Roche, 31400 Toulouse, France.
bmsarpon@laas.fr
2 University de Toulouse, INSA, LAAS, 31400 Toulouse, France.
artigues@laas.fr
3 University de Toulouse, LAAS, 31400 Toulouse, France.
njozefow@laas.fr
Received: 29 September 2014
Accepted: 16 October 2014
We discuss the use of column generation in a bi-objective setting. Just as in single objective combinatorial optimization, the role of column generation in the bi-objective setting is to compute dual bounds (i.e. lower bounds for minimization problems and upper bounds for maximization problems) which can be used to guide the search for efficient solutions or to evaluate the quality of approximate solutions. The general idea used in this paper is to first transform the bi-objective problem into single objective by a scalarization method and then solve the transformed problem several times by varying the necessary parameters. We show that irrespective of the scalarization method used, similar subproblems are solved when applying column generation. For this reason, we investigate possible ways of intelligently searching for columns for these subproblems in order to accelerate the column generation method.
Mathematics Subject Classification: 90C27 / 90C29
Key words: Multi-objective optimization / bound sets / combinatorial optimization / column generation
© EDP Sciences, ROADEF, SMAI, 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.