Skip to Main content Skip to Navigation
Journal articles

A model of anytime algorithm performance for bi-objective optimization

Alexandre Borges de Jesus 1, 2 Luis Paquete 1 Arnaud Liefooghe 3, 2
2 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 allow a practitioner to trade-off runtime for solution quality. This is of particular interest in multi-objective combinatorial optimization since it can be infeasible to identify all efficient solutions in a reasonable amount of time. We present a theoretical model that, under some mild assumptions, characterizes the “optimal” trade-off between runtime and solution quality, measured in terms of relative hypervolume, of anytime algorithms for bi-objective optimization. In particular, we assume that efficient solutions are collected sequentially such that the collected solution at each iteration maximizes the hypervolume indicator, and that the non-dominated set can be well approximated by a quadrant of a superellipse. We validate our model against an “optimal” model that has complete knowledge of the non-dominated set. The empirical results suggest that our theoretical model approximates the behavior of this optimal model quite well. We also analyze the anytime behavior of an ε-constraint algorithm, and show that our model can be used to guide the algorithm and improve its anytime behavior.
Document type :
Journal articles
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-02898963
Contributor : Alexandre D. Jesus <>
Submitted on : Monday, July 27, 2020 - 1:43:30 PM
Last modification on : Monday, May 17, 2021 - 12:00:05 PM
Long-term archiving on: : Tuesday, December 1, 2020 - 7:26:52 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Citation

Alexandre Borges de Jesus, Luis Paquete, Arnaud Liefooghe. A model of anytime algorithm performance for bi-objective optimization. Journal of Global Optimization, Springer Verlag, 2020, ⟨10.1007/s10898-020-00909-9⟩. ⟨hal-02898963⟩

Share

Metrics

Record views

135

Files downloads

391