tai31a に対する DNN 緩和問題

こちらのサイトに QAP の問題が多数収録されている。

tai31a に関して、現在の上界値は 1945072 となっている。以下は tai31a に対する DNN 緩和問題を SDPARA 7.6.0-G を用いて解いた結果である。使用した計算機は九州大学スパコン CX400 で、cx-g-middle キュー(128CPU + 64GPU)を用いた。

64GPU(NVIDIA Tesla K20m) による Cholesky 分解の性能は約 45.5TFlops となっている。
[gpdpotrf] ### END n=433411, nb=1024, 8x8 procs, ver 30: 596.469334sec --> 45497.801690GFlops ###

DNN 緩和問題の最適解による下界値は 1813271 となるので、上界(1945072)と下界(1813271)の gap は約 7.27% となる。
40 2.1e-11 5.8e-10 1.1e-12 +7.73e-01 +7.73e-01 2.1e-01 2.2e-01 1.00e-01

phase.value = pdOPT
Iteration = 40
mu = +2.0868344993717805e-11
relative gap = +9.2148511043887993e-15
gap = +9.2148511043887993e-15
digits = +1.3923840065993467e+01
objValPrimal = +7.7326506207176393e-01
objValDual = +7.7326506207175472e-01
p.feas.error = +5.8794496378042983e-08
d.feas.error = +1.0904347169332069e-10
total time = 47681.815763
main loop time = 47664.554858
total time = 47681.815763
file check time = 0.000000
file change time = 0.016259
file read time = 17.244646
SDPA end at [Mon Jul 21 04:43:46 2014]
ALL TIME = 48079.562744