CSPs

States Of Variables

• State is assignment of values to variables under constraints

• Three kinds:

  • Constraint Satisfaction Problem: Find an assignment that satisfies constraints

  • Optimization Problem: Find an assignment that optimizes some objective function

  • Constraint Optimization Problem: Find assignment that optimizes under constraints

CNF 3-SAT

• Variables are "atoms" in logical formula; values are true or false

• Formula is in Conjunctive Normal Form with at most 3 variables per clause: e.g.

  (A or not B or C) and (not A and B or C) and (A or B or C)
  

• Constraint is that the formula be true: every clause must have at least 1 true literal

  • For this formula take A=f, B=f, C=t

• In general, problem is NP-complete

Complete Search For CSPs (3-SAT)

• Let's add a third "unassigned" state for variables. This extends the state space to include partial assignments

• Algorithm (DPLL):

  • Try assigning A=t. If the formula has no false clauses, try recursively solving the remaining variables

  • Try assigning A=f. If the formula has no false clauses, try recursively solving the remaining variables

  • If no solution has been found, return unsat

• This is breadth-first search to a fixed depth (number of variables)

Variable Ordering

• Free choice at each state of which variable to solve for next

• Heuristics are probably helpful here:

  • Branch on variables that have large number of occurrences (to fail quickly)

  • Branch on variables in short clauses (to fail quickly)

• Generally "most constrained first"

Value Ordering

• Free choice at each state of what order to try values for chosen variable

• Heuristics are probably helpful here:

  • Try value that satisfies most clauses (to succeed quickly)

  • Try value that produces most short clauses (to make problem easy to solve) [Crawford et al]

• Generally "least constraining first"

Local Search for CSPs (3-SAT)

• Start with a random assignment of values to variables

• Neighbors are change of value of some variable: "flips" in 3-SAT

• Heuristic: Number of satisfied clauses (more is better)

• Use "noise moves" and "restarts" as usual to speed up search

Optimization for CSPs (HW Problem)

• Same basic framework: use complete or local search

• Complete search can find an optimal solution — in principle

• Heuristics will involve the scoring of a partial or total solution — greed is good