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