On Constrained Boolean Pareto Optimization
On Constrained Boolean Pareto Optimization
复制标题
DOI：
--
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
Chao Qian;Yang Yu;Zhi-Hua Zhou
中科院分区：
文献类型：
--
作者：
Chao Qian;Yang Yu;Zhi-Hua Zhou
帕累托优化通过将约束优化任务重新表述为双目标问题来解决该任务。帕累托优化在实际应用中表现出了很好的效果，但理论上的支持却很少。本文从理论上比较了帕累托优化与罚函数法，罚函数法是一种将约束优化问题转化为无约束优化问题的常用方法。我们证明了两大类约束布尔优化问题，最小拟阵优化（P-可解）和最小成本覆盖（NP-难），帕累托优化是更有效的比罚函数方法分别获得最优解和近似解。此外，在最小成本覆盖实例中，我们还展示了帕累托优化相对于贪婪算法的优势。
Pareto optimization solves a constrained optimization task by reformulating the task as a bi-objective problem. Pareto optimization has been shown quite effective in applications; however, it has little theoretical support. This work theoretically compares Pareto optimization with a penalty approach, which is a common method transforming a constrained optimization into an unconstrained optimization. We prove that on two large classes of constrained Boolean optimization problems, minimum matroid optimization (P-solvable) and minimum cost coverage (NP-hard), Pareto optimization is more efficient than the penalty function method for obtaining the optimal and approximate solutions, respectively. Furthermore, on a minimum cost coverage instance, we also show the advantage of Pareto optimization over a greedy algorithm.