• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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.5744v1
Date
2012
Journal name
Computers and Operations Research
Volume
39
Number
7
Publisher
Elsevier
Pages
1540-1554
Publication identifier
http://dx.doi.org/10.1016/j.cor.2011.09.003
Metadata
Show full item record
Author(s)
Galand, Lucie
Spanjaard, Olivier
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.
Subjects / Keywords
MIP formulation; Multiobjective spanning tree problem; branch and bound; optimality conditions; ordered weighted average

Related items

Showing items related by title and author.

  • Thumbnail
    Choquet-based optimisation in multiobjective shortest path and spanning tree problems 
    Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (2010) Article accepté pour publication ou publié
  • Thumbnail
    A Branch and Bound Algorithm for Choquet Optimization in Multicriteria Problems 
    Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (2010) Communication / Conférence
  • Thumbnail
    Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal 
    Lacour, Renaud (2014-07) Thèse
  • Thumbnail
    Bidirectional Preference-based Search for Multiobjective State Space Graph Problems 
    Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence
  • Thumbnail
    Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs 
    Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo