• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Exact algorithms for OWA-optimization in multiobjective spanning tree problems

Thumbnail
Date
2012
Link to item file
https://arxiv.org/abs/0910.5744v1
Dewey
Recherche opérationnelle
Sujet
MIP formulation; Multiobjective spanning tree problem; branch and bound; optimality conditions; ordered weighted average
Journal issue
Computers and Operations Research
Volume
39
Number
7
Publication date
2012
Article pages
1540-1554
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.cor.2011.09.003
URI
https://basepub.dauphine.fr/handle/123456789/6081
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Galand, Lucie
Spanjaard, Olivier
Type
Article accepté pour publication ou publié
Abstract (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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.