ࡱ>  (0 g/ 00DTimes New Roman(0(z[ 0 DVerdanaw Roman(0(z[ 0 " DSymbolw Roman(0(z[ 0 0DArialw Roman(0(z[ 0 @ .  @n?" dd@  @@`` n<[ <'&&4**+q!.K  B_  jUi ; B * &%+'  3\]5^_`a?E 4!.!.!))f`qn 0AA @ +̵ ʚ;Zi8ʚ;g4>d>d@z[ 0ppp@ <4ddddl 0~<4!d!dl 0~<4BdBdl 0~80___PPT10 ?  %sSymbolic SAT SolvingCNF  = c1 c2 & cm Convert clause ci to OBDD bi SAT() $x1x2& xn  $x1x2& xn (b1 b2 & bm) Problem: intermediate OBDDs can get too big and computation may be inefficient or impossible^MZ(Z^ZBJBBJBBBJBJ BJBBB `$ BEarly Quantification$x [f(x, Y) g(Z)] = [$x f(x, Y)] g(Z) SAT() $x1x2& xn (b1 b2 & bm) Push some quantifiers inside Variables disappear early and OBDDs tend to get smaller with fewer variables Finding good quantification schedule is hard in generalP/BR/ ?cDavis-Putnam (DP)DP eliminates variables one at a time by resolving clauses that mention the variable Use same procedure to eliminate variables from OBDDs V6Variable Elimination Elimination OrdersfVariable elimination is exponential in width of elimination order Width max number of variables of any intermediate OBDD Existing heuristics: min-fill, hypergraph partitioning:'38 Finding Good Elimination OrdersCombine two independent tools: DTREE and MINCE, both based on hypergraph partitioning DTREE attempts to minimize width MINCE attempts to minimize cutwidth (known that cutwidth e" kwidth) In practice, DTREE and MINCE produce elimination orders of incomparable quality For each CNF, run both tools and use elimination order of smaller widthZPr    FF>> LSymbolic SAT SolverRun DTREE and MINCE on CNF Select elimination order of smaller width Convert clauses to OBDDs and run variable elimination CNF is satisfiable iff result is 1 Use CUDD package for OBDD operationsP,Z23Other Solvers for ComparisonZRes: uses zero-suppressed BDDs in DP Cassatt: uses zero-suppressed BDDs in breadth-first search zChaff: winner of 2004 SAT Competition in industrial category March_eq: winner of 2004 SAT Competition in handmade categoryZl96 ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> l(    6t P  T Click to edit Master title style! !  0    RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0 ``  @*   0@ `   B*   0 `   B* H  0޽h ? ̙33 Default Design P,8(  , , 0Я s$   >*  , 0  /$  @*  , 6̷ s   >*  , 6  /  @* H , 0jB ? 3380___PPT10.9+B#style.visibility<*8M%(D' =-o6Bwipe(up)*<3<*8MD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Mu%(D' =-o6Bwipe(up)*<3<*MuD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*v%(D' =-o6Bwipe(up)*<3<*v+!  `h(  ~  s *P     s *`x<$D  0  H  0޽h ? ___ff3ff___PPT10. b+D' = @B DX' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =-o6Bwipe(up)*<3<**D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+O%(D' =-o6Bwipe(up)*<3<*+OD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Pm%(D' =-o6Bwipe(up)*<3<*PmD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*n%(D' =-o6Bwipe(up)*<3<*nD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bwipe(up)*<3<*+  <(  ~  s *P   ~  s *  H  0޽h ? ___ff3ff___PPT10i.+D=' = @B +p  ##44O#(  ~  s *P     0  p V2$x1x2& xn (b1 b2 & bm)0 2             ,)  0X`P Elimination order: x1 x2 ... xnl 0 2          2  s *"`  ,$@  02  0  @ ,$@  02  0`  ,$@  02  0 @@ ,$@  02   0p @ ,$@  02   0` @ ,$@  02   0P @ ,$@  02   0  ,$@   02   0 0 ,$@   02  0 `,$@   02  0P  ,$@   02  0@@,$@   02  0p @ ,$@  02  0`  ,$@  02  0p   ,$@  02  0` 0 ,$@  02  0  ,$@  02  0  ,$@  02  0` p ,$@  02  0  ,$@  02  0 PP ,$@  02  0 0 ,$@  02  0 ` ,$@  02  0 ` ,$D  02  s *f"`P  ,$@   02  s *f"`p @ ,$@!  02  s *f"``  ,$@"  02   s *f"`p   ,$@#  02 ! s *f"`` 0 ,$D$  02 " s *f"`@  ,$@*  02 # s *f"` @` ,$@+  02 $ s *f"` P ,$@,  02 % s *f"`  ` ,$@-  02 & s *f"` 0P ,$D.  0 ' 0@ ,$  0 Vx180 2( (( ( 0p P ,$/  0 @"0 26 ) 0@   ,$0  0 `$x1>0 2(((2 * 0 p ,$D3  0 + 0 p  ,$1  0 ?b = 0 2(B , s *D@  ,$@2  0 - 0 6@ ,$4  0 Vx280 2( (( . 0@P  ,$D  0 <& 0 2(2 / s *f"`0p,$@Q  02 0 s *f"` 0 ,$@R  0 1 0 ,$S  0 $xn>0 2((( 2 0t$ p ,$T  0 ?b = 0 2( 3 0! ,$U  0 @"0 26 4 0,60p ,$P  0 pxn80 2( ((H  0޽h ? ___ff3ffYQ___PPT101.+%DD-' = @B D' = @BA?%,( < +O%,( < +D6' =%(D86' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(down)*<3<* D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(down)*<3<* D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(down)*<3<* D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(down)*<3<* D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(down)*<3<* D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*'%(D' =-s6Bwipe(down)*<3<*'D' =%(D' =%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(down)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(down)*<3<* D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =-s6Bwipe(down)*<3<*!Dd' =%(D ' =%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*!D' =1:Bhidden*o3>+B#style.visibility<*!%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*"%(D' =-s6Bwipe(down)*<3<*"D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*#%(D' =-s6Bwipe(down)*<3<*#D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =-s6Bwipe(down)*<3<*$D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%%(D' =-s6Bwipe(down)*<3<*%D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*&%(D' =-s6Bwipe(down)*<3<*&D' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =-s6Bwipe(down)*<3<*(D' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)%(D' =-s6Bwipe(down)*<3<*)D' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*+%(D' =-s6Bwipe(down)*<3<*+D&' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =-s6Bwipe(down)*<3<*,D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =-s6Bwipe(down)*<3<**D@' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =-s6Bwipe(down)*<3<*-D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*"D' =1:Bhidden*o3>+B#style.visibility<*"%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*#D' =1:Bhidden*o3>+B#style.visibility<*#%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*$D' =1:Bhidden*o3>+B#style.visibility<*$%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*%D' =1:Bhidden*o3>+B#style.visibility<*%%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*&D' =1:Bhidden*o3>+B#style.visibility<*&%(DB' =A@BBBB0B%(D' =-s6Bwipe(down)*<3<*(D' =1:Bhidden*o3>+B#style.visibility<*(%(DB' =A@BBBB0B%(D' =-s6Bwipe(down)*<3<*)D' =1:Bhidden*o3>+B#style.visibility<*)%(DB' =A@BBBB0B%(D' =-s6Bwipe(down)*<3<*+D' =1:Bhidden*o3>+B#style.visibility<*+%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*,D' =1:Bhidden*o3>+B#style.visibility<*,%(D' =%(D ' =%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<**D' =1:Bhidden*o3>+B#style.visibility<**%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*.%(D' =-s6Bwipe(down)*<3<*.D ' =%(D ' =%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D' =%(D ' =%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =-s6Bwipe(down)*<3<*4D' =%(D,' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*/%(D' =-s6Bwipe(down)*<3<*/D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-s6Bwipe(down)*<3<*0DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =-s6Bwipe(down)*<3<*1DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*2%(D' =-s6Bwipe(down)*<3<*2DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*3%(D' =-s6Bwipe(down)*<3<*3D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D5' =4@BBBB%(D' =-s6Bwipe(down)*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(++0+' ++0+( ++0+( ++0+) ++0+) ++0++ ++0++ ++0+- ++0+. ++0+1 ++0+2 ++0+3 ++0+4 +  <(  ~  s *`yP   ~  s *4z  H  0޽h ? ___ff3ff___PPT10i.m+D=' = @B +  <(  ~  s *8P   ~  s *   H  0޽h ? ___ff3ff___PPT10i.+D=' = @B +  <(  ~  s *P   ~  s *,  H  0޽h ? ___ff3ff___PPT10i. gH+D=' = @B +  <(  ~  s *P   ~  s *  H  0޽h ? ___ff3ff___PPT10i._+D=' = @B +r8 g`)-9KNCEKHJ? MOh+'0d! hp  PowerPoint PresentationoweoweAdnan Darwichee645Microsoft PowerPointon@_@@t|R  GD g  I  x-- @ !x--'@Times New Roman-. %2 LkSymbolic SAT Solving   ."System-@Times New Roman-.  2 +.-@Times New Roman-.  2 >CNF .-@Times New Roman-. h@Times New Roman--. 2 h .--.@Times New Roman-.  2 y= c  .@Times New Roman-.  2 1.@Symbol-.  2  .@Times New Roman-.  2 c .@Times New Roman-.  2 2.@Symbol-.  2  .@"Verdana-.  2 .@Symbol-.  2  .@Times New Roman-.  2 c .@Times New Roman-.  2 m .@"Verdana-.  2 + .@Times New Roman-. 2 >Convert clause   .@Times New Roman-.  2 c .@Times New Roman-.  2 i.@Times New Roman-. 2 to OBDD b    .@Times New Roman-.  2 !i.@"Verdana-.  2 + .@Times New Roman-.  2 >SAT( .@Times New Roman-. i@Times New Roman--. 2 i .--.@Times New Roman-.  2 u) .@Symbol-.  2 .@Symbol-.  2 $ .@Times New Roman-.  2 x .@Times New Roman-.  2 1.@Times New Roman-.  2 x .@Times New Roman-.  2 2.@"Verdana-.  2 .@Times New Roman-.  2 x .@Times New Roman-.  2 n.@Times New Roman-. @Times New Roman--. 2  .--.@Symbol-.  2 .@Symbol-.  2 $ .@Times New Roman-.  2 x .@Times New Roman-.  2 1.@Times New Roman-.  2 x .@Times New Roman-.  2 2.@"Verdana-.  2 .@Times New Roman-.  2 x .@Times New Roman-.  2 n.@Times New Roman-.  2 (b .@Times New Roman-.  2 1 .@Symbol-.  2  .@Times New Roman-.  2 !b .@Times New Roman-.  2 +2.@"Verdana-.  2 6.@Symbol-.  2 K .@Times New Roman-.  2 [b .@Times New Roman-.  2 fm .@Times New Roman-.  2 p).@"Verdana-.  2 4+ .@Times New Roman-. (2 4>Problem: intermediate      .@Times New Roman-. 2 4OBDDsx  .@Times New Roman-. %2 43can get too big and       .@Times New Roman-. I2 I>,computation may be inefficient or impossible            .՜.+,0    1On-screen Shown-sMF  Times New RomanVerdanaSymbolArialDefault DesignSymbolic SAT SolvingEarly QuantificationDavis-Putnam (DP)Variable EliminationElimination Orders Finding Good Elimination OrdersSymbolic SAT SolverOther Solvers for Comparison  Fonts UsedDesign Template Slide Titles&_MAdnan DarwicheAdnan Darwiche  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)Current UserSummaryInformation(!PowerPoint Document(MDocumentSummaryInformation8