Ninguno

In J. Figwer (editor) Proceedings of the 3 Workshop on Constraint Programming in Decision and Control, June 2001, Poland.

rd

Theory and Practice of Constraint Propagation
Roman Barták* Charles University, Faculty of Mathematics and Physics Malostranské námestí 2/25, 118 00 Praha 1, Czech Republic e-mail: bartak@kti.mff.cuni.cz
Abstract: Despite successful application of constraintprogramming (CP) to solving many real-life problems there is still an indispensable group or researchers considering (wrongly) CP as a simple evaluation technique only. Even if sophisticated search algorithms play an important role in solving constraint-based models, the real power engine behind CP is called constraint propagation (domain filtering, pruning or consistency techniques). In the paper wegive a survey of common consistency techniques for binary constraints. We describe the main ideas behind them, list their advantages and limitations, and compare their pruning power. Then we briefly explain how these techniques can be extended to non-binary constraints. Last part of the paper is devoted to modelling issues. We give some hints how the constraint propagation can be exploited more whensolving real-life problems. This part is based on our experience with solving real-life programs and it is also supported by empirical observations of other researchers. Keywords: constraint propagation, filtering algorithms

1

Introduction

Thanks to many constraint satisfaction packages available for end users, constraint programming (CP) is becoming more widespread and CP technology isused to solve various mostly combinatorial problems. It means that there exists a growing group of users without deep knowledge how CP works inside but still able to model and solve problems by means of constraints. However, if difficulty of the problem increases then it is more and more complicated to design an appropriate constraint model that can then be successfully solved. We believe thatbetter understanding of processes inside the constraint packages can help their users to design better models and thus to decrease development time (and expenses as well). Constraint satisfaction problem is defined by a finite set of variables, each variable has assigned a finite domain, i.e. a finite set of possible values, and by constraints restricting combinations of values that the variables cantake together. The task is to find a value for each variable from its domain in such a way that all the constraints are satisfied. Usually, constraints are used actively to reduce domains by filtering values that cannot take part in any solution. This process is called constraint propagation, domain filtering, pruning or consistency technique, and it is the core of most
*

constraintsatisfaction packages. Constraint propagation can be used to solve fully the problem but this is rarely done due to efficiency issues. It is more common to combine an efficient but incomplete consistency technique with nondeterministic search. Such consistency technique does not remove all inconsistent values from the variables' domains, but it can still eliminate many "obvious" inconsistencies and, thus,simplify the problem and reduce the search space. To solve the problem to full-extent, incomplete consistency techniques are accompanied by non-deterministic search that explores possible value assignments. First, we show how a non-binary constraint can be translated to a set of binary constraints giving an equivalent solution set (Section2). Then, we survey basic consistency techniques for binaryconstraints (Section 3). In Section 4 we discuss some issues concerning non-binary constraints and techniques for solving them. Section 5 is devoted to some hints about using consistency techniques in practice.

2

Binary Constraints

It is well known that a non-binary CSP, i.e., the CSP with constraints of arity larger than 2, can be translated to an equivalent binary CSP. This fact is so...