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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Jochen Gorski, Kathrin Klamroth, Stefan Ruzika
URN:urn:nbn:de:hbz:386-kluedo-18165
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (102)
Document Type:Preprint
Language of publication:English
Year of Completion:2006
Year of first Publication:2006
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2006/11/28
Tag:MOCO; Multiple objective combinatorial optimization; adjacency; connectedness; neighborhood search
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011