Basic Introductory Tutorial on Constraint Programming

Table Of Contents

 

  1. History
  2. Constraint Programming
  3. Constraints
  4. Constraint Solving
  5. Constraint Satisfaction Problem
  6. Solving CSP


History

Constraint programming originated from constraint logic programming, which embeds constraints into a logic program. The credit for this variant of logic programming goes to Jaffar and Lassez, who extended a specific class of constraints that were introduced earlier in Prolog II. The first implementations of constraint logic programming were Prolog III, CLP(R), and CHIP. Several constraint logic programming interpreters exist today.

 
Back to Top

Constraint Programming

 

Constraint Programming can best be described as an alternative approach to programming that intertwines reasoning with computing. It is the study of computational systems based on constraints. The basic idea behind Constraint programming is to solve problems by stating the constraints involved. The solution should satisfy all the constraints.

Characteristics of Constraint Programming

  • Declarative programming – modeling
  • Flexible representation – constraints can be added, removed or modified
  • A two phase programming approach

Ø      Generation of a problem representation as a CSP

Ø      Finding a solution of the CSP

·        Presence of built-in mechanisms

Ø      Constraints can be added, removed or modified

Ø      Features to declare and define variables

Ø      Features to generate constraints over the variables

Ø      Constraint solvers

Ø      Constraint propagation algorithm

Ø      Search techniques

Constraint programming consists of three basic techniques:

  1. Declare the domains of the variables
  2. Declare the constraints on the declared variables
  3. Search for the solutions

Constraint Programming Process: 

  1. Constraint Modeling: Representations of a problem as a constraint satisfaction problem with constraints is called constraint modeling.
  1. Constraint Solving: Solving the constraint models formulated by modeling can be carried out using any of the three methods:
    1. Domain specific method (Simplexe, Gröbner bases etc..)
    2. General Method (Constraint propagation )
    3. Combination of both methods ( Solver cooperation )

Back to Top

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 need to be identified in order to solve problems by means of Constraint Programming.

Properties of constraints:

  • May specify partial information

Ø      Doesn’t necessarily specify the values of variables

  • Heterogeneous

Ø      Doesn’t specify relations between variables with different domains

  • Non-directional
  • Declarative

Ø      Specify what variable relationships may hold

  • Additive

Ø      Conjunction of constraints is important

  • Rarely independent

Ø      Constraints share variables

Types of Constraints:

  1. Equality and disequality constraints
  2. Boolean Constraints
  3. Linear Constraints
  4. Arithmetic Constraints
    1. Integer intervals and finite integer domains
    2. Extended intervals of real
    3. The set of reals
 
Back to Top

 

Constraint Solving

  1. Domain Specific Methods
    • Special purpose algorithms devoted to specific domains and constraints
    • Method by means of specialized packages called constraint solvers
    • Examples include:

                                                               i.            Program that solves systems of linear equations

                                                             ii.            Package for linear programming

                                                            iii.            Implementation of unification algorithm

                                                           iv.            Preferred over General methods, should it be available

 

  1. General Methods

·        Can be adopted to several different types of constraints and domains (variables)

·        Concerned with the ways of reducing the search space with specific search methods

This encompasses two different methods:

                                                       i.            Constraint Propagation Algorithm

Ø      Algorithm that repeatedly removes inconsistent values from the domains

Ø      Reduces the search space

Ø      Maintain equivalence while simplifying the problem

Ø      Achieve various forms of local consistency

                                                      ii.            Search Methods

Ø      Explores the search space

Ø      Consists of combination of constraint propagation, backtrack, branch and bound search

 

Back to Top

 

Constraint Satisfaction Problem

  • Fundamental concept in Constraint Programming
  • CSP is defined by a set of variables Each variable Xi has a non-empty domain Di of possible values
  • Constraint Satisfaction Problem consists of:

Ø      Finite set of variables x1, x2, …,xn

Ø      For each variable x1, a finite set Di of possible values (its domain)

Ø      Set of constraints restricting the values that the variables can take

  • Once CSP is represented, solving process include:

Ø      Determining whether the CSP has a solution (check for consistency)

Ø      Finding a solution – A solution to a CSP is a complete consistent assignment of variables

Ø      Finding all solutions

Ø      Finding an optimal solution

Ø      Finding all optimal solutions

Ø      Finding a good solution

Ø      Classify CSPs on the basis of:

Ø      Domain over which the CSP is defined

Ø      Syntax of the used constraint

Constraint Satisfaction Problems can be classified into four categories depending on the types of domains over which the variables range:

1.      CSP on integers      –          Variables range over integer domains

2.      CSP on reals          –          Variables range over real domains

3.      Boolean CSP         –          Variables range over the binary domain [0..1]

4.      Symbolic CSP        –          Variables range over non-numeric domains

CSP on integers

Example1:

Cryptarithmetic problems

·        Mathematical puzzles

·        Digits are replaced by letters of the alphabet or other symbols

·        Alphametic problems – Problems dealing with valid sums

Example:

Replace each letter by a different digit so that the sum complies

 

SEND

            +MORE

  MONEY

Example2:

The n Queens Problem

Given any integer N, the problem is to place N queens on squares in an N*N chessboard.

Constraint:        No queens threaten each other (no two queens on the same row, column or diagonal)

                        N >= 3

Model:

  1. Assume each queen is in a different column
  2. Assign a variable Ri (with domain 1…N) to the queen in the i-th column indicating the position of the queen in the row

Example3:

The Zebra Puzzle

A famous puzzle of Lewis Carroll where there are five different colored houses on a street. Five men of different nationalities, profession, having likes for a different drink and owning a different pet animal live in these five houses.

The task is to find out who has a zebra and who drinks water, given the following information:

  • The Englishman lives in the red house
  • The Spaniard has a dog
  • The Japanese is a painter
  • The Italian drinks tea
  • The Norwegian lives in the first house on the left
  • The owner of the green house drinks coffee
  • The green house is on the right of the white house
  • The sculptor breeds snails
  • The diplomat lives in the yellow house
  • They drink milk in the middle house
  • The Norwegian lives next door to the blue house
  • The violinist drinks fruit juice
  • The fox is in the house next to the doctor’s
  • The horse is in the house next to the diplomat’s

CSP on reals

Example1: Spreadsheets

A spreadsheet can be represented by means of a CSP that consists of variables each ranging over real numbers and with constraints.

The spreadsheet systematically solves the constraints and updates the new solution with every parameter modification.

Boolean CSPs

  • Special case of numeric CSPs
  • Constraints are expressed by Boolean expressions built using some basic set of connectives

Example1: The full adder circuit

This digital circuit made of AND, OR and XOR gates computes the binary sum. The gates take in two Boolean variable inputs and generate an output. Gate behavior is dependent on their following truth tables.

Symbolic CSPs

Example1: The Crossword puzzle

A variable can be assigned to each grid in a crossword puzzle. Each of these variables can be associated with a domain consisting of a set of words that can be used to fill the grid position.

Constraint: The crosswords share a letter at the grid of intersection

Qualitative Reasoning

Example2: Qualitative Temporal Reasoning

The meeting ran non-stop the whole day. Each person stayed at the meeting for a continuous period of time. The meeting began while Mr. Jones was present and finished while Ms. White was present. Ms. White arrived after the meeting has begun. In turn, Director Smith was also present but he arrived after Jones had left. Mr. Brown talked to Ms. White in the presence of Smith. Could possibly Jones and White have talked during the meeting?

Example3: Qualitative Spatial Reasoning

Two free standing houses are connected by a road. The first house is surrounded by its garden or is adjacent to its boundary while the second house is surrounded by its garden. The question is what we can conclude about the relation between the second garden and the road.

 

Back to Top

 

Solving CSP

 

Consider constraint C on variables y1,y2, …,yn with domains D1, D2, …,Dn

·        We know C

·        If C = D1x…x Dk, and C ≠{ }, then we say that C is solved for k > 0

·        A CSP is solved if

Ø      all constraints are solved

Ø      no domain is empty

Ø      CSP is consistent

·        A CSP is failed if

Ø      it contains the false constraint (example: 0 = 1)

Ø      some of its domain or constraints is empty

Ø      CSP is inconsistent

·        Steps involved:

Ø      Given a CSP

Ø      Solution  corresponds to a unique solved CSP

Ø      The unique solved CSP is:

Ø      Such that

 

BASIC FRAMEWORK

 

 

  1. Preprocess
    • Convert CSP to a desired syntactic form
    • Resulting CSP = CSP w.r.t initial sequence of variables
    • Usually applied only once at the top level
  2. Happy
    • Goal set for the initial CSP is achieved

Ø      A solution has been found

Ø      All solutions have been found

Ø      A solved form has been reached wherefrom all solutions can be generated easily

Ø      An inconsistency detected

Ø      An optimal solution w.r.t. some objective function found

Ø      All optimal solutions found

Ø      All interval domains are reduced to smaller sizes

 

  1. Atomic

·        Check to see if suitable for splitting

·        CSP should be atomic if domains are single sets or empty

·        May also predict that further search is not required

 

  1. Split
    • Carried out if CSP is not happy after constraint propagation and not atomic
    • CSP is split into two or more CSPs by splitting a domain or a constraint
    • If domain is split, each constraint applicable to new domains
 
Back to Top