組合最適化問題近似解法

1、組合最適化問題近似解法計數(shù)工學(xué)専攻1発表目次近似解法？MAX SAT問題近似解法/近似解法0632近似解法/近似解法MAX CUT問題0878近似解法半正定値計畫MAX SAT問題0878近似解法2近似解法？近似解法：近似精度存在解法得解最適解距離見積存在発見的解法：近似精度不明近似比率：（最大化問題場合）（得解目的関數(shù)値）（最適値）近似解法：近似比率以上解必求解法3MAX SAT近似解法4SAT問題(問題例)SAT問題（Satisfiability problem：充足可能性問題)変數(shù)：U=a1，a2，a3 ：=C1 ，C，C， C， C， C C1 = a2 ，C = a1， a2，a3

2、，C = a1，a2，a3 ，C = a1，a2， a3 ，C = a1，a2 ， C = a1， a3 （aa否定意味）中全真 U 真?zhèn)胃町?dāng)？真中少真5SAT問題(問題例真?zhèn)胃町?dāng))U= a1， a2， a3 T T FC1 = a2 TC = a1， a2，a3 TC = a1，a2，a3 TC = a1，a2， a3 FC = a1，a2 T C = a1， a3 T 中全真,U 真?zhèn)胃町?dāng)存在6SAT問題（定義）SAT問題（Satisfiability problem：充足可能性問題)入力:変數(shù)U，集合質(zhì)問：? U 真?zhèn)胃町?dāng)， 中全真：入力変數(shù)，否定：集合真中少真NP完全事示最初問題Coo

3、k717MAX SAT(問題例) U= a1， a2， a3 例題提供:宮本裕一郎 T T F 重C1 = a2 T 4C = a1， a2，a3 T 1C = a1，a2，a3 T 6C = a1，a2， a3 FC = a1，a2 T 3C = a1， a3 T 9真重総和最大化 総和=重輪8MAX SAT問題（定義）MAX SAT問題入力:変數(shù)U，集合非負(fù)整數(shù)重:Z問題：中真重和最大，U真?zhèn)胃町?dāng)求各中個以下 MAX SATMAX SAT問題NP困難 Garey，Johnson and Stockmeyer 719MAX SAT1/2 近似解法D.S.Johnson 74非常単純化算法10

4、/近似解法(數(shù)値例)/近似解法：各変數(shù)/確率真 1/2 1/2 1/2 （重総和=27）C1 = a2 (1/2) =2 C = a1， a2，a3 (7/8) =7/8C = a1，a2，a3 (7/8) =21/4C = a1，a2， a3 (7/8) =7/2C = a1，a2 (3/4) =9/4C = a1， a3 (3/4) =27/4真重総和期待値=2211/近似解法/近似解法：各変數(shù)/確率真解析：個含真確率 1-(1/2)k真重期待値，PrC真w（C ）C ( 1-(1/2)k )w （C ）C，|C |= (1/2)w（C ）C(重総和)(最適値)， (1/2)w（C ）|C

5、 (1/2)*最適値121-(1/2)k近似解法個以上含真確率 1-(1/2)k以上任意個以上含，1/2近似解法， 1-(1/2)k近似解法13MAX SAT0.632 近似解法Goemansand Williamson 94線形緩和問題用問題例確率変化算法14整數(shù)計畫定式化変數(shù)集合 =a1,a2,.,an，集合= C1,C2,.,C添字集合1,2,.,n,n+1,.,2nin，iai ，nnin，ni ai 対応変數(shù)x1,x2,.,xn , xn+1,xn+2,.,x2n,z 1,z 2,.,z xi =1ai 真， z =1C 真MS:max.w j z j s.t. xi+xn+i=1

6、(), xi0,1 ()， z j xi (),z j 0,1 () i c15線形緩和問題化算法：（x*，*）線形緩和問題最適解各変數(shù) ai 確率 xi*真max.w j z j s.t. xi+xn+i=1 (), 0 xi1 ()， z j xi (), 0z j 1 () i cMS:16化算法(數(shù)値例) a2 a1， a2，a3 a1，a2，a3 a1，a2， a3 a1，a2 a1， a3 max.4z1+1z2+6z3+4z4+3z5+9z6 s.t. x2 z1x4 + x2 + x6 z2 x4 + x5 + x6 z3 x4 + x5 + x3 z4 x1 + x5 z5

7、x1 + x3 z6 xi + xn+i = 1, 0 xi , xn+i 1( i ) 化算法：線形緩和問題最適解 x* =(3/4,3/4,1/2,1/,1/,1/2) 最適値26最適値上界 各変數(shù) ai 確率 xi*真 期待値21.4 0.632*最適値 0.632最適値9*(1(1/4)(1/2)17化算法（定義)（x*，*）線形緩和問題最適解各変數(shù) ai 確率 xi*真真重総和期待値=i c w j （1- x*i）i =i +n (i =1,.,n)i n (i = n+1,.,2n)|C j |=k，1- x*ii c(1/)補題：z j z j * 18補題証明証明：相加相乗平

8、均，1- x*i1 （ （ 1 x*i ）/） 1（ /） z*j関數(shù)1（ z*j /）凹性 1（1/） |C j |=k，1- x*ii c(1/)補題：i ci cz* jz j * Z*j 19（1/)近似解法真重和期待値？k:個含集合MAX kSAT，i cw j （1- x*i）kckw j z j kck（1/)(線形緩和最適値)（1/) )(MAX kSAT最適値)（1/) )200.632近似解法MAX kSAT，期待値 （1/) )1 3/4=0.75 19/27=0.703 175/256=0.68411/e0.632(MAX kSAT最適値)（1/) )21MAX SAT

9、3/4 近似解法Goemansand Williamson 941/2近似解法 0.632近似解法組合221/2近似解法0.632近似解法 k個含，1/2近似解法： 真確率（1/2) ).632近似解法：真確率（/) ) （1/) ) （1/2) )1 1/2 3/4=0.75 3/4=0.75 19/27=0.703 7/8=0.875 175/256=0.684 15/16=0.973511/e0.632 1234/3近似解法4/3近似解法1/2近似解法 0.632 近似解法一方確率(1/2)選実行任意正整數(shù)対，（1/) )（1/2) )/23/4成立期待値 (MAX SAT線形緩和問題最

10、適値) （1/) )（1/2) )/2 (MAX SAT最適値) (3/4) 244/3近似解法(実際）4/3近似解法1/2近似解法 0.632 近似解法一方確率(1/2)選実行下方同良1/2近似解法 0.632 近似解法両方実行良方選z1/2 :1/2近似解法期待値zLP :0.632 近似解法期待値 ( z1/2 +zLP)/2 maxz1/2,zLP25脫化(derandomization)26脫化 a2 a1， a2，a3 a1，a2，a3 a1，a2， a3 a1，a2 a1， a3 a1 a2 a3真確率( x,1/2,1/2) 期待値 4(1-1/2)+ 1(1-(1/2)2(1

11、-x) +6 (1-(1/2)2 (1-x) +4 (1-(1/2)2(1-x)+3 (1-(1/2) x)+9 (1-(1/2)x) =19+(13/4) x x=1、22.25 a1 a2 a3真確率(1,y,1/2) 期待値 4y+ 1(1-(1/2)y) +6 (1-(1/2) (1-y) +4 (1-(1/2) (1- y)+3 +9 =19+3.5y y=1、22.5 a1 a2 a3真確率(1,1,z) 期待値 22+1(1-z) z=1、23 -重総和=1/2近似解法a1,a2,a3真確率(1/2,1/2,1/2)期待値=20.6 = 4(1-1/2)+1(1-(1/2)3)+

12、6 (1-(1/2)3) +4 (1-(1/2)3)+3 (1-(1/2)2)+9 (1-(1/2)2) 27MAX CUT近似解法28MAX CUT問題(問題例)重=重=29定義G=（V,E)頂點集合UV(U)：w（U）：重14UV-U30MAX CUT問題(定義)MAX CUT問題入力:無向G=(V,E)，非負(fù)枝重:EZ問題：G中， 重最大求頂點部分集合UV 対：(U)=eE |e U中頂點U 無頂點結(jié)(U)重：(U)= (U)中枝重総和 MAX CUT問題：max (U ) | UV NP困難 Karp 7231MAX CUT1/2 近似解法非常単純化算法32/近似解法MAX CUT問題

13、：max (U) | U V /近似解法：各頂點/確率U入解析：各枝，両端內(nèi)一方U入確率1/2重期待値 ，Pre (U)入（e ） e E (1/2)（e ） e E(枝重総和)(最大重)， (1/2)*最適値33MAX CUT0.878 近似解法Goemans and Williamson 95MAX CUT非凸2次連続最適化問題変形半正定値計畫緩和化34球面配置問題入力:無向G=(V,E)，非負(fù)枝重:EZ， S：原點中心，半徑1/ 球表面(大円半円弧長=)v,v S , (vv)= v v結(jié)円弧短方長球面配置問題G頂點S上配置，枝重距離積総和最大化max (i,j) (v(i )v( j)

14、 | v(i ) S ( i V )i,j 35球面配置問題(定理)max (i,j) (v(i )v( j) | v(i )S(iV)定理(U*)：最大 v (i U* ) vS， v*(i )= - v (iV-U* ) 解v*(i )球面配置問題最適解i,j v-v36定理証明(上)配置v* 目的関數(shù)値w (i,j) (v*(i )v*( j)= w (U*) (最大値)(任意配置v目的関數(shù)値) w (U*) 示H：原點境界含閉半空間V(H)：v(i)H含點集合w（H)：V(H)対応重原點境界含閉半空間全等確率発生発生閉半空間H対， w（H)期待値？i,j H37定理証明(中)原點境界含

15、閉半空間全等確率発生発生閉半空間H対， w（H)期待値？頂點i,j間弧長=(v(i )v( j)，発生閉半空間頂點i,j分確率，(v(i )v( j)/(大円半円弧長)=(v(i )v( j)(v(i )v( j)i j半円弧長=38定理証明(下)原點境界含閉半空間全等確率発生発生閉半空間H対， w（H)期待値？Ew（H)=w (i,j) PrH頂點i,j分=w (i,j) (v(i )v( j)w（H)発生重期待値，Ew（H) w (U*) (最大重)以上，任意配置v(i )，w (i,j) (v(i )v( j)= Ew（H) w (U*) i,j i,j i,j 39球面配置生成max

16、(i,j) (v(i )v( j) | v(i )S(iV)定理(U*)：最大 v (i U* ) vS， v*(i )= - v (i V-U* ) 解 v*(i )球面配置問題最適解任意球面配置v対，原點境界含閉半空間全等確率発生事，v目的関數(shù)値 (i,j) (v(i )v( j)以上生成事出來i,j Hi,j 40頂點配置問題緩和MAX CUT問題頂點配置問題本質(zhì)的等価頂點配置問題緩和v,v S , (vv)= v v 間直線距離/2倍2乗（(vv)= v vS直徑 (vv)=）距離置換(vv)=（/2)2|v - v|2 =(1/2)(12 vv）1/1/2dS41緩和問題球面配置問題

17、：maxw (i,j) (v(i )v( j) | v(i )S(iV)緩和問題：maxw (i,j) (v(i )v( j) | v(i )S(iV)i,j i,j 42緩和問題？配置 v : U ：頂點部分集合 v (i U ) vS， v(i )= - v (i V-U). v 配置i,j,(v(i )v( j)01 i,j, f(v(i )v( j)01 w (i,j) (v(i )v( j) =w (i,j) (v(i )v( j)最大配置目的関數(shù)値 =（球面配置問題最適値）(緩和問題最適値)i,j i,j 43距離比率定理v,v S , (vv) 0.878 (vv)(vv)=/(

18、vv)=（1-cos)/2(vv)(vv) (2/)(/（1-cos)）1/1/2dSmin (2/)(/（1-cos)）=0.878044最適値比率定理v(i ):緩和問題最適解. (最大重)(配置v(i )目的関數(shù)値)0.878（球面配置問題最適値）=0.878(最大重)v(i ):緩和問題最適解. v*(i ):球面配置問題最適解.(最大重)w (i,j) (v(i )v( j)0.878w (i,j) (v(i )v( j)0.878w (i,j) (v*(i )v*( j)=0.878w (i,j) (v*(i )v*( j) )i, j i,j i,j i, j 450.878近似

19、解法 任意球面配置v対，原點境界含閉半空間 全等確率発生事, v目的関數(shù)値 w (i,j) (v(i )v( j) 以上生成出來定理 (緩和問題最適解目的関數(shù)値)0.878 (最大重) 0.878近似解法 (1)緩和問題最適解配置v(i )求 (2)球面配置v(i )目的関數(shù)値以上生成i,j 46半正定値計畫Goemans and Williamson 95球面配置問題緩和問題，半正定値計畫問題変形47球面配置問題緩和問題球面配置問題=最大問題（MC）:maxw (i,j) (v(i )v( j) | v(i )S(iV)緩和問題（MC）：maxw (i,j) (v(i )v( j) | v(

20、i )S(iV)i,j i,j 48半正定値行列出現(xiàn)MCmaxw(i,j) (v(i )v( j) | v(i )S (iV)=maxw(i,j) (1-2v(i )v( j) ) | v(i)S(iV)行列Y=ijij=(v(i)（v(j)）定義.X=(v(1),., v(n)， Y= 2XtX ,(1) Y半正定値対稱行列,(2) ii1 (iV)成立i,j i,j 49半正定値計畫変形MCmaxw(i,j) (1-2v(i )v( j) ) | v(i)S(iV)行列Y=ijij=(v(i)（v(j)）定義 変形緩和 max.w(i,j) (1-ij ) sub.to Y =ij半正定値対稱行列, ii1 (iV), Y= 2XtX , X=(v(1),., v(n).i,j i,j 50半正定値計畫等価性 MCmaxw(i,j) (1-2v(i )v( j) ) | v(i)S(iV) |（実問題等） max.w(i,j) (1-ij ) sub.to Y =ij半正定値対稱行列, ii1 (iV)（1/2）Y Cholesky分解（1/2）Y= XtX. X=(v(1),., v(n)， v(i) MC許容解. 緩和問題最適解一致許容解作i,j i,j 51半正定値計畫一般形max.w(i,j) (1-ij ) sub.to Y =ij半正定値対稱行列,