Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization
- Connectedness of efficient solutions is a powerful property in multiple objective combinatorial optimization since it allows the construction of the complete efficient set using neighborhood search techniques. In this paper we show that, however, most of the classical multiple objective combinatorial optimization problems do not possess the connectedness property in general, including, among others, knapsack problems (and even several special cases of knapsack problems) and linear assignment problems. We also extend already known non-connectedness results for several optimization problems on graphs like shortest path, spanning tree and minimum cost flow problems. Different concepts of connectedness are discussed in a formal setting, and numerical tests are performed for different variants of the knapsack problem to analyze the likelihood with which non-connected adjacency graphs occur in randomly generated problem instances.
Verfasser*innenangaben: | Jochen Gorski, Kathrin Klamroth, Stefan Ruzika |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-18165 |
Schriftenreihe (Bandnummer): | Report in Wirtschaftsmathematik (WIMA Report) (102) |
Dokumentart: | Preprint |
Sprache der Veröffentlichung: | Englisch |
Jahr der Fertigstellung: | 2006 |
Jahr der Erstveröffentlichung: | 2006 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 28.11.2006 |
Freies Schlagwort / Tag: | MOCO; Multiple objective combinatorial optimization; adjacency; connectedness; neighborhood search |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |