Titre :

On the design and anytime performance of indicator-based branch and bound for multi-objective combinatorial optimization

Auteur(s) :

Jesus, Alexandre [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Universidade de Coimbra = University of Coimbra [Portugal] [UC]
Paquete, Luís [Auteur]
Universidade de Coimbra = University of Coimbra [Portugal] [UC]
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]

Titre de la manifestation scientifique :

GECCO 2021 - The Genetic and Evolutionary Computation Conference

Ville :

Lille

Pays :

France

Date de début de la manifestation scientifique :

2021-07

Éditeur :

ACM

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL