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

Last modified: Monday, 14 October 2019, 12:37 AM