こちらのホームページから dre30 という QAP のデータを入手することができる。こちらの論文によると、最適解（最適目的関数値）は 508 になっている。ちなみに近似解法では、ほとんど即時に最適解を求めることができるようだ。私自身も以前（１５年以上前）に QAP に対する近似解法を作成したことがある。
この dre30 に対する DNN 緩和問題を作成して SDPARA で解いてみた。
dre30
-------------------------------------------------------------------------------------------------------------------
88770 = mDIM
25 = nBlock
-88192 91 121 121 151 151 91 121 121 151 151 151 91 121 121 151 91 121 121 151 181 181 181 211 181 = bLOCKsTRUCT
-------------------------------------------------------------------------------------------------------------------
SDPA start at [Fri Feb 4 23:59:17 2011]
param is /home/fujisawa/sdpa-src/sdpara.7.3.2.src-RC3.64bit.bak3/param.sdpa
data is /home/fujisawa/data/QAP/SparseSDPrelaxZKRW/dre30_r2.dat-s : sparse
out is /home/fujisawa/sdpa-src/sdpara.7.3.2.src-RC3.64bit.bak3/out.dre30_r2.1.09
NumNodes is set as 16
NumThreads is set as 12
Schur computation : DENSE
mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 +0.00e+00 -2.40e+03 8.3e-01 1.0e+00 2.00e-01
中略
41 7.1e-10 4.9e-10 1.1e-13 +2.18e-01 +2.18e-01 5.2e-01 4.1e-01 1.00e-01
42 4.3e-10 4.9e-10 8.2e-14 +2.18e-01 +2.18e-01 5.2e-01 4.1e-01 1.00e-01
phase.value = pdOPT
Iteration = 42
mu = +4.2534442534053135e-10
relative gap = +6.9388939039072284e-16
gap = +6.9388939039072284e-16
digits = +1.4496794030251626e+01
objValPrimal = +2.1781324107801001e-01
objValDual = +2.1781324107800931e-01
p.feas.error = +4.9685456727461340e-08
d.feas.error = +8.2316788420224567e-11
total time = 13043.572274
この最適解から、元の QAP の目的関数値の下界を計算してみる。
2332 x 0.217813 = 507.9403824
最適解は 508 なので、極めて近い値を DNN 緩和問題を解くことによって得ることができる。もちろん全ての問題でこのような非常に精度の良い下界が得られるわけではないが、この問題では驚異的に精度の高い解を得ることができる。
○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64
この dre30 に対する DNN 緩和問題を作成して SDPARA で解いてみた。
dre30
-------------------------------------------------------------------------------------------------------------------
88770 = mDIM
25 = nBlock
-88192 91 121 121 151 151 91 121 121 151 151 151 91 121 121 151 91 121 121 151 181 181 181 211 181 = bLOCKsTRUCT
-------------------------------------------------------------------------------------------------------------------
SDPA start at [Fri Feb 4 23:59:17 2011]
param is /home/fujisawa/sdpa-src/sdpara.7.3.2.src-RC3.64bit.bak3/param.sdpa
data is /home/fujisawa/data/QAP/SparseSDPrelaxZKRW/dre30_r2.dat-s : sparse
out is /home/fujisawa/sdpa-src/sdpara.7.3.2.src-RC3.64bit.bak3/out.dre30_r2.1.09
NumNodes is set as 16
NumThreads is set as 12
Schur computation : DENSE
mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 +0.00e+00 -2.40e+03 8.3e-01 1.0e+00 2.00e-01
中略
41 7.1e-10 4.9e-10 1.1e-13 +2.18e-01 +2.18e-01 5.2e-01 4.1e-01 1.00e-01
42 4.3e-10 4.9e-10 8.2e-14 +2.18e-01 +2.18e-01 5.2e-01 4.1e-01 1.00e-01
phase.value = pdOPT
Iteration = 42
mu = +4.2534442534053135e-10
relative gap = +6.9388939039072284e-16
gap = +6.9388939039072284e-16
digits = +1.4496794030251626e+01
objValPrimal = +2.1781324107801001e-01
objValDual = +2.1781324107800931e-01
p.feas.error = +4.9685456727461340e-08
d.feas.error = +8.2316788420224567e-11
total time = 13043.572274
この最適解から、元の QAP の目的関数値の下界を計算してみる。
2332 x 0.217813 = 507.9403824
最適解は 508 なので、極めて近い値を DNN 緩和問題を解くことによって得ることができる。もちろん全ての問題でこのような非常に精度の良い下界が得られるわけではないが、この問題では驚異的に精度の高い解を得ることができる。
○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64
アクセス
トータル
