最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

大きなグラフ分割問題

2010年05月07日 00時07分50秒 | Weblog
グラフ分割問題に対する SDP 緩和問題だが、大きめの問題(1000点以上)を作って解いてみた。結論から言うと SDP 緩和問題は意外と速く、しかも安定して解くことができる。問題生成よりも解く方が速かった。点数が大きい方が実行可能内点解を見付けやすいのであろうか。

○計算サーバ
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
gcc : 4.4.3
OS : Fedora 12 for x86_64
環境変数 : OMP_NUM_THREADS = 8
○ソルバー SDPA 7.3.2

○問題1:点数 1000
pFEAS : 10.558s
○問題2:点数 2000
pdOPT : 1m9.772s
○問題3:点数 3000
pdOPT : 3m7.355s
○問題4:点数 4000
pdOPT : 7m26.537s
○問題5:点数 5000
pdOPT : 13m51.122s
コメント