MIP と LP の解の違い

ファイル配置最適化問題に対して MIP（混合整数計画問題) と LP(線形計画問題) の解を比較する。ちなみに MIP の方は変数に binary 条件(0 か 1)が付いていて、LP の方は 0 から 1 の間の実数条件が付いている。少し見にくいのだが、例えば MIP の最適解では x[h40] = x[h42] = 1 になっているが、LP の最適解では x[h40] = x[h42] = 0 になっている。また、MIP では x[h95 から h102] までが 0 で、x[h103] のみが、1になっているが、LP では x[h95 から h103] までが 0.1 になっている。
MIP として簡単な問題は LP の最適解と MIP の最適解の変数の値が近い場合もあるが、このように少し複雑な MIP になってくると、両者の変数の値が大きく離れてくる場合もある。よって、LP の解を使って（変形して）、近似解法を作るのは困難な場合もあるだろう。


min_rep_under_thput_39600.0_test18.mip.out
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
39 x[h39] * 0 0 1
40 x[h40] * 1 0 1
41 x[h42] * 1 0 1
42 x[h43] * 0 0 1

中略

91 x[h94] * 0 0 1
92 x[h95] * 0 0 1
93 x[h96] * 0 0 1
94 x[h97] * 0 0 1
95 x[h98] * 0 0 1
96 x[h99] * 0 0 1
97 x[h100] * 0 0 1
98 x[h101] * 0 0 1
99 x[h102] * 0 0 1
100 x[h103] * 1 0 1

min_rep_under_thput_39600.0_test18.lp.out
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
39 x[h39] NL 0 0 1 <eps 中略

91 x[h94] B 0 0 1
92 x[h95] B 0.1 0 1
93 x[h96] B 0.1 0 1
94 x[h97] B 0.1 0 1
95 x[h98] B 0.1 0 1
96 x[h99] B 0.1 0 1
97 x[h100] B 0.1 0 1
98 x[h101] B 0.1 0 1
99 x[h102] B 0.1 0 1
100 x[h103] B 0.1 0 1

SDPARA-C と TSPLIB

TSPLIB に pcb1173 という問題があるが、これが手頃な大きさなので delaunay グラフ(添付の図を参照)を作って、max cut 問題に対する SDP 緩和問題を作る。何故こんなことをしているかと言うと現在 SDP の疎性に関する研究を行っているからである。疎性を利用する → Schur complemet 行列が疎になる → conversion や completion が効を奏する → 疎性を利用して高速に計算できるようにデータの並び替えやパッキングを行うという流れにしたいからである。これを SDPA と SDPARA-C で解いてみよう。

1: SDPA 7.2.0 + GotoBLAS 1.26 (1スレッド)
1m7.477s (16反復)
2: SDPA 7.2.0 + GotoBLAS 1.26 (8スレッド)
19.216s (16反復)
3: SDPARA-C 1.0 + GotoBLAS 1.26 + ATLAS 3.8.2 (16CPU × 1コア)
4.845s (21反復)

というわけで、この種の sparse な問題では SDPARA-C の圧勝である。相当 completion が効くみたいである。

組み込み系のスペック

ソニーの PSP と 任天堂の DS のスペックを調べると以下の通り。

PSP
CPU: MIPS R4000×2, 333MHz : 浮動小数点演算能力：2.6Gflops（333MHz駆動時）
メモリ 32MB (最新型は 64MB)

DS
CPU: ARM946E-S 67MHz + ARM7TDMI 33MHz
メモリ 4MB

これでも昔（1990年代前半）使用していた EWS(エンジニアリングワークステーション）並の性能なので、やり方によっては最適化プログラムも書けるし、ある程度大きな問題で動作させることもできる。でも今のプログラムやデータでは無理なので、あまりやりたくはない。
そこで現在の組み込み系、例えば NEC NaviEngine では

NaviEngine
CPU: MPCore（ARM11×4）　400MHz, with VFP11
メモリ システムに依存するが 64 から 256Mbytes ぐらい

CPU は ARM11 が 4個搭載になっている。このシステムは 2D/3D グラフィックスエンジンなどを持っているのが特徴の一つ。現在のカーナビシステムは演算能力も描画能力もこの程度であろう。
それでも、何千万点ものデータを入れて、前処理無しで高速かつ最適に最短路を求めるシステムには少し向かないと思われるので、やはり今後はクラリオンなどが発表しているように、Intel Atom 搭載(今後はデュアルコア : 1.6GHz 程度) でメモリ 512MB から 1GB ぐらいが標準になってくれると現在開発中の最短路計算プログラムも生かすことができるようになる。

SDPARA-C が速い問題

SDPARA-C というどちらかというとマイナーなソフトウェアがある。ソフトウェア自体は論文を見てもらえばわかるように、かなり複雑になっている。この図のような疎(sparse)なグラフに対する最大カット問題の SDP 緩和問題を作ると、aggregate sparsity pattern も疎になるので、この SDP 緩和問題は SDPARA-C が得意な部類になる。

1: SDPA 7.2.0 + GotoBLAS 1.26 (4コア)
12.731s(17反復)

2: SDPARA 7.0.1 + GotoBLAS 1.26 (16CPU × 4コア)
13.600s(17反復)

3: SDPARA-C 1.0 + GotoBLAS 1.26 + ATLAS 3.8.2 (16CPU × 4コア)
4.019s(28反復)

となるので、反復回数は多いものの SDPARA-C がかなり高速であることがわかる。この種の問題に対しては SDPARA-C も比較対象になるのではないか。

距離か時間か？ その２

GoogleMaps 上で始点と終点を入力 → opt.indsys.chuo-u.ac.jp 上のダイクストラ法のプログラムで移動距離と移動時間に関する最短路を計算する → GoogleMaps 上で結果を表示という Online Solver をこちらから公開中である。もちろん無料なので、いろいろと試してみると特に最適化に興味が無い人でも面白いと思う。
図は Google 本社から Niagara Falls までの最短路の求めたときの最初の部分である。最短距離で移動する赤い線の方は当然ながら Niagara Falls 方面になるべく直線で向かうので、田舎道を通ってヨセミテ国立公園を越えて東に向かう。最短時間で移動する青い線は慌てずに？インターステイト 80 号線に乗っている。日本でも同じようなシステムを作ってみたいのだが、残念ながら全米のように気軽に利用できるデータがない。

様々なブラウザでの動作検証

最短路 Online Solver が GoogleMaps と連携を開始したので、様々なブラウザでの動作を検証してみよう(OS は Windows XP 32bit を使用)。Online Solver 自体は毎日改善＆変更中なのでバグや不具合もあるが少しずつ修正していく予定だ。全米データで東海岸から西海岸までの大陸横断の query を求める(時間と距離の両方)。実行時間とは実行開始から表示終了までの秒数を示している。

1: FireFox 3.0.1
実行時間 : 22.07秒
マウスによる座標指定のずれが少ない。もっとも無難な動作をする。GoogleMaps の実行も速い方。

2: Opera 9.52
実行時間 : 28.16秒
マウスによる座標指定で少しずれが生じる。GoogleMaps の動きがやや遅い。

3: GoogleChrome 0.2.149.29
実行時間 : 17.98秒
とにかく動作が速い。現時点では最速か？ まだベータ版なので今後の完成度の向上に期待がかかる。

4: Internet Explorer 7.0.5730.11
実行時間 : 1分20秒以上
途中でスクリプトの実行を中止するかの判断を求められる(距離と時間で２回）。実行は遅め。

5: Safari 3.1.2
実行時間 : 21.90秒
実行は速い。FireFox と同程度。表示もきれいで個人的にはインターフェイスなども気に入っている。

現時点では、GoogleChrome が最速で、使い勝手や Linux や MacOS などでも使用も考慮すると FireFox 3.x が無難な選択か。

距離か時間か？

全米の地図データを用いて開発中の高速ダイクストラ法で最短路を計算する。距離と時間の両方の基準で、計算した結果を GoogleMaps に投影したのが、この図になる。赤い方が移動距離最小の最短路で、青い方が移動時間最小の最短路である（ちなみに始点がサンフランシスコ Union Square Park で、終点が CIA 本部)。全米データで西から東までの大陸横断でも、距離と時間による最短路が随分と異なっていることがわかる。もちろんデータが正しければこれが本当に厳密な最短路になる。これは前処理無しのダイクストラ法なので、移動時間などのデータが動的に変化してもそのまま対応することができる。

glpk 4.31 v.s. lp_solve 5.5.0.12

昨日に続いて glpk と lp_solve の比較だが、lp_solve 5.5.0.13 は flex の問題で make 出来なかったので、lp_solve 5.5.0.12 のソースを用いる。昨日の実験は予め make されていた Linux 用の 5.5.0.13 のバイナリを用いているが、今日の結果は 5.5.0.12 をソースから自分で make してバイナリを作成した。

MIPLIB の問題では、かなり lp_solve の方が速いのだが、ファイル複製問題になると glpk の方が速い。この手の問題には glpk の方が向いているのだろうか。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

1: stein27.mps
glpk : 1.526s
lp_solve : 0.357s

2: stein45.mps
glpk : 4m35.837s
lp_solve : 15.640s

3: air06
glpk : 9.862s
lp_solve : 4.157s

4: rentacar
glpk : 5.518s
lp_solve : 8.013s

5: file_replication_0.0_test32.dat
glpk : 0.292s
lp_solve : 14.396s

6: min_rep_and_max_thput_0.0_test32.dat
glpk : 0.625s
lp_solve : 1.262s

glpk 4.31 v.s. lp_solve 5.5.0.13

glpk の最新版 4.31 と lp_solve の最新版 5.5.0.13 を少しだけ比較してみよう。これらの問題では lp_solve の方が優勢である。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

1: stein27.mps
glpk : 1.526s
lp_solve : 0.464s

2: stein45.mps
glpk : 4m35.837s
lp_solve : 19.901s

3: air06
glpk : 9.862s
lp_solve : 4.681s

4: rentacar
glpk : 5.518s
lp_solve : 9.228s

Ubuntu 8.0.4 と SDPA

Ubuntu も 8.0.4 になって随分と使いやすくなり、初心者に対する Linux としては非常に適している。デフォルトのインストールで使用できるアプリケーションはかなり少なめだが、apt-get などで後から追加することができるので、中級者以上では特に問題もない。SDPA 7.x + LAPACK 3.1.1 + GotoBLAS 1.26 も問題なく make & 実行することができた。よって今後は SDPA のサポート OS に Ubuntu も追加することにした。

最短路 Online Solver と GoogleMaps の連携

最短路 Online Solver と GoogleMaps の連携版の開発が進んだので公開を行っている。開発や公開の経緯、GoogleMaps と最短路 Online Solver のアルゴリズムなどの違いについてはこちらのブログに記載されている。最短路 Online Solver の方は DIMACS データを用いているので、高速道路と一般道路の違い、道幅や走りやすさなどは考慮されていない（データがあれば考慮することはできる）。最短路を求めた後に GoogleMaps で経路を確認するといろいろと面白いことがわかる。GoogleMaps の方は様々な事情と理由から厳密な最短路を求めていないが、高速に厳密最短路を求めるエンジンの開発というのは利用価値が多そうな感じだ。

ILOG と Dash

商用の数理計画ソルバーとしては大変有名な CPLEX (ILOG 社) と Xpress-MP (Dash 社)だが、共に本年に母体の会社ごと買収されている。IBM が ILOG を買収して、Fair Issac が Dash を買収したと報道されている。ユーザから見た場合には、特に現在のところ変化はないようだが、中長期的に何らかの変化が出てくるかもしれない。

日本OR学会 2009年春季研究発表会

日本オペーレーションズ・リサーチ学会の春季研究発表会が 2009年3月17日(火), 18日(水)に筑波大学 春日エリア（旧図書館情報大学）で開催されます。通常通りに発表を申し込んでもいいのですが、次回は企画セッションという試みがありまして、幾つか企画セッションのタイトルが公開されています。計算と最適化というセッションで発表してみたい方は連絡を下さい（希望者多数だと希望通りにならないこともあります）。
あと何人かの方にはこちらからご指名が行くかもしれませんので、よろしくお願いします。

CEATEC Japan 2008

今年も参加予定になっている CEATEC Japan 2008が９月３０日から１０月４日まで幕張メッセで開催される。ソフト系中心の展示会はあまり行くことは無いのだが、電子、通信、IT系などの部品やデバイスといったハード面では日本は世界トップなので、参加すると少なくとも今後１年ぐらいの傾向や計画などを見ることができる。2008年のテーマは”デジタルコンバージェンス、新たなるステージへ”であり、「人をつなぐ」、「技術をつなぐ」、「次世代へつなぐ」がキーワードになっている。
個人的にこういった展示会で展示を行う立場になったことが国内外で何回かある。展示の規模と内容にもよるが、準備と片付けで展示会の開催日数と同じくらいの時間がかかる。展示会の準備の日に周りを見ていると、たった数日間の展示のために非常に大きなステージを作ったり、看板を立てたり、装飾したりと大変な手間をかけるものだと感心した。片付けの日に再度見ていると、回収して次の展示のときなどに再利用するものも多いが、看板などは外してそのままゴミとして処理するので、処理されるゴミの量は驚くほど多かった。

Xeon 対 Opteron 対 Atom 対 Pentium M

以前にも行った比較だが、Pentium M 2.0GHz (ただし 32bit)を加えて実験を行う。GLPK は各マシンの実行で反復回数が異なるので参考程度まで。クロック周波数を考慮しても Xeon > Opteron > Pentium M >= Atom といった感じだろうか。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

○ Opteron
自作 PC
CPU : AMD Opteron 270 2.0GHz
メモリ : 4GB
OS : CentOS 5.2 for x86_64

○ Atom
MSI Wind PC
CPU : Intel Atom 230 1.6GHz
メモリ : 1GB
OS : Fedora 9 for x86_64

○ Pentium M
自作 PC
CPU : Pentium M 2.0GHz
メモリ : 1GB
OS : Vine Linux 4.2 for x86

1: GLPK 4.29 整数計画問題
○ stein27.mps
Xeon : 1.486s
Opteron : 2.982s
Atom : 10.033s
Pentium M : 3.992s
○ air06
Xeon : 6.810s
Opteron : 18.507s
Atom : 45.026s
Pentium M : 64.798s
○ min_rep_under_thput_39600.0_test18.dat(ファイル配置最適化問題)
Xeon : 3.984s
Opteron : 12.237s
Atom : 31.217s
Pentium M : 39.298s

2: 最短路問題
○ FLA 10 クエリ(データ名は最短路問題オンライン・ソルバーと同じ)
Xeon : 0.341s
Opteron : 1.318s
Atom : 2.929s
Pentium M : 2.405s
○ LKS 10 クエリ
Xeon : 0.811s
Opteron : 3.929s
Atom : 9.724s
Pentium M : 6.437s

3: SDP (半正定値計画問題) : SDPA 7.2.0 + GotoBLAS 1.26(Xeon & Opteron & Pentium M) or GotoBLAS 1.27(Atom) : 1 スレッド
○ mcp500-1.dat-s
Xeon : 3.970s
Opteron : 11.618s
Atom : 30.442s
Pentium M : 24.394s
○ theta5.dat-s
Xeon : 23.154s
Opteron : 69.083s
Atom : 184.620s
Pentium M : 119.425s
○ mater-4.dat-s
Xeon : 6.890s
Opteron : 13.257s
Atom : 30.635s
Pentium M : 20.134s