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.
Accepté le :
DOI : 10.1051/ro/2014054
Mots clés : Multi-objective optimization, bound sets, combinatorial optimization, column generation
@article{RO_2015__49_3_527_0,
author = {Sarpong, Boadu Mensah and Artigues, Christian and Jozefowiez, Nicolas},
title = {Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {527--554},
publisher = {EDP-Sciences},
volume = {49},
number = {3},
year = {2015},
doi = {10.1051/ro/2014054},
mrnumber = {3349133},
zbl = {1327.90265},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2014054/}
}
TY - JOUR AU - Sarpong, Boadu Mensah AU - Artigues, Christian AU - Jozefowiez, Nicolas TI - Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 527 EP - 554 VL - 49 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2014054/ DO - 10.1051/ro/2014054 LA - en ID - RO_2015__49_3_527_0 ER -
%0 Journal Article %A Sarpong, Boadu Mensah %A Artigues, Christian %A Jozefowiez, Nicolas %T Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 527-554 %V 49 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2014054/ %R 10.1051/ro/2014054 %G en %F RO_2015__49_3_527_0
Sarpong, Boadu Mensah; Artigues, Christian; Jozefowiez, Nicolas. Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 527-554. doi : 10.1051/ro/2014054. http://www.numdam.org/articles/10.1051/ro/2014054/
and , Bicriteria transportation problem. Manage. Sci. 25 (1979) 73–78. | DOI | MR | Zbl
, and , An exact -constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits. Eur. J. Oper. Res. 194 (2009) 39–50. | DOI | MR | Zbl
, and , Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. 34 (2006) 58–68. | DOI | MR | Zbl
and , The median tour and maximal covering tour problems: Formulations and heuristics. Eur. J. Oper. Res. 73 (1994) 114–126. | DOI | Zbl
C. Delort and O. Spanjaard, Using bound sets in multiobjective optimization: Application to the biobjective binary knapsack problem, in Experimental Algorithms, Springer (2010) 253–265.
and , A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR 26 (1988) 191–212. | Zbl
. Note on the complexity of shortest path models for column generation in VRPTW. Oper. Res. 42 (1994) 977–978. | DOI | Zbl
and , Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34 (2007) 2674–2694. | DOI | MR | Zbl
, , and , An exact algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to some vehicle routing problems. Networks 44 (2004) 216–229. | DOI | MR | Zbl
, and , The Covering tour problem. Oper. Res. 45 (1997) 568–576. | DOI | MR | Zbl
, , and , Heuristics for the multi-vehicle covering tour problem. Comput. Oper. Res. 27 (2000) 29–42. | DOI | Zbl
, and , A Covering Tour Model for Planning Mobile Health Care Facilities in SuhumDistrict, Ghama. J. Regional Sci. 38 (1998) 621–638. | DOI
, and , The bi-objective covering tour problem. Comput. Oper. Res. 34 (2007) 1929–1942. | DOI | Zbl
and . Maximizing user convenience and postal service efficiency in post box location. Belgian J. Oper. Res. Stat. Comput. Sci. 26 (1986) 21–35.
and , New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51 (2008) 155–170. | DOI | MR | Zbl
and , A column-generation-based method for multi-criteria direct aperture optimization. Phys. Med. Biol. 58 (2013) 621–639. | DOI
and , A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS J. Comput. 20 (2008) 472–484. | DOI | MR | Zbl
and . The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. Found. Comput. Dec. Sci. 20 (1995) 149–165. | MR | Zbl
F. Vanderbeck, Implementing mixed integer column generation, in Column Generation, edited by G. Desaulniers, J. Desrosiers and M.M. Solomon. Springer (2005) 331–358. | Zbl
and , Multicriteria integer programming: A (hybrid) dynamic programming recursive approach. Math. Prog. 21 (1981) 204–223. | DOI | MR | Zbl
Cité par Sources :
