Geodesic
Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems
Sarpong, Boadu Mensah1, 2  ; Artigues, Christian2, 3  ; Jozefowiez, Nicolas1, 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.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 527-554

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :