Gurobi 3.0.1 と 3.0.2

Gurobi 3.0.2 がリリースされたので、3.0.1 と幾つかの問題で比較してみた。MIP のアルゴリズムの性質上、全ての問題で 3.0.2 が速いわけではないが、MIPLIB2003 の問題などを中心に様々なチューニングが行われているのだろう。

○問題 S-20-30-2-3.mps（ロットサイズ決定問題）
3.0.1 : 330.30秒
3.0.2 : 503.36秒

○問題 gmpl-10-0.2.mps (仮想マシンマイグレーション問題)
3.0.1 : 227.96秒
3.0.2 : 125.21秒

○問題 roll3000.mps (MIPLIB2003)
3.0.1 : 49.87秒
3.0.2 : 31.02秒

○問題 mod011.mps (MIPLIB2003)
3.0.1 : 34.73秒
3.0.2 : 21.50秒

○サーバ (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

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

2010 年度第４回 SCOPE 講演会

11月20日に SCOPE 講演会を行います。今回はファイナンスと多項式最適化及びサプライ・チェインに関する講演（２件）になります。是非ご参加下さい。

日　時 ： 2010年11月20日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス
講演1
講演者 ： 高野 祐一氏（筑波大学, 日本学術振興会PD）
講演題目 ： コンスタント・リバランス・ポートフォリオ選択問題に対する多項式最適化アプローチ
講演概要：
ポートフォリオ選択問題とは、手持ちの資金を各金融資産に投資して運用する際の投
資比率を決定する問題である。本発表では、コンスタント・リバランス戦略を採用し
た多期間ポートフォリオ選択問題を扱う。コンスタント・リバランスとは、計画期間
の複数時点で一定比率にリバランス（投資比率の修正）を行う投資戦略であり、実務
で採用されることも多く、理論的にも好ましい性質を持つ。しかし、この戦略を採用
した多期間ポートフォリオ選択問題は非凸計画問題となるため、その大域的最適解を
得ることは難しい。一方で、平均‐分散基準を利用することで問題は多項式計画問題
として定式化され、本発表では Lasserre (2001) によって提案された「多項式計画
問題に対する半正定値計画緩和」を利用して求解を試みる。さらに、次数の高い多項
式計画問題を解くことを目的に、Lasserre (2001) の半正定値計画緩和を利用した切
除平面法を提案し、数値実験によってその性能を検証する。

講演2
講演者 ： Mozart Menezes氏　（Zaragoza Logistics Center, Zaragoza (Spain)）
講演題目 ： Correlation and Disruption Induced Effects on Location Problems
講演概要：
In this work we study a class of locations models where facilities may fail.
The problems are defined in a network and some important properties of the
objective functions are analyzed. Asymptotic results were obtained suggest
behavioral consistency of location patterns as function of the probability
of failure. In order to go beyond those asymptotic results and, in order to
accept the fact that failures may be correlated, we shift methodology and also
present results developed in a continuous location setting: a simple (yet classic)
2-facility problem on a unit segment, with customer demand distributed uniformly
over the segment. We analyze problems with Median and Center objectives under complete
and incomplete customer information regarding the state of facilities. Managerial
insights are discussed.

MacBook Air

MacBook Air は軽くて薄い代わりに、本体には NIC も DVD/CD ドライブも付いていない。ちなみに NIC は LAN-TX/U2H3B(LAN-TX/U2H3S) という USB2.0 の LAN アダプタを使うことができる。ちなみにこの LAN アダプタは MacBook Air だけでなく SHARP NetWalker でも使うことができる。
11インチ + Intel Core 2 Duo 1.4GHz + 64GB SSD の一番安いモデルでも非常に軽快に OS やソフトウェアが動作する。最短路のソルバーを使って両者の速度を比較してみた。

○最短路ソルバー : msp 2.00
○DIMACS 全米データ(USA : 点数 23,947,347, 枝数 58,333,344)
○クエリ数 256

MacBook Air : 1421.3秒
Intel PC : 702.1秒

クロック周波数以上に差が開いてしまった両者だが、前回の比較でも Linux の方が優勢だった。

○ MacBook Air
CPU : Intel Core 2 Duo 1.4GHz (2コア)
Memory : 2GB
SSD : 64GB
Mac OS X 10.6.4
gcc 4.2.1

○ Intel PC
CPU : Intel Core 2 Duo E8200 2.66GHz (2コア)
Memory : 4GB
HDD : 1TB
Linux CentOS 5.5
gcc 4.1.2

iPod Touch と最短路オンライン・ソルバー

以前試したのだが、DoCoMo の携帯 Xperia では最短路オンライン・ソルバーの完全な実行は出来なかった。　もちろんスマートフォンでない普通の DoCoMo の携帯でも実行は無理だった。



イー・モバイルの WiFi ルーターのおまけ？として新型 iPod Touch を手に入れたので、iPod Touch で最短路オンライン・ソルバーの実行が出来るかを試してみた。結果としては写真の通りで、画面小さいし速度は遅めなので使い勝手はやや悪いのだが、ほぼ完全な実行が出来ているようだ。

全対全最短路と媒介中心性

日本語では媒介中心性とも言われる以下の指標であるが、始点の方はランダムサンプリングで数百点ぐらいを使用しても近似性能は良いようである（幾つかの論文によると）。



いろいろな近似手法を提案して、それらの性能評価するためには全対全の最短路を全て求めて置くのも良いだろう。ただしディスク容量が相当必要となるのでディスク容量の少ない新クラスタ計算機での実行には向いていない。現在のクラスタ計算機は 1 ノードあたり 5TB のディスク容量があるが、新クラスタ計算機は各ノードのディスク容量(73GB x 2)とメモリ量(128GB)はほぼ同じである。

ちなみに以下の計算サーバ（２４コア）で全米データ(点数 23,947,347, 枝数 58,333,344)の1対全最短路を 1,000 回解くと 232 秒になる(平均すると1回の実行で 5.6秒)。



全米データの全対全の最短路問題を解くためには、1対全の最短路問題を 2,394,7347 回解かなければならない。よって、以下の計算サーバだけで実行すると (23,947,347点 / 1,000点) * 232 秒 = 5,555,785秒 ≈ 1543.3時間 ≈ 64.3日 となる。ただし今年の暮れには研究室の計算機の総コア数が 400 を越えるので、数日で終わると予想される。

○計算サーバ (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

超大規模グラフとダイクストラ法

超大規模グラフ(点数=1,073,741,824, 枝数=2,147,483,647 つまり点数 1G, 枝数 2G)を作成して１対全の最短路問題をダイクストラ法で解いてみた。インターネット等で調べた範囲ではこのような大規模なグラフに対して前処理無しで厳密にダイクストラ法を実行している例は見当たらない。この大きさになるとデータの読み込みにかかる時間が非常に多くを占めるようになる。

グラフデータの読み込み時間：1834秒
ダイクストラ法の実行時間：868秒
使用メモリ量：約 40Gbytes

ただし、ダイクストラ法の実行時間自体は 868 秒程度なので、一度メモリ上にデータを格納してしまえば、次からは 868 秒程度で別の始点を持つ１対全最短路問題を解くことができる。ダイクストラ法 with binary heap なので計算量が O((n+m)log(n)) だと仮定して、それぞれの場合について octave で計算すると 240 秒ぐらいが妥当なところで 868 秒というのは少し多めである。

> ((1073741824 + 2147483647) * log2(1073741824)) / ((23947347 + 58333344) * log2(23947347))
> 47.912

> 47.912 * 5
> 239.56

全米データ 24M点、58M枝 : 5秒
今回のデータ 1G点、2G枝 : 868秒

計算サーバ (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

ただし、計算量の中で log n の部分は binary heap に関するものなので、実際には全部の点(n 個)が全て heap に入ることはあまり起こらない。というわけで log n の n は実際の点数よりもかなり小さな値になると推測される。さらにグラフの巨大化によって L3 キャッシュのヒット率等にどのような変化があるのかを調べていく必要がある。



ダイクストラ法程度の計算量だと、計算時間よりも先にメモリ量が限界に達してしまう。128Gbytes メモリ搭載のマシンでももう少し枝を増やすとメモリが足らなくなってしまう。

Westmere-EP

TSUBAME 2.0 というと多くの方は GPU の方に注目するようだが、私のような最適化ソフトウェア開発者から見た TSUBAME 2.0 最大の魅力は各ノードに Intel Xeon X5670(Westmere-EP) を２個搭載しているところである。多くの最適化ソフトウェア(例えば SDP, MIP, 最短路など)にとって現時点で最強の CPU はWestmere-EP になる。

1: 最適化アルゴリズムは構造が複雑で先の計算の状態は直前にならないとわからない場合が多い。よって先読み等も難しい
2: それでもデータの構造(大きさ、疎性など)を利用してデータ要求量やアクセス頻度を抑えていくと、だんだんとメモリバンド幅の要求が減っていき、最終的にはメモリの局所参照性からコア間の共有キャッシュメモリ(特に L3) のバンド幅に律速するようになってくる。よって L3 キャッシュの性能(特に複数スレッドの同時アクセス時)が良い CPU が最適化ソフトウェアにとっても良い CPU となる
3: 2 のような工夫を行うと通常では GPU での実行には適さない形になってしまう
4: Intel Nehalem-EX は、実際に使用したことはないが Westmere-EP よりもクロック周波数が低く、L3 キャッシュの性能が劣るのであまり数値計算向きではないと推測できる

一方、TSUBAME 2.0 のような CPU + GPU ハイブリッド型スパコンにおいて、MPI 下で CPU + GPU が協調して非常に大きな行列の Cholesky 分解を並列に行う高性能なライブラリがあれば、例えば DNN 緩和の SDP などは爆速で解くことができる。DNN 緩和についてはこれらの記事などを参照していただきたいが、DNN 緩和は通常、問題が非常に大きくなるので、最適化の世界では DNN 緩和を近似的に扱う工夫が研究されている。これが近似では無く厳密に解くことができれば非常にインパクトは大きい。ただし、こんな高度なライブラリが作れるのは私知る範囲では某 G 氏ぐらいしかいない。

オガララ帯水層

1999年にアメリカに行ったときに現地でオガララ帯水層(Ogallala Aquifer)の枯渇の危険性を聞いたのだが、それから 10 年以上達って水位さらに低下している。とにかく帯水層に新しく入り込む水よりも組み上げる水の方が多いので、基本的に水位の低下は止まらない。
中国でも黄河水位が低下して、水質の悪化や海水の逆流などが起きているが、黄河流域の地下水循環モデルの調査と解析を行ったいるのが、実は日本の研究機関である。以前、関西の大学で聞いたのだが、上海の地盤沈下を真面目に調査しているのも日本の研究者だったりする。
地上に流れている川の方ばかりに目が向いてしまうが、実は地下水の方が量も多く重要で農業や飲料水などにも深く関わっているので、地下水の流れのモデルとシミュレーションというのはこれから非常に重要になってくることが予想される。詳細は省略するがモデル解析やシミュレーションするためには克服すべき点が幾つかあって予想よりもかなり難しい。

エニグマ暗号機

日本に２台しかないと言われる「エニグマ暗号機」を展示し、実際にデモンストレーションいたします。と書いてあるので、このエニグマ暗号機はまだ動くようだ。エニグマ暗号機と言ってわかるのは僕らの世代までだろうか？

http://www.chuo-u.ac.jp/chuo-u/event/event_j.html?suffix=i&mode=dpttop&topics=12151

エニグマ見にいこうと思っていたら、それ以前に研究発表の担当になっていたことに気が付いた。

GPU ３枚 or ４枚搭載

GPU が４枚搭載できるマザーボード＆マシンは珍しい方で実物は見たことはない。例えば以下の Supermicro のマシンには GPU が４枚搭載できる。ただし４枚搭載すると Infiniband は搭載できないようだ。

SuperServer 7046GT-TRF

こちらは GPU が３枚搭載可能でオンボードで 10Gb、Infiniband QDR を備えている。

HP ProLiant SL390s G7－スペック

あるいは以下の拡張シャーシのように GPU は別搭載にした方が電源や空調の問題上安定して動作するかもしれない。

PowerEdge C410x

例えば SDP のアプリケーションでは MPI で複数のノード(CPU + GPU)を利用した Parallel Cholesky ソルバーなどが存在すれば、これらのハードを揃えるメリットが出てくる。

GPU とグラフアルゴリズム その３

すでに GPU とグラフアルゴリズムのその１とその２で見てきたように、グラフアルゴリズムでは、少なくとも現時点において CPU の方にかなり分があると言って良い。特に大規模なデータになると CPU の独壇場である。

1: 1対全最短路問題に対するダイクストラ法は CPU 上での実行の方が GPU 上での実行よりもはるかに速い
2: 全対全最短路問題に対する Warshall-Floyd 法でも CPU の方が優勢(小規模な問題しか GPU 上では扱うことができない)

ところで、以下は CPU 上でのダイクストラ法の計算量と実行時間の関係であるが、意外に両者が精度良くフィッティングできている。ダイクストラ法 with バイナリヒープの実行時間は with MLB(マルチレベルバケット)の方計算量にむしろフィッティングしている。



全米データ (24M点, 58M枝)で 5秒程度の実行時間なので、点数、枝数を 100 倍して 2.4G点, 5.8G枝(つまり 24億点、58億枝) の場合では、O((n+m)log(n)) の計算量で増大すると仮定すると 100 x log(100) = 664.39 倍の計算時間、つまり 5 秒 x 664.39 = 3321.9 秒になる（実際にはもっと少ないだろう）。さすがに前処理無しでこの規模のグラフの 1対全最短路問題を解くのは相当大変だろう。

GPU とグラフアルゴリズム その２

全対全最短路問題には Warshall-Floyd 法という有名な方法があるのだが、Dijkstra(ダイクストラ)法(１対全最短路問題）を点数の数と同じだけ繰り返して全対全最短路問題を解くこともできる。ところが、Warshall-Floyd 法は以下のようにメモリ要求量が厳しいので、グラフとしては小さい規模に属する DIMACS New York(NY) データ(264,346 点, 733,846 枝)を用いて解く場合でも、教科書通りにプログラムを作成すると 260GB ものメモリが必要になる。



最近では Warshall-Floyd 法を GPU 上に実装して全対全最短路問題を高速に解くという研究を見かけるようになった。上記の理由と現状の GPU のメモリ量を考慮すると中規模のグラフに対する Warshall-Floyd 法を GPU 上で実行するのは難しいので、小規模な問題で比較してみよう。
以下はランダムに生成された 点数 8,192, 枝数 32,768 の小さな規模の問題であり、GPU は１台(GTX 280) を用いた。CPU が 1 コアでは GPU の方が速いが、CPU 側もマルチスレッドで計算すると 4 コアぐらいで逆転する。最新の Tesla C2070 と Intel Core i7-970(6コア) で同じ対決をした場合には、同程度か後者の方が速いぐらいで少なくとも GPU の性能が CPU を圧倒することは無さそうだ。



ちなみに下記の計算サーバ(24コア)では、Dijkstra法 x 点数(8192) の実行が 0.51 秒で終了する。

○サーバ (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

前にも書いたように、１対全最短路問題（ダイクストラ法）の場合では全米データ(点数 23,947,347, 枝数 58,333,344)上で実行を行うと GPU : 672秒、CPU : 5秒と 100 倍ぐらいの差がある。一方、全対全最短路問題では小さい規模の場合 GPU の方が有利と思われいるようだが、意外とそうも言えないのである。
今日、実データから生成されるグラフ上の探索では、点数は数百万から十億を越える規模まで拡大しつつあり、クラスタ計算機やスパコンの CPU 上で分散して処理するか、CRAY XMT のようなマシンの大容量共有メモリ上において大量のスレッドを生成して処理するのが有望であろう。

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

サイズ 30 の QAP(二次割当問題) に対する DNN 緩和問題を考える。



mDIM = 379350
nBLOCK = 2
bLOCKsTRUCT = -379440 900

何と言っても SCM (Schur complement 行列)のサイズが大きい。379350 x 379350 x 8bytes ≈ 1073 Gibytes なので、この行列だけで 1Tibytes ぐらいになる。この行列に関する演算は BLAS 等も含めて整数型 = 8bytes にする必要がある。SDPARA で解く場合では SCM は分散配置するので、ある程度大きな規模のクラスタ計算機やスパコンでは対応可能である。
DNN 緩和問題では行列の全ての要素に対する非負制約を付け加えていくので、mDIM の値が大きくなっていく。しかし、制約式で増えていくのは線形不等式制約なので、SCM の要素計算にはそれほどのメモリアクセス量を必要としない。よって、結果的には全データがメモリに入りきってしまえば、意外と計算時間は少ないのではないかと推測される。

Intel 対 AMD 半正定値計画問題

半正定値計画問題(SDP)において SCM(Schur Complement Matrix)のサイズが大きな場合では、高いメモリバンド幅を活かしてマルチスレッドで疎行列の計算が出来るということで AMD が有利、全体の実行時間の中で行列積の占める割合が増えると Intel が有利と思っていたのだが、後者でも意外と AMD が検討している。SDPA の中身を改造しているうちに特性が変わってきたのかもしれない。

以下は SDPA のマニュアルからの抜粋になる。nBLOCK と bLOCKsTRUCT というパラメータで問題の大きさを示している。mDIM は制約式の数で SCM のサイズと同じになる。



○問題１ mcp7000-10.dat-s : 最大カット問題
mDIM = 7000
nBLOCK = 1
bLOCKsTRUCT = 7000

サーバ１： 1419.845秒
サーバ２： 1580.958秒
サーバ３： 1347.291秒

この場合では行列積の計算に性能が依存するのだが、さすがに AMD でも 24 コアあると、Intel 8 コアには勝てるようだ。サーバ２と３を比較すると、AMD ではコア数が増えても行列積計算の伸びは低いことがわかる。


○問題２ HLi2.2A1.STO6G.pqgt1t2p.dat-s : 量子化学問題
mDIM = 10593
nBLOCK = 22
bLOCKsTRUCT = 11 11 11 11 55 55 121 55 55 121 242 121 121 165 605 605 165 1947 1947 605 605 -274

サーバ１： 20511.361秒
サーバ２： 30382.941秒
サーバ３： 18459.201秒

この場合では、総コア数が３倍あるサーバ３がサーバ１よりもわずかだけ性能が上回る。やはり Intel (質：1コアあたりの性能) v.s. AMD (量：コア数の多さ）の戦いになるようだ。


○サーバ１ (2 CPU x 4 コア = 8 コア)
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64

○サーバ２ (2 CPU x 6 コア = 12 コア)
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64

○サーバ３ (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