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.
Metadaten
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)