Skip to Main content Skip to Navigation
Journal articles

Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems

Christian Artigues 1 Boadu Mensah Sarpong 2, 1 Nicolas Jozefowiez 1
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
2 G-SCOP_ROSP [?-2015] - Recherche Opérationnelle pour les Systèmes de Production [?-2015]
G-SCOP [2006-2015] - Laboratoire des sciences pour la conception, l'optimisation et la production [2006-2015]
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal.laas.fr/hal-01875890
Contributor : Christian Artigues <>
Submitted on : Tuesday, September 18, 2018 - 12:11:57 AM
Last modification on : Friday, July 17, 2020 - 2:34:11 PM

Links full text

Identifiers

Citation

Christian Artigues, Boadu Mensah Sarpong, Nicolas Jozefowiez. Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems. RAIRO - Operations Research, EDP Sciences, 2015, 49 (3), pp.527 - 554. ⟨10.1051/ro/2014054⟩. ⟨hal-01875890⟩

Share

Metrics

Record views

344