Premium
Preference‐Based Constrained Optimization with CP‐Nets
Author(s) -
Boutilier Craig,
Brafman Ronen I.,
Domshlak Carmel,
Hoos Holger H.,
Poole David
Publication year - 2004
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.0824-7935.2004.00234.x
Subject(s) - backtracking , mathematical optimization , computer science , preference , set (abstract data type) , pareto principle , property (philosophy) , optimization problem , mathematics , philosophy , statistics , epistemology , programming language
Many artificial intelligence (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.