Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization
Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization
复制标题
多目标组合优化中有效解的连通性
DOI：
--
复制
发表时间：
2011
影响因子：
1.9
通讯作者：
Stefan Ruzika
中科院分区：
文献类型：
--
作者：
Jochen Gorski;K. Klamroth;Stefan Ruzika
有效解的连通性是多目标组合优化中的一个重要性质，因为它允许使用邻域搜索技术构造完全有效集。然而，我们发现，许多经典的多目标组合优化问题并不具备连通性一般，其中包括背包问题（甚至几个特殊情况下）和线性分配问题。我们还扩展了已知的非连通性的结果，如最短路径，生成树和最小费用流问题的图上的几个优化问题。不同的连通性的概念进行了讨论，在一个正式的设置，并进行数值测试的背包问题的两个变种，以分析的可能性与非连接的邻接图发生在随机生成的实例。
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.