Pruning rules for constrained optimisation for conditional preferences

Wilson, Nic; Trabelsi, Walid

Pruning rules for constrained optimisation for conditional preferences

Files

Pruning_rules_for_CP-11.pdf(335.21 KB)

Accepted Version

Date

2011-09

Authors

Wilson, Nic

Trabelsi, Walid

Publisher

Springer Berlin Heidelberg

Published Version

10.1007/978-3-642-23786-7_60

Abstract

A depth-first search algorithm can be used to find optimal solutions of a Constraint Satisfaction Problem (CSP) with respect to a set of conditional preferences statements (e.g., a CP-net). This involves checking at each leaf node if the corresponding solution of the CSP is dominated by any of the optimal solutions found so far; if not, then we add this solution to the set of optimal solutions. This kind of algorithm can clearly be computationally expensive if the number of solutions is large. At a node N of the search tree, with associated assignment b to a subset of the variables B, it may happen that, for some previously found solution a, either (a) a dominates all extensions of b; or (b) a does not dominate any extension of b. The algorithm can be significantly improved if we can find sufficient conditions for (a) and (b) that can be efficiently checked. In case (a), we can backtrack since we need not continue the search below N; in case (b), α does not need to be considered in any node below the current node N. We derive a sufficient condition for (b), and three sufficient conditions for (a). Our experimental testing indicates that this can make a major difference to the efficiency of constrained optimisation for conditional preference theories including CP-nets.

Keywords

Conditional preferences , Constrained optimisation , Constraint Satisfaction Problem (CSP) , CP-net

Citation

WILSON, N., TRABELSI, W. 2011. Pruning rules for constrained optimisation for conditional preferences. In: LEE, J. (ed.) Principles and Practice of Constraint Programming - CP 2011. Perugia, Italy, 12-16 Sep. Berlin, Heidelberg: Springer, pp 804-818.