Constraint Solving by Martine Ceberio


FAQs – Constraint Programming

Table of Contents

  1. What are constraints ?
  2. What is Constraint Programming ?
  3. Why use Constraint Programming ?
  4. What are the different domains that constraints in constraint programming operate on?
  5. I heard that constraint satisfaction and constraint solving are 2 branches of constraint programming. What exactly are they?
  6. What are the different kinds of constraint satisfaction techniques that we have?
  7. What is a constraint satisfaction problem (CSP) and what are the different approaches for solving it? Also I would like to know how to model a CSP?
  8. What is a continuous CSP?
  9. What is a discrete CSP?
  10. What is the difference between continuous and discrete constraints?
  11. Constraints can be categorized into two types – hard and soft constraints. Can you elaborate more on them?
  12. How to make a good choice of a solver among so many existing solvers that can exactly provides a solution to your problem?
  13. What are constraint libraries?
  14. What is concurrent constraint programming?
  15. What are the ‘alldifferent’ constraints or the ‘constraint of difference’. What exactly is it defined as?
  16. What is an implied constraint?
  17. Why are implied constraints useful?
  18. What are e-constraints?
  19. I would like to have an idea about extensional and global constraints. Can you explain in detail?
  20. Can you explain what constraint hierarchies are and how they are used to handle over-constrained problems?
  21. What is stochastic constraint programming and what are its applications?
  22. In what way are constraints and interval computations related to each other?
  23. What is the impact of constraint programming in real-life?
  24. Is CP all about advantages and plus points or does it have any shortcomings and limitations?
  25. Are there any summer schools that offer courses in Constraint programming?
  26. Applications of CP ?

What are constraints?

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.


What is Constraint Programming ?

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.


Why use Constraint Programming ?

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.


What are the different domains that constraints in Constraint Programming operate on?

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 continuous domains also called as hybrid domains.


I heard that constraint satisfaction and constraint solving are 2 branches of constraint programming. What exactly are they?

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 combinatorial methods, whereas Constraint Solving is based more on mathematical techniques (Example: Taylor series).


What are the different kinds of constraint satisfaction techniques that we have?

Some of the constraint satisfaction techniques are: Node consistency, Arc consistency, and Path consistency. These techniques are not complete as they are still left with some inconsistent values. To solve these few other consistency techniques such as directional arc consistency, directional path consistency, restricted path consistency have been developed to remove inconsistencies.


What is a constraint satisfaction problem (CSP) and what are the different approaches for solving it?

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 algorithms include Backtracking, Arc Consistency Algorithm, etc.


What is a continuous CSP ?

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 when the domains are continuous. The search space of continuous CSP’s is more complex and difficult to represent. Reference


What is a discrete CSP ?

A discrete CSP is a regular CSP with finite domains.


What is the difference between continuous and discrete constraints?

In a search space, each node of the tree is uniquely represented by a label. In discrete constraints, domain 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.


Constraints can be categorized into two types – hard and soft constraints. Can you elaborate more on them?

Hard constraints are constraints which are usually difficult to process; they are usually delayed until the end when 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. Reference


How to make a good choice of a solver among so many existing solvers that can exactly provides a solution to your problem?

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. It’s also advisable to choose a solver whose libraries are built in a programming language that you are comfortable using. Consequently it would be easier for you to write pieces of code in that particular language that can interact directly with the solver. Another option to be considered would be to know beforehand if the solver you chose is compatible with your Operating System. In addition, if you only want to work with only a solver that is freeware and not commercial you need to check the documentation beforehand.


What are constraint libraries?

Constraint Libraries are predefined libraries that are used to solve Constraint satisfaction problems. New algorithms can be built using the existing libraries if so desired, or you can even compile small programs on your own and customize them as you like. The difference between a constraint solver and a constraint library is that libraries can be modified and, or utilized to build your own new constraint solving algorithms. Constraint solvers, on the other hand, are usually fully capable solvers that have already been built and thus are ready for use as you would any other software application.


What is concurrent constraint programming?

Good example of a concurrent constraint programming language is Mozart. In this kind of programming, a number of applications are supported using thousands of threads and they -Than is the applications- are synchronized to achieve more efficiency.


What are the ‘alldifferent’ constraints or the ‘constraint of difference’. What exactly is it defined as?

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) Reference


What is an implied constraint?

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. These newly added constraints do not change the set of solutions, but rather increase the propagation capabilities of the solver. Such constraints are called implied constraints. Nowadays the CP community has designed ways of developing automatic methods to generate implied constraints. Reference


Why are implied constraints useful?

Implied constraints can drastically reduce the solving time of a Constraint satisfaction problem. This due to the fact that implied constraints can efficiently reduce the search space by introducing new constraints that do not affect the outcome of the end result. The only issue that arises is that of processing time.


What are e-constraints?

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 modeling, a bug in the solver etc. In order to help spread 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 when 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.


I would like to have an idea about extensional constraints. Can you explain in detail?

An extensional constraint, also known as a table constraint, is a building block of a constraint library; it is the relational view of a given constraint. An extensional constraint explicitly lists the subset of cartesian product allowed of each variable and the domain that it covers with another variable and its associated domain. Reference


Can you explain what constraint hierarchies are and how they are used to handle over-constrained problems?

An Over-constrained system is a system of constraints which cannot be solved at once, thus it is 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 be held, but also weaker, so called soft constraints at an arbitrary (finite) number of strengths. Reference


What is stochastic constraint programming and what are its applications?

Stochastic constraint programming is used to model decision problems which involve uncertainty and probability. Stochastic constraint programming contains both decision variables, which can be set by us- the (user or the programmer), and stochastic variables which follow some probability distribution and combine the best features of traditional CP and stochastic programming. Reference


In what way are constraints and interval computations related to each other?

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 has been developed as an approach to putting bounds on rounding errors in mathematical computation and thus ensure the acquiring very reliable results. Interval constraints as a term is used to denote a constraint in which variables are linked with intervals.


What is the impact of constraint programming in real-life?

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.


Is CP all about advantages and plus points or does it have any shortcomings and limitations?

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 isn’t 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.


Are there any summer schools that offer courses in Constraint programming?

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.


Applications ?

Among the various applications that take advantage of Constraint Programming the most popular use was that of scheduling.

  • Lufthansa : Short term staff planning
  • Hong-Kong Container Harbor: Resource planning
  • The Munich Rent Advisor
  • Renault : short term production planning
  • Nokia: software configuration for mobile phones
  • Airbus: Cabin Layout
  • Siemens: Circuit Verification
  • Decision Support systems: for planning and Configuration and for design and analysis
  • ARTIFICIAL INTELLIGENCE
    • Machine Vision
    • Natural Language Understanding
    • Temporal and Spatial Reasoning
    • Theorem Proving …. (Comes in SE)
    • Qualitative Reasoning
    • Robotics
    • Agents
  • Operations research