|
Developer facing an optimization problem. |
Constraint ProgrammingThis page is the opportunity to present Constraint Programming to people. This page may be thought as a modest white paper upon this technology. The reader might want to get some additional information about Constraint Programming. That is the reason why I take the risk to explain in a few words what it is about. Do not expect from me a long explanation,
but just the guide lines.Part of Artificial IntelligenceConstraint Programming, that we commonly denote as CP, is an activity that is part of the Artificial Intelligence (AI) in general. CP uses massively computers to implement algorithms taken from the Operational Research, encapsulated into a new paradigm. This device mainly focuses on optimization problems.Operational Research very shortlyLet us say a short word concerning Operational Research (OR). This activity was progressively created as there was a constant need in the industry to solve problems that man could not solve by hand, but which could be tackled thanks to the computer abilities. A typical OR problem is the Traveling Salesman Problem (TSP). Consider that a travel man must visit a group of towns within one day: he cannot come back on a town he has already visited and he knows the distances between each pair of towns. The issue is: what is the best circuit to take in order to minimize its distance ? Another activity of OR is the tasks assignment on machines, taking into account precedence constraints between the tasks, and minimizing the total time span to complete all the tasks. Operational Research deals with this kind of problems. Each time, the aim is not only to find out a solution, but to find the optimal solution.The originsLet us come back to the CP technology itself. The idea of the people having introduced the paradigm of CP, was to enable the programmer to re-use some of the ad hoc algorithms of OR by generalizing them into constraints. Instead of writing each time a specific algorithm for a specific problem, CP proposes a set of constraints primitives that handle the problem.CP very shortlyFor those who do not whish to have a long explanation, I would say that Constraint Programming (CP) is a technology that handles optimization problems. To use it, the programmer has to mathematically design his problem into variables and constraints, and them build a strategy to find correct values for these variables.CP more into detailsCP uses a paradigm that the programmer should learn to use it. The problem that the user of CP would like to solve must be thought in terms of mathematical variables (with discrete or continuous values) and in terms of constraints. We can divide the global mechanism into three stages.Design and defining the variables which are the unknowns of the problemFirst of all, the CP user must design his problem by defining variables, which are called domain-variables in CP. The variables are the unknowns of the problem and they must be given an individual initial domain which represents its feasible values, a priori (most of the time, we work with natural numbers domains). This domain is not fixed and is boundto change as the algorithms present inside the constraints deduce restrictions (we say that the constraints propagate).Defining and post the constraints of the problem upon the variablesSecondly, he must express more or less mathematical constraints on those variables, so that all the real problem constraints are respected during the next step, which is the search phase. At this point, each domain-variable has an initial domain which is most of the time not restricted to a single value: but since all the constraints of the problem have been posted, CP ensures that a variable cannot be bound (i.e. its domain is composed by only one value; we also say that the variable has been instantiated) to an incompatible value, which means that if all the domain-variables have been instantiated, a solution has been found.Search for a solution of the problemAt last, the CP user must search for a feasible value for each one of the domain-variables. In order to find out a solution to the problem, the programmer searches progressively for a solution by dynamically building what we call a search-tree (this is also called to enumerate on the domain-variables). This search-tree is being built little by little using a strategy (we call that heuristics). The building of the search-tree is made of similar stages; each stage is composed by five steps (four handled directly by the programmer, one but not least by the CP kernel):1. Choose a domain-variableThe programmer has to choose a domain-variable among the ones not yet instantiated. Thus, we consider a domain-variable which has more that one single value inside its domain.2. Remember the state of all the domain-variablesThe programmer creates a choice point at this point, which enables the CP kernel (the module that performs consistency between the domain-variables and the constraints) to remember the current state of all the domain-variables (but also the list of constraints posted so far, because it is also possible to post dynamically constraints, even if it is not advised most of the time).3. Choose of a value for the domain-variableFor this domain-variable, he must choose a value among its domain. Note that this domain is most often not the same as the one defined during the first step, because of the constraints propagation.4. Try to bind the chosen domain-variable with the chosen valueNow, the programmer binds the chosen domain-variable to the chosen value, which implies that all the other values of its domain are removed from it.5. The constraints perform propagationThis operation triggers a set of events not handled by the programmer but by the CP kernel. Now, the |