ISMP の発表を見ていて行列の Rank minimization の研究が流行っているように感じた。整数計画問題から SDP 緩和問題を作った場合には変数行列の Rank-1 条件が欠けている（緩和されている）。というわけで単に目的関数を最小化するだけではなく、同時に変数…

関西の若手によるORの研究会 KSMAP 主催で１０月に以下の合宿が行われることになった。SCOPE のつくば合宿も新型インフルエンザによって開催が危ぶまれたこともあったが、秋にかけて新型インフルエンザが流行することが予想されるので、こちらの合宿が無事に…

以下のスペックの Dell PowerEdge サーバが研究室に到着したが、海外出張等があって、まだ何もしていない。昨年の暮れに勝った AMD Opteron (Barcelona) の調子が良くないので、SDPA Online Solver の実行マシンはこちらの Istanbul に交替させたいと思う。 …

以前にもこちらのブログで取り上げた入力の問題の特性と SDPA のボトルネックとなる個所の表を一部更新した。前の表は 2007年11月24日のブログで取り上げている。変更点は n 旧表 : CHOLESKY (Schur complement 行列の Cholesky 分解) 新表 : CHOLESKY or Ot…

イノベーションジャパン 2009 のホームページが更新された。展示会の方はパネルを作ったり、スタッフを揃えて常駐させたりと大変負担が大きいので、新技術説明会の方だけに参加申請を行った。このイノベーションジャパンの趣旨を考えると発表資料を公開する…

QAPLIB に Esc64a という問題があって、現時点での最良の上界は 116 になっている。詳しくは添付の図を参考にしていただきたいが、上界の値 116 は Simulated Annealing で求められているが、下界の値 105 は SDP 緩和で今回求めることが出来た。 ただし、こ…

少し前だが、オープンキャンパスで学科別ガイダンスと模擬講義を合わせて一日で合計２時間話を行った。幸い両方とも評判は良かった。模擬講義(インターネット上のデータを用いた最適化)は講義後に質問もあったりして興味を持ってもらった高校生も多かったよ…

応用に役立つ50の最適化問題という本がようやく朝倉書店から出版されることになった。基礎的な理論やアルゴリズムは他書に任せて、その代わりに他ではあまり触れられていない応用問題に焦点をあてている。 2章：線形計画問題 線形計画問題 包絡分析法 多目的…

8月23日からアメリカ、シカゴで開催される国際会議 ISMP 2009 に参加する。３年に一度開催される数理計画問題を中心となっているが、組合せ最適化系も多数の発表があり、実際には最適化問題に関する非常に大きな規模の国際会議になっている。発表のセッショ…

PS3 の新型機が９月に発売されて、現行モデルより１万円安くなるそうだ。HDD も 120GB に増えるのだが、メモリ量などに変化は無い。USB のコネクタが減るのは仕方が無いとしても、「他のシステムのインストール」機能が削除されてしまうので、Lunux の HDD …

現在、変数行列 Z の逆行列 Z^{-1} の計算だけを４倍精度(正確には double-double)で行うことを試している。 １：逆行列だけなので、Cholesky 分解の補正は行っていない。つまり、Cholesky 分解時におけるエラーの発生は防げていない。 ２：４倍精度の計算は…

SeDuMi の自動実行用のファイルを作ってみた。あとは matlab -r autoSedumi とするだけで良い。 1: install_sedumi2 では fromsdpa 関数への path を通している 2: ./data/bench 以下に実行ファイル(*.dat-s)がある 3: pars.errors=1 で DIMACS errors を書…

昔、山梨大学の工学部に発酵生産学科(現 生命工学科) があったが、今は山梨大学大学院医学工学総合研究部附属ワイン科学研究センターが中心になってワインの研究が行われている。アルコールの生産には免許が必要だが、こちらのセンターはもちろん保持してい…

様々なベンチマーク(SDPLIB や DIMACS など)や新しい SDP の応用問題を用いて SDPA, CSDP, SDPT3, SeDuMi の比較実験を行った。MATLAB の方は自動実験が出来ないので、結構手間がかかってしまった。実験結果はこちらから入手できるようにした。興味のある方…

MATLAB R2008 と R2009 でマルチスレッド計算について少しだけ調べてみた。簡単な行列積の計算で GFLOPS の値を推定してみる。性能的には MATLAB R2008 よりも R2009 の方が少し上がっているのだが、R2009 の方では環境変数 OMP_NUM_THREADS に関係なく、8 …

代表的な SDP ソルバーである SDPA, CSDP, SDPT3, SeDuMi で比較実験を行う(他にも PENSDP, DSDP, SDPLR などもある)。 1: SDPA 7.3.1 : BLAS (GotoBLAS, Intel MKL, ATLAS 等)と内部の計算(Schur complement 行列等 : pthread)の計算がマルチスレッドで行わ…

QAPLIB に含まれている tai30a という問題があるが、いまだに最適解は求められていない（正確にいうと現在の上界が最適解である保証がされていない）。これの DNN 緩和問題を作って SDPARA で解くことを想定しているのだが、16 ノードでは 1 ノードあたりメ…

日本一大きな書店はジュンク堂の池袋店(2001坪)だと思っていたのだが、売り場面積では札幌のコーチャンフォーミュンヘン大橋店(2120坪)の方が大きいようだ。ただし、文具や CD/DVD 等の売り場もあるので、書籍のみではやはりジュンク堂池袋店の方が多い(コー…

オランダからの頼まれ仕事で送ってもらった問題を SDPA-DD で解いただけなのだが、以下の QAPLIB の下界(LB) の更新に成功しているようだ。具体的には以下の３問で、今回の下界算出手法は a semidefinite programming bound: (SDP1) [DKSo:07] と呼ばれてい…

以下のように DNN (SDP制約 + 非負制約)新定式化の効果は非常に良い（精度面と速度面)。問題は QAP の nug20 になる。新定式化の方では目的関数をスケーリングしているので、3.44400000e+03 x 7.2745400147598e-01 = 2505.4 ということで目的関数もほぼ合っ…

旧 SDPA サーバは修理を依頼して、いったん直ったように見えてまた壊れたので、再度修理を依頼した。当初の故障原因は RAID コントローラーにあったのかもしれないが、二回目の故障は BIOS 画面さえ出ないという現象なので明らかに CPU(AMD Barcelona) が怪…

某スパコンを１ノード借りて SDPARA, GotoBLAS, MUMPS, BLACS, ScaLAPACK の make を行ってみた。純正のコンパイラ及び MPI 以外はサポート外ということで、何とか純正コンパイラでの make を頑張ってみた。ただし、各ノード内のみで動作するソフトウェアは …

オランダの研究者の方からある SDP のファイルを送ってもらったのだが、これが非常に解きにくい問題で、通常のソルバー(SDPA, CSDP, SDPT3, SeDuMi)では全て高精度で解けなかったばかりか、その答え自体が全てのソルバーで違っていた。こういう時のために SD…

前回のブレードサーバの件で具体的に見積もり額いくらですか？と聞かれたのだが、私的な見積もり額をインターネットに出すわけにはいかなので、昨年調達した同規模のクラスタの約半分ということにしておこう。実際にはいろいろと追加していって、もう少し高…

以前からブレードサーバ買いませんかと勧誘されていたのだが、見積りをしてみると意外と安くはないので、通常のノード型のサーバを購入してきた。今のクラスタでは1ノードが 5U なので、16ノード(32CPU)で合計 5U x 16 = 90U のラックが必要になる。ところが…

12年前ぐらいに作った時間枠付き配送計画問題に対する Tabu Search の C++ のプログラムがある。単純なピストン型の初期解や GRASP などのプログラムも含まれるが、k-d tree などの外部プログラムも利用している。これを何故か Excel の VBA に変換して再利…

今はこちらの SDPA クラスタで SDPARA 7.3.1 の大規模な数値実験を行っている。SDPARA 7.3.1 もそろそろ公開しても良いだろう。SDPA 7.3.1 も様々なベンチマーク問題まで対象を広げて実験を行っている。速度面でもまだまだ改善の余地があるのだが、次には精…

オーム社から Excel で学ぶシリーズが多数出版されているので、オペレーションズ・リサーチ関係を幾つか抜き出してみた。 Excelで学ぶ経営科学 Excelで学ぶ遺伝的アルゴリズム Excelで学ぶ意思決定論 Excelで学ぶデータマイニング入門 Excelで学ぶデリバティ…

文部科学省の基準では 1.5TFlops 以上をスーパーコンピュータという定義をしているそうだ。スーパーコンピュータとして認定されると調達基準などが変わる（制約が増える）ということなので、別に良いことがあるわけではないようだ(本当はもっと複雑だが)。Te…

イノベーションジャパン 2009 に参加することになった。新技術説明会に出る予定で題材は"大規模最短路問題に対する高速&高性能計算システム"になっている。 会期 2009年9月16日（水）～18日（金）10:00～18:00 ※9月18日は17:00終了 会場 東京国際フォーラム…