研究会の概要

日本オペレーションズ・リサーチ学会 研究部会

計算と最適化の新展開
Seminar on Computation and OPtimization for new Extensions (SCOPE)

この研究部会は，オペレーションズ・リサーチの基礎をなす計算と最適化をテーマにしています。近年では非常に多くの分野や新領域において最適化手法の適用が行われていますが、この研究会においては、良い意味で境界を設けずに非常に多様な分野から発表者を招待する予定になっています。また同時に数理計画法や組合せ最適化系の研究者から新領域での適用方法について提案、議論を行うことも計画しています。他の研究部会でもオペレーションズ・リサーチの応用を扱っていきますが、これまで以上に最適化手法の新領域を獲得していくことや新展開を模索していくことに重点を置きたいと考えています。さらに理論的特性だけでなく、実際の計算性能や効率も重視して、数理科学分野と情報科学分野の融合の場所としても活用していく予定です。また関連する全国の研究部会とも積極的に人的交流を行う予定もあります。
一回の会合ではおよそ二人の人に話していただく予定です。時間を一人１時間半―２時間と長めに確保し，活発にディスカッションできるような雰囲気にしたいと考えています。１５分から３０分程度の発表も歓迎します。

SCOPE（「計算と最適化の新展開」研究部会） ホームページ
主査 ： 藤澤克樹 （中央大学）
幹事 ： 後藤順哉 （中央大学）

SCOPE研究会終了のお知らせ

2009年3月から SCOPE(計算と最適化の新展開)研究会を開催して参りましたが、2012年2月でその活動を終了することになりました。研究会としての最後の仕事は以下の JORSJ 特集号となりました。また、この３月から新しい研究会(最適化の理論と応用：主査 牧野和久（東京大学), 幹事 小林佑輔（東京大学）)が開始されますので、こちらも引き続きよろしくお願い致します。


JORSJ, Vol.54 No.4

EDITORIAL INTRODUCTION
Katsuki Fujisawa and Jun-ya Gotoh (Chuo University)

LAGRANGIAN RELAXATION AND PEGGING TEST FOR LINEAR ORDERING PROBLEMS
Noriyoshi Sukegawa, Yoshitsugu Yamamoto, and Liyuan Zhang (University of Tsukuba)

AN EXTENSION OF THE ELIMINATION METHOD FOR A SPARSE SOS POLYNOMIAL
Hayato Waki and Masakazu Muramatsu (The University of Electro-Communications)

LOWER BOUNDS FOR THE MAXIMUM NUMBER OF SOLUTIONS GENERATED BY THE SIMPLEX METHOD
Tomonari Kitahara and Shinji Mizuno (Tokyo Institute of Technology)

A NONLINEAR CONTROL POLICY USING KERNEL METHOD FOR DYNAMIC ASSET ALLOCATION
Yuichi Takano (Tokyo Institute of Technology) and Jun-ya Gotoh (Chuo University)

LAGRANGIAN-BASED COLUMN GENERATION FOR THE NODE CAPACITATED IN-TREE PACKING PROBLEM
Yuma Tanaka, Shinji Imahori, and Mutsunori Yagiura (Nagoya University)

MAXIMUM FLOW-COVERING LOCATION AND SERVICE START TIME PROBLEM AND ITS APPLICATION TO TOKYO METROPOLITAN RAILWAY NETWORK
Ken-ichi Tanaka (The University of Electro-Communications)

NETAL: HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY
Yuichiro Yasui, Katsuki Fujisawa (Chuo University), Kazushige Goto (Microsoft Corporation), Naoyuki Kamiyama (Kyushu University), and Mizuyo Takamatsu (Chuo University)

2011年度第2回 SCOPE講演会

JORSJ の SCOPE 特集号(Vol.54, No.4)の刊行を記念しまして、以下の特集号論文による講演会を開催したいと思います。年末のお忙しい時期ではございますが、是非ご参集下さい。夜には懇親会も予定しています。

○2011年度 第2回 SCOPE 講演会

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

講演1 14:00 ～
講演者 ： 高野 祐一(東京工業大学 大学院 社会理工学研究科 経営工学専攻)
題目 ： A Nonlinear Control Policy Using Kernel Method for Dynamic Asset Allocation
(動的資産配分のためのカーネル法を利用した非線形制御ポリシー)
概要： 本発表では, 非線形制御ポリシーを用いて多期間にわたる動的な資産配分を決定する最適化問題を定式化し, 問題求解のための計算手法を提案する. ここで, 制御ポリシーとは投資対象資産の過去の収益の関数である.カーネル法を利用することで, 非線形関数の中から最適な制御ポリシーを選択する問題は凸2次最適化問題として定式化される. さらに, L1-ノルムを用いた正則化を利用することで問題を線形最適化問題に帰着する. 計算実験では, 投資対象資産の収益率のシナリオを1期間自己回帰モデルによって生成し,先行研究の手法と比較して我々の提案する投資戦略は良好な運用成績を得られることを示す.


講演1 15:30 ～
講演者 ： 田中　勇真(名古屋大学大学院　情報科学研究科　計算機数理科学専攻)
題目 ： Lagrangian-based column generation for the node capacitated in-tree packing problem
(頂点容量付き有向全域木パッキング問題に対するラグランジュ緩和に基づく列生成法)
概要：本論文では, 頂点容量制約付き有向全域木パッキング問題を扱う. この問題は入力として, 有向グラフ,ルート頂点, 頂点容量, 辺の始点側と終点側それぞれに消費量が与えられる. 目的はルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし, 有向全域木の各頂点に対する消費量の合計は, 与えられた頂点容量を超えてはいけない. この問題はNP 困難である.
　以前, 我々はこの問題に対して２段階の発見的解法を提案した. このアルゴリズムは, １段階目に木の候補を生成し, ２段階目に生成したそれぞれの木のパッキング回数を決定する. 本論文では, ラグランジュ緩和を用いることで１段階目を改善した. 計算実験により, 提案アルゴリズムは以前のアルゴリズムより速く木を生成でき, 少ない木の候補でもよい解を得ることを確認した.

2011年度第1回 SCOPE講演会

開催が１週間後となりましたので再掲します。終了後は後楽園駅近辺で懇親会も予定しています。

○2011年度 第1回 SCOPE 講演会

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

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

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

SCOPE@つくば -未来を担う若手研究者の集い2011 報告

5月28日、29日と SCOPE@つくば合宿を行いまして、台風や余震等が続いておりましたが特にトラブルもなく無事に終了しました。以下が簡単な開催報告となります。

一般発表：２５件
５大学交流授業「問題発見とモデル化」：１２件
参加者：１２５人

最優秀発表賞：
木村慧（東京大学情報理工学系研究科数理情報学専攻D1）整数線形不等式系に対する符号情報に基づく計算複雑さの指標

優秀発表賞：
川矩義（筑波大学システム情報工学研究科社会システム工学専攻M2）線形順序付け問題に対するラグランジュ緩和と釘付けテスト
Byungjun You （防衛大学校理工学研究科情報数理D3）DP Solution Algorithms for the Multi-Period Knapsack Problem with Carry-Over Capacities
牧田純弥（中央大学理工学研究科情報工学専攻M1）スライディングブロックパズルを用いた画像再構築
岡田佳也（東京農工大学工学府情報工学専攻M1）現実的な制約を考慮した優等列車停車駅の決定 -JR 南武線を実例として-
相浦大司（東京大学情報理工学系研究科数理情報学専攻M1）行列＊代数を用いた対称構造物の釣合経路追跡法
田中未来（東京工業大学大学院社会理工学研究科経営工学専攻D1）0-1 整数変数を含む非凸2 次最適化問題に対する面的縮小を用いた非負半正定値緩和

開催日 : 2011年5月28日(土), 29日(日)
会　場 : 筑波大学 筑波キャンパス 春日地区 講堂
参加費 : 無料（ただし, 宿泊, 懇親会への参加は有料）
事前登録 : 不要

SCOPE＠つくば プログラム決定

SCOPE つくば合宿のプログラムが決定しました。以下のホームページを参照下さい。

SCOPE＠つくば -- 未来を担う若手研究者の集い2011 --
開催日 : 2011年5月28日(土), 29日(日)
会　場 : 筑波大学 筑波キャンパス 春日地区 講堂
参加費 : 無料（ただし, 宿泊, 懇親会への参加は有料）
事前登録 : 不要

発表件数は２５件（2010年23件、2009年21件）となりました。宿泊者の述べ人数は５１名です。もちろん宿泊無しで２８日、２９日とそれぞれ日帰りでの参加は可能です。懇親会も参加下さい。当日参加や懇親会については事前の予約は必要ありません。

筑波大学は３月１１日の大震災でかなりの被害をうけましたが、関係者の方の努力で今年も開催することが出来ました。今後も大規模な余震が起きる可能性は否定できませんが、春日キャンパスの会場は３月１１日の本震においても大きな被害は無かったと聞いております。

日本OR学会2011年春季研究発表会中止と SCOPE延期のお知らせ

３月１７、１８日開催予定の日本OR学会2011年春季研究発表会は中止となりました。

日本オペレーションズ・リサーチ学会2011年春季研究発表会中止のお知らせ

また 19 日開催予定の 2011 年度第1回 SCOPE講演会は延期となりました。今後開催時期等については決定次第お知らせしたいと思います。

SCOPE@つくば -未来を担う若手研究者の集い2011

今年も SCOPE@つくば合宿を行う予定です。以下は開催日等の情報ですが、今後変更する予定もありますのでご注意下さい。任期３年目ということでいよいよ SCOPE@つくば合宿も今年で最後となります。

開催日 : 2011年5月28日(土), 29日(日)　（予定）
会　場 : 筑波大学 筑波キャンパス 春日地区 講堂（予定）
参加費 : 無料（ただし, 宿泊, 懇親会への参加は有料）
事前登録 : 不要（ただし, 筑波大学の宿泊施設利用希望の場合は必要）

2011年度第1回 SCOPE講演会

2011 年度の第１回 SCOPE 研究会をOR学会後の 3月19日に行ないます。当日は土曜日のため 6号館では暖房が使えませんので、3号館の 3300 号室を用います。夜は懇親会もありますので、是非ご参加下さい。

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

講演2
講演者 ： 今野浩氏　 (中央大学 理工学部 経営システム工学科)
題目 ： 数理計画法とともに過ごした半世紀
概要 ： 最初に、われわれのグループの最新の研究成果：「最大マージン超楕円面を用いた企業の格付け」を
手短に紹介した後、"数理計画法とともに過ごした50年"を回顧したいと思います。

2010年度第5回 SCOPE講演会

2010年度最後の SCOPE 講演会開催は今週の土曜日となりました。是非ご参加下さい。

○2010年度第5回 SCOPE 講演会
日　時 ： 2011年2月26日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6 号館　6402号室
講演1
講演者 ： Thorsten Koch氏 （Zuse Institute Berlin(ZIB), Berlin）
Title: How to survive Real-World Projects as a Mathematician
(Lessons and experiences from 10 years of industry projects)

Abstract: This talks aims at sharing the experience from 10 years of
successfully employing integer programming in industry projects with the
audience. After numerous research-industry collaboration projects we
found that there are several reoccurring topics during these projects.
The problems encountered seem to be universally the same, as there are
very common misunderstandings between the partners. We will try to draw
some general conclusions and using the projects of the author as
examples to show some common pitfalls. We will talk about acquiring
projects, getting them running and how to explain the results to
practitioners. Listening to this talk requires no particular knowledge
of mathematics.

講演2
講演者 ： 品野勇治氏　（Zuse Institute Berlin(ZIB), Berlin）
Title: Parallel MIP solvers developed at ZIB: current state of the art
Abstract:
混合整数計画(MIP: Mixed Integer Programming)ソルバの近年の性能向上は著しく，
様々な現実問題が混合整数計画問題に定式化され解かれるケースも増えつつある．
商用の混合整数計画ソルバの多くは，既にマルチ・スレッド化され並列化されて
いる．本講演では，ZIB(Zuse Institute Berlin)で開発されている並列混合整数
計画ソルバ群について紹介する．並列混合整数計画ソルバは，既存の混合整数計画
ソルバを並列化する共通のソフトウェア・フレームワーク上に構築されている．
そのフレームワークの概要と，北ドイツ最大のスーパーコンピュータHLRN IIによる
最新の数値実験結果（１ジョブの実行に最大7,168コアを利用）について報告する．

2010 年度第４回 SCOPE 講演会

11月20日に SCOPE 講演会を行います。今回はファイナンスと多項式最適化及びサプライ・チェインに関する講演（２件）になります。是非ご参加下さい。

日　時 ： 2010年11月20日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6 号館4階 6410号室
講演1
講演者 ： 高野 祐一氏（筑波大学, 日本学術振興会PD）
講演題目 ： コンスタント・リバランス・ポートフォリオ選択問題に対する多項式最適化アプローチ
講演概要：
ポートフォリオ選択問題とは、手持ちの資金を各金融資産に投資して運用する際の投
資比率を決定する問題である。本発表では、コンスタント・リバランス戦略を採用し
た多期間ポートフォリオ選択問題を扱う。コンスタント・リバランスとは、計画期間
の複数時点で一定比率にリバランス（投資比率の修正）を行う投資戦略であり、実務
で採用されることも多く、理論的にも好ましい性質を持つ。しかし、この戦略を採用
した多期間ポートフォリオ選択問題は非凸計画問題となるため、その大域的最適解を
得ることは難しい。一方で、平均‐分散基準を利用することで問題は多項式計画問題
として定式化され、本発表では Lasserre (2001) によって提案された「多項式計画
問題に対する半正定値計画緩和」を利用して求解を試みる。さらに、次数の高い多項
式計画問題を解くことを目的に、Lasserre (2001) の半正定値計画緩和を利用した切
除平面法を提案し、数値実験によってその性能を検証する。

講演2
講演者 ： Mozart Menezes氏　（Zaragoza Logistics Center, Zaragoza (Spain)）
講演題目 ： Correlation and Disruption Induced Effects on Location Problems
講演概要：
In this work we study a class of locations models where facilities may fail.
The problems are defined in a network and some important properties of the
objective functions are analyzed. Asymptotic results were obtained suggest
behavioral consistency of location patterns as function of the probability
of failure. In order to go beyond those asymptotic results and, in order to
accept the fact that failures may be correlated, we shift methodology and also
present results developed in a continuous location setting: a simple (yet classic)
2-facility problem on a unit segment, with customer demand distributed uniformly
over the segment. We analyze problems with Median and Center objectives under complete
and incomplete customer information regarding the state of facilities. Managerial
insights are discussed.

2010 年度第３回 SCOPE 講演会

10月2日に SCOPE 講演会を行います。今回は整数計画問題に関する講演（２件）になります。是非ご参加下さい。

日　時 ： 2010年10月2日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6 号館4階 6410号室
講演1
講演者 ： Karen Aardal氏（Delft Institute of Technology and CWI - Amsterdam）
講演題目 ： Integer programming, lattices, reduced bases
講演概要：
I will discuss how to use the structure of lattices to reformulate and solve
integer programming problems. I will take a closer look at integer knapsack
problems and illustrate how it is possible to use the structure of lattices
to prove properties of certain classes of knapsack problems, and how these
properties can be used in designing practically efficient algorithms.


講演2
講演者 ： Timo Berthold氏（Zuse Institute Berlin(ZIB), Berlin）
講演題目 ： Solving MIQCPs with SCIP
講演概要：
Mixed-integer programming (MIP) and constraint programming (CP) proved to be powerful tools to model and solve
large-scale optimization problems. Constraint integer programming (CIP) is a novel generalization of MIP that
supports the notion of arbitrary constraints as in CP. We introduce the algorithmic ideas of CIP and present
SCIP, a framework for constraint integer programming.
We show how to extend SCIP towards a solver for mixed integer quadratically constrained programs (MIQCPs).
The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies
already implemented in SCIP. We give an overview of the relaxation, reformulation, separation, and propagation
techniques that are used to handle quadratic constraints efficiently. Computational experiments indicating
the potential of the approach are provided.
In the second part of the talk, we present Undercover, a primal heuristic for mixed-integer nonlinear
programming (MINLP). The heuristic constructs a MIP subproblem (sub-MIP) of a given MINLP by fixing a subset
of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed
in order to linearize each constraint. Subsequently, these variables are fixed to approximate values, e.g.
obtained from a linear outer approximation. The resulting sub-MIP is solved by a MIP solver. We present
computational results on a general test set of MIQCPs selected from the MINLPLib.

2010 年度第2回 SCOPE 講演会

次の土曜日(10日)に SCOPE 講演会を行います。蒸し暑い時期ですが、飲み会も兼ねてご参加下さい。次は夏休みを挟んで 10月2日の予定です。

日　時 ： 2010年7月10日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6 号館4階 6418号室
講演1
講演者 ： 金森敬文氏　（名古屋大学 大学院情報科学研究科 計算機数理科学専攻）
講演題目 ： 密度比の推定と計算 ―smoothed analysis からのアプローチ
講演概要：
２つの確率密度の比 (密度比) の推定は，機械学習における重要な課題のひと
つである．例えば，共変量シフト下での回帰分析，外れ値検出，ダイバージェ
ンス推定，条件付き確率密度の推定など，さまざまな統計的推論の問題が密度
比推定の枠組で定式化される．本発表では，密度比推定に対してカーネル関数
と最小２乗法を用いた学習アルゴリズムを提案し，その統計的ないし数値的性
質について考察する．計算効率や数値安定性などの性質は，計算対象となる関
数から定義される条件数と関係が深い．統計的推論においては，データがラン
ダムなので条件数もランダムな確率変数となる．ランダムネスのある状況下で，
学習アルゴリズムの計算効率を議論するために，計算量の分野で提案されてい
る "smoothed analysis" の考え方を利用する．この視点から，提案法は他の
方法と比べて，広いクラスの確率分布に対して条件数が小さな値に分布するこ
とを示す．これにより，提案法が大規模データに対して高い計算効率を持つこ
とが，理論的に裏付けられる．また，学習アルゴリズムを設計するための枠組
として，smoothed analysis の考え方を積極的に利用することの有用性につい
て，今後の可能性を探る．

講演2
講演者 ： 安井雄一郎氏　（中央大学 理工学研究科 博士後期課程）
講演題目 ： 大規模最短路問題に対するダイクストラ法の高速化
講演概要：
最短路問題はネットワーク上の経路探索などの多くの応用を持ち, また他の最適化
問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.
そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.
最短路問題に対する解法にはダイクストラ法などの安定的かつ効率的な高速アルゴ
リズムが存在するが, 実問題は非常に大規模(約2,400万点, 約5,800万枝)になるため
高速化が不可欠である. そこで本研究では, バイナリ・ヒープを適用したダイクス
トラ法に対し,メモリ階層構造を考慮した汎用的かつ効率的な高速化を適用することで,
実行性能, グラフ特性に対する安定性, メモリ要求量, 並列実行など, 総合的に最も
優れたソルバーを開発することに成功した. 計算機上の律速箇所を解析するための
実験方法を合わせて示し, 本実装の有用性を裏付けていく.

SCOPE@ つくば -未来を担う若手研究者の集い2010 : 25日夜の懇親会

25日夜の懇親会ですが、以下の場所で１９時半から開始することになりました。参加希望者の方は連絡をお願い致します。お手数ですが、宿泊施設にチェックイン後に直接以下の場所までお越し下さい。

季彩かがり
http://www.kisai-kagari.com/

所在地
〒305-0032 　茨城県つくば市竹園1-9-2　ディスタウンB1
TEL・FAX
029-875-7219

SCOPE@ つくば -未来を担う若手研究者の集い2010- 連絡 ６月７日

現時点で確定している情報をお伝えします。随時更新しますので SCOPE つくばの HP もご覧下さい。

○一般講演 23件
１：筑波大学 7件
２：中央大学 5件
３：東京工業大学 2件
３：防衛大学 2件
３：京都大学 2件
３：東京大学 2件
７：慶應大学 1件
７：九州大学 1件
７：理化学研究所 1件

○特別講演 4件

○宿泊希望者５３名、２５日宿泊希望者９名
宿泊場所は大学会館、天久保、春日の３箇所
２５日の夜に前夜祭（飲み会）を予定しています。場所と時間については HP やブログに掲示します。

○２６日の予定 9時20分開始、18時終了、懇親会18時半開始
○２７日の予定 9時開始、16時15分終了