■第18回研究会(2005年11月19日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『資源節点集合を持つグラフを均等分割する問題について』豊橋技術科学大学 石井 利昌 氏
資源節点集合を持つグラフを均等分割する問題とは,グラフGと資源節点集合族 {T1,T2,…,Tk} (|Ti|:偶数)が与えられたとき,次の(i)(ii)を満たすGの2分割{G1,G2}を求める問題である.(i) Gj, j=1,2は連結である.(ii) Gj, j=1,2は各Tiの節点を丁度|Ti|/2個含む.一般の場合,与えられたグラフにこのような分割が存在するかどうか判定する問題は,NP困難であることが知られている.一方で,k=1, 2のとき,それぞれグラフが2点連結, 3点連結であれば必ず分割が存在することが知られている.本発表では,k=3の場合を中心に,分割が存在するための十分条件とグラフの連結度の関係について紹介する. なお, 本研究は, 岩田健吾(マツダ), 永持仁(京都大学)との共同研究である.
 
16:10--18:00『不確実な最適化問題に対するConditional Value-at-Riskアプローチとその機械学習への応用』東京工業大学 武田 朗子 氏
現実の問題には様々な不確実性が存在しており,その不確実性に対処するための1つの方法としてロバスト最適化が注目を集めている.ロバスト最適化法は,不確実性の範囲をあらかじめ設定し,その中で最悪の状況が生じた場合を想定して最適化を行う方法である.不確実性をうまく記述することによって,不確実な最適化問題を解きやすい問題(二次錐計画問題や半正定値計画問題)に帰着できるという利点があるものの,一方で,応用を考えた場合にロバスト最適化による最適解は"保守的すぎる"と評されることもある.

そこで本発表では,ロバスト最適化のように1つの最悪状況を想定して最適化を行なうのではなく,conditional value-at-risk (CVaR) を用いて幾つかの状況を想定して最適化を行なう手法を提案する.提案手法がロバスト最適化と確率計画法(目的関数値の期待値を評価して最適化)の中間的なアプローチになっており,二値判別に適用するとν-support vector machine (ν-SVM)と同等のモデルが得られることを示す.

 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.