過去の記録

2012年度 前期

7/5 (木) 17:00--19:00 @W9-201

  1. 講演者: 鈴木翔太氏 (経営工学専攻 中田研究室 M2)
    • 題目: 汎用的なシフトスケジューリングシステムの開発
    • 概要: 病院や店舗におけるスタッフの勤務スケジュールを決める問題はシフトスケジューリング問題として知られている. 本研究では業種, 店舗の規模にかかわらずにシフトを最適化できるようなシステムの作成を目的とした. 一般にシフトスケジューリング問題では制約の種類が多く実行可能解を見つけることすら難しい. さらに実運用を前提としたシステムでは計算時間が限られてしまうことが多い. そこで問題の構造を利用した初期解の生成と, タブー探索法を基にした局所探索を行い高速に良いスケジュールを作成することができた. 実際の店舗のデータを用いた数値実験を行い, 本システムの有用性を示す.
  2. 講演者: 高松瑞代氏 (中央大学 理工学部 情報工学科 助教)
    • 題目: 混合多項式行列の小行列式の最大次数を計算する組合せ緩和法
    • 概要: 動的システムの解析では, 有理関数行列のSmith-McMillan標準形と行列束のKronecker標準形が重要な役割を果たす. これらの標準形を計算する手法として, 組合せ緩和法が室田 (1995) により提案されている. 組合せ緩和法は, 組合せ的なアルゴリズムを用いて解の暫定値を求め, その妥当性を確認するステップにおいてのみ数値計算を行うという, 数値計算と組合せ的手法を融合した方法である. 大部分で組合せ的なアルゴリズムを用いるため効率的で数値誤差に強いだけでなく, 所与の行列の疎性を保つこともできる. 本研究では, 室田 (1995) によって与えられた多項式行列に対する組合せ緩和法の枠組みを, 混合多項式行列へ拡張する. 本研究は岩田覚氏 (京都大学) との共同研究である.

6/7 (木) 17:00--19:00 @W9-201

  1. 講演者: 吉良知文氏 (JST CREST, 中央大学 研究開発機構 専任研究員)
    • 題目: 先行順序付き合流可能配送計画問題に対する局所探索法
    • 概要: 小売店への商品の配送, ゴミ収集車の運行経路など, 複数の車両を用いて顧客に需要を運搬/収集するときの最適なルートを求める問題はいろいろなバリエーションが考えられており, 総称して運搬経路問題または配送計画問題と呼ばれる. 現実の問題においては様々な制約条件を考慮するため, 実行可能領域内で効率的な局所探索を行えないことも多い. 本発表では, 顧客間の先行順序制約および車両が合流して分担作業をするための制約条件を考慮した問題に対して, シンプルかつ強力な局所探索法を提案できたので紹介する. 提案手法は「扱い易い異なる探索空間を用意し, そこから本来の実行可能領域への写像を定義する」方法の一例である.
  2. 講演者: 穴井宏和氏 ((株) 富士通研究所, 九州大学 マス・フォア・インダストリ研究所 教授)
    • 題目: 実代数幾何と最適化---数式処理による最適化
    • 概要: 実代数幾何は, 実数体上での代数方程式・不等式系の解集合について研究する分野で, 解集合の性質 (実数解の存否, 解集合の次元, 半代数的集合としての数式表現) を探ることが中心的な研究課題である. それらの研究を構成論的に実現するために必要なのが計算代数 (数式処理) のさまざまな代数的アルゴリズムである. 特に, 実代数幾何に対する代数的アルゴリズムとしては, Cylindrical Algebraic Decomposition (CAD) とQuantifier Elimination (QE) がある. CADとQEは, (実) 解集合を探る代数的アルゴリズムであるため最適化問題の代数的解法としての顔も持つ. 本発表では、QEやCADのアルゴリズムについて簡単に説明した後に, QEによる最適化手法について応用例を交えながら紹介する.

5/10 (木) 17:00--19:00 @W9-201

  1. 講演者: 福田光浩氏 (数理・計算科学専攻 准教授)
    • 題目: 量子化学に登場する半正定値計画問題
    • 概要: 量子化学・計算化学・理論化学においての最適化は余り馴染みのない分野であるように思われるが, 実はマイナーなところで活躍をしている. 理研の中田真秀氏と長年研究しているこのテーマは, (分子の) 電子状態が一番安定する最小エネルギーを求める問題である. これは1960年代から半正定値計画問題として近似的に定式化できることが知られているが, 実際に高精度で数値的に解かれたのはSDPAなど, 半正定値計画問題を解くソフトウェアが整備されてからである.
  2. 講演者: 宮内敦史氏 (経営工学専攻 中田研究室 M1)
    • 題目: モジュラリティの上界値算出
    • 概要: 与えられたグラフを密な部分グラフに分割する操作は, コミュニティ検出と呼ばれる. コミュニティ検出結果の評価関数として, Newmanらにより提案されたモジュラリティが知られている. モジュラリティ最大化問題はNP困難であるため, 数多くのヒューリスティクスが提案されてきた. しかし一方で, 厳密解法や精度保証付き近似解法はほとんど提案されていない. さらに, モジュラリティの上界値算出に特化した手法は全く提案されていない. そのため, 提案されたヒューリスティクスの性能評価は十分に行えていないと言える. 本発表では, モジュラリティの上界値算出に特化した手法を提案する. そして, 大規模なグラフにおいて, その上界値を求める.
  3. 講演者: 笹山賢司氏 (経営工学専攻 水野研究室 M1)
    • 題目: Ineffectiveness of efficiency and inefficiency measures in Network DEA
    • 概要: Data Envelopment Analysis (DEA) とは, 事業体 (Decision Making Unit; DMU) の効率性の相対的評価を行う数理的手法である. 従来のDEAモデルでは, DMUを入力要素を出力要素に変換する単一の活動とみなし, 効率性の評価を行ってきた. 一方, DMUを複数の部門から構成される活動とみなし, 効率性の評価を行うNetwork DEA (NDEA) が近年研究させている. NDEAでは, DMUを構成する各部門の入力, 出力要素, さらに各部門間を流れる中間財 (中間要素) を用いて効率性の評価を行うモデル (NDEAモデル) が考案されている. 本研究は, 従来のDEAモデルには存在しなかったNDEAモデルに存在する特有の問題点を示し, その問題を避ける ことができるNDEAモデルを提案する.

それ以前