This document is a first introduction to Constraint Programming in Alice.

Constraint Progamming is a problem-solving technique for combinatorial problems that works by incorporating constraints into a programming environment (after [3] Principles of Constraint Programming. by Krysztof R. Apt).

Combinatorial problems question about properties (constraints) of a class of combinatorial structures which are characterized in terms of a finite set of variables and a finite value for each variable.

Finally, the constraint programming features of Alice that are build upon the Gecode [12] constraint library realize the requirements of Apt's definition.

First, this document covers combinatorial problems that can be stated with variables ranging over finite domains of integers. Later, those problems are expanded by allowing variables to range over finite sets of integers. Problems in this class range from puzzles to real world applications as diverse as scheduling, ware house allocation, configuration and placement.

The two basic techniques of constraint programming are constraint propagation and branching. Constraint propagation is an efficient inference mechanism obtained with concurrent propagators accumulating information in a constraint store. Branching splits a problem into complementary cases once constraint propagation cannot advance further, i.e. it reaches a fixpoint. By iterating propagation and branching, propagation will eventually determine the solutions of a problem.

Branching can easily lead to an exponential growth of the number of subproblems to be considered. Fortunately, this potential combinatorial explosion can often be contained by combining strong propagation mechanisms with problem specific heuristics for selecting branching steps.

The following puzzles give a first idea of the combinatorial problems that will be solved in this document:

The problems have in common that they can be stated with variables that are a priori constrained to finite sets of nonnegative integers. Consequently, the problems could be solved by simply checking all possible combinations of the values of the variables. This naive generate and test method is however infeasible for most realistic problems since there are just too many possible combinations.

Andreas Rossberg 2006-08-28