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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jochen Gorski, Kathrin Klamroth, Stefan Ruzika
URN (permanent link):urn:nbn:de:hbz:386-kluedo-18165
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (102)
Document Type:Preprint
Language of publication:English
Year of Completion:2006
Year of Publication:2006
Publishing Institute:Technische Universität Kaiserslautern
Tag:MOCO ; Multiple objective combinatorial optimization ; adjacency; connectedness; neighborhood search
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $