article based on Chapter 5 of Artificial Intelligence: A Modern Approach 2^nd Edition

a constraint satisfaction problem is defined by:

• set of variables
• set of constraints
• set of domains for each variable

consistent - an assignment of some/all variables that does not violate constraints
complete - every variable is assigned a value
solution - a complete and consistent assignment. some CSPs also require a solution that maximizes an objective function

Constraint Optimization Problem - CSP with preference constraints

Types of Constraints

• linear constraint - variable appears in linear form only

• nonlinear constraint - variable appears in nonlinear form

• unary constraint

  • restricts value of single variable
  • used with node-consistency

• binary constraint

  • restriction on 2 variables
  • used with arc-consistency

• global/high-order constraint - restriction on 3 or more variables

• resource/atmost constraint (less so called bound constraint)

  • for example, let A, B, C denote the numbers of personnel assigned to each of the 3 variables. The constraint that no more than 10 personnel are assigned in total is written as atmost(10, A, B, C). An inconsistency can be detected by checking the sum total of the minimum values of the current domains. We can enforce consistency by deleting any maximum values that are inconsistent with the minimum values of other domains
  • used with bounds consistency

• absolute constraint - a violation of constraint rules out potential solution

• preference constraint - indicates which solutions are preferred

• precedence constraint - whenever a task must occur before another, and the task takes duration d to complete

• constraint weighting - concentrate the search on the important constraints

  • each constraint is given a weight
  • at each step, algorithm choose a variable/value pair to change, resulting in the lowest total weight of all violated constraints
  • weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment

Types of Domains

• discrete domains
  • finite domains - e.g. Boolean CSPs, whose variables are either true or false
  • infinite domains - e.g. integers
• continuous domains
  • e.g. real numbers
  • well-known category of continuous-domain CSPs is linear programming problems, where constraints must be linear inequalities forming a convex region

CSPs Structure: Constraint Graph

• nodes are variables
• arcs correspond to constraints

• constraint hypergraph - ordinary nodes and hypernodes which represent n-ary constraints

Modes of Solving CSPs

Incremental Formulation

1. initial state: the empty assignment {}, in which all variables are unassigned
2. successor function: a value can be assigned to any unassigned variable, provided that it does not conflict with previously assigned variables
3. goal test: the current assignment is complete
4. path cost: a constant cost for every step

Complete-State Formulation

1. initial state: start with a complete state whether or not it satisfies the constraints
2. successor function: 
   1. (1. choose a variable) and (2. assign it a different value)
   2. local search methods work well for this formulation
3. goal test: the current assignment is consistent
4. path cost: a constant cost for every step

Search Methods for CSPs

heuristics in choosing (the next variable to assign) and (the value to assign that variable)

• minimum remaining values (MRV) or most constrained variable - choose variable with the fewest legal values
• degree heuristic - select variable that is involved in largest number of constraints on other unassigned variables
• least constraining value (LCV) or min-conflicts heuristic - choose value that rules out the fewest choices for the neighboring unassigned variables

consistency and propagating information through constraints - details on Consistency Types

• constraint propagation - using the constraints to reduce the number of legal values for a variable

• bounds propagation

• node consistency (1-consistency)

  • variable X is node consistent if, all values in X’s domain satisfy the X’s unary constraints

• forward checking

  • whenever variable X is assigned, look at each unassigned variable Y connected to X by a constraint and deletes from Y’s domain any value that is inconsistent with the value chosen for X

• arc consistency (2-consistency)

  • stronger than forward checking

  • arc consistency tightens down the domains (unary constraints) using the arcs (binary constraints)

  • (X,Y) is arc consistent if, for every value in domain X, there is some value in domain Y that is consistent

  • the algorithm MAC (for Maintaining Arc Consistency (MAC)) detects arc inconsistency

  • the most popular algorithm for arc consistency is called AC-3. The complexity of AC-3 can be analyzed as follows. Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Each arc (X_k,X_i) can be inserted in the queue only d times because Xi has at most d values to delete. Checking consistency of an arc can be done in O(d²) time, so we get O(cd³) total worst-case time

    List indent undo

    

• generalized arc consistent
  • A variable X is generalized arc consistent with respect to i an n-ary constraint if for every value v in the domain of X_ithere exists a tuple of values that is a member of the constraint, has all its values taken from the domains of the corresponding variables, and has its X_icomponent equal to v. For example, if all variables have the domain {0,1,2,3}, then to make the variable X consistent with the constraint X < Y < Z, we would have to eliminate 2 and 3 from the domain of X because the constraint cannot be satisfied when X is 2 or 3
• directed arc consistency (DAC)
  • A CSP is defined to be directed arc-consistent under an ordering of variables X₁, X₂, …, X_nif and only if every X_iis arc-consistent with each X_jfor j>i
• path consistency
  • path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables
  • any pair of adjacent variables can always be extended to a third neighboring variable
• k-consistency
  • a CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any k^th variable
• strongly k-consistent
  • a graph is strongly k-consistent if it is k-consistent, (k-1)-consistent, …, 1-consistent
• bounds consistent (used with resource/atmost/bound constraint)
  • if every variable X, and for both the lower bound and upper bound values of X’s domain, there exists some value of Y that satisfies the constraint between X and Y, for every variable Y

intelligent backtracking: looking backward

• chronological backtracking
  • when branch of search fails, backup to the preceding variable and try a different value
• backjumping
  • backtracks to the most recent variable in the conflict set
  • conflict set - a conflict set for variable X is the set of previously assigned variables that are connected to X by constraints
• conflict-directed backjumping
  • a variant of the backjumping algorithm where each parent variable inherits the children’s conflict set

CSPs Structure: Continued

• CSP Decomposition into Independent Subproblems
• Constraint Satisfaction Problems (CSP)
• Constraint Satisfaction Problems (CSP)
• Constraint Satisfaction Problems (CSP)

CSP Decomposition into Independent Subproblems

• any solutions of any subproblems yields a solution for the whole problem
• independence can be ascertained simply looking for connected components of the CSP’s constraint graph
• consider the following: suppose each independent subproblem CSP_i has c variables from the total of n variables, where c is a constant. Then there are n/c subproblems, each of which takes at most d^cwork to solve, where d is the size of the domain.
  • with decomposition of independent subproblems: the total work is O(d^cn/c), which is linear in n, exponential in d
  • without the decomposition, the total work is O(dⁿ), which is exponential in n
• for example, dividing a Boolean CSP with 80 variables into four subproblems reduces the worst-case solution time from the lifetime of the universe down to less than a second
• however, completely independent subproblems are rare

CSP tree-structured constraint graph

• simplest constraint graph

• any 2 variables/nodes are connected by at most 1 path

• tree-structure algorithm - can be solved in the following steps: runtime = O(nd²) where CSP tree have n variables/nodes and d possible domain values

  • topologically sort tree - choose any variable as root of tree, then order all variables and label them X₁, X₂, …, X_n. therefore every variable except the root has exactly 1 parent
  • for j from n to 2, apply arc consistency to arc (X_i, X_j), where X_i is the parent of X_j, removing values from X_i’s domain
  • for j from 1 to n, assign any value for X_j consistent with the value assigned for X_i, where X_i is the parent of X_j

  List indent undo

  

  List indent undo

  

CSP turning constraint graph into tree-structure

• general algorithm is as follows: runtime = O(d^c(n-c)d²) where c is the size of the cycle cutset
  1. choose a subset S from Variable[csp] such that the constraint graph becomes tree after removal of subset S. S is called the cycle cutset
  2. for each possible assignment to the variables in S that satisfies all constraints on S:
     1. remove from the domains of the remaining variables (Variable[csp] - S) any values that are inconsistent with the assignment for S
     2. run tree-structure algorithm on remaining CSP. If tree-structure algorithm has a solution, return it together with the assignment of S
• finding the smallest cycle cutset is NP-hard

  List indent undo

  

CSP tree-decomposition

• another approach in solving CSP

• construct a tree-decomposition of the constraint graph into a set of connected subproblems

• a tree-decomposition must satisfy the following requirements:

  • every variable in the original problem appears in at least one of the subproblems
  • if 2 variables are connected by a constraint in the original problem, they must appear together (along with constraint) in at least one of the subproblems
  • if a variable appears in two subproblems in the tree, it must appear in every subproblem along the path connecting those subproblems

  List indent undo