论文标题
使用最小校正子集对帕累托集的精确和近似测定
Exact and approximate determination of the Pareto set using minimal correction subsets
论文作者
论文摘要
最近，已经表明，布尔公式的最小校正子集（MC）的枚举允许求解多目标布尔优化（MOBO）公式。但是，这种方法的一个主要缺点是大多数MCS不对应于帕累托最佳解决方案。实际上，只能知道当所有MCS列举时，给定的MCS对应于帕累托最佳解决方案。此外，如果无法枚举所有MCS，则无法保证帕累托边境的近似质量。本文扩展了使用MCSS解决主板的最新技术。首先，我们表明可以使用MC枚举来解决主板问题，以便每个MC必须对应于帕累托最佳解决方案。此外，我们还提出了两种新算法，可以找到（1 + {\ varepsilon}） - 使用MCS枚举的帕累托前沿的近似。几个基准集的实验结果表明，新提出的算法可以比最新的算法找到更好的帕累托前沿近似值，并且具有保证的近似值。
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.
