Skip to Main content Skip to Navigation
Conference papers

Algorithm selection of anytime algorithms

Alexandre Borges de Jesus 1, 2 Arnaud Liefooghe 3, 1 Bilel Derbel 1 Luis Paquete 2 
1 BONUS - Optimisation de grande taille et calcul large échelle
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Alexandre D. Jesus Connect in order to contact the contributor
Submitted on : Monday, July 27, 2020 - 1:38:41 PM
Last modification on : Tuesday, July 5, 2022 - 8:38:39 AM
Long-term archiving on: : Tuesday, December 1, 2020 - 7:26:21 AM


Files produced by the author(s)



Alexandre Borges de Jesus, Arnaud Liefooghe, Bilel Derbel, Luis Paquete. Algorithm selection of anytime algorithms. GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Jul 2020, Cancún, Mexico. pp.850-858, ⟨10.1145/3377930.3390185⟩. ⟨hal-02898962⟩



Record views


Files downloads