On the computation of all supported efficient solutions in multi-objective integer network flow problems |
| |
Authors: | Augusto Eusébio José Rui Figueira |
| |
Institution: | 1. Escola Superior de Tecnologia e Gestão, Instituto Politécnico de Leiria, Morro do Lena – Alto Vieiro, 2411-901 Leiria, Portugal;2. CEG-IST, Center for Management Studies, Instituto Superior Técnico, Technical University of Lisbon, TagusPark, Av. Cavaco Silva, 2780-990 Porto Salvo, Portugal;3. Associate Researcher at LAMSADE, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75 775 Paris Cedex 16, France |
| |
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. |
| |
Keywords: | Multi-objective linear and integer programming Multi-objective network flows Negative-cycle algorithms Parametric programming |
本文献已被 ScienceDirect 等数据库收录! |
|