Preference-based Constrained Optimization with CP-nets

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5, Canada
email: cebly@cs.toronto.edu

Ronen I. Brafman
Department of Math and Computer Science
Ben-Gurion University
Beer Sheva, ISRAEL 84105
email: brafman@cs.bgu.ac.il

Carmel Domshlak
Department of Computer Science
Cornell University
Ithaca, NY 14853, USA
email: dcarmel@cs.cornell.edu

Holger H. Hoos
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: hoos@cs.ubc.ca

David Poole
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: poole@cs.ubc.ca

Abstract
Many AI tasks, such as product configuration, decision support, and the construction of autonomous agents, involve a process of constrained optimization, that is, optimization of behavior or choices subject to given constraints. In this paper we present an approach for constrained optimization based on a set of hard constraints and a preference ordering represented using a CP-network---a graphical model for representing qualitative preference information. This approach offers both pragmatic and computational advantages. First, it provides a convenient and intuitive tool for specifying the problem, and in particular, the decision maker's preferences. Second, it admits an algorithm for finding the most preferred feasible (Pareto optimal) outcomes that has the following anytime property: the set of preferred feasible outcomes are enumerated without backtracking. In particular, the first feasible solution generated by this algorithm is Pareto optimal.

Computational Intelligence 20(2):137-157

Return to List of Papers