Exact algorithms for OWA-optimization in multiobjective spanning tree problems
Galand, Lucie; Spanjaard, Olivier (2012), Exact algorithms for OWA-optimization in multiobjective spanning tree problems, Computers and Operations Research, 39, 7, p. 1540-1554. http://dx.doi.org/10.1016/j.cor.2011.09.003
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/0910.5744v1Date
2012Journal name
Computers and Operations ResearchVolume
39Number
7Publisher
Elsevier
Pages
1540-1554
Publication identifier
Metadata
Show full item recordAbstract (EN)
This paper deals with the multiobjective version of the optimal spanning tree problem. More precisely, we are interested in determining the optimal spanning tree according to an Ordered Weighted Average (OWA) of its objective values. We first show that the problem is weakly NP-hard. In the case where the weights of the OWA are strictly decreasing, we then propose a mixed integer programming formulation, and provide dedicated optimality conditions yielding an important reduction of the size of the program. Next, we present two bounds that can be used to prune subspaces of solutions either in a shaving phase or in a branch and bound procedure. The validity of these bounds does not depend on specific properties of the weights (apart from non-negativity). All these exact resolution algorithms are compared on the basis of numerical experiments, according to their respective validity scopes.Subjects / Keywords
MIP formulation; Multiobjective spanning tree problem; branch and bound; optimality conditions; ordered weighted averageRelated items
Showing items related by title and author.
-
Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (2010) Article accepté pour publication ou publié
-
Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (2010) Communication / Conférence
-
Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence
-
Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence