Constraints and Search约束的搜索

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Constrainedness,Including slides from Toby Walsh,Constraint satisfaction,Constraint satisfaction problem(CSP)is a triple where:,V is set of variables,Each X in V has set of values,D_X,Usually assume finite domain,true,false,red,blue,green,0,10,C is set of constraints,Goal:find assignment of values to variables to satisfy all the constraints,Constraint solver,Tree search,Assign value to variable,Deduce values that must be removed from future/unassigned variables,Constraint propagation,If any future variable has no values,backtrack else repeat,Number of choices,Variable to assign next,value to assign,Some important refinements like nogood learning,non-chronological backtracking,Constraint propagation,Arc-consistency(AC),A binary constraint r(X1,X2)is AC iff,for every value for X1,there is a consistent value(often called,support,)for X2 and vice versa,E.g.With 0/1 domains and the constraint X1=/=X2,Value 0 for X1 is supported by value 1 for X2,Value 1 for X1 is supported by value 0 for X2,A problem is AC iff every constraint is AC,Tree search,Backtracking(BT),Forward checking(FC),Backjumping(BJ,CBJ,DB),Maintaining arc-consistency(MAC),Limited discrepancy search(LDS),Non-chronological backtracking&learning,Probing,Modelling,Choose a basic model,Consider auxiliary variables,To reduce number of constraints,improve propagation,Consider combined models,Channel between views,Break symmetries,Add implied constraints,To improve propagation,Propositional Satisfiability,SAT,does a truth assignment exist that satisfies a propositional formula?,special type of constraint satisfaction problem,Variables are Boolean,Constraints are formulae,NP-complete,3-SAT,formulae in clausal form with 3 literals per clause,remains NP-complete,(x1 v x2)&(-x2 v x3 v-x4),x1/True,x2/False,.,Random 3-SAT,Random 3-SAT,sample uniformly from space of all possible 3-clauses,n,variables,l,clauses,Which are the hard instances?,around,l/n,=4.3,What happens with larger problems?,Why are some dots red and others blue?,Random 3-SAT,Varying problem size,n,Complexity peak appears to be largely invariant of algorithm,backtracking algorithms like Davis-Putnam,local search procedures like GSAT,Whats so special about 4.3?,Random 3-SAT,Complexity peak coincides with solubility transition,l/n 4.3 problems over-constrained and UNSAT,l/n=4.3,problems on“knife-edge between SAT and UNSAT,Shape,“Sharp(in a technical sense)Friedgut 99,Location,2-SAT occurs at l/n=1 Chavatal&Reed 92,Goerdt 92,3-SAT occurs at 3.26 l/n 4.598,Theoretical results,“But it doesnt occur in X?,X=some NP-complete problem,X=real problems,X=some other complexity class,“But it doesnt occur in X?,X=some NP-complete problem,Phase transition behaviour seen in:,TSP problem(decision not optimization),Hamiltonian circuits(but NOT a complexity peak),number partitioning,graph colouring,independent set,.,“But it doesnt occur in X?,X=real problems,Phase transition behaviour seen in:,job shop scheduling problems,TSP instances from TSPLib,exam timetables Edinburgh,Boolean circuit synthesis,Latin squares(alias sports scheduling),.,“But it doesnt occur in X?,X=some other complexity class,Phase transition behaviour seen in:,polynomial problems like arc-consistency,PSPACE problems like QSAT and modal K,.,Algorithms at the phase boundary,What do we understand about problem hardness at the phase boundary?,How can this help build better algorithms?,Kappa,Defined for an ensemble of problems,Kappa (motivation),Kappa,When every state is a solution,When every state is not a solution,When there is a unique solution,Kappa,When every state is a solution,When every state is not a solution,When there is a unique solution,Easy Soluble,Easy Insoluble,On the knife edge,Hard,An Example:random CSPs,Each of n variables has a uniform domain size m,There is a probability p1 of a constraint between a pair of variables,There is a probability p2 that a pair of values conflict(when a constraint exists),An Example:random CSPs,An Example:random CSPs,Can rearrange this formula so that we find the value of p2,such that we are at the phase transition,i.e.when kappa=1,Then perform experiments to see if it is accurate predictor,i.e.we put theory to the test,Kappa as a heuristic,Minimise that,An Example:not random CSPs,An Example:not random CSPs,Kappa is general(3 examples),SAT with n variables,l clauses,a literals/clause,Graph colouring,n vertices,e edges,m colours,Number partitioning,n numbers,range(0,l,m bags with same sum,Kappa as a heuristic,Minimise that,Minimise that,assume we only measure domain size(denominator),assume we only measure top line(numerator),assume we measure top and bottom line(numerator and denominator,But thats costly to do.,Is there a low cost surrogate?,Looking inside search,Three key insights,constrainedness“knife-edge,backbone structure,2+p-SAT,Suggests branching heuristics,also insight into branchi