SCOPE ＠つくば – 未来を担う若手研究者の集い 2010 –

日時 : 2010 年 6 月 26 日（土） & 27 日（日）
会場 : 筑波大学筑波キャンパス春日地区春日講堂

（住所: 〒 305-8577 つくば市天王台 1-1-1）

主催 : 日本オペレーションズ・リサーチ学会「計算と最適化の新展開」研究部会（SCOPE）

筑波大学

1 日目： 6 月 26 日（土）

• 9:20-9:30 開会の挨拶 & 諸連絡

• 9:30-10:45 座長：安井雄一郎

1. 田代泰史（筑波大学システム情報工学研究科社会システム工学専攻 M1）

水面に映り込む倒景に関する解析研究

水面により倒景と呼ばれる対称な景色が生まれる．倒景の代表的な景観として逆さ富士が挙げられる．また倒景を意図してつくられた建物として金閣寺やタージマハルがある．本研究の目的は，視対象，視点場，水面との位置関係に注目し，倒景の見えの大きさに対応する見込角や立体角という幾何学的概念を通して倒景の基本構造を数理的に解析することにある．なお，倒景の本質を追求するために，極力状況を単純化する．

2. 菴木嶺（筑波大学システム情報工学研究科社会システム工学専攻 M1）

都市内道路における日向経路と日陰経路

本研究の目的は，道路面での日向・日陰という日照状況を加味したときの経路選択を考察することにある．沿道建物によって影が生成されるとし，日照条件を日向量というもので定義する．この日向量を用いて，日照に関する経路選択を論じる．まず，格子状道路において，方位のずれに着目し，沿道建物による影の落ち方を見ていく．さらに，一般道路網において，移動距離と日照条件とのトレードオフに着目したパレート最適経路を求める．

3. 高橋莉里香（中央大学理工学研究科情報工学専攻 M1）

航空における時空間ネットワークの構築

本発表では，国際航空旅客データを整理することによって，現在の航空路線のいくつかの特徴を明らかにする．また，航空時刻表を用いて，航空網に時間の概念を加えた「時空間ネットワーク」を構築し，旅客便のフライトを表す．時空間ネットワークを用いて，空港間の距離と所要時間，乗継回数の関係について比較する．日本航空の全路線を廃止した場合の影響についても考察する．（鳥海重喜，田口東との共著）

• 10:55-12:10 座長：奥野貴之

1. PATO， Maria Carmela （東京工業大学社会理工学研究科経営工学専攻 D1） Performance Assessment of Philippine Administrative Divisions by Means of Data Envelopment Analysis

The performance of administrative divisions (regions) in the Philippines is traditionally measured by the regional GDP. This measure is limited because it only reflects economic output. It is necessary to consider other significant indicators to have a proper performance analysis. The purpose of this study is to develop a new efficiency measure that will take into account economic output, education, peace and order, health, and poverty incidence, and use it to analyze regional performance. This is done through data envelopment analysis (DEA), which is a linear programming based method primarily used to evaluate relative performance. The results show the efficiency of all regions when evaluated using the indicators chosen, as well as the specific areas of improvement for lower-performing regions.

2. 篠崎桂太（中央大学理工学研究科経営システム工学専攻 M1）

マルチファクターモデルを用いたロバスト CVaR 最小化

ポートフォリオ選択問題における下方リスクモデルの CVaR 最小化問題にロバスト最適化の概念を取り入れたモデルを提案する。提案モデルでは、資産収益率の分布を重回帰モデルで表したマルチファクターモデルを用いて、資産収益率の不確実性集合に対してパラメータの信頼領域を決定している。本発表では、提案モデルと従来の CVaR 最小化モデルとの計算実験の報告・比較をする。

3. 大城戸慎平（慶應義塾大学理工学研究科開放環境科学専攻 M1）

太陽光発電システム導入計画に対するロバスト最適化

本研究では、ある地域でコストや環境負荷を低く抑える電力調達を行うためには、どれくらいの規模の太陽光発電の装置を導入するべきか、という問題を考えた。現状の電力買取制度に適用できる数理モデルとその解法を紹介する。また、太陽光発電量に関わる日射量を不確実データとして、それを含む相補性問題に対してロバスト最適化のアプローチを適用し、太陽電池モジュール導入計画に対するロバスト最適化モデルを提案する。

昼休み 12:10〜13:10

• 13:10-14:00 座長：前原貴憲

1. 宮崎未来（筑波大学システム情報工学研究科社会システム工学専攻 M1）

オンラインスケジューリング –同時到着した複数のジョブに対して到着時に順序関係が与えられるケース–

私の働くレストランの調理作業について、処理の開始時刻に順序関係のあるジョブ列についてのオンラインスケジューリング問題としてモデル化する．さらに，このようなジョブ列に対して従来の Longest Processing Time ルールをベースに後行ジョブの処理時間まで考慮したオンラインアルゴリズムを提案し，競合比を用いてアルゴリズムの評価を行う．

2. 野田峻弘（京都大学大学院情報学研究科数理工学専攻 M1）

サプライチェーンにおける配送戦略の競合モデル

1 人の顧客と n 人の供給者により構成されるサプライチェーンの数理モデルを構築し、各供給者にとっての均衡戦略を求める問題を、各供給者から顧客への製品配送頻度を戦略とする一般化ナッシュ均衡問題へと定式化する。さらに一般化ナッシュ均衡問題がある仮定の下で変分不等式問題に変換できることを用いて、均衡戦略の導出方法を示す。また、具体的な問題を想定した数値実験から得られた均衡戦略の振る舞いについて検証する。

• 14:05-14:55 座長：高松瑞代

1. 谷口誠（筑波大学システム情報工学研究科社会システム・マネジメント専攻 D1）

グラフの cut の列挙に対する Provan and Shier の枠組みの拡張

グラフの cut の列挙に対する Provan and Shier の枠組みの拡張を行い、それを元に得られたより一般化された枠組みについて述べる。また、グラフの cut の列挙問題のいくつかに対して、拡張した枠組みが適用できるかどうか考察した結果を述べる。

2. 松田俊一（東京大学情報理工学系研究科コンピュータ科学専攻 M1）

巡回セールスマン問題に対する低分枝幅グラフの生成

本発表では、巡回セールスマン問題に対する分枝分解に基づいた動的計画法を効率的に実行するための低分枝幅グラフの生成法について考察し、実験結果を報告する.

• 15:05-16:20 座長：野中良哲

1. 柳秉�（防衛大学校理工学研究科情報知能メディア学専攻 D2）

Shift-and-Merge Technique for the DP Solution of the Backpacker Problem

0-1 ナップサック問題を無閉路有効グラフ上に拡張し、新たにバックパッカー問題を定式化した。これに対し、通常の動的計画法やリスト形式の動的計画法による厳密解法を紹介する。さらに、最適目的関数値がナップサックの容量に関して、ステップ関数になっていることからこれを「シフト・マージ法」に改善し、実際の計算時間を大幅に縮小させた。数値実験結果についても報告する。

2. 横谷大輔（防衛大学校理工学研究科情報知能メディア学専攻 D3）

反復割当問題に対する問題縮小アプローチ

同じ割当ては重複しないという制約が追加された，繰返しのある割当問題を考える．大規模な 0-1 計画問題となるため，上下界値を利用した釘付けテストによる問題縮小を試みる．上界値は反復ハンガリー法と局所探索法により，下界値は遅延取込法により連続緩和問題を解いて得られる．ラグランジュ緩和により釘付けテストが分解され，独立した全節点対最短路問題に帰着されることを示す．さらに，仮想釘付けテストを導入する．

3. 森山裕子（中央大学理工学研究科情報工学専攻 M1）

ドミノポートレート問題

ドミノポートレートは, 与えられたドミノを用いて, 画像を近似したものである. Bosch は, ドミノポートレートを作る問題を整数線形計画問題として定式化している. 本研究では, 整数線形計画問題の線形緩和と丸め法を用いた，新しい手法を提案する. 実例として 5 種の画像に対して提案手法を適用したところ, すべての例において整数線形計画問題の最適解と一致する解を得た.

• 16:30-18:00 特別講演 I

1. 神山直之 (中央大学)

超私的計算世界観

本発表では，離散最適化分野の若手研究者である発表者の，私的な計算世界観にもとづいて，どのようなことを思いながら研究をしているのか，どのようなことに興味があるのかを，具体的な例を含めてお話する予定です．もちろん，個人的な興味をもとに話題を選択しますので，偏ったものになる予定です．

2. 吉瀬章子 (筑波大学)

最適化モデルの紙芝居

昨年来、高校生や中小企業の社会人の方々を対象として、最適化モデルを知ってもらうための授業を行っています。それらの経験を紹介するとともに、最適化モデルを普及する際に生じるいくつかの問題点を挙げたいと思います。

懇親会 18:30〜

2 日目： 6 月 27 日（日）

• 9:00-9:50 座長：山口大輔

1. 曾力舜（東京工業大学社会理工学研究科経営工学専攻 M2）

A hybrid meta-heuristic approach to the traveling tournament problem

This work considers the traveling tournament problem (TTP), which is a well-known problem in the field of sports scheduling in recent years. The TTP considers scheduling round-robin tournaments that minimize traveling distance under some constraints on home-away patterns. Meta-heuristic approaches, especially those based on local search in the neighborhood, are widely used due to the complexity of the TTP. In this work, new neighborhood structures are proposed and analyzed for round-robin tournaments. A hybrid of tabu search (TS) and variable neighborhood search (VNS) meta-heuristic approach to the TTP is proposed based on the new neighborhood structures. The new approach are analyzed and compared with other meta-heuristic approaches in the literature by numerical experiments for benchmark problems.

2. �川矩義（筑波大学システム情報工学研究科社会システム工学専攻 M1）

Gale-Shapley アルゴリズムでのプロポーズを決定する完全選好リストの存在とその判定方法

男性と女性の人数が等しく選好リストが完全な安定結婚問題を扱う。男女の組の集合 Pro と完全マッチング μ を指定して、男女の完全選好リストの組が、 Gale-Shapley アルゴリズムを実行すると、 Pro に属する男女の組だけにプロポーズが起き、指定した完全マッチング μ が出力されるような、完全選好リストの組であるための必要十分条件を紹介する。

• 9:55-10:45 座長：小林佑輔

1. 野中良哲（九州大学システム情報科学府情報学専攻 D2）

ランダムウォークの高速化について

標準ランダムウォークでは，頂点数 n のグラフにおける到達時間および全訪問時間がともに O(n^{3}) である．本発表では、素朴なメトロポリス歩によって、到達時間が O(n^{2})、全訪問時間が O(n^{2} log n) へそれぞれ改善されることを示す。また、木上の標準ランダムウォークの到達時間は、最適なランダムウォークと比べ高々O(\sqrt{n}) 倍であることを示す。

2. 中坪亮（中央大学理工学研究科情報工学専攻 M1）

分割表のパーフェクトサンプリング法

本研究では， m 行 n 列分割表のパーフェクトサンプリング法を提案する．与えられた行和, 列和を満たす非負整数行列を分割表と呼ぶ．行数が 2 の分割表に対し， Kijima-Matsui は多項式時間パーフェクトサンプリング法を提案した．行数が一般の場合, Wicker がパーフェクトサンプリング法を与えている．我々は, 行数が一般の場合に対し新たなパーフェクトサンプリング法を提案し，計算実験によって実行時間を評価する.

• 10:50-11:40 座長：成島康史

1. 奥野貴之（京都大学情報学研究科数理工学専攻 D1）

無限個の二次錐制約をもつ半無限計画問題に対する KKT 条件と収束アルゴリズム

半無限計画問題とは, 変数の次元が有限であり, 制約の数が無限個あるような数理計画問題である. 今回は, 半無限計画問題の中でも無限個の二次錐制約をもつ問題（SISOCP）について考える. SISOCP は多くの応用先をもつにも関わらず, その研究はほとんどされていないのが現状である. 本発表では,SISOCP の KKT 条件を示し, SISOCP の最適解を求めるためのアルゴリズムを提案する. また, その収束性についても述べ, 数値実験結果を報告する.

2. 木村康宏（筑波大学大学院システム情報工学研究科社会システム工学専攻 M2）

問題構造を用いたノード分割によるセンサー位置同定問題に対する半正定値緩和アルゴリズム

本発表では，センサーネットワーク位置同定問題に対して，問題構造をもとにノードの分割を行い，半正定値緩和問題を複数回解くアルゴリズムを提案する．また，計算実験の結果を報告する．

昼休み 11:40〜12:40

• 12:40-13:30 座長：林俊介

1. 松川恭明（筑波大学システム情報工学研究科社会システム工学専攻 M2）

非負半正定値行列錐上の最適化について

本発表では半正定値計画問題の変数に非負制約を追加した問題について考え, この問題を半正定値計画問題に対する主双対内点法を使わずに解く方法について紹介する.

2. 前原貴憲（東京大学情報理工学系研究科数理情報学専攻 D2）

誤差制御付き同時ブロック対角化法の半正定値計画問題への応用

与えられた半正定値計画問題に対し，その係数行列を同時ブロック対角化することによって大規模問題を効率的に解く手法が近年盛んに研究されている．最近，誤差を含む複数の行列が与えられたとき，それらを近似的にブロック対角化する数値的手法が発表者らによって提案された．本発表ではこの手法を半正定値計画問題に適用する方法と，その結果を述べる．本研究は室田一雄教授との共同研究である．

• 13:35-14:25 座長：横谷大輔

1. 中田真秀（理化学研究所情報基盤センター）

超高精度 SDPA ソルバー SDPA-GMP, -QD, -DD の性能評価と応用

半正定値計画を安定かつ、または精密に解こうとすると、コンピューター上で通常使われる IEEE 754 という規格の倍精度 (有効桁 16 桁) を使っても一般には困難である。それを我々は多倍長精度計算ライブラリを用い、力づくで解く SDPA-GMP, -QD, -DD という三つのプログラムを開発した。本講演では SDPA-GMP, -QD, -DD の紹介をし、性能評価と、応用を行った結果も発表する。

2. 安井雄一郎（中央大学理工学研究科経営システム工学専攻 D2）

大規模最短路問題に対するダイクストラ法の高速化

最短路問題は非常に良く知られた基礎的な組合せ最適化問題である。バイナリ・ヒープを適用したダイクストラ法に対し、メモリ階層構造を考慮した汎用的かつ効率的な高速化を適用することで、実行性能、安定性、メモリ要求量, 並列実行など、総合的に最も優れたソルバを開発した。本発表では特に計算機上の実行において、どのような特性を示しているか、またどのような箇所に律速しているか明らかにしていく。

• 14:35-16:05 特別講演 II

1. 宮代隆平 (東京農工大学)

或Ｍ君の半々生発表者がこれまでやってきた研究は，不思議な縁から始まったものが多いような気がします．まだ思い出話をするような年齢ではない（と思いたい）ですが，これまでの研究テーマを始めたきっかけや面白かったことなどを技術的な側面にあまり立ち入らずに話せればと思います．

2. 藤澤克樹 (中央大学)

計算と最適化に今後訪れる世界

OR とコンピュータが生まれてからの約 60 年間、常に計算機、最適化アルゴリズム共に進歩を遂げてきました。しかし、ここ数年間で起きたことは単なるそれまでの進歩の延長だったのでしょうか？今、立ち止まって考えてみると、単に計算が速くなったとか、大きな問題が解けるようになったとか、そういった表層部分とは別に大きな変化があったことが見えてきます。また計算と最適化に今後訪れる世界についても考えてみたいと思います。

• 16:05-16:15 表彰式 & 閉会の挨拶