论文标题
用于多目标组合优化的新核心引导和击中集合算法
New Core-Guided and Hitting Set Algorithms for Multi-Objective Combinatorial Optimization
论文作者
论文摘要
在过去的十年中，已经提出了多种单目标布尔优化的算法，该算法依赖于迭代性用法的高效命题满意度（SAT）求解器。但是，在多目标组合优化（MOCO）算法中使用SAT求解器仍然很少。由于MOCO的有效工具短缺，因此使用线性组合或目标函数的词典组合订购来优化，许多以多目标为单位的现实世界应用被简化为单对象。在本文中，我们通过两种基于新的基于难以满足性的算法扩展了MoCo求解器的艺术状态。第一个是核心引导的moco求解器。第二个是基于集合的MOCO求解器。在广泛的基准实例中获得的实验结果表明，我们新的基于难以满足性的算法可以优于MOCO的最先进的SAT算法。
In the last decade, a plethora of algorithms for single-objective Boolean optimization has been proposed that rely on the iterative usage of a highly effective Propositional Satisfiability (SAT) solver. But the use of SAT solvers in Multi-Objective Combinatorial Optimization (MOCO) algorithms is still scarce. Due to this shortage of efficient tools for MOCO, many real-world applications formulated as multi-objective are simplified to single-objective, using either a linear combination or a lexicographic ordering of the objective functions to optimize. In this paper, we extend the state of the art of MOCO solvers with two novel unsatisfiability-based algorithms. The first is a core-guided MOCO solver. The second is a hitting set-based MOCO solver. Experimental results obtained in a wide range of benchmark instances show that our new unsatisfiability-based algorithms can outperform state-of-the-art SAT-based algorithms for MOCO.
