Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems
RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 3, pp. 527-554.

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.

Received:
Accepted:
DOI: 10.1051/ro/2014054
Classification: 90C27, 90C29
Keywords: Multi-objective optimization, bound sets, combinatorial optimization, column generation
Sarpong, Boadu Mensah 1, 2; Artigues, Christian 2, 3; Jozefowiez, Nicolas 1, 2

1 CNRS, LAAS, 7 avenue du colonel Roche, 31400 Toulouse, France.
2 University de Toulouse, INSA, LAAS, 31400 Toulouse, France.
3 University de Toulouse, LAAS, 31400 Toulouse, France.
@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://archive.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://archive.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://archive.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, Volume 49 (2015) no. 3, pp. 527-554. doi : 10.1051/ro/2014054. http://archive.numdam.org/articles/10.1051/ro/2014054/

Y.P. Aneja and K.P.K. Nair, Bicriteria transportation problem. Manage. Sci. 25 (1979) 73–78. | DOI | MR | Zbl

J.-F. Bérubé, M. Gendreau and J.-Y. Potvin, 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

N. Boland, J. Dethridge and I. Dumitrescu, Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. 34 (2006) 58–68. | DOI | MR | Zbl

J.R. Current and D.A. Schilling, 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.

M. Desrochers and F. Soumis, A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR 26 (1988) 191–212. | Zbl

M. Dror. Note on the complexity of shortest path models for column generation in VRPTW. Oper. Res. 42 (1994) 977–978. | DOI | Zbl

M. Ehrgott and X. Gandibleux, Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34 (2007) 2674–2694. | DOI | MR | Zbl

D. Feillet, P. Dejax, M. Gendreau and C. Gueguen, 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

M. Gendreau, G. Laporte and F. Semet, The Covering tour problem. Oper. Res. 45 (1997) 568–576. | DOI | MR | Zbl

M. Hachicha, M.J. Hodgson, G. Laporte and F. Semet, Heuristics for the multi-vehicle covering tour problem. Comput. Oper. Res. 27 (2000) 29–42. | DOI | Zbl

M.J. Hodgson, G. Laporte and F. Semet, A Covering Tour Model for Planning Mobile Health Care Facilities in SuhumDistrict, Ghama. J. Regional Sci. 38 (1998) 621–638. | DOI

N. Jozefowiez, F. Semet and E.-G. Talbi, The bi-objective covering tour problem. Comput. Oper. Res. 34 (2007) 1929–1942. | DOI | Zbl

M. Labbé and G. Laporte. Maximizing user convenience and postal service efficiency in post box location. Belgian J. Oper. Res. Stat. Comput. Sci. 26 (1986) 21–35.

G. Righini and M. Salani, New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51 (2008) 155–170. | DOI | MR | Zbl

E. Salari and J. Unkelbach, A column-generation-based method for multi-criteria direct aperture optimization. Phys. Med. Biol. 58 (2013) 621–639. | DOI

F. Sourd and O. Spanjaard, A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS J. Comput. 20 (2008) 472–484. | DOI | MR | Zbl

E.L. Ulungu and J. Teghem. 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

B. Villarreal and M.H. Karwan, Multicriteria integer programming: A (hybrid) dynamic programming recursive approach. Math. Prog. 21 (1981) 204–223. | DOI | MR | Zbl

Cited by Sources: