ISMP の発表を見ていて行列の Rank minimization の研究が流行っているように感じた。整数計画問題から SDP 緩和問題を作った場合には変数行列の Rank-1 条件が欠けている（緩和されている）。というわけで単に目的関数を最小化するだけではなく、同時に変数行列の Rank も最小化したらどうなるのかというのが興味があるところだが、まず理論的に何がわかるかが探られている。信号処理や画像処理などで用いられているということもあって、処理の速さも重要になる。
関西の若手によるORの研究会 KSMAP 主催で１０月に以下の合宿が行われることになった。SCOPE のつくば合宿も新型インフルエンザによって開催が危ぶまれたこともあったが、秋にかけて新型インフルエンザが流行することが予想されるので、こちらの合宿が無事に行われることを願いたい。開催場所はつくばが大都会に見えるような所である。
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
日本オペレーションズ・リサーチ学会
研究部会『若手によるＯＲ横断研究』
「若手研究交流会(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
実行委員長：梅谷俊治（大阪大学）
実行委員：来嶋 秀治（京都大学），檀 寛成（関西大学），蓮池 隆（大阪大学）
林 俊介（京都大学），福永 拓郎（京都大学），増山 博之（京都大学）
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
日本オペレーションズ・リサーチ学会
研究部会『若手によるＯＲ横断研究』
「若手研究交流会(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
実行委員長：梅谷俊治（大阪大学）
実行委員：来嶋 秀治（京都大学），檀 寛成（関西大学），蓮池 隆（大阪大学）
林 俊介（京都大学），福永 拓郎（京都大学），増山 博之（京都大学）
以下のスペックの 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)
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 のボトルネックとなる個所の表を一部更新した。前の表は 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 がボトルネックとなる。
旧表 : CHOLESKY (Schur complement 行列の Cholesky 分解)
新表 : CHOLESKY or Other O(n^3) parts
となる。
正確には n << m で、問題が Sparse のときに、Schur complement 行列が密になる場合には CHOLESKY がボトルネックになり、疎になる場合には Sparse Cholesky 分解が適用できる関係で Other O(n^3) parts がボトルネックとなる。
QAPLIB に Esc64a という問題があって、現時点での最良の上界は 116 になっている。詳しくは添付の図を参考にしていただきたいが、上界の値 116 は Simulated Annealing で求められているが、下界の値 105 は SDP 緩和で今回求めることが出来た。
ただし、この SDP 緩和問題は非常に数値的な性質が悪い。SDPA, CSDP, SDPT3, SeDuMi では最適解を求めることが出来なかった(添付の図を参照)。ただし SDPA-DD では高精度で最適解を求めることが出来た。もちろん SDPA-QD, SDPA-GMP でも可能だが、実行速度から判断すると SDPA-DD がお勧めとなる。
ただし、この SDP 緩和問題は非常に数値的な性質が悪い。SDPA, CSDP, SDPT3, SeDuMi では最適解を求めることが出来なかった(添付の図を参照)。ただし SDPA-DD では高精度で最適解を求めることが出来た。もちろん SDPA-QD, SDPA-GMP でも可能だが、実行速度から判断すると SDPA-DD がお勧めとなる。
少し前だが、オープンキャンパスで学科別ガイダンスと模擬講義を合わせて一日で合計２時間話を行った。幸い両方とも評判は良かった。模擬講義(インターネット上のデータを用いた最適化)は講義後に質問もあったりして興味を持ってもらった高校生も多かったように思う。ちなみにほぼ同じ内容で普段講義を行っているが、こちらでの評判は良くない。やはり一旦最適化やコンピュータに興味が無い人を集めてしまうと、その後でいろいろと努力してもかなり厳しい。
応用に役立つ50の最適化問題という本がようやく朝倉書店から出版されることになった。基礎的な理論やアルゴリズムは他書に任せて、その代わりに他ではあまり触れられていない応用問題に焦点をあてている。
2章：線形計画問題
線形計画問題 包絡分析法 多目的(線形)計画問題 確率分布の推定 区分線形関数の最小化
3章：整数計画問題
整数計画問題 混合整数計画問題 ナップサック問題(→8章) 2次割当問題 施設配置問題(→6章) 巡回セールスマン問題 集合被覆問題(→6章) ロットサイズ決定問題 制約充足問題
4章：非線形計画問題
微分不可能な目的関数をもつ制約なし最適化問題 相補性問題 変分不等式問題 均衡制約付き数理計画問題 (金融工学)平均・分散モデル (金融工学)平均・絶対偏差モデル (金融工学)条件付きCVaR最小化問題 2次錐計画問題
5章：半正定値計画問題
半正定値計画問題 0-1整数計画問題 グラフ分割問題 システムと制御分野への半正定値計画問題の応用 ロバスト最適化問題 ロバスト線形計画問題ロバスト最短路問題 最小２乗法 ロバストチェビシェフ近似問題 多項式最適化問題 サポートベクターマシン 最小包囲楕円問題 双線形行列不等式
6章：集合被覆問題
集合被覆問題(→3章) 集合分割問題 配送計画問題 施設配置問題(→3章)
7章：勤務スケジューリング問題
乗務員スケジューリング問題 乗務パターン作成問題 乗務員勤務スケジュール作成問題 看護師スケジューリング問題
8章：切出し・詰込み問題
ナップサック問題(→3章) ビンパッキング問題 １次元資材切出し問題 長方形詰込み問題 (長方形)ストリップパッキング問題 (長方形)面積最小化問題 (長方形)パレット積込み問題 多角形詰込み問題
9章：最適化問題に対する情報技術の適用
量子化学分野における半正定値計画問題の応用 蛋白質立体構造解析
2章：線形計画問題
線形計画問題 包絡分析法 多目的(線形)計画問題 確率分布の推定 区分線形関数の最小化
3章：整数計画問題
整数計画問題 混合整数計画問題 ナップサック問題(→8章) 2次割当問題 施設配置問題(→6章) 巡回セールスマン問題 集合被覆問題(→6章) ロットサイズ決定問題 制約充足問題
4章：非線形計画問題
微分不可能な目的関数をもつ制約なし最適化問題 相補性問題 変分不等式問題 均衡制約付き数理計画問題 (金融工学)平均・分散モデル (金融工学)平均・絶対偏差モデル (金融工学)条件付きCVaR最小化問題 2次錐計画問題
5章：半正定値計画問題
半正定値計画問題 0-1整数計画問題 グラフ分割問題 システムと制御分野への半正定値計画問題の応用 ロバスト最適化問題 ロバスト線形計画問題ロバスト最短路問題 最小２乗法 ロバストチェビシェフ近似問題 多項式最適化問題 サポートベクターマシン 最小包囲楕円問題 双線形行列不等式
6章：集合被覆問題
集合被覆問題(→3章) 集合分割問題 配送計画問題 施設配置問題(→3章)
7章：勤務スケジューリング問題
乗務員スケジューリング問題 乗務パターン作成問題 乗務員勤務スケジュール作成問題 看護師スケジューリング問題
8章：切出し・詰込み問題
ナップサック問題(→3章) ビンパッキング問題 １次元資材切出し問題 長方形詰込み問題 (長方形)ストリップパッキング問題 (長方形)面積最小化問題 (長方形)パレット積込み問題 多角形詰込み問題
9章：最適化問題に対する情報技術の適用
量子化学分野における半正定値計画問題の応用 蛋白質立体構造解析
8月23日からアメリカ、シカゴで開催される国際会議 ISMP 2009 に参加する。３年に一度開催される数理計画問題を中心となっているが、組合せ最適化系も多数の発表があり、実際には最適化問題に関する非常に大きな規模の国際会議になっている。発表のセッションだけでもまるまる５日間もあって、全部参加するのは結構大変である。ここ数年米国入国が厳しくなっていて（事前承認や生体認証など)、国籍によっては入国自体が難しいこともあるので、米国開催の国際会議は減っているらしい。
PS3 の新型機が９月に発売されて、現行モデルより１万円安くなるそうだ。HDD も 120GB に増えるのだが、メモリ量などに変化は無い。USB のコネクタが減るのは仕方が無いとしても、「他のシステムのインストール」機能が削除されてしまうので、Lunux の HDD へのインストールが出来なくなるだろう。PS2 のソフトも動かないので、やはり初期の PS3 の方が良い(でも無茶苦茶熱くなる)。
現在、変数行列 Z の逆行列 Z^{-1} の計算だけを４倍精度(正確には double-double)で行うことを試している。
１：逆行列だけなので、Cholesky 分解の補正は行っていない。つまり、Cholesky 分解時におけるエラーの発生は防げていない。
２：４倍精度の計算は並列化も最適化も行われていないので、特に速度面ではかなり遅くなっている。
○通常の 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
○逆行列の計算だけを４倍精度で行った 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
１：逆行列だけなので、Cholesky 分解の補正は行っていない。つまり、Cholesky 分解時におけるエラーの発生は防げていない。
２：４倍精度の計算は並列化も最適化も行われていないので、特に速度面ではかなり遅くなっている。
○通常の 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
○逆行列の計算だけを４倍精度で行った 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
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
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 のマシンを見つけた。この前部の独特な曲線が GATEWAY 2000 の特徴でまだ現役で動作しているのだろうか？特定の観測機器などを用いる場合では、いまだに PC-9801 などを用いている所も少なくない（いまだに結構見かける)。
こちらのホームページで非常に懐かしい GATEWAY 2000 のマシンを見つけた。この前部の独特な曲線が GATEWAY 2000 の特徴でまだ現役で動作しているのだろうか？特定の観測機器などを用いる場合では、いまだに PC-9801 などを用いている所も少なくない（いまだに結構見かける)。
様々なベンチマーク(SDPLIB や DIMACS など)や新しい SDP の応用問題を用いて SDPA, CSDP, SDPT3, SeDuMi の比較実験を行った。MATLAB の方は自動実験が出来ないので、結構手間がかかってしまった。実験結果はこちらから入手できるようにした。興味のある方は持って行っていただきたい。
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
>> 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
アクセス
トータル
