DNN緩和問題と QAP(二次割当問題) その２

QAPLIB の中に Esc という名前の問題があるが、問題サイズが 32 以上の問題はまだ最適解が求められていない。全ての条件を入れて DNN 緩和問題を作ると非常に問題が大きくなるので、Esc32a の問題に対して疎性を考慮して少し小さな DNN 緩和問題を作る。しかしそれでも以下のように巨大な SDP になる。

102208 = mDIM
14 = nBLOCK
-101740 193 129 129 161 65 193 225 225 161 193 193 225 257 = bLOCKsTRUCT



この SDP を解いて求めた最適目的関数値は 99.568 なので、現在求められている最も良い下界(103)よりも少しだけ小さい。よってフル DNN 緩和問題を作れば下界を更新できる可能性はありそうだ。しかし、以下の計算サーバではもはやメモリ量が限界なので、これから先はより高度な計算サーバが必要になる。

ちなみに計算時間は 143548.8秒で、その内 Cholesky 分解は 136246.8秒と全体の 95% を占めるので、やはりこの種の問題では Cholesky 分解の高速化は大変効果がある。

○サーバ (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64