Exact algorithms for OWA-optimization in multiobjective spanning tree problems

DSpace/Manakin Repository

Exact algorithms for OWA-optimization in multiobjective spanning tree problems

Show full item record

Title: Exact algorithms for OWA-optimization in multiobjective spanning tree problems
Author: Spanjaard, Olivier; Galand, Lucie
Type: Article accepté pour publication ou publié
Date de création: 2012
Résumé en anglais: 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.
Lien vers un document non conservé dans cette base: http://arxiv.org/abs/0910.5744v1
Indexation documentaire: Recherche opérationnelle
Sujet(s): optimality conditions; Multiobjective spanning tree problem; MIP formulation; ordered weighted average; branch and bound
URL de la notice: http://basepub.dauphine.fr/xmlui/handle/123456789/6081
PUBLIE DANS
Nom de la revue: Computers and Operations Research
Volume: 39
Numéro: 7
Parution: 2012
Pages: 1540-1554
Editeur: Elsevier
Réf. Version publiée: http://dx.doi.org/10.1016/j.cor.2011.09.003

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show full item record

Browse

My Account

Statistics