Affordable Access

Publisher Website

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

Authors
Journal
European Journal of Operational Research
0377-2217
Publisher
Elsevier
Publication Date
Volume
199
Issue
1
Identifiers
DOI: 10.1016/j.ejor.2008.10.031
Keywords
  • Multi-Objective Linear And Integer Programming
  • Multi-Objective Network Flows
  • Negative-Cycle Algorithms
  • Parametric Programming
Disciplines
  • Computer Science

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.