成 瞑 大 学 理 工 学 研 究 報 告 J.Fac.Sci.Tech.,SeikeiUniv. Vol.54No.2(2017)pp.17-20
組 合 せ 最 適 化 問題 に対 す る ロバ ス ト最 適 化
呉
偉*1
RobustOptimizationfbrCombinatorialOptimizationProblems
WeiWU*1
ABSTRACT:Manycombinatorialoptimizationproblemsarisinginreal-worldapplicationsdonothave
accurateestimatesoftheproblemparameterswhentheoptimizationdecisionistaken.Stochastic
programmingandrobustoptimizationaretwocommonapproachesforthesolutionofoptimization
problemsunderuncertainty.Inthispaper,wedescribethecommondefinitionsofuncertaintyset,aswellas
3criteria,min-max,min-maxregretandmin-maxrelativeregret,toevaluateasolution.Furthermore,we
presentgenerallemmasfbrobtainingworstcasescenariosbasedonagivensolution.
Keywords:robustoptimization,combinatorialoptimization,min-maxregret,robustlevel
(ReceivedOctober30,2017)
1.は じ め に技 術 革 新 に 伴 い,大 量 の 情 報 資 源 を有 効 に利 用 す る最
適 化 手 法 の 必 要性 が 高 ま っ て きた.現 実 社 会 の 重 要 な 意
思 決 定 の 多 くが組 合 せ 最 適 化 問 題 と して 定 式 化 で き る.
この よ うな 問題 を解 決 す る方 法 と して さま ざま な 最 適 化
手 法 が 提案 され て き て い る。 厳 密 な 最 適 解 を求 め る手 法
で あ る分枝 限 定 法 や 動 的 計 画 法,そ
して,最 適 性 の 保 証
は な い が 良 質 の 解 を 出 来 るだ け効 率 良 く求 め よ うとす る
発 見 的解 法 な どで あ る.分 枝 限 定 法 の 近 年 の 発 展 は 目覚
ま し く,実 用 的 で 汎 用 性 の 高 い 解 法 と して 多 くの 数 理 計
画 ソフ トウェ ア の エ ンジ ン と して利 用 され て い る.発 見
的解 法 の 多様 な ア イ デ ィア を うま く組 み 合 わ せ る こ と に
よっ て 高 い性 能 を 得 よ うとす るパ ラダ イ ム で あ る メ タ戦
略 の 有 用性 は 広 く認 知 され る よ うに な っ て き た.
しか し,最 適 化 手 法 の ほ とん どは,入 力 デ ー タが 既 知
とい う前 提 の も とに ア ル ゴ リズ ム が 設 計 され て い る.一
方 で,多
くの 現 実 問題 に お け る入 力 デ ー タ には 曖 昧 さや
不確 定 要 素 が 内 在 して い る.た と えば,生 産 計 画 を立 て
るた め に 最適 化 問題 を 解 く段 階 で は,需 要 が 確 定 して お
らず,需 要 予 測 に基 づ い て計 画 を行 わ な けれ ば な らな い.
した が っ て,「計 画 段 階 で 別 の 判 断 を して い れ ば も っ と利
益 が 上 が っ た の に 」 と後 悔 す る こ と の な い よ うな 計 画, つ ま り,入 力 デ ー タ の 変 動 に 大 き く影 響 さ れ な い よ うな 解 が 望 ま れ る.不 確 定 要 素 を 深 く 考 慮 せ ず,た と え ば 予 測 値 を そ の ま ま 入 カ デ ー タ と し て 既 存 の 最 適 化 手 法 を 適 用 し て 得 られ た 解 が,実 用 に お け る 良 い 解 に な る と は 限 ら な い.も う 一 つ の 例 と し て,渋 滞 予 測 に 基 づ い て 平 均 所 要 時 間 最 短 の ル ー トを 選 ん で も 天 気 や 渋 滞 の 要 因 で 最 も早 く着 く と は 限 ら な い. ロバ ス ト最 適 化(robustoptimization)と は,こ の よ う な 問 題 の 入 力 に 不 確 定 さ 或 は 曖 昧 さ が 内 在 し て い る 場 合 に も,信 頼 で き る結 果 を 返 す よ うな モ デ リ ン グ 技 法 及 び そ の 解 法 を 指 す 。 組 合 せ 最 適 化 問 題 の ロバ ス ト最 適 化 に 関 す る研 究 は, 1997年 にKouvelisら が 発 足 した1).2006年,Bertimasら は 入 力 デ ー タ の 不 確 定 さ分 布 が な い 場 合 に ロ バ ス ト レ ベ ルFを 考 慮 し た 設 定 を 提 案 し た2).2009年 に,Aissiら は 基 本 のmin-maxモ デ ル よ り実 用 性 の 高 いmin-maxregret モ デ ル に 関 す る 研 究 を サ ー ベ イ し た3).古 典 的 な 組 合 せ 最 適 化 問 題 と し て,最 短 路 問 題 や,巡 回 セ ー ル ス マ ン 問 題 や,一 般 化 割 当 問 題 な ど の ロ バ ス ト最 適 化 に 対 し て, 厳 密 と近 似 ア ル ゴ リ ズ ム が 提 案 さ れ て お り4)・5)・6),経済, 建 築,都 市 計 画,化 学 な ど 多 数 の 分 野 で 応 用 事 例 も あ げ られ た7). *1:情 報 科 学 科 助 教(wuwei@st ,seikei.ac.jp) 一17一成 践 大 学 理 工 学 研 究 報 告
Vol.54No.2(2017.12)
2.不
確 定 さ の 設 定
本 論 文 で は 目 的 関 数 の 係 数 に 不 確 定 さ が 内 在 す る ケ ー ス を 中 心 と し て 議 論 す る.決 定 要 素 の 集 合 を ハ1ニ {1,2,...,n},要 素 ご(∈N)に お け る 目 的 関 数 の 係 数 をCi, 整 数 制 約 あ り の 決 定 変 数 を κi,ま た,実 行 可 能 領 域 をX と す る 場 合 に,線 形 目 的 関 数 を 持 つ0-1組 合 せ 最 適 化 問 題 は min(ormax)Σ 窪1C`κ` subjecttoJC∈X⊆{O,1}n (1) (2) の よ うに 定 義 で き る.式(1)と(2)の 形 は,最 短 路 問 題(shortestpathproblem),割 当 問 題(assignmentproblem), 最 小 全 域 木 問 題(minimumspanningtreeproblem)な ど の よ うな 多 項 式 ア ル ゴ リズ ム の 存 在 す る 問 題 や,ナ ッ プ サ ッ ク 問 題(knapsackproblem),一 般 化 割 当 問 題(generalized assignmentproblem),集 合 被 覆 問 題(setcoveringproblem) な ど の よ うなNP困 難 な 問 題 を 含 め,多 く の 種 類 の 組 合 せ 最 適 化 問 題 を 表 せ る. ロ バ ス ト最 適 化 の 一 つ の 特 徴 と し て,不 確 定 な 入 力 に 関 す る 特 定 な 確 率 分 布 が な い 場 合 で も,信 頼 で き る 解 を 求 め る こ と が で き る.目 的 関 数(1)で のcの 取 り う る値(シ ナ リオ)の 集 合 を σ と し,θ は 離 散 で あ る 場 合 と連 続 で あ る 場 合 が あ り,そ れ ぞ れ 離 散 シ ナ リオ と 連 続 シ ナ リオ と 呼 ぶ.連 続 シ ナ リオ の 中 に 単 純 区 間 と ロ バ ス ト レベ ル を 考 慮 し たFロ バ ス トな ど の 凸 多 面 体 が 多 く の 研 究 に 使 用 さ れ た.(そ の ほ か に も 楕 円 型 の 集 合 な ど の 設 定 も あ る 8).)単 純 区 間 の設 定 で は,各 要 素`に お い て,標 準 値ciと 変 動 幅 δi(≧0)が 与 え られ,係 数c`が[ci一 δi,ci十 δ`]区 間 で の 値 が 取 り得 る,す な わ ち,
〔ノ ニ{(Cl,C2,...,Cn)1∀i∈ ハ1,Ci=ci十 δiγi,
γi∈[-1,1]}.(3)
現 実 に 近 い 不 確 定 さ を モ デ ル に取 り組 む た め に,近
年
Bertsimasら よ り,ロ バ ス トレベ ル(F上
限)を 考 慮 で き
る連続 シ ナ リオ が 提 案 され た2).不
確 定 要 素 の 予 測 値 か
ら外 れ る個 数(必 ず し も整 数 とは 限 らな い)の 最 大 レベ
ル を表 す パ ラ メ ー タFを
設 定 す る こ とで,よ
り一 般 化
した 不確 定集 合 が 設 定 で き る:
Uニ{(Cl,c2,...,Cn)1∀i∈N,Ciニci十 δiγi, γi∈[-1,1]andΣi∈N1γi1≦r}.(4)特 殊 ケ ー ス と して,Fニ0の
場 合 は 変 動 な しの 古 典 的
な 組 合 せ 最 適 化 問 題 と な り;F=nの 場 合 は,単 純 区 間 の 設 定(3)と な る.Fレ ベ ル の 設 定 に よ り,単 純 区 間 の 一 般 化 を 実 現 で き る が,そ の 設 定 で の ロ バ ス ト最 適 化 問 題 が さ ら に 難 し く な る.3.ロ
バ ス トな 解 の 評 価 基 準
不 確 定 集 合 ひの 下 で ロ バ ス ト最 適 化 の 解 評 価 基 準 と し て,min-max基 準,min-maxregret基 準 とmin-max relativeregret基 準 が 知 ら れ て い る.問 題(1)が 最 小 化 問 題 の 場 合,min-max基 準 は minmaxΣ 』C`κ` x∈x σ∈ひ (5) の よ う に な る.ま た,係 数cがc'で あ る と き の 最 適 値 を z(c'),す な わ ち,z(c)ニminΣ 』c`κ`と す る と,解 κが シ x∈x ナ リ オCの 下 で の 後 悔 を 表 す 値 が Σ』C`κ`-Z(C)と な り, min-maXregret基 準 は minmax(Σ 匹1C西 一z(C)) X∈X σ∈ひ (6) の よ う に 表 せ る.min-maxrelativeregret基 準 で は 各 解 が 最 適 値 と割 合 で 後 悔 を 表 し て い る: Σ窪1CiXi-z(c).(7)minmax X∈XC∈UZ〔C)Min-max基 準 はmin-maxregret基 準 とmin-maxrelative regret基 準 よ り,保 守 的 と な る た め,再 決 定 す る機 会 の な い 場 合(線 路 の 設 計,原 発 事 故 の 予 防)に 応 用 さ れ る. ま た,決 定 者 の あ らか じ め 設 定 した 目標 を 達 成 す る に も, 有 効 で あ ろ う. 一 方 ,min-maxregret基 準 とmin-maxrelativeregret基 準 は 解 の 「後 悔 の 度 合 い 」 を 評 価 す る た め,投 資 問 題 な ど で はmin-max基 準 よ り,良 い 解 が 得 ら れ る傾 向 が あ る.
