Constraint Programming

This 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 Intelligence

Constraint 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 shortly

Let 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 origins

Let 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 shortly

For 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 details

CP 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 problem

First 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 variables

Secondly, 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 problem

At 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-variable

The 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-variables

The 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-variable

For 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 value

Now, 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 propagation

This operation triggers a set of events not handled by the programmer but by the CP kernel. Now, the CP kernel wakes up all the constraints concerned by the domain-variable chosen during this stage. We describe what happens for each one of them.

The cascade triggering of constraints deductions

The first one awaken (which one it is, is not deterministic, which means that it cannot be said a priori, because there is no specification on that point) is notified that the domain-variable has been removed some values from its domain, and it tries to deduce whether it would induce the reduction of the domain of any other domain-variables it also handles. If it is the case, the same operation we are describing is applied to this newly concerned domain-variable. If it is not the case, the next concerned constraint also performs the operation we have described.

Some constraint complains

However, it is also possible that one of the overall concerned constraints (from the beginning of the stage we are currently describing) discovered that the domain-variable domain restriction is not acceptable (it could not deduce that before because the algorithm inside the constraint is not smart enough to discover that inconsistency), which means, on its turn, that the value given to the chosen domain-variable of the current stage is not acceptable within the solution the programmer is building: in that very special case, the CP kernel notifies the programmer of this fact (we say that the domain-variable instantiation fails).

The value tried must be removed

The programmer knows that he must remove from its domain the unfeasible value he tried for the domain-variable he chose during the current stage, and he must redo the value choice by returning to the third step of the current stage. In some case, it may happen that the fact to remove an unfeasible value from a domain-variable failed as well, because of the attached constraints propagation. If this is the case, the programmer must backtrack to the stage treated before the one he is currently handling, just like in the following paragraph.

No value is acceptable: backtracking

If, for the current stage, all the domain values of the currently chosen domain-variable went to a failure, it means that the problem can no longer be solved with the value given to the previously instantiated domain-variables during the previous stage. The programmer will have to perform what we call backtracking (this is automatically provided by Prolog): he must consider to come back to the previous stage and make it the current stage. For that stage, he must come back to the previous step, undo the choice point he set during that previous step, so as to recover the state of the domain-variables (especially the state of the domain-variable chosen during that previous step). To be able to find a solution to his problem, the programmer must remove the value that he tried from that previously selected domain-variable of that previous stage, just like in the former paragraph.

No constraint complains

In opposition, if no constraint complained, the current stage is completed and the programmer must tackles to the next one, which becomes the current stage, and handle that new stage at the first step. When no more domain-variable can be chosen, it means that all the domain-variables are instantiated, so that every domain-variable has now a feasible single value: a solution has been found for the problem.

All this set of triggered events is called propagation and one understands that this can be very complex, and that the fact of binding a domain-variable to one of its feasible value (not only, but just restricting its domain) may have severe aftermath on other domains reduction. Moreover, it may notify the CP kernel of some inconsistency. To sum up somehow the paradigm encapsulated inside the Constraint Programming, let us say that this a device using massively computation, which enables to solve problems that must be designed into mathematical variables and constraints, thanks to a strategy.

Some comments about the CP technology

I would like to make few comments about the CP technology.

Complexity

First of all, I would like to draw the attention of the reader on the fact that CP is used where most of the other traditional technologies fail. And this is mostly due to the fact that CP focuses on very complex problem, which would require specific algorithms to be treated. I do not know the case of a not complex problem that has been solved through this technology.

The complexity comes first from the fact that the problems tackled with present a huge variety of combinations, which grows most of the time exponentially with their size. To be convinced, think of the simplistic example of the air traffic control where a flight plan is designed by one variable which may take a value among a range of 3 hours let us say (i.e. 180 minutes). If you take a day period when at least 20.000 air planes take off from Europe, you will get a universe cardinality of 180^20.000 ! I let you imagine what it makes. In other technical words, most of the problems handled with CP are said NP-complex, which means that it is not possible to build an algorithm enumerating all the configurations of the problem within a time period curbed by an polynomial size of the problem.

Moreover, what makes the complexity of this subject is that we always challenge problems, in the sense that there is no predefined methodology to apply each time (except the one of programming). Each time a problem is tackled with CP, there is no guaranty beforehand that we will get valuable results rapidly. There is very often a long tuning stage of the strategy, which makes the difference between an average and a good solution to the problem.

Intelligence inside the constraints and inside the strategy

I draw the attention that the Artificial Intelligence part lies in the algorithms encapsulated inside the constraints. These constraints are the result of years of experimentation. For a given strategy, the smarter these constraints are, the faster the CP programmer will get a solution (or the proof that there is no solution at all).

This intelligence comes also from the strategy. For given constraints, the smarter the strategy is, the faster you will get a solution: it is of the responsibility of the programmer to discuss with the operational experts what a good strategy is made of for the problem he tackles. A little bit like the expert system (which CP does not provide at all), the function of the programmer is to embed the operational expertise.

Flexibility and re-use

One of the interests of CP is also that, once a problem designed, it is most of the time possible to adapt it quite rapidly, so that it takes into account new constraints, or reflects modified constraints. It is something that does not provide an ad hoc algorithm: once you change the constraints of the problem, you very often have to re-write everything from scratch with ad hoc algorithm. Even with linear programming, it is sometimes very tedious to adapt the design to take into account new constraints. CP ensures this kind of re-use of what has been already done for a problem.

Something which is very important is that most of the time, real problems expressed do not have any solution. Not because CP does not succeed in searching for a solution, but simply because CP prooves that there is no solution for the problem. This comes from the fact that operational experts who enact the rules of the real problem, very often violate the rules, even without being aware of it. One force of CP is just to provide more flexibility by enabling the relaxation of the problem. Sometimes, instead of imposing strong constraints, it is more advisable to post soft constraints which can be violated, to get a dynamical measure of that violation, ans to try to minimize this violation.

Interactivity for a decision making technology

Very often, CP does not only provide basic solutions to problems, it may also guide people to make the right choice. CP is often used to enable people making simulations. The end-user often whishes to interact with the application based on CP, wondering what would happen (what it would cost indeed) if some parameters of the problem he is dealing with, were fixed like that. CP brings much of this interactivity through impressive response times. This makes often applications built with CP some decision making tools.

Current date: 2020.10.23 8:44:30 Number of hit: 1145

Site generated by WedSitor