Constraint Satisfaction 101 Foundations of Constraint Processing CSCE421/821, Fall 2005: www.cse.unl.edu/~choueiry/F05-421-821/ Berthe Y. Choueiry (Shu-we-ri) AVH 123B [email protected] Tel: +1(402)472-5444 Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 1 Outline Motivating example, application areas CSP: Definition, representation Some simple modeling examples More on definition and formal characterization Basic solving techniques (Implementing backtrack search) Advanced solving techniques Issues & research directions Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 2 Motivating example • Context: You are a senior in college • Problem: You need to register in 4 courses for the Spring semester • Possibilities: Many courses offered in Math, CSE, EE, CBA, etc. • Constraints: restrict the choices you can make – Unary: Courses have prerequisites you have/don't have Courses/instructors you like/dislike – Binary: Courses are scheduled at the same time – n-ary: In CE: 4 courses from 5 tracks such as at least 3 tracks are covered • You have choices, but are restricted by constraints – Make the right decisions!! Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 3 Motivating example (cont’d) • Given – A set of variables: 4 courses at UNL – For each variable, a set of choices (values) – A set of constraints that restrict the combinations of values the variables can take at the same time • Questions – Does a solution exist? (classical decision problem) – How two or more solutions differ? How to change specific choices without perturbing the solution? – If there is no solution, what are the sources of conflicts? Which constraints should be retracted? – etc. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 4 Practical applications Adapted from E.C. Freuder • • • • • • • • • • • • Radio resource management (RRM) Databases (computing joins, view updates) Temporal and spatial reasoning Planning, scheduling, resource allocation Design and configuration Graphics, visualization, interfaces Hardware verification and software engineering HC Interaction and decision support Molecular biology Robotics, machine vision and computational linguistics Transportation Qualitative and diagnostic reasoning Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 5 Constraint Processing • is about ... – Solving a decision problem… – … While allowing the user to state arbitrary constraints in an expressive way and – Providing concise and high-level feedback about alternatives and conflicts • Related areas: – AI, OR, Algorithmic, DB, TCS, Prog. Languages, etc. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 6 Power of Constraints Processing • Flexibility & expressiveness of representations • Interactivity users can relax reinforce constraints Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 7 Outline Motivating example, application areas CSP: Definition, representation Some simple modeling examples More on definition and formal characterization Basic solving techniques Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 8 Defining a problem • General template of any computational problem – Given: • Example: a set of objects, their relations, etc. – Query/Question: • Example: Find x such that the condition y is satisfied • How about the Constraint Satisfaction Problem? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 9 Definition of a CSP • Given P = (V, D, C ) – V is a set of variables, V V1 , V 2 , , V n – D is a set of variable domains (domain values) D DV 1 , DV 2 , , DV n – C is a set of constraints, C C 1 , C 2 , , C l with C V a ,V b ,..., V i ( x , y , , z ) D V a D V b D V i • Query: can we find a value for each variable such that all constraints are satisfied? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 10 Other queries… • • • • Find a solution Find all solutions Find the number of solutions Find a set of constraints that can be removed so that a solution exists • Etc. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 11 Representation I • Given P = (V, D, C ), where V V1 , V 2 , , V n D DV 1 , DV 2 , , DV n C C 1 , C 2 , , C l • Find a consistent assignment for variables Constraint Graph • Variable node (vertex) • Domain node label • Constraint arc (edge) between nodes Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 12 Representation II • Given P = (V, D, C ), where V V1 , V 2 , , V n D DV 1 , DV 2 , , DV n C C 1 , C 2 , , C l Example I: V1 {1, 2, 3, 4} v1 < v2 { 3, 6, 7 } V2 v1+v3 < 9 • Define C ? v2 < v3 V3 { 3, 4, 9 } v2 > v4 { 3, 5, 7 } V4 Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 13 Outline Motivating example, application areas CSP: Definition, representation Some simple modeling examples More on definition and formal characterization Basic solving techniques Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 14 Example II: Temporal reasoning B A<B A [ 1.... 10 ] [ 5.... 18] B<C 2<C-A<5 [ 4.... 15] C • Give one solution: ……. • Satisfaction, yes/no: decision problem Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 15 Example III: Map coloring Using 3 colors (R, G, & B), color the US map such that no two adjacent states have the same color • Variables? • Domains? • Constraints? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 16 Example III: Map coloring (cont’d) Using 3 colors (R, G, & B), color the US map such that no two adjacent states have the same color NE WY KS { red, green, blue } CO AR { red, green, blue } { red, green, blue } UT { red, green, blue } AZ OK NM LA TX Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 17 Example IV: Resource Allocation { a, b, c } { a, b } { a, c, d } { b, c, d } What is the CSP formulation? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 18 Example IV: RA (cont’d) { a, b, c } { a, b } { a, c, d } { b, c, d } Constraint Graph T1 { R1, R3 } Interval Order T2 T3 { R1, R3 } T1 { R1, R3 } { R1, R3, R4 } T4 { R1, R3 } { R1, R2, R3 } T5 { R2, R4 } T6 { R2, R4 } T7 T6 { R1, R2, R3 } { R1, R3 } T2 T4 T3 { R1, R3 } { R2, R4 } { R2, R4 } { R1, R2, R3 } T5 T7 Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 19 Example V: Puzzle Given: • Four musicians: Fred, Ike, Mike, and Sal, play bass, drums, guitar and keyboard, not necessarily in that order. • They have 4 successful songs, ‘Blue Sky,’ ‘Happy Song,’ ‘Gentle Rhythm,’ and ‘Nice Melody.’ • Ike and Mike are, in one order or the other, the composer of ‘Nice Melody’ and the keyboardist. • etc ... Query: Who plays which instrument and who composed which song? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 20 Example V: Puzzle (cont’d) Formulation 1: • Variables: Bass, Drums, Guitar, Keyboard, Blue Sky, Happy Song Gentle Rhythm and Nice Melody. • Domains: Fred, Ike, Mike, Sal • Constraints: … Formulation 2: • Variables: Fred's-instrument, Ike's-instrument, …, Fred's-song, Ikes's-song, Mike’s-song, …, etc. • Domains: { bass, drums, guitar, keyboard } { Blue Sky, Happy Song, Gentle Rhythm, Nice Melody} • Constraints: … Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 21 Example VI: Product Configuration Train, elevator, car, etc. Given: • Components and their attributes (variables) • Domain covered by each characteristic (values) • Relations among the components (constraints) • A set of required functionalities (more constraints) Find: a product configuration i.e., an acceptable combination of components that realizes the required functionalities Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 22 Example VII: Cryptarithmetic puzzles • DX1 = DX2 = DX3 = {0,1} • DF=DT=DU=DW=DR=DO=[0,9] • • • • • O+O = R+10X1 X1+W+W = U+10X2 X2+ T+T = O + 10X3 X3=F Alldiff({F,D,U,V,R,O}) Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 23 Constraint types: examples • Example I: algebraic constraints V1 v1 < v2 {1, 2, 3, 4} v1+v3 < 9 { 3, 6, 7 } V2 v2 > v4 v2 < v3 V3 { 3, 4, 9 } • Example II: (algebraic) constraints of bounded difference { 3, 5, 7 } V4 B A<B A [ 5.... 18] [ 1.... 10 ] 2<C-A<5 B<C [ 4.... 15] C • Example III & IV: coloring, mutual exclusion, difference constraints Constraint Graph NE T1 WY { R1, R3 } KS { red, green, blue } CO { red, green, blue } OK NM { R1, R3 } { red, green, blue } AZ { R2, R4 } { red, green, blue } T3 LA T6 { R1, R2, R3 } AR UT T4 { R1, R2, R3 } { R1, R3 } { R2, R4 } T5 T7 TX • Example V & VI: elements of C must be made explicit Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 24 More examples • Example VII: Databases – Join operation in relational DB is a CSP – View materialization is a CSP • Example VIII: Interactive systems – Data-flow constraints – Spreadsheets – Graphical layout systems and animation – Graphical user interfaces • Example IX: Molecular biology (bioinformatics) – Threading, etc Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 25 Outline Motivating example, application areas CSP: Definition, representation Some simple modeling examples More on definition and formal characterization Basic solving techniques Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 26 Representation (again) Macrostructure G(P): V1 - constraint graph for binary constraints - constraint network for non-binary constraints V2 a, c (V1, a ) Micro-structure (P): (V2, a ) (V2, c) (V1, a ) Co-microstructure co-(P): (V2, a ) (V2, c) a, b b, c V3 (V1, b) (V3, b ) (V1, b) (V3, b ) (V3, c) no goods (V3, c) Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 27 Constraint arity I • Given P = (V, D, C ) , where V V1 , V 2 , , V n D DV 1 , DV 2 , , DV n C C 1 , C 2 , , C l V1 {1, 2, 3, 4} v1 < v2 { 3, 6, 7 } V2 v1+v3 < 9 v2 < v3 V3 { 3, 4, 9 } v2 > v4 { 3, 5, 7 } V4 • How to represent the constraint V1 + V2 + V4 < 10 ? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 28 Constraint arity II • Given P = (V, D, C ) , where V V1 , V 2 , , V n D DV 1 , DV 2 , , DV n C C 1 , C 2 , , C l Constraints: universal, unary, binary, ternary, … , global. V1 A Constraint Network: v1 < v2 { 3, 6, 7 } { 1, 2, 3, 4 } v1+v3 < 9 v2 < v3 { 3, 4, 9 } V2 v1+v2+V 4 < 10 v2 > v4 { 3, 5, 7 } V 4 V3 Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 29 Domain types • P = (V, D, C ) where V V1 , V 2 , , V n D DV 1 , DV 2 , , DV n C C 1 , C 2 , , C l with C V k ,V l ,..., V m ( x , y , , z ) D V k D V l D V m • Domains: – Restricted to {0,1}: Boolean CSPs – Finite (discrete), enumeration works – Continuous, sophisticated algebraic techniques are needed • Consistency techniques on domain bounds Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 30 Constraint terminology • Arity: – universal, unary, binary, ternary, …, global • Scope: – The set of variables to which the constraint applies • Definition: – Extension: all allowed tuples are listed – Constrained Decision Diagrams ([Cheng & Yap, AAAI 05]) – Intention: when it is not practical (or even possible) to list all tuples • Define types/templates of common constraints to be used repeatedly: linear constraints, All-Diff (mutex), Atmost, TSPconstraint, cycle-constraint, etc.) • Implementation: – predicate, set of tuples (list or table), binary matrix (bit-matrix), etc. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 31 Complexity of CSP Characterization: – Decision problem – In general, NP-complete by reduction from 3SAT Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 32 Proving NP-completeness 1. Show that 1 is in NP 2. Given a problem 1 in NP, show that an known NP-complete problem 2 can be efficiently reduced to 1 – – – Select a known NP-complete problem 2 (e.g., SAT) Construct a transformation f from 2 to 1 Prove that f is a polynomial transformation (Check Chapter 3 of Garey & Johnson) Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 33 What is SAT? Given a sentence: – Sentence: conjunction of clauses – Clause: disjunction of literals c 2 c 3 – Literal: a term or its negation c1 , c 6 – Term: Boolean variable c1 1 c1 0 c1 c 4 c 5 c 6 c 2 c 3 c 4 Question: Find an assignment of truth values to the Boolean variables such the sentence is satisfied. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 34 CSP is NP-Complete • Verifying that an assignment for all variables is a solution – Provided constraints can be checked in polynomial time • Reduction from 3SAT to CSP – Many such reductions exist in the literature (perhaps 7 of them) Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 35 Problem reduction Example: CSP into SAT (proves nothing, just an exercise) Notation: variable-value pair = vvp • vvp term – V1 = {a, b, c, d} yields x1 = (V1, a), x2 = (V1, b), x3 = (V1, c), x4 = (V1, d), – V2 = {a, b, c} yields x5 = (V2, a), x6 = (V2, b), x7 = (V2,c). • The vvp’s of a variable disjunction of terms – V1 = {a, b, c, d} yields x1 x 2 x 3 x 4 • (Optional) At most one VVP per variable x1 x 2 x 3 x 4 x1 x 2 x 3 x 4 x1 x 2 x 3 x 4 x1 x 2 x 3 x 4 Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 36 CSP into SAT (cont.) Constraint: 1. Way 1: Each inconsistent tuple one disjunctive clause – 2. C V1V 2 {( a , a ), ( a , b ), ( b , c ), ( c , b ), ( d , a )} For example: x1 x 7 how many? Way 2: a) b) Consistent tuple conjunction of terms x1 x 5 Each constraint disjunction of these conjunctions x1 x 5 x1 x 6 x 2 x 7 x3 x6 x 4 x5 transform into conjunctive normal form (CNF) Question: find a truth assignment of the Boolean variables such that the sentence is satisfied Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 37 Outline Motivating example, application areas CSP: Definition, representation Some simple modeling examples More on definition and formal characterization Basic solving techniques • Modeling and consistency checking • Constructive, systematic search • Iterative improvement, local search Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 38 How to solve a CSP? Search 1. Constructive, systematic 2. Iterative repair, local search Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 39 Before starting search! Consider: • Importance of modeling/formulation: – To control the size of the search space • Preprocessing – A.k.a. constraint filtering/propagation, consistency checking – reduces size of search space Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 40 Importance of modeling • N-queen: formulation 1 1 2 3 4 V1 – Variables? – Domains? – Size of CSP? V2 4 Rows 4 Column positions V3 4444 4 2 4 8 V4 • N-queens: formulation 2 V11 V12 V13 V14 – Variables? 16 Cells {0,1} – Domains? 16 – Size of CSP? 2 V21 V22 V23 V24 V31 V32 V33 V34 V41 V42 V43 V44 Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 41 Constraint checking Arc-consistency B A< B A 1- B: [ 5 .. 14 ] 13 14 C: [ 6 .. 15 ] [ 5.... 18] B<C 2 [ 1.... 10 ] 2- A: [ 2 .. 10 ] C: [ 6 .. 14 ] 2<C -A<5 6 3- B: [ 5 .. 13 ] 14 [ 4.... 15] C Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 42 Constraint checking Arc-consistency: every combination of two adjacent variables 3-consistency, k-consistency (k n) Constraint filtering, constraint checking, etc.. Eliminate non-acceptable tuples prior to search Warning: arc-consistency does not solve the problem B A { 1, 2, 3 } A { 2, 3 } { 2, 3, 4 } ( A 2 ) ( B 3) B { 2, 3 } still is not a solution! Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 43 Systematic search Starting from a root node Consider all values for a variable V1 For every value for V1, consider all values for V2 etc.. S V ar 1 v1 v2 v3 v4 V ar 2 For n variables, each of domain size d Maximum depth? fixed! Maximum number of paths? size of search space, size of CSP Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 44 Systematic search (I) Back-checking • Systematic search generates dn possibilities • Are all possibilities acceptable? S S V ar 1 v1 V ar 1 v1 v2 v3 v2 v3 v4 v4 V ar 2 V ar 2 Expand a partial solution only when it is consistent This yields early pruning of inconsistent paths Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 45 Systematic search (II) Chronological backtracking What if only one solution is needed? S S Var 1 V ar 1 v1 v2 v3 v1 v2 v4 V ar 2 • Depth-first search & Chronological backtracking • DFS: Soundness? Completeness? Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 46 Systematic search (III) Intelligent backtracking What if the reason for failure was higher up in the tree? Backtrack to source of conflict !! S Var 1 v1 S v2 V ar 1 v1 v2 Backjumping, conflict-directed backjumping, etc. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 47 Systematic search (IV) Ordering heuristics • Which variable to expand first? Exp : V1 , V 2 , D V1 { a , b , c , d }, D V 2 { a , b } Sol : {( V 1 c ), (V 2 a )} and {( V 1 c ), (V 2 b )} s V1 • Heuristics: V2 a a s b b a c b a V2 d b V1 a a b b c d – most constrained variable first (reduce branching factor) – most promising value first (find quickly first solution) Strategies variable ordering static for could be value ordering dynamic Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 48 Systematic search (V) Back-checking • Search tree with only backtrack search? Root node Q Q Q Q 2 1 Q Q 1 2 3 4 1 2 3 4 1 2 3 4 Q 1 2 3 4 1 2 3 4 1 1 2 3 Solution! 26 nodes visited. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 49 Systematic search (VI) Forward checking Search Tree with domains filter by Forward Check Root node Q Q Q 2 1 Q Q Q Q 3 4 4 Domain 2 Wipe Out V3 Domain Wipe Out V4 1 3 Solution! 8 nodes visited. Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 50 Improving BT search • General purpose methods for 1. Variable, value ordering 2. Improving backtracking: intelligent backtracking avoids repeating failure 3. Look-ahead techniques: propagate constraints as variables are instantiated Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 51 Search-tree branching • K-way branching – One branch for every value in the domain • Binary branching – One branch for the first value – One branch for all the remaining values in the domain – Used in commercial constraint solvers: ILOG, Eclipse • Have different behaviors (e.g., WRT value ordering heuristics [Smith, IJCAI 95]) Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 52 Summary of backtrack search • Constructive, systematic, exhaustive – In general sound and complete • Back-checking: expands nodes consistent with past • Backtracking: Chronological vs. intelligent • Ordering heuristics: – Static – Dynamic variable – Dynamic variable-value pairs • Looking ahead: – Partial look-ahead • Forward checking (FC) • Directional arc-consistency (DAC) – Full (a.k.a. Maintaining Arc-consistency or MAC) Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 53 CSP: a decision problem (NP-complete) 1. 2. Modeling: abstraction and reformulation Preprocessing techniques: • 3. eliminate non-acceptable tuples prior to search Systematic search: • • • • potentially dn paths of fixed lengths chronological backtracking intelligent backtracking variable/value ordering heuristics Search ‘hybrids:’ 4. • Mixing consistency checking with search: look-ahead strategies Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 54 Non-systematic search • Iterative repair, local search: modifies a global but inconsistent solution to decrease the number of violated constraints • Examples: Hill climbing, taboo search, simulated annealing, GSAT, WalkSAT, Genetic Algorithms, Swarm intelligence, etc. • Features: Incomplete & not sound – Advantage: anytime algorithm – Shortcoming: cannot tell that no solution exists Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 55 Outline of CSP 101 • We have seen Motivating example, application areas CSP: Definition, representation Some simple modeling examples More on definition and formal characterization Basic solving techniques • We will move to (Implementing backtrack search) Advanced solving techniques Issues & research directions Foundations of Constraint Processing, Fall 2005 Aug 25, 2005 Overview 1 56

Descargar
# Foundations of Constraint Processing CSCE421/821, Fall …