On the computation of all supported efficient solutions in multi-objective integer network flow problems
Eusebio, Augusto; Figueira, José (2009), On the computation of all supported efficient solutions in multi-objective integer network flow problems, European Journal of Operational Research, 199, 1, p. 68-76. http://dx.doi.org/10.1016/j.ejor.2008.10.031
Type
Article accepté pour publication ou publiéDate
2009Journal name
European Journal of Operational ResearchVolume
199Number
1Publisher
Elsevier
Pages
68-76
Publication identifier
Metadata
Show full item recordAbstract (EN)
This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.Subjects / Keywords
Multi-objective linear and integer programming; Multi-objective network flows; Negative-cycle algorithms; Parametric programmingRelated items
Showing items related by title and author.
-
Eusebio, Augusto; Figueira, José (2009) Article accepté pour publication ou publié
-
Eusebio, Augusto; Figueira, José; Ehrgott, Matthias (2009) Article accepté pour publication ou publié
-
Dächert, Kerstin; Klamroth, Kathrin; Lacour, Renaud; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
-
Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2014) Article accepté pour publication ou publié
-
Mavrotas, George; Figueira, José; Florios, Kostas (2009) Article accepté pour publication ou publié