---
title: "On Constrained Boolean Pareto Optimization"
authors:
  - "Chao Qian"
  - "Yang Yu"
  - "Zhi-Hua Zhou"
doi: ""
url: "https://ijcai.org/proceedings/2015/61"
pdf: "https://ijcai.org/proceedings/2015/0061.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "389-394"
track: "Main Track"
keywords:
---

# On Constrained Boolean Pareto Optimization

Chao Qian, Yang Yu, Zhi-Hua Zhou

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 389-394.

## Abstract

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.