Exact and approximate determination of the Pareto set using minimal correction subsets
This work addresses a bottleneck in MOBO for researchers and practitioners by improving the efficiency and quality of Pareto frontier approximations, though it is incremental as it builds on existing MCS methods.
The paper tackles the problem of solving Multi-Objective Boolean Optimization (MOBO) using Minimal Correction Subsets (MCS) by ensuring each MCS corresponds to a Pareto-optimal solution and proposing algorithms for (1 + ε)-approximation of the Pareto frontier, with experimental results showing better approximations than state-of-the-art algorithms and guaranteed ratios.
Recently, it has been shown that the enumeration of Minimal Correction Subsets (MCS) of Boolean formulas allows solving Multi-Objective Boolean Optimization (MOBO) formulations. However, a major drawback of this approach is that most MCSs do not correspond to Pareto-optimal solutions. In fact, one can only know that a given MCS corresponds to a Pareto-optimal solution when all MCSs are enumerated. Moreover, if it is not possible to enumerate all MCSs, then there is no guarantee of the quality of the approximation of the Pareto frontier. This paper extends the state of the art for solving MOBO using MCSs. First, we show that it is possible to use MCS enumeration to solve MOBO problems such that each MCS necessarily corresponds to a Pareto-optimal solution. Additionally, we also propose two new algorithms that can find a (1 + {\varepsilon})-approximation of the Pareto frontier using MCS enumeration. Experimental results in several benchmark sets show that the newly proposed algorithms allow finding better approximations of the Pareto frontier than state-of-the-art algorithms, and with guaranteed approximation ratios.