Constraint graph Binary CSP:each constraint relates two variables Constraint gra :s are constraints NT WA SA NS W 4Feb2004 CS 3243-Constraint Satisfaction 6
4 Feb 2004 CS 3243 - Constraint Satisfaction 6 Constraint graph ◼ Binary CSP: each constraint relates two variables ◼ ◼ Constraint graph: nodes are variables, arcs are constraints ◼
Varieties of CSPs Discrete variables finite domains: n variables,domain size d)complete assignments e.g.,Boolean CSPs,incl.~Boolean satisfiability (NP-complete) infinite domains: integers,strings,etc. e.g.job scheduling,variables are start/end days for each job need a constraint language,e.g.,Startob,+5s StartJoba Continuous variables ■ e.g.,start/end times for Hubble Space Telescope observations linear constraints solvable in polynomial time by linear programming 4Feb2004 CS 3243-Constraint Satisfaction 7
4 Feb 2004 CS 3243 - Constraint Satisfaction 7 Varieties of CSPs ◼ Discrete variables ◼ ◼ finite domains: ◼ n variables, domain size d → O(d n ) complete assignments ◼ e.g., Boolean CSPs, incl.~Boolean satisfiability (NP-complete) ◼ infinite domains: ◼ integers, strings, etc. ◼ e.g., job scheduling, variables are start/end days for each job ◼ need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3 ◼ Continuous variables ◼ ◼ e.g., start/end times for Hubble Space Telescope observations ◼ linear constraints solvable in polynomial time by linear programming
Varieties of constraints Unary constraints involve a single variable, ■e.g,SA+green Binary constraints involve pairs of variables, ▣e.g,SA+WA Higher-order constraints involve 3 or more variables, 4Feb2g,cryptarithretis olmssonsraints P
4 Feb 2004 CS 3243 - Constraint Satisfaction 8 Varieties of constraints ◼ Unary constraints involve a single variable, ◼ e.g., SA ≠ green ◼ ◼ Binary constraints involve pairs of variables, ◼ e.g., SA ≠ WA ◼ ◼ Higher-order constraints involve 3 or more variables, ◼ e.g., cryptarithmetic column constraints ◼
Example:Cryptarithmetic T WO +T WO FOUR o Variables:FTUW ROXXX3 ■Domains:{01,2,3,456☑8，y Constraints:Alldiff (FTU,WR,O) ◆ 0+0=R+10·X ■X+W+W=U+10:X2 4 Feb 2002=24Constraint Satisfaction 9 FT0厂0
4 Feb 2004 CS 3243 - Constraint Satisfaction 9 Example: Cryptarithmetic ◼ Variables: F T U W R O X1 X2 X3 ◼ Domains: {0,1,2,3,4,5,6,7,8,9} ◼ Constraints: Alldiff (F,T,U,W,R,O) ◼ ◼ O + O = R + 10 ·X1 ◼ ◼ X1 + W + W = U + 10 ·X2 ◼ ◼ X2 + T + T = O + 10 ·X3 ◼ X3 = F, T ≠ 0, F ≠ 0
Real-world CSPs Assignment problems e.g.,who teaches what class Timetabling problems ◆ e.g.,which class is offered when and where? Transportation scheduling o Factory scheduling FeNetice that mamy sreafowerletiproblems involve real-10
4 Feb 2004 CS 3243 - Constraint Satisfaction 10 Real-world CSPs ◼ Assignment problems ◼ e.g., who teaches what class ◼ ◼ Timetabling problems ◼ ◼ e.g., which class is offered when and where? ◼ ◼ Transportation scheduling ◼ ◼ Factory scheduling ◼ ◼ Notice that many real-world problems involve realvalued variables