On the computation of all supported efficient solutions in multi-objective integer network flow problems

Eusébio, Augusto; Figueira, José Rui

http://hdl.handle.net/10400.8/12937

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
On the computation of all supported efficient solutions in multi-objective integer network flow problems.pdf	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.	577.17 KB	Adobe PDF	Download

Send Feedback

Authors

Eusébio, Augusto

Figueira, José Rui

Abstract(s)

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.

Keywords

Multi-objective linear and integer programming Multi-objective network flows Negative-cycle algorithms Parametric programming

URI

http://hdl.handle.net/10400.8/12937

Citation

Augusto Eusébio, José Rui Figueira, On the computation of all supported efficient solutions in multi-objective integer network flow problems, European Journal of Operational Research, Volume 199, Issue 1, 2009, Pages 68-76, ISSN 0377-2217, https://doi.org/10.1016/j.ejor.2008.10.031.