CW 2008_13

Leslie De Koninck
Execution control for constraint handling rules

Advisor(s): Bart Demoen

Abstract

Constraint Programming (CP) is a high-level declarative programming paradigm in which problems are modeled by means of constraints on the problem variables that need to hold in all solutions to the problem. Many problems of high practical relevance can easily be described in terms of constraints. Example application areas include production planning and crew scheduling. A constraint programming system contains a constraint solver whose task it is to find valuations for the problem variables that satisfy all constraints.

Constraint programming systems can be classified by the variable domains and types of constraints their solver supports. However, for many problems it is not so straightforward to create a model in terms of basic constraint domains. Therefore, on the one hand, systems emerged that can handle more specialized constraint domains. On the other hand, facilities were designed that make it easier to implement an application-specific constraint solver. Some notable examples of these facilities are attributed variables, and Constraint Handling Rules.

Constraint Handling Rules (CHR) is a rule-based language, designed for the implementation of application-specific constraint solvers. CHR is a very flexible language for the specification of a constraint solvers' logic, but flexible execution control is almost completely lacking. Execution control is of great importance for the efficiency of CP systems. However, so far, the problem of execution control has received only very limited attention in the context of CHR. In this thesis, we propose a solution to the problem of execution control in CHR. In particular, we extend CHR with high-level facilities to support the specification of execution strategies.

More precisely, we extend CHR with user-defined rule priorities into CHRrp. CHR rules correspond to constraint propagators, and so rule priorities enable the specification of propagation strategies. An optimized implementation of CHRrp is presented and evaluated empirically. Next, we extend CHR with facilities for search strategy control. Our approach combines CHR (CHR with disjunction) and CHRrp into a new language called CHRbrp in which the propagation strategy is determined by means of rule priorities, and the search strategy by means of branch priorities. We propose a framework for analyzing the time complexity of CHRrp programs, by combining the Logical Algorithms framework (LA) of Ganzinger and McAllester with CHRrp. We present translation schemas from and to LA and propose an alternative implementation for CHRrp with strong complexity guarantees. Finally, we investigate the join order optimization problem, which is an important aspect of optimized CHR compilation. We propose a cost model for matching multi-headed rules, approximations of its parameters, and methods to find an optimal join order. An extension of the model for CHRrp is given.

Libridoc 1941 / text.pdf (1.2M) / mailto: dtai team