Constraints in Constraint Programming are relationships between variables or unknowns, each taking a value in a domain. They restrict possible values that a variable can take. Constraints are literally everywhere. One example of a constraint in day-to-day life would be that you cannot stay at school beyond 5 PM.
Constraint Programming is an alternative approach to programming that intertwines reasoning with computing. Problems solved with CP techniques are required to satisfy the constraints that are stated.
In general systems based on Constraint Programming are much more expressive and hence easy to understand. Compared to other techniques such as Genetic algorithms modeling complex problems can be done in a better way using CP.
Constraints in Constraint programming mainly operate on domains which are either discrete or continuous. In some cases constraint programming can handle a mix of both discrete and continous domains also called as hybrid domains.
One can say that constraint programming was developed from logic programming. But nowadays constraint logic programming has gained more preference as a term what with logic being used in every step of decision making and constraint building in CP.
Constraint satisfaction deals mainly with finite domains whereas constraint solving deals with problems defined over infinite or more complex domains. Also the solving techniques differ for both. Constraint satisfaction deals with more of combinatorial methods whereas the constraint solving is based more on mathematical techniques (Example: Taylor series)
Some of the constraint satisfaction techniques are Node consistency, Arc consistency, Path consistency. These techniques are not complete as they are still left with some inconsistent values. To solve this few other consistency techniques such as directional arc consistency, directional path consistency, restricted path consistency have been developed to remove inconsistecies.
Constraint Propagation is a local consistency technique that considerably reduces the search space and makes a problem more easier to solve. Branches of search tree that might lead to failure are pruned with the help of constraint propagation techniques There are different constraint propagation techniques such as backtracking, forward checking and look ahead. Though each of the techniques as its own advantages forward checking and backtracking are used more in applications as look ahead is a bit more expensive.
A CSP is defined as a set of Variables and each variable has a finite set of possible values called its domain. A CSP is then defined by a set of constraints which restrict the values that the variables can take. An example of a CSP could be the Sudoku game. It should be noted that a CSP can have one, more or maybe even no solution at all. A lot of search methods and heuristics are used in combination to solve CSP's. Some of the alogirthms including Backtracking, Arc Consistency Algorithm etc.
A continuous CSP is defined as a sequence of variables taking values respectively in a set of continuous domains and constrained by a set of Relations. Continuous variables are fixed with When the domains are continuous the search space is more complex and difficult to represent.
A discrete CSP is a regular CSP with finite domains.
In a search space each node of the tree is uniquely represented by a label. In discrete constraints domains labels are represented simply as enumeration of values or value combinations. On the other hand in continuous constraints each domain that's a label is represented by one or a small collection of intervals.
Hard constraints are constraints which are usually difficult to process. They are usually delayed till the end until they become directly solvable. Another definition that has been given by Margaret Wright and Fred.T.Krogh is that constraints that must be satisfied at all points are described as hard whereas constraints that can be relaxed to an extent and only need an approximate satisfaction while obtaining a solution are called soft constraints.
A good choice of a solver depends entirely on what your requirements are. If you think your constraint satisfaction problem covers more of hybrid or discrete domains rather than continuous domains then a hybrid or discrete solver would be appropriate. Its also advisable to go for a solver whose libraries are built in a programming language that you are comfortable with. This will make it easy to write pieces of code in that particular language for the solver. Other option to be considered would be to know before hand if the solver you chose is compatible with your Operating System. In addition if you want to work with only a solver that is freeware and not commercial you need to check the documentation before hand.
Constraint Libraries are predefined libraries that are used to solve Constraint satisfaction problems. New algorithms can be built using the existing libraries if desired or you can even compile small programs on your own and customize as you like. The difference between a constraint solver and a constraint library is that libraries can be modified and used to built a new algorithm on your own whereas a constraint solver is already built and you can just plug in the input and it will give the desired output.
Good example of concurrent constraint programming language is Mozart. In this kind of programming a number of applications are supported using thousands of threads and are synchronized to achieve more efficieny.
The 'alldifferent' constraint is a global constraint and it states that all variables in this constraint must be pairwise different. In other words The 'alldifferent' constraint finds an important application in problems such as air traffic management, rostering problems etc. For example if x and y are variables which both range over the domain {1,2,3}, the not-equal constraint [ x (not equal to) y ] does not include the set (x,y) = (1,1), (2,2), (3,3)
Given a constraint problem if after the initial modeling the problem takes too much time to obtain a solution then it can be refined further by adding new constraints which do not change the set of solutions but increase the propagation capabilities of the solver. Such constraints are called implied constraints. Nowadays the CP community has designed ways of developing automatic ways of generating implied constraints
Implied constraints can drastically reduce the solving time of a Constraint satisfaction problem. This is because it efficiently reduces the search space by introducing new constraints that do not effect the outcome of the end result. It has only to do with the processing time.
Redundant constraints are the ones which exist initially while formulating the CSP. They just are an overhead and are of no good to the final solution. Whereas implied constraints as you might have read before are introduced in to the CSP for solving the purpose of reducing the processing time.
Classical constraint programming systems are helpless when the constraints system to solve has no solution. Indeed, only a no solution message is provided. The user is left alone to find out why: is it because of the problem itself (no solution exists), a bad modelling, a bug in the solver etc. In order to help spreading constraint programming, the constraints community needs to address that issue. For example, the user can be helped by pointing out a set of constraints that left alone lead to the unexpected situation. A promising technique for providing such an information seems to be using explanations. An explanation is a set of constraints justifying an action of the solver (value removal, bound update, contradiction). These constraints are called the e-constraints.
An extensional constraint also known as a table constraint and is a building block of a constraint library. It is the relational view of a given constraint.It explicitly lists the subset of cartesian product allowed of each variable and the domain that it covers with another variable and its associated domain.
Over-constrained system is a system of constraints which cannot be solved at once, thus over-constrained.Constraint hierarchies were introduced for describing over-constrained systems by specifying constraints with hierarchical strengths or preferences. It allows one to specify declaratively not only the constraints that are required to hold, but also weaker, so called soft constraints at an arbitrary (finite) number of strengths.
Stochastic constraint programming is used to model decision problems which involve uncertainity and probability. It contains both decision variables which can be set by us and stochastic variables which follow some probability distribution and combine the best feautres of traditional CP and stochastic programming.
The main idea of interval computations and constraints was put forward by Ramon Moore in the late 1950's as a part of his PhD Dissertation. Since then IC is developed as an approach to putting bounds on rounding errors in mathematical computation and thus obtaining very reliable results. Interval constraints as a term is used to denote a constraint in which variables are linked with intervals.
Constraint programming is used a lot for solving combinatorial problems such as time-tabling, DNA structure analysis, scheduling, knowledge application, deduction and reasoning etc. Nowadays its impact can be seen in almost all major fields such as Artificial Intelligence, Mathematics, Physical Sciences, 3D Graphics, transportation problems, Business applications and many more.
As Roman Bartak points out in his paper CP does have its shortcomings and is coming more into light these days due to its wide spread applications. The stability of constraint systems has always been challenged as, even a small change to the program results in a serious difference to the overall performance of the system. There isnt also any online constraint solving help that is required in current changing environment. Cost optimization is another problem in most of the constraint models. One more problem is that as CP mostly deals with NP-hard problems efficiency is most of the time unpredictable.
There are a lot of summer schools being conducted from time to time in the field of Constraint programming. Please check the conferences webpage in this website for further information.
Among the various applications that take advantage of Constraint Programming the most popular use was that of scheduling.