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
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (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 / KeywordsMulti-objective linear and integer programming; Multi-objective network flows; Negative-cycle algorithms; Parametric programming
Showing items related by title and author.
Dächert, Kerstin; Klamroth, Kathrin; Lacour, Renaud; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
An efficient procedure for finding best compromise solutions to the multi-objective assignment problem Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2014) Article accepté pour publication ou publié