A model of anytime algorithm performance for biobjective optimization problems

Anytime algorithms allow a practitioner to trade-off runtime for solution quality. This is of particular interest in multiobjective optimization since it might be infeasible to identify the Pareto set in a reasonable amount of time. We present a theoretical model to characterize the trade-off between solution quality, in terms of relative hypervolume, and runtime for exact anytime algorithms for biobjective optimization problems. Our model works under some basic assumptions, such as, Pareto optimal solutions are collected sequentially and the Pareto front can be well approximated by a quadrant of a particular superellipse. We validate our model against an anytime algorithm based on the -constraint approach for the biobjective unconstrained knapsack problem.