最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

Rank minimization

2009年08月31日 03時00分45秒 | Weblog
ISMP の発表を見ていて行列の Rank minimization の研究が流行っているように感じた。整数計画問題から SDP 緩和問題を作った場合には変数行列の Rank-1 条件が欠けている(緩和されている)。というわけで単に目的関数を最小化するだけではなく、同時に変数行列の Rank も最小化したらどうなるのかというのが興味があるところだが、まず理論的に何がわかるかが探られている。信号処理や画像処理などで用いられているということもあって、処理の速さも重要になる。
コメント
この記事をはてなブックマークに追加

KSMAP 合宿 in 明日香村

2009年08月30日 23時25分45秒 | Weblog
関西の若手によるORの研究会 KSMAP 主催で10月に以下の合宿が行われることになった。SCOPE のつくば合宿も新型インフルエンザによって開催が危ぶまれたこともあったが、秋にかけて新型インフルエンザが流行することが予想されるので、こちらの合宿が無事に行われることを願いたい。開催場所はつくばが大都会に見えるような所である。

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
日本オペレーションズ・リサーチ学会
研究部会『若手によるOR横断研究』
「若手研究交流会(KSMAP合宿 in 明日香村)」のご案内
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

本研究部会では,昨年に引き続いて今年も,異なる大学・企業に所属する
様々な研究領域の若手研究者が活発に交流することを目的としたセミナーを
企画しました.

今回は,参加者の皆様に交流の機会をより多く持っていただこうと考え,
日程を一日延ばして二泊三日としました.
本セミナーを通じて,大学・企業や研究領域の枠を超えた新たな出会いが
生まれることを期待しています.


日程:2009年10月10日(土)~ 10月12日(月)
場所:関西大学 飛鳥文化研究所(奈良県高市郡明日香村)
発表申込み締切: 2009年9月10日(木)
参加申込み締切: 2009年9月24日(木)

本研究交流会の詳細,ならびに参加申し込み等については
http://www-or.amp.i.kyoto-u.ac.jp/ksmap-camp/
をご覧ください.

※宿泊施設の収容人数に限りがあるため,申込人数に上限を設けさせて
頂きます.先着順となりますので,早めにご検討頂ければ幸いです.

※本研究交流会に関するお問い合わせの際は下記のメールアドレスを
ご利用ください.
実行委員会メールアドレス:ksmap-camp09@amp.i.kyoto-u.ac.jp

実行委員長:梅谷俊治(大阪大学)
実行委員:来嶋 秀治(京都大学),檀 寛成(関西大学),蓮池 隆(大阪大学)
林 俊介(京都大学),福永 拓郎(京都大学),増山 博之(京都大学)
コメント (2)
この記事をはてなブックマークに追加

AMD Opteron (Istanbul)

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

CPU : AMD Opteron 2435(2.6GHz / 6MB L3)x 2
Memory : 64GB(16 x 4GB / 800MHz)
HDD : 300GB(10,000RPM, SAS, 2.5inch)x 2 (RAID 1)
コメント
この記事をはてなブックマークに追加

SDPA とボトルネック

2009年08月28日 21時27分20秒 | Weblog
以前にもこちらのブログで取り上げた入力の問題の特性と SDPA のボトルネックとなる個所の表を一部更新した。前の表は 2007年11月24日のブログで取り上げている。変更点は n << m で問題が Sparse な時であるが、
旧表 : CHOLESKY (Schur complement 行列の Cholesky 分解)
新表 : CHOLESKY or Other O(n^3) parts
となる。
正確には n << m で、問題が Sparse のときに、Schur complement 行列が密になる場合には CHOLESKY がボトルネックになり、疎になる場合には Sparse Cholesky 分解が適用できる関係で Other O(n^3) parts がボトルネックとなる。
コメント
この記事をはてなブックマークに追加

イノベーションジャパン 2009 新技術説明会

2009年08月27日 20時47分56秒 | Weblog
イノベーションジャパン 2009 のホームページが更新された。展示会の方はパネルを作ったり、スタッフを揃えて常駐させたりと大変負担が大きいので、新技術説明会の方だけに参加申請を行った。このイノベーションジャパンの趣旨を考えると発表資料を公開するのは構わないと思うので、可能ならば近いうちにこちらから公開していきたい。
コメント
この記事をはてなブックマークに追加

QAPLIB と SDP 緩和

2009年08月26日 02時36分26秒 | Weblog
QAPLIB に Esc64a という問題があって、現時点での最良の上界は 116 になっている。詳しくは添付の図を参考にしていただきたいが、上界の値 116 は Simulated Annealing で求められているが、下界の値 105 は SDP 緩和で今回求めることが出来た。
ただし、この SDP 緩和問題は非常に数値的な性質が悪い。SDPA, CSDP, SDPT3, SeDuMi では最適解を求めることが出来なかった(添付の図を参照)。ただし SDPA-DD では高精度で最適解を求めることが出来た。もちろん SDPA-QD, SDPA-GMP でも可能だが、実行速度から判断すると SDPA-DD がお勧めとなる。
コメント
この記事をはてなブックマークに追加

オープンキャンパス

2009年08月25日 02時52分25秒 | Weblog
少し前だが、オープンキャンパスで学科別ガイダンスと模擬講義を合わせて一日で合計2時間話を行った。幸い両方とも評判は良かった。模擬講義(インターネット上のデータを用いた最適化)は講義後に質問もあったりして興味を持ってもらった高校生も多かったように思う。ちなみにほぼ同じ内容で普段講義を行っているが、こちらでの評判は良くない。やはり一旦最適化やコンピュータに興味が無い人を集めてしまうと、その後でいろいろと努力してもかなり厳しい。
コメント
この記事をはてなブックマークに追加

応用に役立つ50の最適化問題

2009年08月24日 02時44分11秒 | Weblog
応用に役立つ50の最適化問題という本がようやく朝倉書店から出版されることになった。基礎的な理論やアルゴリズムは他書に任せて、その代わりに他ではあまり触れられていない応用問題に焦点をあてている。

2章:線形計画問題
線形計画問題 包絡分析法 多目的(線形)計画問題 確率分布の推定 区分線形関数の最小化

3章:整数計画問題
整数計画問題 混合整数計画問題 ナップサック問題(→8章) 2次割当問題 施設配置問題(→6章) 巡回セールスマン問題 集合被覆問題(→6章) ロットサイズ決定問題 制約充足問題

4章:非線形計画問題
微分不可能な目的関数をもつ制約なし最適化問題 相補性問題 変分不等式問題 均衡制約付き数理計画問題 (金融工学)平均・分散モデル (金融工学)平均・絶対偏差モデル (金融工学)条件付きCVaR最小化問題 2次錐計画問題

5章:半正定値計画問題
半正定値計画問題 0-1整数計画問題 グラフ分割問題 システムと制御分野への半正定値計画問題の応用 ロバスト最適化問題 ロバスト線形計画問題ロバスト最短路問題 最小2乗法 ロバストチェビシェフ近似問題 多項式最適化問題 サポートベクターマシン 最小包囲楕円問題 双線形行列不等式

6章:集合被覆問題
集合被覆問題(→3章) 集合分割問題 配送計画問題 施設配置問題(→3章)

7章:勤務スケジューリング問題
乗務員スケジューリング問題 乗務パターン作成問題 乗務員勤務スケジュール作成問題 看護師スケジューリング問題

8章:切出し・詰込み問題
ナップサック問題(→3章) ビンパッキング問題 1次元資材切出し問題 長方形詰込み問題 (長方形)ストリップパッキング問題 (長方形)面積最小化問題 (長方形)パレット積込み問題 多角形詰込み問題

9章:最適化問題に対する情報技術の適用
量子化学分野における半正定値計画問題の応用 蛋白質立体構造解析
コメント (4)
この記事をはてなブックマークに追加

ISMP 2009

2009年08月23日 03時03分57秒 | Weblog
8月23日からアメリカ、シカゴで開催される国際会議 ISMP 2009 に参加する。3年に一度開催される数理計画問題を中心となっているが、組合せ最適化系も多数の発表があり、実際には最適化問題に関する非常に大きな規模の国際会議になっている。発表のセッションだけでもまるまる5日間もあって、全部参加するのは結構大変である。ここ数年米国入国が厳しくなっていて(事前承認や生体認証など)、国籍によっては入国自体が難しいこともあるので、米国開催の国際会議は減っているらしい。
コメント
この記事をはてなブックマークに追加

新型 PS3

2009年08月22日 20時16分25秒 | Weblog
PS3 の新型機が9月に発売されて、現行モデルより1万円安くなるそうだ。HDD も 120GB に増えるのだが、メモリ量などに変化は無い。USB のコネクタが減るのは仕方が無いとしても、「他のシステムのインストール」機能が削除されてしまうので、Lunux の HDD へのインストールが出来なくなるだろう。PS2 のソフトも動かないので、やはり初期の PS3 の方が良い(でも無茶苦茶熱くなる)。
コメント (2)
この記事をはてなブックマークに追加

逆行列だけ4倍精度

2009年08月21日 22時18分17秒 | Weblog
現在、変数行列 Z の逆行列 Z^{-1} の計算だけを4倍精度(正確には double-double)で行うことを試している。
1:逆行列だけなので、Cholesky 分解の補正は行っていない。つまり、Cholesky 分解時におけるエラーの発生は防げていない。
2:4倍精度の計算は並列化も最適化も行われていないので、特に速度面ではかなり遅くなっている。

○通常の SDPA 7.3.1
phase.value = pFEAS
Iteration = 15
mu = +7.8353935386985536e-06
relative gap = +7.6347894084098359e-06
gap = +3.9167961774637661e-03
digits = +5.1172029376549588e+00
objValPrimal = -5.1301758515989809e+02
objValDual = -5.1302150195607555e+02
p.feas.error = +1.8189894035458565e-12
d.feas.error = +4.2773426022213457e-06
total time = 2.240069

○逆行列の計算だけを4倍精度で行った SDPA 7.3.1
phase.value = pdOPT
Iteration = 18
mu = +5.6723802117630842e-08
relative gap = +5.4951808894764425e-08
gap = +2.8191245974085177e-05
digits = +7.2600180069696192e+00
objValPrimal = -5.1301760154052249e+02
objValDual = -5.1301762973176847e+02
p.feas.error = +1.3642420526593924e-12
d.feas.error = +4.6277648380055325e-11
total time = 48.697048
コメント
この記事をはてなブックマークに追加

MATLAB の自動実行

2009年08月20日 21時57分56秒 | Weblog
SeDuMi の自動実行用のファイルを作ってみた。あとは matlab -r autoSedumi とするだけで良い。

1: install_sedumi2 では fromsdpa 関数への path を通している
2: ./data/bench 以下に実行ファイル(*.dat-s)がある
3: pars.errors=1 で DIMACS errors を書き込む
4: tic, toc で実行時間(実時間)も書き込む

function autoSedumi
install_sedumi2;
pars.errors=1;

files = dir('./data/bench/*.dat-s');

for file_index = 1:length(files)

tic;
file_name = sprintf('./data/bench/%s', files(file_index).name);
result_name = sprintf('%s.result',file_name);
pars.fid = fopen(result_name,'w');
fprintf('Reading %sn',file_name);
[At,b,c,K] = fromsdpa(file_name);
fprintf('Solving %sn',file_name);
[x,y,info] = sedumi(At,b,c,K,pars);
t = toc;
fprintf(pars.fid, 'Execution time (real) = %fn', t);

end

コメント
この記事をはてなブックマークに追加

GATEWAY 2000

2009年08月19日 18時03分45秒 | Weblog
昔、山梨大学の工学部に発酵生産学科(現 生命工学科) があったが、今は山梨大学大学院医学工学総合研究部附属ワイン科学研究センターが中心になってワインの研究が行われている。アルコールの生産には免許が必要だが、こちらのセンターはもちろん保持しているので、ワインの醸造なども行われている。
こちらのホームページで非常に懐かしい GATEWAY 2000 のマシンを見つけた。この前部の独特な曲線が GATEWAY 2000 の特徴でまだ現役で動作しているのだろうか?特定の観測機器などを用いる場合では、いまだに PC-9801 などを用いている所も少なくない(いまだに結構見かける)。
コメント (2)
この記事をはてなブックマークに追加

SDP ソルバー比較実験結果

2009年08月18日 02時14分48秒 | Weblog
様々なベンチマーク(SDPLIB や DIMACS など)や新しい SDP の応用問題を用いて SDPA, CSDP, SDPT3, SeDuMi の比較実験を行った。MATLAB の方は自動実験が出来ないので、結構手間がかかってしまった。実験結果はこちらから入手できるようにした。興味のある方は持って行っていただきたい。
コメント (2)
この記事をはてなブックマークに追加

MATLAB R2008 と R2009 : マルチスレッド計算

2009年08月17日 01時53分05秒 | Weblog
MATLAB R2008 と R2009 でマルチスレッド計算について少しだけ調べてみた。簡単な行列積の計算で GFLOPS の値を推定してみる。性能的には MATLAB R2008 よりも R2009 の方が少し上がっているのだが、R2009 の方では環境変数 OMP_NUM_THREADS に関係なく、8 スレッドで計算が行われているようだ。

>> n=4000; A=randn(n); B=randn(n);
>> tic; C=A*B; t=toc, GFLOPS=2*n^3/t*1e-9

1: MATLAB R2008
1-1: OMP_NUM_THREADS 未定義
GFLOPS = 7.0436

1-2: OMP_NUM_THREADS = 1
GFLOPS = 7.0462

1-3: OMP_NUM_THREADS = 8
GFLOPS = 51.3471

2: MATLAB R2009
2-1: OMP_NUM_THREADS 未定義
GFLOPS = 53.6599

2-2: OMP_NUM_THREADS = 1
GFLOPS = 54.6816

2-3: OMP_NUM_THREADS = 8
GFLOPS = 54.3214

○実行マシン:Intel Xeon 5550 (2.66GHz) x 2 : メモリ 72GB : Fedora 11 for x86_64
コメント (2)
この記事をはてなブックマークに追加