December 31 - Constraint Satisfaction Problems

(Stanford AI/ML)
[Constraint Satisfaction Problems (CSPs) 1 - Overview Stanford CS221: AI (Autumn 2021)](https://youtu.be/-IO4fPO0rxk?si=40fGtjIu_AjF5New)
[Constraint Satisfaction Problems (CSPs) 2 - Definitions Stanford CS221: AI (Autumn 2021)](https://youtu.be/uj5wCcHsSlA?si=kGZ7IVtRJKlqVdOR)
[Constraint Satisfaction Problems (CSPs) 3 - Examples Stanford CS221: AI (Autumn 2021)](https://youtu.be/Tu6BiZhMDCc?si=AQuUYqLC4H7DW-9i)
Variable based Models - Constraint Satisfaction
- Factor graphs -(variables and factors)
  - Objective: find the best assignment of values to the variables
- Special cases
  - Constraint satisfaction problems
  - Markov networks
  - Bayesian networks
Key Idea: Variables!
- A Solution (to a problem) => is the assignments to variables (modeling)
- Decisions about variable ordering (using inference)
- ** Higher-level modeling language than state-based models! **
Applications
- Delivery/routing - assign packages to trucks to deliver to customers
- Sports scheduling - when to schedule pairs of teams to minimize travel, fitting TV broadcast schedule, etc. (also can think about class scheduling at a university)
- Former verification - ensure circuit/program works on all inputs
  - This is different then the above items, where you are trying to prove that “no such satisfying assignment exists” because that would mean an error in your program (in the example where you write a circuit and you are trying to confirm that you’ve handled every possible case)
Assignment Weights -
- Each assignment x has a weight, and the Weight is equal to product of all f_j(x)
- An assignment is consistent if Weight(x) > 0
- Objective: find the maximum weight assignment (argmax Weight(x)
- A Constraint Satisfaction Problem (CSP) is satisfiable if max_x*Weight(x) > 0
- Weights cannot be negative, and these are not analogous to weights in AI/ML (they can be non-negative)
CSPs
- Boolean satisfiability (SAT): variables are booleans, factors are logical formulas [X1 or/and !X2 or/and X5)
- Linear programming (LP): variables are reals, factors are linear inequalities [ X2 + 3X <= 1]
- Integer Linear Programs (ILP)…same as LP, but variables are integers; , factors are linear inequalities
  - Because they are integers, this makes them as hard to solve as SAT
- Mixed Integer Programming (MIP)
  - Variables are reals and integers, factors are linear inequalities
Summary (so far)
- Factor Graph
  - Variables (unknown quantities that we want to ascertain)
  - Factors (scoped) - specify preferences or constraints for partial assignments
  - What’s special about factor graphs, is that you are specifying constraints and preferences in a local way
- Key definition - the weight of an assignment is the product of all the factors
  - This is where you have to think globally
- Objective: (which requires global reasoning over all the factors)
- Specify locally and optimize globally (inference algo’s job)
LSAT Problem (example) - A, B, C, sculptures in rooms 1 or 2, with some rules (A, B cannot be in the same room, B and C must be in the same room, Room 2 can only hold one sculpture)
- Variables:
  - ‘A’, [1,2]
  - ‘B’, [1,2]
  - ‘C’, [1,2]
- Factors: factor is a function that takes on an assignment to the variables in that scope*
  - A, B cannot be in the same room
    - factor(‘name:ab’, ‘scope: variables A and B’, function (a, b) { return a !=b })
- B and C must be in the same room
  - factor(‘name: bc’, scope: variables B C, function(b, c) { return b ==c })
- Room 2 can only hold one sculpture
  - factor (‘room2’, scope: A, B, C), function(a, b, c) {
    - num=0
    - If ( a == room2) n++;
    - If ( b == room2) n++;
    - If ( c == room2) n++;
    - If n >1 return false else true
Object Tracking Problem (example)
Event Schedule (example)
- Solved from two angles…from an events perspective…and the timeslot perspective
Program Verification (example)
CSP Summary
- Decide on variables and domains
  - An assignment to all these variables give you the result of interest
- Translate each desideratum (constraints, preferences, wishes) into a set of factors
  - This can often be done in parallel, where you set these factors as discovered and at the end of the day, you throw them all into the CSP
- Try to keep CSP small (variables, factors, domains, arities) to help in computational efficiency
- When implementing each factor, think in terms of checking a solution rather than computing the solution (the CSP algo will figure out the solution!!)