Chapter 13Constraint OptimizationAnd counting, and enumeration275 classOutline Introduction Optimization tasks for graphical models Solving optimization problems with inference and search Inference Bucket elimination, dynamic programming Mini-bucket elimination Search Branch and bound and best-first Lower-bounding heuristics  AND/OR search spaces Hybrids of search and inference Cutset decomposition Super-bucket schemeA Bred greenred yellowgreen redgreen yellowyellow greenyellow redExample: map coloringVariables - countries (A,B,C,etc.)Values - colors (e.g., red, green, yellow)Constraints: etc. ,ED D, AB,A CABDEFGTask: consistency?Find a solution, all solutions, countingConstraint Satisfaction= {(¬C), (A v B v C), (¬A v B v E), (¬B v C v D)}.Propositional SatisfiabilityConstraint Optimization Problemsfor Graphical Modelsfunctionscost - },...,{ domains - },...,{ variables- },...,{ :where,, triplea is A 111mnnffFDDDXXXFDXRCOPfiniteA B D Cost1 2 3 31 3 2 22 1 3 02 3 1 03 1 2 53 2 1 0 miiXfXF1)(FunctionCost Globalf(A,B,D) has scope {A,B,D}Constraint Optimization Problemsfor Graphical Modelsfunctionscost - },...,{ domains - },...,{ variables- },...,{ :where,, triplea is A 111mnnffFDDDXXXFDXRCOPfiniteA B D Cost1 2 3 31 3 2 22 1 3 02 3 1 03 1 2 53 2 1 0GAB CD F miiXfXF1)(FunctionCost GlobalPrimal graph =Variables --> nodesFunctions, Constraints -arcsf1(A,B,D)f2(D,F,G)f3(B,C,F)f(A,B,D) has scope {A,B,D}F(a,b,c,d,f,g)= f1(a,b,d)+f2(d,f,g)+f3(b,c,f)Constrained OptimizationExample: power plant scheduling)X,...,ost(XTotalFuelC minimize :)(Power : demandpower time,down-min and up-min ,, :sConstraint. domain ,VariablesN143211ObjectiveDemandXXXXX{ON,OFF}},...,X{Xin8 A graphical model (X,D,F): X = {X1,…Xn} variables D = {D1, … Dn} domains F = {f1,…,fm} functions Operators: combination  elimination (projection) Tasks: Belief updating: X-y j Pi  MPE: maxX j Pj CSP: X j Cj Max-CSP: minX j fjGraphical Models)( : CAFfiADBCEF All these tasks are NP-hard exploit problem structure identify special cases approximateA C F P(F|A,C)0 0 0 0.140 0 1 0.960 1 0 0.400 1 1 0.601 0 0 0.351 0 1 0.651 1 0 0.721 1 1 0.68Primal graph(interaction graph)A C Fred green blueblue red redblue blue greengreen red blueRelationCombination of Cost FunctionsA B f(A,B)b b 6b g 0g b 0g g 6B C f(B,C)b b 6b g 0g b 0g g 6A B C f(A,B,C)b b b 12b b g 6b g b 0b g g 6g b b 6g b g 0g g b 6g g g 12+= 0+ 69Elimination in a Cost FunctionA B f(A,B)b b 4b g 6b r 1g b 2g g 6g r 3r b 1r g 1r r 6Elim(f,B)A g(A)bgr112Elim(g,A)h1Min10Conditioning a Cost FunctionA B f(A,B)b b 6b g 0b r 3g b 0g g 6g r 0r b 0r g 0r r 6Assign(fAB,A,b)Bb 6g 0r 3g(B)Assign(g,B,r)03h11Outline Introduction Optimization tasks for graphical models Solving by inference and search Inference Bucket elimination, dynamic programming, tree-clustering, bucket-elimination Mini-bucket elimination, belief propagation Search Branch and bound and best-first Lower-bounding heuristics  AND/OR search spaces Hybrids of search and inference Cutset decomposition Super-bucket scheme13Computing the Optimal Cost Solution0eminConstraint graphADECBB CEDVariable Eliminationbcde ,,,min0f(a,b)+f(a,c)+f(a,d)+f(b,c)+f(b,d)+f(b,e)+f(c,e)OPT =f(a,c)+f(c,e) +cmin),,,( ecdahBf(a,b)+f(b,c)+f(b,d)+f(b,e)bmindminf(a,d) + Combination14Elimination operatorOPTbucket B: f(c,a) f(c,e) f(a,b) f(b,c) f(b,d) f(b,e)bucket C: bucket D:bucket E: bucket A:e=0(a)hEe)c,d,(a,hBe)d,(a,hCFindingbminrjjXXXfOPTn11)(min,...,Algorithm elim-opt (Dechter, 1996)Non-serial Dynamic Programming (Bertele and Briochi, 1973)BCDEAf(a,d) e)(a,hD),(),(),(),(),(),(),(min,,,,ecFebFdbFcbFdaFcaFbaFOPTbcdea15Generating the Optimal AssignmentC:E:f(a,b) f(b,c) f(b,d) f(b,e)B:D:A:f(c,a) f(c,e)e=0e)(a,hD(a)hEe)c,d,(a,hBe)d,(a,hC(a)hEamin arga' 1. 0e' 2. Cf(a',d) h (a',d,e')d3. d' arg min( , ') ( ', ', , ')Bf(c,a') f c eh a d c e  c4. c' arg min f(a',b) f(b,c')f(b,d') f(b,e')  b5. b' arg min)e',d',c',b',(a' Returnf(a,d)16exp(w*=4)”induced width” (max clique size)ComplexityElimination operatorOPTbucket B: f(c,a) f(c,e) f(a,b) f(b,c) f(b,d) f(b,e)bucket C: bucket D:bucket E: bucket A:e=0(a)hEe)c,d,(a,hBe)d,(a,hCbminBCDEAf(a,d) e)(a,hDAlgorithm elim-opt (Dechter, 1996)Non-serial Dynamic Programming (Bertele and Briochi, 1973)),(),(),(),(),(),(),(min,,,,ecFebFdbFcbFdaFcaFbaFOPTbcdeaComplexity of bucket elimination))((exp (*dwrOddw ordering alonggraph primal theof width induced the)(*The effect of the ordering:4)(1*dw2)(2*dwconstraint graphADECBBCDEAEDCBAFinding smallest induced-width is hardr = number of functionsBucket-elimination is time and space18exp(w*=4)”induced width” (max clique size)ComplexityElimination operatorOPTbucket B: f(c,a) f(c,e) f(a,b) f(b,c) f(b,d) f(b,e)bucket C: bucket D:bucket E: bucket A:e=0(a)hEe)c,d,(a,hBe)d,(a,hCbminBCDEAf(a,d) e)(a,hDAlgorithm elim-opt (Dechter, 1996)Non-serial Dynamic Programming (Bertele and Briochi, 1973)),(),(),(),(),(),(),(min,,,,ecFebFdbFcbFdaFcaFbaFOPTbcdeaDirectional i-consistencyDCBRAECDBDCBEDCBEDCBE:AB A:BBC :CAD C,D :DBE C,E D,E :EAdaptive d-arcd-pathDBDCRR ,CBRDRCRDRMini-bucket approximation:MPE taskSplit a bucket into mini-buckets =>bound complexityXXgh )()()O(e :decrease complexity lExponentian rnreOeOMini-Bucket EliminationAB CDEP(A)P(B|A)P(C|A)P(E|B,C)P(D|A,B)Bucket BBucket CBucket DBucket EBucket AP(B|A) P(D|A,B)P(E|B,C)P(C|A)E = 0P(A)maxB∏hB(A,D)MPE* is an upper bound on MPE --UGenerating a solution yields a lower bound--LmaxB∏hD(A)hC(A,E)hB(C,E)hE(A)MBE-MPE(i) Algorithm Approx-MPE (Dechter&Rish 1997) Input: i – max number of variables allowed in a mini-bucket Output: [lower bound (cost of a sub-optimal solution), upper bound]Example: approx-mpe(3) versus elim-mpe2* w4* wProperties of MBE(i) Complexity: O(r exp(i)) time and O(exp(i)) space. Yields an upper-bound and a lower-bound. Accuracy: determined by upper/lower (U/L) bound. As iincreases, both accuracy and complexity increase. Possible use of mini-bucket approximations: As anytime algorithms As heuristics