Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization |
| |
Authors: | Jochen Gorski Kathrin Klamroth Stefan Ruzika |
| |
Institution: | 1.Arbeitsgruppe Optimierung und Approximation, Fachbereich C–Mathematik und Naturwissenschaften,Bergische Universit?t Wuppertal,Wuppertal,Germany;2.Department of Mathematics,University of Kaiserslautern,Kaiserslautern,Germany |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|