日本OR学会「計算と最適化の新展開」研究部会

• 松井知己氏（中央大学）
• [題目] この先は工事中です
• 最適化とアルゴリズムに関する近年の研究を，いくつか取り上げて紹介します．
  ただし，個人的な興味をもとに話題を選択しますので，偏ったものになる予定です．

• 今堀慎治氏（東京大学）
• [題目] メタ戦略の新展開
• メタ戦略とは，局所探索法や欲張り法を基本とした実用的な近似アルゴリズムの総称であり，コンピュータの
  急速な進化とともに，様々な分野において広く用いられるようになった技術である．この講演では，まず，
  メタ戦略の歴史と代表的なアルゴリズムを紹介する．さらに，最近の研究の主流となりつつある，メタ戦略と
  他手法（線形・非線形計画，動的計画など）を融合する枠組みであるハイブリッドメタ戦略に関して，その
  考え方と具体的なアルゴリズムについて述べる．

• 久保幹雄氏（東京海洋大学）
• [題目] サプライ・チェイン最適化について研究者・実務家が知っておくべき基礎理論
• サプライ・チェイン最適化について研究者・実務家が知っておくべき基礎理論には様々なことあるのだが，
  ここでは最適化に絞ってお話しする．数理計画：混合整数計画（MIP）ソルバーを利用する際には，定式化の
  強さについて留意する必要がある．しばしば，Large-Mを多用したMIPソルバーが泣きを入れるような定式化を
  みかけるが，ちょっとした理論を知るだけで，それを避けることができる．また，Lagrange緩和や列生成法を
  統一的した分解法のフレームワークを紹介し，頑強でかつ実務的にも有効な解法を構築するための使い分けや
  コツについて論じる．また，実務的な問題を解くためのアルゴリズムの選択は，理論家が論文を書くための
  それと異なることなどの経験的哲学についても，時間が許せば触れるつもりである．

• 矢部　博氏（東京理科大学）
• [題目] 非線形最適化法 事始
• 非線形最適化問題は制約条件の無い最小化問題と制約条件の付いた最小化問題とに分けられます。最近では
  大規模な問題を解くための数値解法が研究されています。本発表では、導関数を用いない数値解法（直接探索法）、
  １次導関数を用いた数値解法（共役勾配法を中心として）、２次導関数を用いた数値解法（逐次２次計画法、
  内点法を中心として）をそれぞれ紹介し、最近の話題について解説します。

• 高野祐一氏（筑波大学 システム情報工学研究科 社会システム・マネジメント専攻）
• [題目] 取引コストを考慮したコンスタント・リバランス・ポートフォリオ最適化
• 本発表では、リバランスの際の取引コストを考慮して、コンスタント・リバランス戦略を用いた
  多期間ポートフォリオ最適化問題を定式化し、局所探索解法を提案し、計算実験の結果を報告する。

• 神山直之氏（中央大学 理工学部 情報工学科）
• [題目] 辺容量が一定のグリッドを一般化した動的ネットワークにおける普遍的最速フロー問題に対する多項式時間アルゴリズム
• 本発表では，最速かつ任意の時刻において最大のサプライを流すことのできる動的フローを
  求める問題が，辺容量が一定のグリッドを一般化したネットワーク上では多項式時間で解けることを示す．

• 山口大輔氏（中央大学大学院 理工学研究科 情報工学専攻）
• [題目] An Improved Approximation Algorithm for the Traveling Tournament Problem
• 本研究では、巡回トーナメント問題を解く近似解法の提案を行う。3連続のホームゲームや3連続の
  アウェイゲームの無いスケジュールを作成する問題については、提案手法の近似比率は約5/3となっている。

• 安井雄一郎氏（中央大学 理工学研究科 経営システム工学専攻）
• [題目] 大規模最短路問題に対する高速処理システム - メモリ階層構造の考慮とクラスタ&クラウド技術による高速化 -
• 本発表では、当研究室で公開している最短路問題オンライン・ソルバーの説明を行う。クラスタ・コンピューティングや
  クラウド・コンピューティングとの融合により、負荷に応じた動的な計算機資源の確保/解放が可能となった。

• 佐藤潤一氏（九州大学 大学院数理学研究院）
• [題目] レプリケータダイナミクスの頂点の不安定性と対称ゲームとの関係
• 進化ゲーム理論の柱のひとつであるレプリケータダイナミクスについて、不安定な定常点と対称ゲームとの関係は
  よくわかっていない。そこで、本発表では頂点に絞って、対称ゲームとの関係を明らかにする。

• 小林佑輔氏（東京大学大学院 情報理工学系研究科 数理情報学専攻）
• [題目] (n-3)-連結度増大問題に対するマトロイド構造を利用したアルゴリズム
• 本発表では，頂点数 n の (n-4)-連結グラフが与えられたときに，できるだけ少ない数の新しい辺を加えてグラフを
  (n-3)-連結にする問題を考え，この問題に対する多項式時間アルゴリズムを紹介する．

• 高松瑞代氏（東京大学大学院 情報理工学系研究科 数理情報学専攻）
• [題目] 混合行列束のKronecker標準形の組合せ論的解析
• 各成分の次数が高々1の多項式行列を行列束という．行列束はKronecker標準形という正準形を持つ．
  本研究では，正確な数値と独立パラメータを区別する混合行列束のKronecker標準形を組合せ的に解析する．

• 林俊介氏（京都大学 情報学研究科）
• [題目] ある構造をもつロバスト最適化問題に対する半正定値計画変換
• 本研究では，特殊な構造を有するロバスト最適化問題を，非凸二次計画問題の強双対性の理論を用いて，
  半正定値計画問題に変換することを考える．さらに，数値実験により，既存の変換法との比較を行う．

• 伊藤好彦氏（京都大学 情報学研究科）
• [題目] 線形二次錐計画問題に対する半無限計画変換を用いた単体法的アプローチ
• 本発表では，線形二次錐計画問題を半無限計画問題に変換し，単体法的手法を適用する．また，
  数値実験により，構造が類似した複数の問題を逐次的に解く場合に，本手法が有効であることを検証する．

• 山中翔太氏（京都大学 情報学研究科）
• [題目] 絶対値計画問題に対する主双対法と逐次線形化アルゴリズム
• 本研究では，絶対値方程式に変換した絶対値計画問題に対して逐次線形化アルゴリズムを適用する方法を提案し，
  数値実験を行う．その結果，広い範囲から選んだ初期点に対して最適解に収束することを確認する．

• 流王智子氏（筑波大学大学院 システム情報工学研究科 社会システム工学 卒）
• [題目] グラフによってきまる提携構造をもつゲームの解
• 本研究では、グラフ構造によって協力関係が制限されている下でプレイヤー全体で得た財の各プレイヤーへの
  配分問題を考える。既存の解を満たす公理を拡張し、新しい解とゲームのコアとの関係について考察を行う。

• 荻原隆一氏（東京工業大学 情報理工学研究科 数理・計算科学専攻）
• [題目] 剛性を維持した極小部分グラフへの縮小
• 本発表では、グラフ理論のひとつである剛性理論に着目し、あるグラフを剛性を維持した極小部分グラフへ
  縮小する方法を紹介する。また、計算実験の結果を報告する。

• 北原知就氏（東京工業大学 社会理工学研究科 経営工学専攻）
• [題目] 重みつき最小2乗法と層別最小2乗法の定量的関係について
• 本発表では、層別最小2乗法とは何か、またその歴史的経緯を説明し、一般的な重みつき最小2乗法と
  層別最小2乗法の定量的関係が、行列のある条件数を用いて得られることを示す。

• 木幡周治氏（筑波大学大学院 システム情報工学研究科 コンピュータサイエンス専攻）
• [題目] ポリゴン情報の最小トライアングルストリップ化
• ポリゴンモデルの位相情報(三角形の接続情報)に対して最小のトライアングルストリップ化を行う.
  最適化問題へ定式化を行い，それを元にしたヒューリスティクスを提案する.

• 角田淳史氏（筑波大学 システム情報工学研究科 社会システム工学専攻）
• [題目] メニュー販促を考慮した売場陳列決定モデル
• 本発表では，平成20年度データ解析コンペティションで提供された食MAPのデータを用いて，
  小売店におけるメニュー販促と陳列材料を決定するモデルについて報告する。

• 今道貴司氏（京都大学大学院 情報学研究科 数理工学専攻）
• [題目] 矩形ストリップパッキング問題に対する厳密解法
• 与えられた矩形を、幅が固定の容器の中に高さが最小となるように配置するストリップパッキング問題に対して、
  矩形の配置の標準形を利用した分枝限定法を紹介し、計算実験の結果を報告する。

• Paul Buckland氏（筑波大学大学院 システム情報工学研究科 コンピュータサイエンス専攻）
• [題目] Global Optimisation in the New Zealand Electricity Market
• An interesting optimisation problem occurs in the day-to-day running of the electricity system in New Zealand.
  This problem is usually simplified to allow faster solution times, by enforcing restrictions on the electricity market.
  In this presentation , we try removing these restrictions, which leads to an optimisation problem with multiple local solutions.
  We formulate the problem as a d.c. programming problem and apply a global optimisation method.

• 越川 満氏（筑波大学大学院 システム情報工学研究科 コンピュータサイエンス専攻）+内山将夫氏ほか3名との共著
• [題目] 統計翻訳におけるフレーズ対応最適化を利用した翻訳候補のリランキング
• 本研究では対訳文に対してフレーズ対応を求める問題を　整数計画問題として定義し、統計翻訳システムに応用する
  手法について提案する。翻訳実験の結果、提案手法により翻訳精度が有意に改善されることが確認された。

• 佐野良夫氏（京都大学大学院　理学研究科　数学・数理解析専攻）
• [題目] 凸幾何上に定義されたマトロイドにおける制限と縮約
• 本発表では、凸幾何上に定義されたマトロイドの制限や縮約といった作用と
  凸幾何上のマトロイドのある部分クラスとの関係について考察する。

• 藤原 稔久氏（大阪大学大学院 情報科学研究科 情報数理学専攻）
• [題目] 作業分割および短縮費用に基づく動的プロジェクトスケジューリングに関する基礎的研究
• 本発表では，プロジェクト実行過程におけるスケジュール修正方策として，作業分割および短縮費用に基づく 方策を提案する．
  また，数値実験の結果を報告する．

• 松川恭明氏（筑波大学大学院 システム情報工学研究科 社会システム工学専攻）
• [題目] 二次割り当て問題に対する完全正行列を用いた緩和について
• 本発表では,完全正性を用いて定式化した二次割り当て問題に対しての半正定値緩和を紹介する.
  また,その計算実験の結果について報告する.