Connectedness of Efficient Solutions in Multiple Criteria Combinatorial Optimization
- In multiple criteria optimization an important research topic is the topological structure of the set \( X_e \) of efficient solutions. Of major interest is the connectedness of \( X_e \), since it would allow the determination of \( X_e \) without considering non-efficient solutions in the process. We review general results on the subject,including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem.
Author: | Matthias Ehrgott, Kathrin Klamroth |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-48443 |
Series (Serial Number): | Preprints (rote Reihe) des Fachbereich Mathematik (265) |
Document Type: | Report |
Language of publication: | English |
Date of Publication (online): | 2017/10/13 |
Year of first Publication: | 1995 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2017/10/16 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Licence (German): | Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0) |