Efficient Enumeration of Supported Solutions for General Multi-Objective Optimization Problems

Real-life decision problems often involve multiple objectives, such as the integration of environmental cost and fairness concerns in industry. Since these objectives are usually conflicting, multi-objective optimization aims to enumerate all compromises (Pareto-optimal solutions). One standard approach is to transform the problem into a single-objective one through a weighted sum to benefit from the wide range of available solvers and algorithms. The main challenge is the computation of the weight vectors to enumerate all the supported solutions as many vectors can lead to the same solution. For two objectives, a systematic exploration can be done with a dichotomy scheme. We present the GeneralDichotomy algorithm, that generalizes this method to any number of objectives. It performs incremental exploration and can be combined with any single-objective solver. Our algorithm offers completeness guarantees when the set of solutions is enumerable. Experimentally, it consistently decreases runtime, up to two order of magnitudes. For ease of use, we provide C++ and Python libraries.