Article ID: | iaor20118630 |
Volume: | 150 |
Issue: | 3 |
Start Page Number: | 475 |
End Page Number: | 497 |
Publication Date: | Sep 2011 |
Journal: | Journal of Optimization Theory and Applications |
Authors: | Klamroth Kathrin, Ruzika Stefan, Gorski Jochen |
Keywords: | programming: multiple criteria, programming: assignment, graphs |
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. However, we show that many classical multiple objective combinatorial optimization problems do not possess the connectedness property in general, including, among others, knapsack problems (and even several special cases) and linear assignment problems. We also extend 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 two variants of the knapsack problem to analyze the likelihood with which non‐connected adjacency graphs occur in randomly generated instances.