Excel で学ぶ OR ：発売日

Excel で学ぶ OR はすでに入稿が終了したので、７月２２日頃に書店に並ぶ予定です。

Excel で学ぶ OR
Excelを使いながらORの具体例、数値例を学ぶ!!
ORとはオペレーションズリサーチ（Operations Research）のことで数学・統計モデルを使って諸問題を解決していく手法です。本書では、第1部で基本的なツール（数理計画法とシミュレーション）を学んだ後、第2部で具体的な問題を扱っていきます。全体的に、OR（オペレーションズリサーチ）の教科書で扱われているような古典的な問題は少なめにして、なるべく社会人、大学生に興味が持てる新しい問題を扱っています。また、解析的な方法論はなるべく少なくしてExcelなどを活用する手法に重点を置いていきます。「簡単な具体例→一般化」の流れを徹底して解説していきます。
★このような方におすすめ
経営工学関連学科の学生
経営戦略に関心のある社会人
主要目次

OR概論/本書の使い方
第1部　基本編―ORの基本的なツールを学ぶ
第1章　数理最適化
第2章　シミュレーション
第2部　応用編―具体的な問題例を通じて学ぶ
第3章　都市・交通のデザインとネットワーク概論
第4章　計画、運用のためのモデルとサプライチェイン最適化
第5章　予測・検証・発見のための最適化モデルとデータマイニング
第6章　投資効率評価とDEA
第7章　不確実性下の意思決定とファイナンス理論
付録

第14回情報論的学習理論ワークショップ

11月9日から11日までの間に以下の IBIS ワークショップが開催されることになりました。機械学習系の研究者が集うワークショップですが、最適化も強く関連していますし、最近では制御系、機械学習系との連携が増えてきています。

第14回情報論的学習理論ワークショップ, 2011.11.9～11, 奈良女子大学（奈良市）

ホームページ： http://ibisml.org/ibis2011/
開催日時：2011.11.9～11
開催場所：奈良女子大学（奈良市）

Turbo Boost on Intel Xeon X5670 その３

以下の計算機だが、16 ノード x 12 コア & Turbo Boost 時に以下のような爆音となる。しかし、16 ノード x 6 コア & Turbo Boost では、そんなにうるさくはない。もっと少ないノード数になると計算しているのかどうかわからないレベルの騒音となっている。

○ OPT クラスタ
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.6 for x86_64



Turbo Boost 中のビデオ：3GP 形式 15MB

Barcelona 2048 コア v.s. Westmere-EP 192コア

SDPARA を以下の二つの計算機(Barcelona 2048 コアと Westmere-EP 192コア)で実行したときの速度の比較。環境等で異なる面も多いので参考程度の情報。それでもコア数で 10 倍以上差があっても Westmere-EP 192コア の方が速いというのは意外な結果になった。

○問題：CH2.1A1.DZ.pqgt1t2p.dat-s
○ Barcelona 2048コア(京大T2K) : 26656.16秒
○ Westmere-EP 192コア(OPT) : 26297.09秒

○問題：NH2-.1A1.DZ.pqgt1t2p.dat-s
○ Barcelona 2048コア(京大T2K) : 27949.12秒
○ Westmere-EP 192コア(OPT) : 23748.89秒

○問題：CH3.2A2".VDZ.pqgt1t2p.dat-s
○ Barcelona 2048コア(京大T2K) : 68593.46秒
○ Westmere-EP 192コア(OPT) : 60831.82秒

○ 京大 T2K スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

○ OPT クラスタ
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.6 for x86_64

GbE 対 Myrinet

投稿中の論文の修正に関して幾つか再実験が必要なので、GbE と Myrinet-10G との性能差を以下のクラスタ計算機を用いて検証した。

○ソフトウェア SDPARA 7.3.1

○問題１：Be.1S.SV.pqgt1t2p.dat-s
○ GbE : 807.02秒
○ Myrinet-10G : 785.65秒
ELEMENTS > CHOLESKY タイプの型なので、GbE でも Myrinet-10G でも大きな差が出ない



○問題２：nug12_r2.dat-s
○ GbE : 303.91秒
○ Myrinet-10G : 248.17秒
ELEMENTS < CHOLESKY タイプの型なので、Myrinet-10G の方が速くなる

○問題３：mater-6.dat-s
○ GbE : 377.64秒
○ Myrinet-10G : 340.51秒
Sparse Cholesky 分解を適用するタイプだが、やはりデータが疎なのでそれほど大きな差は出ない。


○ POWER クラスタ
4 Nodes, 8 CPUs, 32 CPU コア;
CPU : Intel Xeon E5345 2.33GHz (quad cores) x 2 / node
Memory : 16GB / node
HDD : 2TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.6 for x86_64

Excel で学ぶ OR ：最終校正

Excel で学ぶ OR (7月刊行予定：オーム社)の目次と内容。いよいよ最終校正の段階に入った。最後に”はじめに”を書いて追加した。いよいよページ数の変更は許されなくなり、ページ数は 336 ページで固定されることになった。

Excelで学ぶOR

・著者：藤澤 克樹　後藤 順哉　安井 雄一郎　共著
・定価：3360円(本体3200円＋税)
・B5変　336頁
・ISBN　978-4-274-06852-2
・発売日：2011/07

はじめに
序章: OR とは？
１章: 数理最適化
２章: シミュレーション
３章: 交通のデザインとネットワーク理論
４章: 計画、運用のためのモデルとサプライ・チェイン最適化
５章: 予測・検証・発見のための最適化モデルとデータマイニング
６章: 投資効率評価とDEA
７章: 不確実性下の意思決定とファイナンス理論

最適化と計算に関する最新の傾向 その２

以前にも同様のことを記事にしたことがあるが、最適化分野の研究及びソフトウェアに関する最新の傾向について以下に要点だけを記す。状況はどちらかというとより悪い方向に加速していて、日本の業界全体で見ると改善される可能性はほとんど無い。一方で、今後の進展に依存するが日本のグループあるいは日本人が関わるプロジェクトで国際競争力を持ったソフトウェアが（少数だが）今後登場する可能性もある（実はすでに数個ぐらいはある）。しかし、これらはほとんど例外扱い（特定の個人やグループが好きでやっている）で、日本全体での最適化ソフトウェアに関する戦略らしきものは（私の知る範囲では）全く無いし、今後も無さそうである。

----------------------------------------------------------------------------------------------------------
最近の欧米などの海外では, 以下のような研究の傾向が見られる.

1. 理論的な研究であっても数値実験による評価, 検証がほぼ必須となっている
2. 実用的な最適化問題を解くために理論から実装, パラメータ設定, 大規模並列計算等の各分野の研究者が集結して総力戦を行っている

一方, 日本では最適化アルゴリズムの実装技術とソフトウェア開発能力が低く,"優れた理論が提案されても実装してソフトウェアとして公開することができない" また"実用的な問題を解く際に海外の最適化ソフトウェアに極度に依存している"という状態になっている.

とっても大きな SDP その８

以下の超巨大 SDP だが、新クラスタ計算機(opt)でも解いてみて、以前 SDPA クラスタで解いた結果と比較してみた。今回は少し精度を押さえて計算したので、反復回数は少し少なくなっている。反復回数や両クラスタ計算機のコア数を考慮しても、１コアあたりでは OPT クラスタ(Xeon X5670)の方が、SDPA クラスタ(Xeon X5460)よりも 1.3倍ほど高速になっている（控えめに見ても 1.2倍)。この高速化は単に浮動小数点演算だけでなく、様々な実行を含めた総合的な結果となる。

問題名：C2.1Sigmag+.VDZ.pqgt1t2p.dat-s
76554 (= mDIM)
22 (= nBLOCK)
18 18 18 18 153 153 324 153 153 324 648 324 324 816 2754 2754 816 8604 8604 2754 2754 -694 (= bLOCKsTRUCT)

◯OPTクラスタでの結果
phase.value = pdOPT
Iteration = 41
mu = +5.5940898847164287e-10
relative gap = +3.2411675067891204e-08
gap = +2.9487340640343973e-06
digits = +7.4892985236131659e+00
objValPrimal = -9.0977526155964412e+01
objValDual = -9.0977529104698476e+01
p.feas.error = +7.3341257716509419e-08
d.feas.error = +1.5886456594671472e-09

Time(sec) Ratio(% : MainLoop)
Make bMat time = 650412.762437, 97.578841
Cholesky bMat = 6912.158352, 1.037004
Total = 666578.254319, 100.004086


◯SDPAクラスタでの結果
phase.value = pdOPT
Iteration = 48
mu = +3.7701550392400866e-11
relative gap = +0.0000000000000000e+00
gap = +0.0000000000000000e+00
digits = +inf
objValPrimal = -9.0977516315119601e+01
objValDual = -9.0977516315119601e+01
p.feas.error = +6.3903804436704646e-09
d.feas.error = +2.9498643527858803e-09

Time(sec) Ratio(% : MainLoop)
Make bMat time = 1513766.862287, 97.370655
Cholesky bMat = 10299.300986, 0.662486
Total = 1554675.150952, 100.002016

○ OPT クラスタ
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.6 for x86_64

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.4 for x86_64

最適化と計算に関する最新の傾向

アルゴリズムによる高速化と計算機による高速化が明確に分離（区別）することが出来なくなった. つまり最新のアルゴリズムでは最新の計算機アーキテクチャでの実行を前提としたものが増えてきている．計算量による理論的解析の優劣とソフトウェア実装後に計算機で実行したときの計算結果が大きく異なるという現象が見られる.その理由としては以下のような原因が考えられる

1: 理論的な解析時に想定されている最悪な場合という現象が計算機上で扱うことのできる問題の範囲では起こらない. 例えば，現在の計算機においては整数型の変数は大きくても 2^64-1 であるので，計算機で扱うことができる範囲では log n 関数(底は2) は大きくても 64 程度である（つまり定数とみなすこともできる）．
2: 計算量の評価において,演算量とデータ移動量が混同されている(一般的には後者の方がコストが高い).

Turbo Boost on Intel Xeon X5670 その２

以下のクラスタ計算機は Turbo Boost で実験中。熱いのは空調でカバーできるのだが、あまりにもうるさい。Turbo Boost 切ったらもう少し静かになるのだろうか？



Turbo Boost 中のビデオ：3GP 形式 15MB

計算やり直し その２

昨年、京大 T2K スパコンで実行した結果を再度解析中。データ量が非常に多いので大変だが、一番困るのはやり直しの実験が出来ないこと。

問題名 : H2O.1A1.DZ.pqgt1t2p.dat-s


○ 京大 T2K スパコン
○ELEMENTS : 25198.24秒
○CHOLESKY : 284.34秒
○全体：27523.88秒

○ OPT クラスタ
○ELEMENTS : 21582.47秒
○CHOLESKY : 370.74秒
○全体：22988.00秒

ELEMENTS の部分はコア数が増えれば基本的に性能が上がっていく種類の計算なので、CPU もクロック周波数も異なるとは言え 2048 コア時の計算が、192 コア時の計算よりも遅くなるというのはちょっと考えにくい。多分、もう一回実行できれば事情はかなり異なってくると思われるが、そこまでする価値は無いものと判断する。

○ OPT クラスタ
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.6 for x86_64

○ 京大 T2K スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

計算やり直し

Variational approach for the electronic structure calculation on the second-order reduced density matrices and the $N$-representability problemの論文の 23 ページにある以下の実験結果の中で 2048 コアを使用しているものは、京大 T2K スパコンでの SDPARA の実験結果になる。最近の実験結果によると、以下のような速度の優劣になるので、23 ページの実験は全て SDPARA 7.3.3 + OPT クラスタ (192コア) 解き直してみることにした。本格的な電力不足になる前に必要な実験は済ませておきたい。

速い：SDPARA 7.3.3 + OPT クラスタ (192コア) > 遅い：SDPARA 7.3.2 + 京大 T2K スパコン (2048コア)

system r N-repres. cond. u vmax time (s) nodes CPU cores
NH2- 28 P,Q,G, T1, T2′ 27,888 4,032 27,949 128 2048
CH2 28 P,Q,G, T1, T2′ 27,888 4,032 26,656 128 2048
NH3 30 P,Q,G, T1, T2′ 36,795 4,965 72,026 128 2048
CH3 30 P,Q,G, T1, T2′ 36,795 4,965 68,593 128 2048
C2 36 P,Q,G, T1, T2′ 76,554 8,604 1,554,675 32 512
O2+ 40 P,Q,G 116,910 800 5,943 128 2048

○ OPT クラスタ
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.6 for x86_64

○ 京大 T2K スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

2011年度第1回 SCOPE講演会

2011年度第1回 SCOPE 研究会を以下の日程で開催することになりました。講演会の後は懇親会も予定しています。

○2011年度 第1回 SCOPE 講演会

日　時 ： 2011年7月9日（土）14:00～17:00
会　場 ： 中央大学 後楽園キャンパス 6号館 4階 6410室

講演1
講演者 ： 北原知就氏 (東京工業大学 大学院社会理工学研究科 経営工学専攻)
題目 ： 単体法によって生成される実行可能基底解の個数の上界について
概要 ： 単体法は線形計画問題に対する最初の解法で，実用上は非常に効率的であることが知られている。しかし，一般的な線形計画問題に対する単体法の反復回数の評価はほとんど知られていない．その大きな障害となっているのが，Klee-Mintyによって発表された単体法が指数回の反復回数を必要とし得るという事実である．北原-水野(2010年)はマルコフ決定問題に対するYeの解析(2010年)を応用し，単体法が生成する実行可能基底解の上界を示した。得られた上界は問題の制約式の個数、変数の個数，およびすべての実行可能基底解の正の要素の最大値と最小値の比，の多項式で表される．そして問題が非退化のとき，この上界は反復回数の上界となる。本講演では、上界を得るための解析について詳しく説明する。また，新たに開発した簡易版Klee-Minty問題を使い，良い上界が得られていることを示す．

講演2
講演者 ： 後藤和茂氏 (米 Microsoft Corporation)
題目 ： 最適化における性能測定　
概要 ： 本講演では構成を大きく２つに分ける。前半では講演者の経験をもとにアメリカの文化及び労働環境について具体例を交えて紹介する。後半では講演者の専門である最適化に関して、特に最適化の評価をするための性能測定（いわゆるベンチマーク）についての解説を行う。プログラムの作成においては単に正しい結果が必要なだけではなく多くの場合同時に性能を必要とする場合が多いが、その性能を評価する手法に関してはあまり知られていない。そこで本講演では性能を正確に測定する手法を紹介するとともに、対象となるシステムから得られる特性から性能を予測することにより得られた性能の妥当性を検証する手法を紹介する。

SDPA クラスタ

これから夏にかけて電力使用の総量規制が厳しくなり、大学全体で規定電力使用量を越えた場合には罰金が課されることになっている。というわけなので、今後は研究室内のクラスタ計算機でどれだけ安定して長時間計算が出きるのか怪しくなってきた。以下の SDPA クラスタは３月１２日以降はずっと停止状態が続いている。Dell のサポート期間(3年)が終了することもあり、今後しばらく電力事情が改善する見込みも無いので、以下のクラスタ計算機は実質的に引退ということになりそうだ。

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
Disk : 6TB(RAID 5)
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.6 for x86_64

Node Interleaving

Dell の PowerEdge のマニュアルには Node Interleaving について以下のように書いてある。

Node Interleaving

対称的なメモリ構成の場合、このフィールドが有効に設定されていると、メモリのインタリービングがサポートされます。このファイルが無効（デフォルト）に設定されていると、システムは NUMA（Non-Uniform Memory Architecture）（非対称）メモリ構成をサポートします。
メモ： 冗長メモリ機能を使用する際には、Node Interleaving（ノードのインタリービング）フィールドは Disabled（無効）に設定する必要があります。
-----------------------------------------------------------------------------------------------------------------------------------------------

そこで Magny-Cours 48 コアサーバで Node Interleaving 機能を ON と OFF の両方に設定して SDPA の比較実験を行なった。numactl コマンドなどの組み合わせが絡んでくると少し複雑になるのだが、この場合では明らかに Node Interleaving 機能を ON にした方が得になる。ただし、両者とも HT Assist は ON にしている。

○ソフトウェア SDPA 7.4β

○問題 : theta6.dat-s
Node Interleaving ON : 13.8秒
Node Interleaving OFF : 24.8秒

○問題 : Be.1S.SV.pqgt1t2p.dat-s
Node Interleaving ON : 11分30秒
Node Interleaving OFF : 18分4秒

○問題 : nug12_r2.dat-s
Node Interleaving ON : 2分15秒
Node Interleaving OFF : 4分35秒

○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64