QAP と DNN 定式化

以下のように DNN (SDP制約 + 非負制約)新定式化の効果は非常に良い（精度面と速度面)。問題は QAP の nug20 になる。新定式化の方では目的関数をスケーリングしているので、3.44400000e+03 x 7.2745400147598e-01 = 2505.4 ということで目的関数もほぼ合っている(Dual の定式化なので符号は逆になる)。新定式化の方は以下のパラメータを使用している。

100 unsigned int maxIteration;
1.0E-7 double 0.0 <epsilonStar; 1.0E5 double upperBound;
0.01 double 0.0 <= betaStar < 1.0;
0.03 double 0.0 <= betaBar < 1.0, betaStar <= betaBar;
0.7 double 0.0 <gammaStar < 1.0;

○ DNN の旧定式化 (Primal での定式化)
phase.value = pFEAS
Iteration = 34
mu = +4.3767103611534584e-05
relative gap = +9.3919754547110038e-04
gap = +3.5276285510896876e+00
digits = +3.0272430510940649e+00
objValPrimal = -2.5057490005036816e+03
objValDual = -2.5081034994843531e+03
p.feas.error = +1.2732925824820995e-11
d.feas.error = +8.5402253944266704e-06
total time = 10199.954908

○ DNN での新定式化 (Dual (LMI) での定式化)
phase.value = pdOPT
Iteration = 49
mu = +2.6193727846385673e-09
relative gap = +1.5543122344752192e-15
gap = +1.5543122344752192e-15
digits = +1.4670267271639116e+01
objValPrimal = +7.2745400147598249e-01
objValDual = +7.2745400147598094e-01
p.feas.error = +9.3335382773439526e-08
d.feas.error = +1.2992888459573138e-08
total time = 9672.617371

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.3 for x86_64