Integer Programming boolean variables:X1,x2,...,xn 1 if xi=true )if xi=false truth assignment→ye{0,l}” a clause C=(1v2v...vek) ljefxi,xib C+:set of i that xi is in C C:set of i that xi is in C C is satisfied <〉 +>(1-)≥1 i∈C+ i∈C-
Integer Programming a clause C = (1 2 ···k ) j {xi ,¬xi} C + : C : yi = 1 if xi = true 0 if xi = false set of i that xi is in C set of i that ¬xi is in C truth assignment y {0, 1}n boolean variables: x1,x2,...,xn C is satisfied iC+ yi + iC (1 yi) 1
Integer Programming boolean variables:x1,x2,...,xn clauses: C1,C2,.,Cm m maximize ∑ j=1 subject to ∑+∑(1-)≥，1≤j≤m icC时 iECj yE{0,1 V1≤i≤n e{0,1} V1≤j≤m integral solution
maximize m j=1 zj subject to iC+ j yi + iC j (1 yi) ⇤ zj , ⇧1 ⇥ j ⇥ m yi ⌅ {0, 1}, ⇧1 ⇥ i ⇥ n zj ⌅ {0, 1}, ⇧1 ⇥ j ⇥ m Integer Programming clauses: C1, C2,...,Cm boolean variables: x1,x2,...,xn integral solution