グラフ分割問題に対する SDP 緩和と SDPA-GMP

応用に役立つ５０の最適化問題の 5.4 章(グラフ分割問題に対する SDP 緩和問題)において SDP 緩和問題を SDPA-GMP を用いて解いているが、SDPA ではダメなのか？という質問があった。この問題では SDPA を用いても別に問題は無いと思われるが、以下のように数値精度という点で SDPA-GMP に劣るので、出来れば SDPA-GMP の値の方を使いたい。
SDPA では主問題の最適目的関数値(上界) -1.1972046804133166e-01 > 双対問題の最適目的関数値(下界) -1.2187341887583791e-01 であるが、双対問題の実行可能性の指標(d.feas.error) があまり良くないので、SDPA-GMP の最適目的関数値 -1.1957989287e-01 が SDPA のこの上界と下界の範囲に含まれていない。この点がやはり気になったので、SDPA-GMP の方を用いた。

SDPA 7.3.1
objValPrimal = -1.1972046804133166e-01　　 <-- 主問題の目的関数値
objValDual = -1.2187341887583791e-01　　 <-- 双対問題の目的関数値
p.feas.error = +2.2737367544323206e-13
d.feas.error = +2.1173717223987865e-09

SDPA-GMP 7.1.2
objValPrimal = -1.1957989287e-01 <-- 主問題の目的関数値
objValDual = -1.1957989287e-01 <-- 双対問題の目的関数値
p.feas.error = 2.8917634547e-76
d.feas.error = 4.5890565996e-38

スーパーコンピュータで最短路検索

中高生の方向けに以下の企画を考えてみました（今年の８月に予定）。コンピュータや数学の応用に興味のある方であれば、多分中学生でも大丈夫だと思います。というよりも公開セミナーに参加してくる中高生の方が、並の理工系大学生よりもやる気、能力、知識で上回っていることが多いです。

"スーパーコンピュータで最短路検索"
スーパーコンピュータと言っても中規模以下のものは研究室でも作れます。スーパーコンピュータの基本に触れてから、全米の道路ネットワークという非常に巨大データを使って、主要な地点間の最短路を高速に計算してみましょう。最短路を求める方法は難しくはないので、そのアルゴリズムとデータ構造についても学習しましょう。

Fedora 12 と VMware Player 3.01

VMware Player の 3.0.1 がリリースされたが、やはり Fedora 12 上では以前と同じような現象が発生するようなので、以下のように設定した。理由は良くわからないが、これで一応正常に VMware Player が動作しているようだ。

1: yum install gcc kernel-devel (必要ならば)
2: vmware-modconfig --console --install-all
3: mv /usr/lib/vmware/resources/mozilla-root-certs.crt /usr/lib/vmware/resources/mozilla-root-certs.crt.old

地震とマンション

地震とマンションという本が２０００年に出版された。また改めて読み返してみたのだが、絶版になったのが大変惜しい本である（中古品は簡単に入手可能）。一方 2006 年に出版された本でマンションの地震対策という本があるが、こちらの中では前述の地震とマンションという本の中身にも触れられているので、参考にした点も多かったと思われる。簡単に論点をまとめると、以下のようになる。
１：大型の地震時にも一般住宅と比べるとマンション内での死傷者はかなり少ない。
２：RC（鉄筋コンクリート）の建物の中でも、比較的な単純な構造を持ち、広い部屋が少ないマンションの方が、商業ビルやオフィスビルよりも一般的には地震に強い
３：上の階の方が揺れやすいが、かかる重さが少ないので壊れにくい
４：新耐震基準（１９８１年以降）で立てられたマンションは崩壊、大破することはほとんどないが、中破以下の被害は結構多い
５：大破したマンションでも修復できる場合がある
６：古いマンションでも耐震補強を行うことによって、地震の被害を減らすことができる
７：液状化現象は地盤改良によって、かなり防ぐことはできる
８：中層以下のマンションは固有周期が短いので、長周期振動に関する心配はほとんどない
戦前に建てられたRC造の建築物で現存しているものは、非常に柱や梁も太くて素人目にも地震に強そうな感じがする（東工大の本館など）。一方、最新の建築の方が基準ぎりぎりで建てているせいか、どうしても華奢な感じを受けてしまう。

高校数学

入試の採点を行うときに、まず自分でも解いたみたが、合格点を取るのではなく、模範解答（つまり満点の解答）を作るのは大変難しい。予備校などが出している解答も必ずしも満点ではないらしい（特に証明に関して）。また、解き方が高校数学の範囲を超えていても数学的に正しければ良いので、模範解答以外の別解も多く、結構苦労した。最適化問題に限らないが、数学的な諸問題に対して適切なアルゴリズムとデータ構造を考案して実装を行うには、やはり数学の知識、能力も重要であり、高校数学のレベル（これでも十分高いが）は押さえておくべきだと実感した。

Windows 7 Ultimate 64bit とノートパソコン

CPU が Atom では非力すぎるので、少し性能が上の Celeron T1700(1.83G) 搭載のノートパソコンを購入したら、Windows 7 Ultimate 64bit がインストールされていた。DSP 版でも 22,280 円ぐらいはするので、ノートパソコンの価格が 69,107 円であることを考えると OS が占める価格が異様に大きい。
あとのスペックは 画面のサイズ 17inch, メモリ 4GB, HDD 320GB であって、OS 価格を引いた残り 45,000 円程度で済んでいることを考えるとかなり安い。安さには何か秘密があるかもしれないので、しばらく使用してみないとわからない。

ソフトウェアは既存のものを使っただけです

現在審査している論文を始めとして、最適化問題の定義 → 定式化 → ソフトウェアの結果 → 考察というパターンを良く見かけるのだが、いくら自分でソフトウェアを作らないからとは言っても、これはちょっと悪いパターンだ。別の論文を見ると、少し良くはなっているのだが、やはり計算機環境、最適化問題のサイズや実行時間等が書かれていない。
ソフトウェアに関する部分が完全にブラックボックス化されているが、自分で作成したソフトウェアではないので、実際に定式化した問題が解けるかどうかはわかりません（作った人に聞いてくれということ）という答えが帰ってくる。定式化までが自分の仕事で、その後に実際に解けるかどうかは自分の責任ではないと思っている人も多いのではないだろうか。

Handbook of Semidefinite Programming の続編

Handbook of Semidefinite Programming という 2000 年に発行された半正定値計画問題(SDP)のハンドブックがあり、SDP の世界では非常に有名な書籍になっている。ゼミ等で使用している研究室も多いだろう。ただし、すでに発行から１０年が経過して古くなっているので、ハンドブックの新版を作る計画がある。
ソフトウェアに限定しても 10 年前と今では段違いの性能差があるので、その辺の取り上げられることになるが、今度はソフトウェアとアプリケーションにも力が入れられるようである。

yum で落ちる Nehalem-EP マシン

以下の Nehalem-EP 搭載の PowerEdge R710 だが、最近 OS が落ちまくっている。yum コマンドでディスクアクセスを行うときに落ちる確率が高い。以前はこのような現象は無かったのだが、思い当たる原因？としては、BIOS で VT 機能を ON にしたぐらいしかない。とは言っても VT を ON したぐらいで落ちる理由はわからない。

○PowerEdge R710
CPU : Intel Xeon 5550 (2.66GHz) x 2 :
メモリ 72GB
OS : Fedora 12 for x86_64

SCOPE 2009年度 第５回研究会

開催が一週間後に迫りましたので、再掲載します。大勢の方の参加をお待ちしております。夜はいつものように懇親会も予定しています。また、正式決定ではないですが、今年の SCOPE つくば合宿は例年よりも１ヶ月程度遅くなりまして、６月２６、２７日の予定です（ワールドカップの日本の試合も避けています。すでに負けそうですが）。

2009年度 第５回研究会
日　時 ： 2010年02月27日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演者：渡部大輔 (東京海洋大学 海洋工学部流通情報工学科)
講演題目：一般化Weberモデルによる航空貨物ハブ施設配置の最適化
講演概要：本研究では、航空貨物輸送における輸送費用の変化が単一のハブ空港配置に与える影響について、輸送距離と輸送量をべき関数として一般化したウェーバー問題を用いて考察する。まず、一次元・二次元の規則的な点配置における輸送費用関数の変化による最適配置の分析を行う。さらに、東アジアにおける航空貨物の輸送を対象に分析を行い、各国の航空運賃から推定したパラメータにより、同じ需要分布でも異なる最適配置の結果が得られた。

講演者：小林和博 (海上技術安全研究所 物流研究センター)
講演題目：船舶スケジューリングと船の最短路問題
講演概要：船舶スケジューリングは、複数の荷物を運搬するための最も効率のよい船舶の運航スケジュールを求める問題である。数理的構造はVehicle Routing Problem(VRP)と同じであるが、船舶および港湾の運用上の特徴により、有効な解法が陸上のVRPとは異なる. 本発表では集合被覆問題と列生成によるヒューリスティックな解法を紹介する。船の最短路問題では、出発港から目的港までの航路の選定を、制約付き2目的最短路問題に定式化する。この問題に対して、ロバスト性をもつ解を与える計算方法について報告する。

Pthread v.s. OpenMP その２

昨日の実験を他のマシンでも行ってみたが、現在の実装方法では基本的に以下の通り。

1: gcc 4.1.2 と 4.4.3 では性能差はほとんどない
2: Pthread と OpenMP の性能差はあまり大きくない
3: インテルコンパイラは gcc よりも性能が高い(Pthread でも OpenMP でも同じ傾向になる)

いつも上記のようになるわけではない。例えば以前行った以下のブログなどを参考にしていただきたい。

OpenMP の性能: gcc と Intel Compiler

Pthread v.s. OpenMP

プログラムをマルチスレッド化するときに、Pthread を使うか、OpenMP を使うか迷うところで、OpemMP を用いると簡単にマルチスレッド化できるが、細かい制御があまり出来ないようなイメージがある。しかし、Pthread 風に thread function を作っておいて、その関数を for 文で包んでから

#pragma omp parallel for schedule(static)

とすると、結構いろいろな制御を行うことができる。以下で Pthread と OpenMP の性能比較を行う。gcc 4.1.2 の OpenMP の性能は一般的には良くないのだが、作り方に依存する面も大きいので、以下のように Pthread と OpenMP の性能差がほとんど無いということもある。

---------------------------------------------------------------
○最適化ソフトウェア : 最短路ソルバー msp Ver. 0.21

○計算サーバ
CPU : Intel Xeon 5460 (3.16GHz / 6MB L2 x 2) x 2
Memory : 48GB (12 x 4GB)
gcc : 4.4.3 (デフォルトは 4.1.2)
Intel コンパイラ : 11.1.064
OS : CentOS 5.4 for x86_64

○最短路問題 LKS 1000 クエリ
1: gcc 4.1.2
pthreads: 31.359s
openmp: 34.956s

2: gcc 4.4.3
pthreads: 31.472s
openmp: 34.939s

3: icc 11.1.064
pthreads: 28.198s
openmp: 30.976s

クラウド関係のセミナー

クラウド関係のセミナーの案内が幾つか来ましたので、紹介しておきます。

AMD Opteron(TM) プロセッサではじめる仮想化・クラウド」セミナー
https://reg.amd.jp/public/seminar/view/48

事例とデモでわかる！プライベート・クラウド構築セミナー
http://www-06.ibm.com/systems/jp/saiteki/event/pcloud03/

ついでに IBM Academic Initiative のリンクも貼っておきます（クラウドとは直接関係無いですが）。

理論計算量と実際の計算性能

詳しくは添付の図を見ていただくとして、全米データでは 点数 n = 2400 万点, 枝数 m = 5800 万枝なので、優先キューなどを用いない原始的なダイクストラ法では計算量が O(n^2) になって、2400 万の二乗で計算量が計上される。一方、例えば 2-heap を用いたダイクストラ法の計算量は O(m log n) であるが、n = 23,947,347 でも log n = 約17 にしかならないので、実際には m (枝数) によって計算量が決定される。道路データでは点は交差点を表す場合が多いが、点の次数（つまり交差点に接続している道路）は多くても４程度なので、グラフはかなり疎になる（つまり n^2 >> m となる)。
ただし、理論計算量（最悪時想定）が小さい方が、ソフトウェアの性能においても上回るとは限らない。それは以下のような原因が考えられる。
１：最悪の場合はめったに起こらない
２：実装が悪い（そもそも実装を真面目にやる気がない）
３：定数項が予想以上に大きい
４：比較演算のコスト（分岐予測のミス）が大きい、スワップ操作の多用（書き込みと読み込みの連続）、演算とメモリ操作の混同による計算量推定。
よくある質問で、問題が非常に大きくなれば理論計算量が少ない方が結局は勝つ（速い）というものがあるが、必ずしもそうとは言い切れない。
１：計算機で扱える問題の大きさの範囲では、定数項の影響が非常に大きい場合が多い
２：上記の４のように、理論計算量の値が実際の計算性能を正確に反映していない場合がある。
我々もいろいろな事例で確認しているが、現在の計算機上で有名なアルゴリズムとデータ構造がどういった特性を示すのか調べてみると面白い。

仮想マシン

現在、様々なイメージファイルを用意して仮想マシンを多用している。用途は以下のようになる。
１：SDPA などのサポートのため（動作確認、デバッグ）
２：スパコンなどは実際に借りて使うと課金されるので、仮想マシンでほぼ同じ環境（OS, コンパイラ)を作って、開発やデバッグを行う
３：単なる趣味(Windows 95, BeOS, Chrome OS 等)。今度は OS/2 Warp V4 の仮想マシンが欲しい。
欠点は性能が実マシンに対して落ちることと、ノートパソコンで使うとバッテリの減り具合が激しいこと。