On Constrained Boolean Pareto Optimization
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. 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.
@inproceedings{ijcai2015p61,
title = {On Constrained Boolean Pareto Optimization},
author = {Qian, Chao and Yu, Yang and Zhou, Zhi-Hua},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {389--394},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/61},
}
TY - CPAPER TI - On Constrained Boolean Pareto Optimization AU - Qian, Chao AU - Yu, Yang AU - Zhou, Zhi-Hua T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 389 EP - 394 UR - https://ijcai.org/proceedings/2015/61 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
