ファイル配置最適化問題に対して MIP（混合整数計画問題) と LP(線形計画問題) の解を比較する。ちなみに MIP の方は変数に binary 条件(0 か 1)が付いていて、LP の方は 0 から 1 の間の実数条件が付いている。少し見にくいのだが、例えば MIP の最適解では…

TSPLIB に pcb1173 という問題があるが、これが手頃な大きさなので delaunay グラフ(添付の図を参照)を作って、max cut 問題に対する SDP 緩和問題を作る。何故こんなことをしているかと言うと現在 SDP の疎性に関する研究を行っているからである。疎性を利…

ソニーの PSP と 任天堂の DS のスペックを調べると以下の通り。 PSP CPU: MIPS R4000×2, 333MHz : 浮動小数点演算能力：2.6Gflops（333MHz駆動時） メモリ 32MB (最新型は 64MB) DS CPU: ARM946E-S 67MHz + ARM7TDMI 33MHz メモリ 4MB これでも昔（1990年代…

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

GoogleMaps 上で始点と終点を入力 → opt.indsys.chuo-u.ac.jp 上のダイクストラ法のプログラムで移動距離と移動時間に関する最短路を計算する → GoogleMaps 上で結果を表示という Online Solver をこちらから公開中である。もちろん無料なので、いろいろと試…

最短路 Online Solver が GoogleMaps と連携を開始したので、様々なブラウザでの動作を検証してみよう(OS は Windows XP 32bit を使用)。Online Solver 自体は毎日改善＆変更中なのでバグや不具合もあるが少しずつ修正していく予定だ。全米データで東海岸か…

全米の地図データを用いて開発中の高速ダイクストラ法で最短路を計算する。距離と時間の両方の基準で、計算した結果を GoogleMaps に投影したのが、この図になる。赤い方が移動距離最小の最短路で、青い方が移動時間最小の最短路である（ちなみに始点がサン…

昨日に続いて 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 を…

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 …

Ubuntu も 8.0.4 になって随分と使いやすくなり、初心者に対する Linux としては非常に適している。デフォルトのインストールで使用できるアプリケーションはかなり少なめだが、apt-get などで後から追加することができるので、中級者以上では特に問題もない…

最短路 Online Solver と GoogleMaps の連携版の開発が進んだので公開を行っている。開発や公開の経緯、GoogleMaps と最短路 Online Solver のアルゴリズムなどの違いについてはこちらのブログに記載されている。最短路 Online Solver の方は DIMACS データ…

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

日本オペーレーションズ・リサーチ学会の春季研究発表会が 2009年3月17日(火), 18日(水)に筑波大学 春日エリア（旧図書館情報大学）で開催されます。通常通りに発表を申し込んでもいいのですが、次回は企画セッションという試みがありまして、幾つか企画セッ…

今年も参加予定になっている CEATEC Japan 2008が９月３０日から１０月４日まで幕張メッセで開催される。ソフト系中心の展示会はあまり行くことは無いのだが、電子、通信、IT系などの部品やデバイスといったハード面では日本は世界トップなので、参加すると…

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

長年使用した扇風機のモーター、コード、コンデンサー等の電気部品の経年劣化による発煙・発火事件が報告されている。自宅の部屋では三菱電機製の D30-GX という1982 年製の扇風機が現役で稼働している。昔の電器製品は幸か不幸か壊れないので、買い換えるこ…

VIA から発表されている CPU Nano は Intel Atom の対抗馬と見られている。Atom は内部の回路を簡単にして、インオーダーと２命令同時実行にしているので、ご先祖様の Pentium に近い構造になっている。整数演算と単精度演算はそれなりに性能が出るが、倍精…

SDPA 7.x は公開中だが、SDPARA 7.x とは何ですか？という質問を何件か頂いた（国内外から）。SDPARA 1.x をベースにして、現在様々な改良を加えているソースファイルなので、しばらく公開は行わない予定(SDPA Online Solver では随時公開する）。今後の開発…

近日中に SDPA 7.2.0 が公開になる予定。ソース自体はほぼ完成済みだが、マニュアル整備などの問題があるので公開まではもう少しかかる。ソース中身は結構変更されているが、ユーザの観点から見ると SDPA 6.x のように callable library が使えるようになる…

仕事（国際会議）で台湾に行くことになり、台湾高鐵 HSR（通称：台湾新幹線）で移動した。切符は売り場に並んでもいいのだが、タッチパネルの自動券売機の方が簡単で速い。漢字は共通なものが多いのだが、やはり英語の方がわかりやすい。実際に乗ってみると…

numactl コマンドを用いて以下のように 16, 32, 64, 128 プロセスで SDPARA を実行してみよう。問題(SDP)は非常に疎なものを選んでいるので、Schur complemet matrix は全て F3 式で計算を行う。 1: time mpiexec -n 16 numactl --physcpubind=0 ./sdpara.mp…

今回導入した SDPA クラスタだが、1 ノードあたりで 2 CPU, 8 コアになっている。 ●新 SDPA クラスタ (2008年) 16 Nodes, 32 CPUs, 128 CPU cores; CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node Memory : 48GB / node HDD : 6TB(RAID 5) / node N…

Xeon と比べればだいぶ性能的に見劣りする Atom。しかし、一昔（三年前）の Opteron とならばいい勝負をすると思っていたのだが、さすがは Opteron であって、以下のように Opteron 270 とAtom 230 にはかなりの性能差がある。やはり Atom というのは、Celer…

近所の中古屋で写真のハードが売られていた（在庫は２台もあった）。わかる人は見ればわかるので説明不要だが、定価が高い割には (39,800円)、対応ソフトが極端に少なく期待外れで終わったハードだった。中古のゲームソフトの中には電池などが入っている場合…

SDPA クラスタでの SDPARA の実験 その３、その４と非常に大規模な SDP を解いたときの結果を掲載したが、要点は以下の通り。 1: 計算機環境が異なるが、２年前に２４日かかった計算が２６時間ほどで終了した。 2: 反復回数は減っているが、精度はやや上がっ…

図に示したブロック対角構造を持った非常に大きな SDP を SDPA クラスタで解いた結果を示す（もちろん SDPARA を用いる）。 問題名 : H2O.1A1.DZ.pqgt1t2p.dat-s 2: SDPA クラスタ CPU : Xeon 5460 3.16GHz メモリ : 48GB 64 CPU を用いて実行時間は 94479.5…

図に示したブロック対角構造を持った非常に大きな SDP を SDPA クラスタで解いた結果を示す（もちろん SDPARA を用いる）。参考までに以前 AIST Super Cluster (ASC) M-64 で解いた結果を始めに示す。 問題名 : H2O.1A1.DZ.pqgt1t2p.dat-s 1: ASC M-64 クラ…

SDPARA では SCM(Schur Complement Matrix) の Cholesky 分解のときに ScaLapack などを利用している。そこで図のような SCM の二次元分割と並列計算を採用している。2003 年ではこのブロックサイズを 40 にしていたが、最近ではさらに大きな値が良いようだ…

SDPARA になるとパラメータκの値を決め方が難しくなる。まずは図の説明から。二つの割と大き目の SDP を用いる(CH4, LiOH)。横軸はκの値、縦軸は１反復あたりの実行時間を示している。128x1 とは 128 プロセス x 1 スレッド、32x4 とは 32 プロセス x 4 スレ…

SDPA と SDPARA における重要なパラメータにκというのがある。簡単に説明はできないので、興味のある方は図の説明を見ていただくとして、行列データ中にどのくらい非零要素があれば、密(Dense)あるいは疎(Sparse)とみなすべきかという決定を行うためのパラメ…