On the design and anytime performance of ...
Document type :
Communication dans un congrès avec actes
DOI :
Title :
On the design and anytime performance of indicator-based branch and bound for multi-objective combinatorial optimization
Author(s) :
Jesus, Alexandre [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Universidade de Coimbra [Coimbra]
Paquete, Luís [Auteur]
Universidade de Coimbra [Coimbra]
Derbel, Bilel [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Liefooghe, Arnaud [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Optimisation de grande taille et calcul large échelle [BONUS]
Optimisation de grande taille et calcul large échelle [BONUS]
Universidade de Coimbra [Coimbra]
Paquete, Luís [Auteur]
Universidade de Coimbra [Coimbra]
Derbel, Bilel [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Liefooghe, Arnaud [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Optimisation de grande taille et calcul large échelle [BONUS]
Conference title :
GECCO 2021 - The Genetic and Evolutionary Computation Conference
City :
Lille
Country :
France
Start date of the conference :
2021-07
Publisher :
ACM
HAL domain(s) :
Informatique [cs]/Recherche opérationnelle [cs.RO]
Mathématiques [math]/Optimisation et contrôle [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]
English abstract : [en]
In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next ...
Show more >In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the ε-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on a multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available.Show less >
Show more >In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the ε-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on a multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- document
- Open access
- Access the document
- jesus2021design.pdf
- Open access
- Access the document
- 3449639.3459360
- Open access
- Access the document