イノベーション・ジャパン 2010 の展示会開催中に、今年からショートプレゼンテーションが導入された。１分間で研究内容を説明することになっているが、１分間での説明は結構難しそう。
●ショートプレゼン発表番号：I-13
（発表日：10/01（金）、発表時間：12:00）
●ショートプレゼン発表番号：I-13
（発表日：10/01（金）、発表時間：12:00）
ロットサイズ決定問題とは異なるが、制約条件の使い方が類似している新種の MIP を解こうとしている。作者の許可が得られればいずれ詳細についても公開する予定である。整数変数の使い方の問題なのか、小さめの問題でも上界 308, 下界 231 とかなり大きな Gap が存在して、この差がなかなか縮まらない。
○ Gurobi 3.0.1
180198189 88986976 234.29690 57 11 308.00000 231.00000 25.0% 6.1 5690s
180411994 89063415 infeasible 69 308.00000 231.00000 25.0% 6.1 5695s
Interrupt request received
Cutting planes:
Gomory: 1
Cover: 2
Clique: 2
MIR: 11
Explored 180560497 nodes (1096432931 simplex iterations) in 5698.34 seconds
Thread count was 8 (of 8 available processors)
○ CPLEX 12.2
97932164 71462927 234.4493 11 308.0000 231.0000 1.59e+09 25.00%
98180941 71639181 233.4474 13 308.0000 231.0000 1.59e+09 25.00%
98433354 71822240 231.5846 8 308.0000 231.0000 1.60e+09 25.00%
98683848 71999697 234.2772 15 308.0000 231.0000 1.60e+09 25.00%
98934881 72177175 infeasible 308.0000 231.0000 1.61e+09 25.00%
99182068 72350893 231.0000 8 308.0000 231.0000 1.61e+09 25.00%
^C
Clique cuts applied: 31
Cover cuts applied: 246
Implied bound cuts applied: 13
Zero-half cuts applied: 10
Gomory fractional cuts applied: 10
Root node processing (before b&c):
Real time = 0.09
Parallel b&c, 24 threads:
Real time = 5345.84
Sync time (average) = 97.14
Wait time (average) = 417.56
-------
Total (root+branch&cut) = 5345.93 sec.
Solution pool: 2 solutions saved.
MIP - Aborted, integer feasible: Objective = 3.0800000000e+02
Current MIP best bound = 2.3100000000e+02 (gap = 77, 25.00%)
Solution time = 5346.04 sec. Iterations = 1612309356 Nodes = 99347929 (72465987)
Solve interrupted
Best objective 3.0800000000e+02, best bound 2.3100000000e+02, gap 25.0000%
○ SCIP 1.2.0
5116s| 4833k| 1453k| 74873k|1300M| 72 | 7 | 310 | 865 | 23 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74874k|1300M| 72 | - | 310 | 865 | 11 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74875k|1300M| 72 | 7 | 310 | 868 | 20 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74877k|1300M| 72 | - | 310 | 868 | 22 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74879k|1300M| 72 | 8 | 310 | 868 | 19 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
time | node | left |LP iter| mem |mdpt |frac |vars |cons |ccons|cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
5116s| 4833k| 1453k| 74880k|1300M| 72 | - | 310 | 868 | 16 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
^Cpressed CTRL-C 1 times (5 times for forcing termination)
SCIP Status : solving was interrupted [user interrupt]
Solving Time (sec) : 5116.43
Solving Nodes : 4833931
Primal Bound : +3.08000000000000e+02 (503 solutions)
Dual Bound : +2.31000000000000e+02
Gap : 33.33 %
○ Cbc 2.5
Cbc0010I After 510000 nodes, 66216 on tree, 308 best solution, best possible 231 (4910.05 seconds)
Cbc0010I After 511000 nodes, 66215 on tree, 308 best solution, best possible 231 (4914.81 seconds)
Cbc0003I Exiting on maximum nodes
Cbc0005I Partial search - best objective 308 (best possible 231), took 135309858 iterations and 6834692 nodes (4920.52 seconds)
Cbc0032I Strong branching done 1300424 times (17638874 iterations), fathomed 5502 nodes and fixed 29689 variables
Cbc0041I Maximum depth 52, 3285 variables fixed on reduced cost (6323286 nodes in complete fathoming taking 117671210 iterations)
Cuts at root node changed objective from 214.383 to 231
Probing was tried 746190 times and created 2041645 cuts of which 285418 were active after adding rounds of cuts (237.447 seconds)
Gomory was tried 370648 times and created 299575 cuts of which 63042 were active after adding rounds of cuts (107.059 seconds)
Knapsack was tried 370651 times and created 2735251 cuts of which 430317 were active after adding rounds of cuts (364.819 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.004 seconds)
MixedIntegerRounding2 was tried 370651 times and created 105656 cuts of which 444 were active after adding rounds of cuts (56.647 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 100 times and created 640 cuts of which 0 were active after adding rounds of cuts (0.088 seconds)
Result - Stopped on nodes objective 308 after 6834692 nodes and 135309858 iterations - took 4920.53 seconds (total time 4920.54)
Total time 4920.54
○ GLPK 4.44
Time used: 5107.2 secs. Memory used: 371.1 Mb.
+3175727: mip = 3.080000000e+02 >= 1.170000000e+02 62.0% (679365; 38172)
+3177299: mip = 3.080000000e+02 >= 1.170000000e+02 62.0% (679703; 38192)
+3179161: mip = 3.080000000e+02 >= 1.170000000e+02 62.0% (680042; 38212)
○ Gurobi 3.0.1
180198189 88986976 234.29690 57 11 308.00000 231.00000 25.0% 6.1 5690s
180411994 89063415 infeasible 69 308.00000 231.00000 25.0% 6.1 5695s
Interrupt request received
Cutting planes:
Gomory: 1
Cover: 2
Clique: 2
MIR: 11
Explored 180560497 nodes (1096432931 simplex iterations) in 5698.34 seconds
Thread count was 8 (of 8 available processors)
○ CPLEX 12.2
97932164 71462927 234.4493 11 308.0000 231.0000 1.59e+09 25.00%
98180941 71639181 233.4474 13 308.0000 231.0000 1.59e+09 25.00%
98433354 71822240 231.5846 8 308.0000 231.0000 1.60e+09 25.00%
98683848 71999697 234.2772 15 308.0000 231.0000 1.60e+09 25.00%
98934881 72177175 infeasible 308.0000 231.0000 1.61e+09 25.00%
99182068 72350893 231.0000 8 308.0000 231.0000 1.61e+09 25.00%
^C
Clique cuts applied: 31
Cover cuts applied: 246
Implied bound cuts applied: 13
Zero-half cuts applied: 10
Gomory fractional cuts applied: 10
Root node processing (before b&c):
Real time = 0.09
Parallel b&c, 24 threads:
Real time = 5345.84
Sync time (average) = 97.14
Wait time (average) = 417.56
-------
Total (root+branch&cut) = 5345.93 sec.
Solution pool: 2 solutions saved.
MIP - Aborted, integer feasible: Objective = 3.0800000000e+02
Current MIP best bound = 2.3100000000e+02 (gap = 77, 25.00%)
Solution time = 5346.04 sec. Iterations = 1612309356 Nodes = 99347929 (72465987)
Solve interrupted
Best objective 3.0800000000e+02, best bound 2.3100000000e+02, gap 25.0000%
○ SCIP 1.2.0
5116s| 4833k| 1453k| 74873k|1300M| 72 | 7 | 310 | 865 | 23 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74874k|1300M| 72 | - | 310 | 865 | 11 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74875k|1300M| 72 | 7 | 310 | 868 | 20 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74877k|1300M| 72 | - | 310 | 868 | 22 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
5116s| 4833k| 1453k| 74879k|1300M| 72 | 8 | 310 | 868 | 19 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
time | node | left |LP iter| mem |mdpt |frac |vars |cons |ccons|cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
5116s| 4833k| 1453k| 74880k|1300M| 72 | - | 310 | 868 | 16 | 310 | 353 | 4 | 138k| 32k| 2.310000e+02 | 3.080000e+02 | 33.33%
^Cpressed CTRL-C 1 times (5 times for forcing termination)
SCIP Status : solving was interrupted [user interrupt]
Solving Time (sec) : 5116.43
Solving Nodes : 4833931
Primal Bound : +3.08000000000000e+02 (503 solutions)
Dual Bound : +2.31000000000000e+02
Gap : 33.33 %
○ Cbc 2.5
Cbc0010I After 510000 nodes, 66216 on tree, 308 best solution, best possible 231 (4910.05 seconds)
Cbc0010I After 511000 nodes, 66215 on tree, 308 best solution, best possible 231 (4914.81 seconds)
Cbc0003I Exiting on maximum nodes
Cbc0005I Partial search - best objective 308 (best possible 231), took 135309858 iterations and 6834692 nodes (4920.52 seconds)
Cbc0032I Strong branching done 1300424 times (17638874 iterations), fathomed 5502 nodes and fixed 29689 variables
Cbc0041I Maximum depth 52, 3285 variables fixed on reduced cost (6323286 nodes in complete fathoming taking 117671210 iterations)
Cuts at root node changed objective from 214.383 to 231
Probing was tried 746190 times and created 2041645 cuts of which 285418 were active after adding rounds of cuts (237.447 seconds)
Gomory was tried 370648 times and created 299575 cuts of which 63042 were active after adding rounds of cuts (107.059 seconds)
Knapsack was tried 370651 times and created 2735251 cuts of which 430317 were active after adding rounds of cuts (364.819 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.004 seconds)
MixedIntegerRounding2 was tried 370651 times and created 105656 cuts of which 444 were active after adding rounds of cuts (56.647 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 100 times and created 640 cuts of which 0 were active after adding rounds of cuts (0.088 seconds)
Result - Stopped on nodes objective 308 after 6834692 nodes and 135309858 iterations - took 4920.53 seconds (total time 4920.54)
Total time 4920.54
○ GLPK 4.44
Time used: 5107.2 secs. Memory used: 371.1 Mb.
+3175727: mip = 3.080000000e+02 >= 1.170000000e+02 62.0% (679365; 38172)
+3177299: mip = 3.080000000e+02 >= 1.170000000e+02 62.0% (679703; 38192)
+3179161: mip = 3.080000000e+02 >= 1.170000000e+02 62.0% (680042; 38212)
SDPA クラスタでは SDPARA を用いた量子化学 SDP の長期実験中。それとは別に MIP の話題を最近続けているが、MIP ソルバーである CPLEX や Gurobi はマルチスレッドに対応していることは知られている。以下の二つのサーバはコア数では３倍の差があるが、計算サーバ１の方がクロック周波数大きいにもかかわらず３倍速いということはなくて、SDPA の場合では計算サーバ２の方が速いこともある。MIP のマルチスレッド計算はやや複雑で単純にスレッド数と計算時間が対応しないが、一般的にはスレッド数を増やした方が高速であることに変わりはない。
問題 S-20-20-2-3.mps
○ CPLEX 12.2
計算サーバ１：138.90s
計算サーバ２：274.95s
○ Gurobi 3.0.1
計算サーバ１：122.23s
計算サーバ２：131.61s
○計算サーバ１
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
○計算サーバ２
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2 (8コア)
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
問題 S-20-20-2-3.mps
○ CPLEX 12.2
計算サーバ１：138.90s
計算サーバ２：274.95s
○ Gurobi 3.0.1
計算サーバ１：122.23s
計算サーバ２：131.61s
○計算サーバ１
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
○計算サーバ２
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2 (8コア)
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
以下の計算サーバにおいて CPLEX 12.2 を用いて最適解を得ようとしたのだが、こちらも Gurobi と同じくメモリが切迫してきたので実行を中止した。残念ながら以下の問題を解くのは単独のソフトウェアではかなり難しいようだ。
S-20-50-3-3.mps.gz
Nodefile size = 697831.92 MB (169971.27 MB after compression)
433612296 356186112 cutoff 883439.0000 839525.9672 1.55e+10 4.97%
433782278 356323355 858435.7173 424 883439.0000 839526.2118 1.55e+10 4.97%
433955388 356464661 876927.3369 280 883439.0000 839526.4604 1.55e+10 4.97%
434127419 356607280 862653.5716 436 883439.0000 839526.7060 1.55e+10 4.97%
434306172 356753064 858314.6577 444 883439.0000 839526.9562 1.55e+10 4.97%
434483618 356892974 882571.0497 384 883439.0000 839527.2159 1.55e+10 4.97%
434659566 357029269 882927.4020 258 883439.0000 839527.4687 1.56e+10 4.97%
434832334 357163942 883418.9404 394 883439.0000 839527.7231 1.56e+10 4.97%
435002707 357298035 869082.8417 384 883439.0000 839527.9653 1.56e+10 4.97%
○計算サーバ
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
S-20-50-3-3.mps.gz
Nodefile size = 697831.92 MB (169971.27 MB after compression)
433612296 356186112 cutoff 883439.0000 839525.9672 1.55e+10 4.97%
433782278 356323355 858435.7173 424 883439.0000 839526.2118 1.55e+10 4.97%
433955388 356464661 876927.3369 280 883439.0000 839526.4604 1.55e+10 4.97%
434127419 356607280 862653.5716 436 883439.0000 839526.7060 1.55e+10 4.97%
434306172 356753064 858314.6577 444 883439.0000 839526.9562 1.55e+10 4.97%
434483618 356892974 882571.0497 384 883439.0000 839527.2159 1.55e+10 4.97%
434659566 357029269 882927.4020 258 883439.0000 839527.4687 1.56e+10 4.97%
434832334 357163942 883418.9404 394 883439.0000 839527.7231 1.56e+10 4.97%
435002707 357298035 869082.8417 384 883439.0000 839527.9653 1.56e+10 4.97%
○計算サーバ
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
メモリ消費量が本体のメモリ量を越えてマシンの動きがかなり不安定になってきたので、プロセスを停止した。残念ながら Gurobi 3.0.1 での挑戦はこれで終了。
53948000 45008115 872260.818 63 193 875061.971 865318.681 1.11% 39.2 392646s
53948541 45008511 869598.036 55 203 875061.971 865318.681 1.11% 39.2 392650s
53948816 45008729 871139.995 83 163 875061.971 865318.681 1.11% 39.2 392655s
53949361 45009159 872355.960 108 159 875061.971 865318.681 1.11% 39.2 392661s
53949919 45009623 874053.037 148 135 875061.971 865318.691 1.11% 39.2 392665s
○計算サーバ
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64
53948000 45008115 872260.818 63 193 875061.971 865318.681 1.11% 39.2 392646s
53948541 45008511 869598.036 55 203 875061.971 865318.681 1.11% 39.2 392650s
53948816 45008729 871139.995 83 163 875061.971 865318.681 1.11% 39.2 392655s
53949361 45009159 872355.960 108 159 875061.971 865318.681 1.11% 39.2 392661s
53949919 45009623 874053.037 148 135 875061.971 865318.691 1.11% 39.2 392665s
○計算サーバ
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64
この世界ではスケーラビリティとかアムダールの法則が好きな方が多いので、SDPARA でも頻繁に問い合わせがある。詳細なデータや説明については論文の方に譲るとして簡単な例を添付図の方に示した。比較相手は PCSDP になる。SDPARA の括弧の中の数字は Schur complement 行列計算のマルチスレッド数を示している。PCSDP から BLAS を呼び出す場合でも BLAS はマルチスレッドで動作しているので、PCSDP がマルチスレッドを全く利用してないというわけではない。
SDPARA の場合では 1 ノード x 1 スレッドの時が 36204秒で、128 ノード x 16 コアのときが 565 秒なので、128 コア使用で約 64 倍の高速化になっている。アルゴリズムの全ての部分が並列化されているわけではないので、アムダールの法則的にはまずまずの結果になっている。これは SDPARA 7.3.1 の結果なので、最新の 7.3.2 ではもう少し性能が上がっている。
SDPARA の場合では 1 ノード x 1 スレッドの時が 36204秒で、128 ノード x 16 コアのときが 565 秒なので、128 コア使用で約 64 倍の高速化になっている。アルゴリズムの全ての部分が並列化されているわけではないので、アムダールの法則的にはまずまずの結果になっている。これは SDPARA 7.3.1 の結果なので、最新の 7.3.2 ではもう少し性能が上がっている。
2002年10月1日から埼玉県に住んでおりましたが、2010年8月10日をもって埼玉県から離れることになりました。埼玉県の印象としましては、以下のような感じになります。
１：山が少なく平らなので（日本の中では）非常に広く感じる
２：車社会。駅の近くか街中で無いと車無しでは生きていけない
３：大型店や大規模ショッピングセンターが多い。駐車場も広く、品揃えも多い。その代わりに駅前はあまり栄えていない
４：横の移動が不便。武蔵野線、川越線や東武野田線が無かったら埼玉から埼玉に行くのに一旦東京に行くという事態になってしまう
５：いまだに県の中心がどこだかわからない
６：地震に関しては東京、神奈川よりも安全に見えるが、荒川沿いは軟弱地盤なので埼玉南部と中部も危険らしい
１：山が少なく平らなので（日本の中では）非常に広く感じる
２：車社会。駅の近くか街中で無いと車無しでは生きていけない
３：大型店や大規模ショッピングセンターが多い。駐車場も広く、品揃えも多い。その代わりに駅前はあまり栄えていない
４：横の移動が不便。武蔵野線、川越線や東武野田線が無かったら埼玉から埼玉に行くのに一旦東京に行くという事態になってしまう
５：いまだに県の中心がどこだかわからない
６：地震に関しては東京、神奈川よりも安全に見えるが、荒川沿いは軟弱地盤なので埼玉南部と中部も危険らしい
量子化学に対する SDPARA の数値実験を４月から行っているが、残りやっと１２問になった。多くが pdOPT だが、たまに解けていない問題もある。８月１０日に自宅の引越しがあるが、研究室のクラスタ計算機はそれとは関係なく問題を解き続けてくれている。
phase.value = pdOPT
Iteration = 32
mu = +1.9745331466385050e-11
relative gap = +1.2139713807945350e-15
gap = +8.8817841970012523e-15
digits = +1.4915791551571731e+01
objValPrimal = -7.3163044347785089e+00
objValDual = -7.3163044347785178e+00
p.feas.error = +4.8102916434701486e-09
d.feas.error = +6.9331261565164226e-10
total time = 246875.948672
○ SDPARA 7.3.2 + GotoBLAS2 1.13(LAPACK 3.1.1) + MUMPS 4.9.2
○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64
phase.value = pdOPT
Iteration = 32
mu = +1.9745331466385050e-11
relative gap = +1.2139713807945350e-15
gap = +8.8817841970012523e-15
digits = +1.4915791551571731e+01
objValPrimal = -7.3163044347785089e+00
objValDual = -7.3163044347785178e+00
p.feas.error = +4.8102916434701486e-09
d.feas.error = +6.9331261565164226e-10
total time = 246875.948672
○ SDPARA 7.3.2 + GotoBLAS2 1.13(LAPACK 3.1.1) + MUMPS 4.9.2
○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64
78615 秒を突破して、現在メモリ消費量が 28.2Gbytes となっている。最適解が見付かる前にメモリが無くなりそう。
14792928 12445862 869671.411 66 152 875061.972 864704.194 1.18% 39.6 78590s
14793853 12446659 871638.844 97 149 875061.972 864704.204 1.18% 39.6 78595s
14794798 12447418 867993.274 71 165 875061.972 864704.240 1.18% 39.6 78600s
14795564 12448090 874611.380 140 133 875061.972 864704.240 1.18% 39.6 78605s
14796630 12448987 870853.188 82 152 875061.972 864704.272 1.18% 39.6 78610s
14797525 12449765 874775.472 133 168 875061.972 864704.283 1.18% 39.6 78615s
○計算サーバ
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64
14792928 12445862 869671.411 66 152 875061.972 864704.194 1.18% 39.6 78590s
14793853 12446659 871638.844 97 149 875061.972 864704.204 1.18% 39.6 78595s
14794798 12447418 867993.274 71 165 875061.972 864704.240 1.18% 39.6 78600s
14795564 12448090 874611.380 140 133 875061.972 864704.240 1.18% 39.6 78605s
14796630 12448987 870853.188 82 152 875061.972 864704.272 1.18% 39.6 78610s
14797525 12449765 874775.472 133 168 875061.972 864704.283 1.18% 39.6 78615s
○計算サーバ
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64
S-20-50-3-3.mps.gz の問題を Gurobi 3.0.1 を用いて 9146 秒ほど解いてみたのだが、gap が 1.27% にしか減らないので、このまま解けるまで継続して実行することにした。やはり以前思っていたよりも難しい問題のようだ。
4979886 4263630 875146.194 113 137 875389.973 864275.516 1.27% 32.9 9135s
4982953 4266170 875274.113 106 134 875389.973 864275.926 1.27% 32.9 9140s
Cutting planes:
Gomory: 26
Cover: 42
Implied bound: 53
Flow cover: 632
Flow path: 1513
Explored 4985658 nodes (163987549 simplex iterations) in 9146.06 seconds
Thread count was 24 (of 24 available processors)
Solve interrupted
Best objective 8.7538997271e+05, best bound 8.6427598759e+05, gap 1.2696%
4979886 4263630 875146.194 113 137 875389.973 864275.516 1.27% 32.9 9135s
4982953 4266170 875274.113 106 134 875389.973 864275.926 1.27% 32.9 9140s
Cutting planes:
Gomory: 26
Cover: 42
Implied bound: 53
Flow cover: 632
Flow path: 1513
Explored 4985658 nodes (163987549 simplex iterations) in 9146.06 seconds
Thread count was 24 (of 24 available processors)
Solve interrupted
Best objective 8.7538997271e+05, best bound 8.6427598759e+05, gap 1.2696%
１：発表者が質問に対して的確に答えられないことが多い。基本的に勉強不足。多分野や昔のことはほとんど知らない。
２：アプリを作る人は一通り、理論＆応用分野を勉強してからの方が良い。
３：１と関連するが、例えば最適化問題を扱うのであれば、以下の行動が必要。
○最新の研究を調査する
○最適化関連の学会や研究会に参加して発表する
○最適化の研究者と交流する
上記には自戒の意味も含まれているが、それにしても問題が多過ぎる。
２：アプリを作る人は一通り、理論＆応用分野を勉強してからの方が良い。
３：１と関連するが、例えば最適化問題を扱うのであれば、以下の行動が必要。
○最新の研究を調査する
○最適化関連の学会や研究会に参加して発表する
○最適化の研究者と交流する
上記には自戒の意味も含まれているが、それにしても問題が多過ぎる。
7月31日に筑波大学で行われたシンポジウムで SDP のサイズについて質問があったので、こちらで補足を行う。
資産の数を n とすると、mDIM (制約式の数 = Schur complement 行列の大きさ) = (n(n + 1)) / 2 + 2n + 5 となる。よって n = 225 のときには mDIM = 25880 となる。DNN(半正定値 + 非負)制約があるので mDIM のかなり大きくなる。ところが、制約式のほとんどが DNN なので以下のように各制約行列の第一ブロックは 225 とかなり小さめになっている。
25880 (mDIM)
2 (nBLOCK)
226 -25877 (bLOCKsTRUCT)
そのため、SDPARA で解いたときの各部分の実行時間は以下のようになる。一見すると mDIM = 25880 となる巨大な SDP が 1095 秒程で解くことができるのは不思議に見えるのだが、上記の性質から F3 式の計算部分(Make bF3 time) が少なくなっている。Parallel Cholesky 分解は効率良く並列に計算できるので、F3 式の計算に大きく依存しなければ、このように高速に解くことができる。つまり mDIM が大きくても bLOCKsTRUCT の正の部分の値が小さければ高速に解くことができる（これも SDPARA による高速化の恩恵)。
Predictor time = 1082.062081, 98.831590
Corrector time = 11.097648, 1.013619
Make bMat time = 34.830153, 3.181259
Make bF3 time = 50.397050, 4.603082
copy bMat time = 93.721031, 8.560136
symm bMat time = 64.199433, 5.863741
Cholesky bMat = 878.015744, 80.194744
solve = 20.991411, 1.917279
makedX = 0.330666, 0.030202
symmetriseDx = 0.007777, 0.000710
makedXdZ = 0.717884, 0.065569
Main Loop = 1094.854472, 100.000000
Total = 1095.090178, 100.021529
○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64
資産の数を n とすると、mDIM (制約式の数 = Schur complement 行列の大きさ) = (n(n + 1)) / 2 + 2n + 5 となる。よって n = 225 のときには mDIM = 25880 となる。DNN(半正定値 + 非負)制約があるので mDIM のかなり大きくなる。ところが、制約式のほとんどが DNN なので以下のように各制約行列の第一ブロックは 225 とかなり小さめになっている。
25880 (mDIM)
2 (nBLOCK)
226 -25877 (bLOCKsTRUCT)
そのため、SDPARA で解いたときの各部分の実行時間は以下のようになる。一見すると mDIM = 25880 となる巨大な SDP が 1095 秒程で解くことができるのは不思議に見えるのだが、上記の性質から F3 式の計算部分(Make bF3 time) が少なくなっている。Parallel Cholesky 分解は効率良く並列に計算できるので、F3 式の計算に大きく依存しなければ、このように高速に解くことができる。つまり mDIM が大きくても bLOCKsTRUCT の正の部分の値が小さければ高速に解くことができる（これも SDPARA による高速化の恩恵)。
Predictor time = 1082.062081, 98.831590
Corrector time = 11.097648, 1.013619
Make bMat time = 34.830153, 3.181259
Make bF3 time = 50.397050, 4.603082
copy bMat time = 93.721031, 8.560136
symm bMat time = 64.199433, 5.863741
Cholesky bMat = 878.015744, 80.194744
solve = 20.991411, 1.917279
makedX = 0.330666, 0.030202
symmetriseDx = 0.007777, 0.000710
makedXdZ = 0.717884, 0.065569
Main Loop = 1094.854472, 100.000000
Total = 1095.090178, 100.021529
○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64
添付の図はロットサイズ決定問題の MIP の定式化になっている。この定式化は１製品の定式化なので、これを複数製品に拡張する。実際にはもう少し定式化は複雑になっているのだが、20 製品、50 期間(T = 50)ぐらいに拡張すると MIP としては非常に解きにくい問題になる(C の値にも依存する)。
以下の問題を２時間ほど CPLEX 12.2 と Gurobi 3.0.1 を用いて解いてみたが、数％の gap がなかなか縮まらず、簡単に解けそうな感じではない。
S-20-50-3-3.mps.gz
以下が CPLEX の初期出力で 0-1 変数は 20 製品 x 50 期間で 1000 個になる。
MIP Presolve eliminated 1004 rows and 4 columns.
Reduced MIP has 3050 rows, 5000 columns, and 10960 nonzeros.
Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
以下の問題を２時間ほど CPLEX 12.2 と Gurobi 3.0.1 を用いて解いてみたが、数％の gap がなかなか縮まらず、簡単に解けそうな感じではない。
S-20-50-3-3.mps.gz
以下が CPLEX の初期出力で 0-1 変数は 20 製品 x 50 期間で 1000 個になる。
MIP Presolve eliminated 1004 rows and 4 columns.
Reduced MIP has 3050 rows, 5000 columns, and 10960 nonzeros.
Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
以下の四つの MIP ソルバーを用いて、簡単な性能比較を行った。パラメータはデフォルトのままで用いている。やはり 1 と 2 は速い。
1: Gurobi 3.0.1
2: IBM CPLEX 12.2
3: SCIP 1.2.0
4: GNU GLPK 4.44
○問題１: nw04.mps
1: 9.86s
2: 5.01s
3: 549.90s
4: 523.90s
○問題２: stein45.mps
1: 1.46s
2: 2.52s
3: 23.20s
4: 42.20s
○計算サーバ
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
1: Gurobi 3.0.1
2: IBM CPLEX 12.2
3: SCIP 1.2.0
4: GNU GLPK 4.44
○問題１: nw04.mps
1: 9.86s
2: 5.01s
3: 549.90s
4: 523.90s
○問題２: stein45.mps
1: 1.46s
2: 2.52s
3: 23.20s
4: 42.20s
○計算サーバ
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
計算サーバ１と２はかなりの性能差がある。例えば SDPA 7.3.2 の実行では１０倍以上の差がある。
○問題 mcp500-1.dat-s
サーバ１：1.611s
サーバ２：22.591s
計算サーバ１で glpk 4.44、計算サーバ２で Gurobi 3.0.1 を用いて実行時間の比較を行った。
○問題１：stein45.mps
サーバ１(glpk 4.44)：34.36s
サーバ２(gurobi 3.0.1)：45.11s
○問題２：air06.mps
サーバ１(glpk 4.44)：10.72s
サーバ２(gurobi 3.0.1)：6.17s
○計算サーバ１
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2 (8コア)
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
○計算サーバ２
CPU : Intel Atom 330 1.6GHz
Memory : 2GB
OS : Fedora 13 for x86_64
○問題 mcp500-1.dat-s
サーバ１：1.611s
サーバ２：22.591s
計算サーバ１で glpk 4.44、計算サーバ２で Gurobi 3.0.1 を用いて実行時間の比較を行った。
○問題１：stein45.mps
サーバ１(glpk 4.44)：34.36s
サーバ２(gurobi 3.0.1)：45.11s
○問題２：air06.mps
サーバ１(glpk 4.44)：10.72s
サーバ２(gurobi 3.0.1)：6.17s
○計算サーバ１
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2 (8コア)
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
○計算サーバ２
CPU : Intel Atom 330 1.6GHz
Memory : 2GB
OS : Fedora 13 for x86_64
アクセス
トータル
