On constrained boolean pareto optimization
Chao Qian, Yang Yu, Zhi‐Hua Zhou · 2015
Pareto optimization solves a constrained optimiza-tion task by reformulating the task as a bi-objective problem. Pareto optimization has been shown quite effective in applications; however, it has little the-oretical 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 cov-erage (NP-hard), Pareto optimization is more effi-cient than the penalty function method for obtain-ing the optimal and approximate solutions, respec-tively. Furthermore, on a minimum cost coverage instance, we also show the advantage of Pareto op-timization over a greedy algorithm. 1