A preference-based approach to spanning trees and shortest paths problems

A preference-based approach to spanning trees and shortest paths problems

0.00 Avg rating0 Votes
Article ID: iaor2006328
Country: Netherlands
Volume: 162
Issue: 3
Start Page Number: 548
End Page Number: 601
Publication Date: May 2005
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: multiple criteria
Abstract:

Comparison of solutions in combinatorial problems is often based on an additive cost function inducing a complete order on solutions. We investigate here a generalization of the problem, where preferences take the form of a quasi-transitive binary relation defined on the solutions space. We first propose preference-based search algorithms for two classical combinatorial problems, namely the preferred spanning trees problem (a generalization of the minimum spanning tree problem) and the preferred paths problem (a generalization of the shortest path problem). Then, we introduce a very useful axiom for preference relations called independence. Using this axiom, we establish admissibility results concerning our preference-based search algorithms. Finally, we address the problem of dealing with non-independent preference relations and provide different possible solutions for different particular problems (e.g. lower approximation of the set of preferred solutions for multicriteria spanning trees problems, or relaxation of the independence axiom for interval-value preferred path problems).

Reviews

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