Constraint Solving by Martine Ceberio

Tutorial on Constraint Programming.

The basic idea behind Constraint programming is that users would just need to state their constraints, and the solver would take care of finding solutions, which should satisfy all the constraints vlc skins kostenlos downloaden.

Brief 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 speedfan for free german. The first implementations of constraint logic programming were Prolog III, CLP(R), and CHIP. Several constraint logic programming interpreters exist today cod mw nur warzone herunterladen.

Constraints

Constraints are relationships between variables or unknowns, each taking a value in a given domain: constraints restrict possible values that variables can take download linux ubuntu. Constraints need to be identified in order to solve problems by means of constraint solving techniques.

Properties of constraints:

  • May specify partial information
    • Don’t necessarily specify the values of variables
  • Heterogeneous
    • May specify relations between variables with different domains
  • Non-directional
  • Declarative
    • Specify what variable relationships may hold
  • Additive
    • Conjunction of constraints is important: relations add to each other
  • 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 domain
    2. Extended intervals of real
    3. The set of reals

Constraint Satisfaction Problems (CSP)

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 gta san andreas kostenlos herunterladen für pc. CSP on integers      –          Variables range over integer domains

2. CSP on reals          –          Variables range over real domains

3 download your own pictures facebook. 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 download film from swr mediathek.

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 tubemate android kostenlos. 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 format factory herunterladen.

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 virtual room planner for free. 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.

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

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
  • 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

    Constraint Programming.

    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 steps:

    1. Declaring the domains of the variables
    2. Declaring the constraints on the declared variables
    3. Searching for the solutions

    The Constraint Programming Process

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

    Constraint Solving

    Domain Specific Methods

    • Special purpose algorithms devoted to specific domains and constraints
    • Method by means of specialized packages called constraint solvers
    • Examples include:
      1. Program that solves systems of linear equations
      2. Package for linear programming
      3. Implementation of unification algorithm
      4. Preferred over General methods, should it be available

    General Methods

    • Can be used for several different types of constraints and domains (of the variables)
    • Concerned with the ways of reducing the search space with specific search methods

    This encompasses two different methods:

    • 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
    • Search Methods
      • Explores the search space
      • Consists of combination of constraint propagation, backtrack, branch and bound search