Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization

Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: multiple criteria, programming: assignment, graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.