A model of anytime algorithm performance for bi-objective optimization

Alexandre D. Jesus (), Luís Paquete () and Arnaud Liefooghe ()
Additional contact information
Alexandre D. Jesus: University of Coimbra, CISUC, DEI
Luís Paquete: University of Coimbra, CISUC, DEI
Arnaud Liefooghe: University of Tokyo

Journal of Global Optimization, 2021, vol. 79, issue 2, No 4, 329-350

Abstract: 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 $$\varepsilon $$ ε -constraint algorithm, and show that our model can be used to guide the algorithm and improve its anytime behavior.

Keywords: Multi-objective optimization; Combinatorial optimization; Anytime algorithms; Anytime behavior; $$\varepsilon $$ ε -constraint (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00909-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:79:y:2021:i:2:d:10.1007_s10898-020-00909-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00909-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().