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.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Jochen Gorski, Kathrin Klamroth, Stefan Ruzika
URN (Permalink):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 Verö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:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $