大規模な組合せ最適化問題に対する 発 見見的解法 大阪 大学 大学院情報科学研究科 科学技術振興機構 梅 谷俊治 2014 年年 3 月 12 日 数学協働プログラムチュートリアル ビッググラフと最適化

Transcription

1 大規模な組合せ最適化問題に対する 発 見見的解法 大阪 大学 大学院情報科学研究科 科学技術振興機構 梅 谷俊治 2014 年年 3 月 12 日 数学協働プログラムチュートリアル ビッググラフと最適化

2 講演の概要 かつては IT インフラの整備, 今は 大規模データの解析, 将来は効率率率的な計画の 立立案 運 用が重要な課題になる? 実世界から収集された 大規模データに基づく 大規模かつ多様な組合せ最適化問題を効率率率良良く解くことが求められる? これらの組合せ最適化問題の多くは NP 困難で, 現場では経験と勘に基づくアルゴリズム設計 開発が主流流? 狭い範囲の事例例にしか適 用できないノウハウではなく, 広い範囲の事例例に適 用できるアルゴリズム設計のノウハウは無いのだろうか? 本講演では以下の話題を紹介します. 組合せ最適化問題とその応 用 計算困難な組合せ最適化問題に対するアプローチ 大規模な組合せ最適化問題に対する発 見見的解法 講演途中でいくつかスライドを 飛ばすかも知れませんが, 本講演のスライドはウェブ上で公開する予定なのでご安 心下さい. 2

3 組合せ最適化問題とその応 用 3

4 最適化 手法による問題解決アプローチ 最適化は意思決定 問題解決のための 一つの 手段. 最適化問題に定式化 + 最適化計算 +( 近似 ) 最適解の分析 検証 + 最適化モデルの修正. 現実問題 最近適定式化 最適化計算 似分析 検証 化モ最デ適ル解 ( ) 解決策 最適化モデルの修正 最適化問題 制約条件を満たす解の中で 目的関数を最 小 ( 最 大 ) にする解を求める問題. 4

5 最適化問題に定式化する 生産計画問題 あるシャトーでは 3 種類のブドウ, カルベネ, メルロー, セミヨンを原料料として,3 種類のワイン, 赤ワイン, 白ワイン, ロゼワインを製造している. 収益が最 大となる各ワインの 1 日当たりの製造量量を求めよ. 種類 赤ワイン 白ワイン ロゼワイン 最 大供給量量 カルベネ (t/ 日 ) メルロー (t/ 日 ) セミヨン (t/ 日 ) 収益 ( 百万円 / 日 ) maximize 3x 1 +4x 2 +2x 3 subject to 2x 1 apple 4, x 1 +2x 3 apple 8, 3x 2 + x 3 apple 6, x 1, x 2, x 3 0. 収益を最 大化 カルベネの使 用量量は 4t/ 日以内 メルローの使 用量量は 8t/ 日以内 セミヨンの使 用量量は 6t/ 日以内 各ワインの製造量量は 非負 5

6 線形計画問題と整数計画問題 線形計画問題 (Linear Program; LP) 線形制約の下で線形関数を最 小化 ( 最 大化 ) 整数計画問題 (Integer Program; IP) 広義 : 変数に整数条件の付いた最適化問題 狭義 : 線形計画問題 + 変数の整数条件 x 2 連続変数と整数変数が混在する問題は, 混合整数計画問題 (Mixed Integer Program; MIP) LP の実 行行可能領領域 IP の実 行行可能領領域 MIP の実 行行可能領領域 x 1 のようにベクトルと 行行列列を 用いて書く場合も多い. 6

7 組合せ最適化問題 探索索空間が離離散的であるもしくは離離散的なものに減らせる最適化問題, 解が集合, 順序, 割当て, グラフ, 論論理理, 整数などの離離散構造で記述される場合が多い. 多くの組合せ最適化問題は整数計画問題として定式化できる. 組合せ最適化問題の例例 最短路路問題 ( カーナビのルート検索索, 乗換案内など ) ネットワーク設計問題 ( ライフライン, 交通 通信網, 石油 ガスのパイプライン網の設計など ) 配送計画問題 ( 宅宅配便便, 店舗 工場への製品配送, ゴミ収集など ) 施設配置問題 ( 工場, 店舗, 公共施設など ) スケジューリング問題 ( 工場の操業計画, 乗務員 看護師などの勤務表, スポーツの対戦表 日程表, 時間割の作成など ) 現実問題の多くが組合せ最適化問題として定式化できる! 整数計画問題に定式化した 方が解き易易い場合もあれば, そうでない場合もある. 7

8 巡回セールスマン問題 都市の集合と各 2 都市間の移動コスト ( 例例えば距離離 ) が与えられたとき, 全ての都市をちょうど 一度度ずつ訪問し, 出発地に戻る巡回路路の中で総移動コストが最 小のものを求める問題. 点 (i,j) 間の距離離 ( 定数 ) 枝 (i,j) を通る x ij =1, 通らない x ij =0( 変数 ) Newsweek, July 26, 1954 そのまま解くには 制約式が多過ぎる PCB3038 D15112 出典 : The Traveling Salesman Problem ( 8

9 集合分割問題 m 個の要素からなる集合 M と,n 個の部分集合 S j M が与えられたとき, 集合 M の全ての要素 i M をちょうど 1 回ずつ含む部分集合の組み合わせの中で, コストの総和が最 小になるものは? 部分集合 S j が要素 i を含む a ij =1, 含まない a ij =0( 定数 ) 部分集合 S j のコスト ( 定数 ) 部分集合 S j を選ぶ x j =1, 選ばない x j =0( 変数 ) 集合分割問題は, 配送計画, シフトスケジューリング, 施設配置, 選挙区割り, データ解析など多くの現実問題を応 用に持つ. 9

10 長 方形詰込み問題 幅が固定で 十分な 高さのある 長 方形の容器と n 個の 長 方形の荷物が与えられる. 荷物を互いに重ならないように容器内に配置する制約の下で必要な容器の 高さを最 小にするには? H 長 方形の集合 長 方形 iの幅 長 方形 iの 高さ 容器の幅 容器の 高さ W 荷物の 自由な回転は考えない 詰込み 切切出し問題は, 長 方形詰込み問題, 円詰込み問題, コンテナ詰込み問題, 多 角形詰込み問題, など図形の次元や形状によりさまざまなバリエーションを持つ. 10

11 長 方形詰込み問題 (x i, y i ) を 長 方形 i の左下隅の座標とする. 制約 1: 長 方形 i は容器内に配置される. 制約 2: 長 方形 i,j は互いに重ならない. 11

12 長 方形詰込み問題 をそれぞれ 長 方形 i が 長 方形 j の左, 右, 下, 上にあるならば 1, そうでなければ 0 を取る変数とする. そのまま解くには 制約式が多過ぎる M は 十分に 大きな定数 12

13 応 用 : 配送計画 m ヵ所の店舗に商品を配送するのに必要なトラックの台数を最 小にするような配送ルートの組み合わせは? 1 台のトラックが時間内に配送できるルートを全て列列挙すると集合分割問題として定式化できる. 1h store1 1.5h 1h 1.5h 1h depot store3 1h 1.5h 1h 1h 1.5h store5 1h store6 store2 1h store4 6 時間で配送可能な経路路を全て列列挙 c = A = 各列列が対応するルートを表す 勤務スケジュール作成問題や時間割問題も定式化できる! 13

14 応 用 : 選挙区割り m 個の市区郡を 一票の格差が最 小になるように n 個の選挙区に分割するには?( 飛び地を持つ選挙区を作ってはならない ) 市区郡を頂点とするグラフを描いて, 連結な頂点の部分集合を全て列列挙すると集合分割問題として定式化できる 施設配置問題やネットワーク設計問題も定式化できる! 根本俊男, 堀 田敬介, 区割画定問題のモデル化と最適区割の導出, オペレーションズ リサーチ, 48(2003),

15 応 用 : 機械翻訳におけるフレーズ対応 大量量の対訳 文から確率率率モデルに基づく翻訳規則を学習する. 連続する単語列列 ( フレーズ ) を最 小単位として翻訳する. 確率率率が最 大となる 入 力力 文のフレーズ区切切りと翻訳前後の訳語関係 ( フレーズ対応 ) を求める. 越川満, 内 山将夫, 梅 谷俊治, 松井知 己, 山本幹雄 : 統計的機械翻訳におけるフレーズ対応最適化を利利 用した N- best 翻訳候補のリランキング, 情報処理理学会論論 文誌, 51 (2010),

16 応 用 : 機械翻訳におけるフレーズ対応 塗りつぶした矩形の縦横に重複が起きないよう全単語を被覆する. フレーズ対応問題は集合分割問題として定式化できる. フレーズ対 kの翻訳スコア ( 定数 ) フレーズ対 kが原 言語 文のi 番 目の単語を被覆 ( 定数 ) フレーズ対 kが 目的 言語 文のj 番 目の単語を被覆 ( 定数 ) フレーズ対 kを使 用する x k =1, 使 用しない x k =0 ( 変数 ) 目的 言語 文 原 言語 文 文書要約問題も定式化できる! 16

17 応 用 : 推薦商品の最適化 顧客の過去の購 入履履歴からその嗜好を推測はできるが, 実際には実務上の様々な制約の下で, 顧客に商品を推薦する必要がある. 顧客 i に商品 j を推薦したときの期待費 用 ( 定数 ) 顧客 i に商品 j を推薦したときの期待利利得 ( 定数 ) 商品 j の総期待利利得の下限 ( 定数 ) 総期待費 用の上限 ( 定数 ) 顧客 1 人に推薦する商品数 ( 定数 ) 顧客 i に商品 j を推薦する x ij =1, しない x ij =0( 変数 ) 与えられた予算内に収める 推薦する商品が偏らない 顧客に推薦できる商品数の上限...,etc. 顧客 商品 土 谷拓拓 人, 西村直樹, 川矩義, 高野祐 一, 中 田和秀, 松本健 : 大規模な推薦商品最適化問題に対する確率率率的勾配法, 日本オペレーションズ リサーチ学会春季研究発表会,2014 年年 3 月6 日. 17

18 応 用 : 人の移動履履歴の推定 人の移動履履歴を収集 加 工したデータベースを 用いて時々刻々と変化する 人の流流れを解析する研究や調査が盛ん. 各 自治体のパーソントリップ調査や Suica などのデータがあるが任意の 目的に利利 用することは困難. 地域内の各地点に配置されたセンサーで観測される通過 人数の履履歴から 人の移動履履歴を推定できないだろうか? 2 8 時刻 センサによる観測データ ( 入 力力 ) 時刻 3 人 5 人 2 人 パーソントリップの集合 ( 出 力力 ) 熊野徹, 蓮池隆, 梅 谷俊治, 森 田浩 : 観測データに基づく 人の移動履履歴の推定, 日本オペレーションズ リサーチ学会春季研究発表会,2014 年年 3 月 6 日. 18

19 空間 応 用 : 人の移動履履歴の推定 入 力力 : ネットワーク外部との間の流流 入出者数, 各枝の移動 人数, パス候補の集合 P 出 力力 : 各パスの利利 用者数 x j (j P) 観測データと出 力力の誤差を最 小化 時刻 観測データ ( 入 力力 ) 空間 時刻 人の移動履履歴 ( 出 力力 ) multi- target tracking と呼ばれる多くの分野に現れる問題 19

20 応 用 : 基板検査プローブの経路路計画 2 本の移動型プローブを 用いてプリント基板の導通を検査. 全ての導線の導通検査にかかる時間を最 小化. 全ての導線を導通検査するのに必要な 2 本のプローブの訪問先と訪問順を決定. chip chip checked! chip Probe2 chip chip chip K.Murakami, Formulation and heuristic algorithms for multi- chip module substrate testing, Computers and Electrical Engineering, 39 (2013),

21 応 用 : 基板検査プローブの経路路計画 1. 制約付き最短路路問題に定式化 ラベリング法 2. 集合被覆問題 + 巡回セールスマン問題の 2 段解法 集合被覆問題 : 全ての導線の導通を検査するプローブの訪問先 ( 端 子ペアの集合 ) を決定 巡回セールスマン問題 : 総移動距離離が最短となるプローブの訪問順を決定 1 2 a b c 3 4 d e f 5 6 g 7 h i (1,2) (1,4) home a b a c 4 e 3 d f 6 h 5 g i 7 (3,6) (5,7) 総移動距離離が最 小になるプローブの訪問順 全ての導線を検査するプローブの訪問先 21

22 応 用 : 電気 自動 車車の充放電計画 電気 自動 車車に充放電させて蓄電池の代替として利利 用する. 電気 自動 車車を適切切なタイミングで充放電させることで, ピーク時間帯での配電系統からの受電量量の平準化と低減を実現する. 電気 自動 車車は放電時には直流流電源, 充電時には負荷となり, 出庫時には電 力力ネットワークから離離脱する. 電 力力ネットワークを時間軸 方向に拡張して, 各枝のフロー量量を決定する ( 混合 ) 整数計画問題として定式化する. 配 電 系 統 太 陽 光 発 電 A C / D C コ ン バ ー タ 交 流流 系 統 A C / D C コ ン バ ー タ 直 流流 系 統 D C / A C イ ン バ ー タ A C 負 荷 D C 負 荷 E V 1 E V 2 A C コン バ ー タ イン バ ー タ D C 配電 系 統 A C 負荷 D C 負荷 E V 1 E V 2 太 陽 光 発 電 交 流流 系 統 直 流流 系 統 交 流流 系 統 直 流流 系 統 交 流流 系 統 直 流流 系 統 時 刻 森 田浩, 小林林美佐世 : 電気 自動 車車インフラの効率率率的な運 用と設計, システム / 制御 / 情報,56 (2012),

23 計算困難な組合せ最適化問題に対する アプローチ 23

24 巡回セールスマン問題の難しさ n 都市に対して (n- 1)!/2 通りの巡回路路を列列挙すれば巡回セールスマン問題は解ける? 実際に計算機で数え上げるとどれぐらい時間がかかる? 都市数 巡回路路の総数 計算時間 秒 秒 秒 秒 秒 約 56 日 秒 約 122 万年年 秒 約 億年年 100TFlops(1 秒間に10 13 回四則演算できる ) の コンピュータの場合 フカシギの数え 小規模の問題なら良良いデータ構造を 使えば数え上げできますが 全ての解を列列挙することは現実的には不不可能 ( 組合せ爆発 ) 出典 :JST ERATO 湊離離散構造処理理系プロジェクト ( erato.ist.hokudai.ac.jp/) 24

25 組合せ最適化問題の難しさ 易易しい問題 最悪の場合でも 入 力力サイズに対する多項式時間で厳密な最適解を求めるアルゴリズムが存在する問題. 割当問題 ハンガリー法, 最 小全域 木問題 クラスカル法, 最短路路問題 ダイクストラ法など. 難しい問題 厳密な最適解を求めるのに最悪の場合に 入 力力サイズに対して指数時間を要すると多くの研究者が考えている問題. NP 困難問題と呼ばれる. ナップサック問題, 巡回セールスマン問題, 整数計画問題など. 現実社会にあらわれる組合せ最適化問題の多くは NP 困難 Yes/No を出 力力する決定問題では NP 完全問題と呼ばれる. 25

26 計算困難な問題に対するアプローチ 厳密解法と近似解法 厳密解法 : 最悪の場合に指数時間かかっても最適解を求める. 近似解法 : 現実的な計算時間で良良い実 行行可能解を求める. 汎 用解法と専 用解法 汎 用解法 : 整数計画問題や制約充 足問題などに定式化して汎 用ソルバーを適 用する. 専 用解法 : 問題特有の性質を利利 用した専 用ソルバーを適 用もしくは開発する. 現実世界の問題 a b c d e 整数計画問題 分枝限定法 現実世界の問題 a b c d e 問題 a 問題 b 問題 e アルゴリズム a アルゴリズム b アルゴリズム e 多様な問題に適 用可能な 汎 用性の 高いアルゴリズム 個々の問題の特徴を利利 用した 高性能なアルゴリズム 26

27 精度度保証付き近似解法 同時に緩和問題を解いて下界も求めるアルゴリズムを設計できれば, 任意の問題例例に対して精度度を保証できる場合がある. 緩和問題 : 原問題の 一部の制約条件を緩めた問題 線形計画緩和問題 : 整数変数の整数条件を外す 線形計画問題 ただし, 独 立立に緩和問題を解いて下界を求めれば, 得られた解の精度度を事後的に評価することは可能. 目的関数値 x 2 x 2 上界 最適値 下界 最 小化 実行可能 実行不可能 整数計画問題 x 1 線形計画緩和問題 MIP の実 行行可能領領域 LP の実 行行可能領領域 x 1 27

28 現実問題に対するアプローチ 既存の汎 用ソルバーを利利 用 現実問題が既知の最適化問題と完全に 一致することは稀. 専 用ソルバーが利利 用可能な状態で公開されていることは稀. ( 混合 ) 整数計画問題に定式化して厳密解法に基づく汎 用ソルバーを適 用する. 実 用的に解ける問題の規模が限られる場合が多い. 自分で専 用ソルバーを開発 ( 混合 ) 整数計画ソルバーでは解けない 大規模 複雑な問題. 問題構造を上 手く利利 用すれば効率率率的なソルバーが開発可能. 十分な知識識 技術と開発期間が必要. 厳密解法 : 整数計画ソルバーを使いこなす 近似解法 : メタヒューリスティクスを設計する 問題の分割や定式化の 工夫などで対応できる場合も多い 最適化モデルの正確さを犠牲にして易易しい問題に定式化する 方法も良良く採られる. 28

29 大規模な組合せ最適化問題に対する 発 見見的解法 29

30 なぜ専 用ソルバーを開発するか? 整数計画問題の記述が困難もしくは多くの変数や制約が必要 順列列を決定するタイプの問題は変数 制約が 非常に多く, 汎 用ソルバーの単純な適 用では 大規模な問題例例が解けないことが多い. 多 角形詰込み問題のように定式化 自体が困難な問題も多い. 汎 用ソルバーで対応できないほど 大規模 and/or 難しい 汎 用ソルバーの進歩は 目覚ましいものの対応できない問題はまだ多い. 整数計画問題の記述に現れない有 用な情報がある 入 力力データに偏りがあることが分かっている場合, 汎 用ソルバーでは実 行行可能解すら求まらないのに, 簡単なアルゴリズムで良良い近似解が求まることがある. 高性能な汎 用ソルバーは有償のため営利利 目的での利利 用が困難 1 製品ごとに 1 ライセンスを利利 用すると 大 赤字になってしまう. 大規模プロジェクトで少数のライセンスを利利 用する場合は OK. 動作原理理の説明が難しい 最適解が期待していた解と異異なる場合に理理由の説明が難しい. 汎 用ソルバーに含まれるライブラリを使って 大規模問題に対応できるアルゴリズムを 開発することも可能です. 30

31 ヒューリスティクス メタヒューリスティクス もともとは発 見見的法則, 経験則に基づく問題解決の 方法を指す. それが転じて, 最適化問題における最適性の保証のないアルゴリズムの総称として呼ばれる. 結果が 非常に悪くなるごく少数の反例例が存在する場合や, アルゴリズムが複雑過ぎて解析的な評価ができない場合が多い. メタヒューリスティクス 最適化問題に対する実 用的なアルゴリズムを設計するための 一般的な枠組み ( レシピ集 ), もしくはそのような考え 方に従って設計された様々なアルゴリズムの総称として呼ばれる. アニーリング法, タブー探索索法, 遺伝アルゴリズム, 進化計算, アント法, 粒粒 子群最適化など多くの探索索戦略略がある. 自然現象にアナロジーを持つ 手法が多いが, 自然現象を模倣すればアルゴリズムの性能が良良くなるわけではない. 解析的に評価できなくてもそれなりに説明できるノウハウはあります 31

32 メタヒューリスティクス 多くの最適化問題は近接最適性 ( 良良い解の近くに良良い解がある ) と多峰性 ( 局所最適解が多数存在する ) を持つ. 近似解法の基本戦略略は貪欲法 ( 構築法 ) と局所探索索法 ( 改善法 ). 貪欲法や局所探索索法などの基本的な 手法に様々な 手法を組み合わせて, 探索索の集中化と多様化をバランス良良く実現する. 計算の効率率率化, 探索索空間の削減, 問題構造の利利 用など, アルゴリズム, 最適化, 離離散数学の知識識を活 用すれば, 大規模な組合せ最適化問題に対して 高性能なメタヒューリスティクスを開発できる. 目的関数値 局所最適解 大域最適解 解空間 32

33 メタヒューリスティクスの設計 メタヒューリスティクスが向いている場合 1 厳密な最適解を求めるのが困難である ( 効率率率的な解法が知られている or 問題規模が 十分に 小さい場合はダメ ) 2 解の評価が 高速にできる ( 評価関数が black- box で評価にシミュレーションや実験を要する場合はダメ ) 3 近接最適性が成り 立立つ ( 微 小な変形で評価関数の値が 大きく変わる場合はダメ ) メタヒューリスティクスの多くは局所探索索法の 一般化なので, まずは 高性能な局所探索索法を設計することが重要. 局所探索索法では, 探索索空間, 解の評価, 近傍の定義, 移動戦略略などの各要素を注意深く設計することで 高性能なアルゴリズムを実現できる. 申し訳ありませんが今回は多点探索索に関わる部分は説明しません 多点探索索を含むメタヒューリスティクス全般については, オペレーションズ リサーチ 58(2013) の特集 はじめようメタヒューリスティクス をご参照下さい. 33

34 貪欲法 目的関数への貢献度度を 示す局所的な評価値に基づいて実 行行可能解を直接構成する 方法. ナップサック問題の例例 各荷物 i の重さ w i と価値 p i に対して,w i / p i は単位重さ当たりの価値と解釈できるので, これの 大きい順に詰めて 行行く. この貪欲法を少し修正すると, 常に最適値の 1/2 以上の近似値が得られる精度度保証付き近似解法になる. max s.t. nx p i x i i=1 nx w i x i apple c, i=1 荷物 i の価値 荷物 i の重さ x i 2 {0, 1}, i = 1,..., n. 34

35 巡回セールスマン問題に対する最近近傍法 貪欲法 現在いる都市から最も近い未訪問の都市に移動する操作を繰り返す. 全ての都市を訪問したら出発した都市に戻る. 巡回セールスマン問題に対する最近追加法 部分巡回路路 T に都市を 1 つずつ加える操作を繰り返す. 部分巡回路路 T からの距離離 d(t,i) が最 小となる都市 i を選ぶ. 都市 j と隣隣接する都市 k の間の枝 (j,k) を繋ぎ替えて新たな部分巡回路路を作る. k i j 最近近傍法の例例 最近追加法の例例 最近追加法は最適巡回路路の 2 倍以内の 長さの巡回路路を常に出 力力する. 35

36 局所探索索法 適当な初期解 x から始めて, 現在の解 x の近傍 xʼ NB(x) に改善解があれば移動する ( 近傍探索索 ). 勾配法では微分 f(x) を 用いるが, 局所探索索法では差分 Δf(x) = f(xʼ ) f(x) を 用いて探索索 方向を決定する. 集合分割問題の近傍の例例 1- flip 近傍 :x j =0 1 (or 1 0) 2- flip 近傍 :x j1 =1 0, x j2 =0 1 初期解の 生成 近傍解の 生成と評価 局所最適解 近傍内に改善解あり? 初期解 no yes 改善解に移動 局所最適解 36

37 局所探索索法 整数計画問題によらない 自然な定式化で扱える. 微 小な変形 ( 近傍操作 ) による評価関数の変化量量のみ計算すれば良良いので, 短時間に多くの解が探索索可能. 巡回セールスマン問題に対する 2- opt 近傍 現在の巡回路路から辺を 高々 2 本交換する 巡回路路を順列列で記述している場合は 一部を反転する操作に対応する. 巡回順 順列列を反転 37

38 局所探索索法 自由な発想に基づいて様々な近傍を定義できる. 巡回セールスマン問題に対する 3- opt 近傍,Or- opt 近傍 枝を 3 本付け替えて得られる巡回路路, 部分路路を別の場所に挿 入して得られる巡回路路. 3- opt 近傍の例例 Or- opt 近傍の例例 38

39 探索索空間 問題によっては実 行行可能領領域とは異異なる探索索空間を定義する 方が有効な場合も多い. 探索索空間の定義は 大きく以下の 3 通りに分類できる. a) 実 行行可能解のみ探索索する. b) 実 行行不不可能解も含めて探索索する 実 行行不不可能解の評価が必要 c) 解空間とは異異なる探索索空間をを導 入して, 探索索空間から解空間への写像を 用いて探索索する. 実 行行可能領領域 実 行行不不可能領領域 実 行行可能領領域 探索索空間 解空間 a) 実 行行可能解のみ探索索 b) 実 行行不不可能解も探索索 c) 解空間と異異なる探索索空間を 用意 39

40 実 行行不不可能解も探索索 集合分割問題の例例 実 行行可能解を 一つ 見見付けることも 非常に難しい. 制約条件を緩和して実 行行不不可能解も探索索空間に含める. 各制約 i に対する違反度度に重み w i を掛けた値をペナルティとして 目的関数に加える. ペナルティ重み w i の設定は容易易ではないので適応的に調整する. ( 実 行行可能領領域の境界近辺を集中的に探索索できると嬉しい ) ペナルティ重み 実 行行不不可能領領域 実 行行可能領領域 各制約式の重みパラメータを適応的に増減しつつ探索索する 違反度度 有望な解が含まれる領領域 40

41 長 方形詰込み問題の例例 解空間と異異なる探索索空間 BL 法 (bottom- left 法 ): 順列列 σ の順に BL 点に 長 方形を配置する. BL 点 : 配置可能な最も低い位置の中で最も左の位置. 順列列 σ 全ての集合を探索索空間として, 対応する配置の 目的関数で σ を評価する. σ : の場合 σ : の場合

42 近傍探索索の効率率率化 局所探索索法では計算時間の 大部分が近傍探索索に費やされるので, 近傍探索索の効率率率化はアルゴリズム全体の 高速化に直結する. 近傍探索索の 高速化により, 同程度度の計算時間でより 大きな近傍を探索索できるようになり, 解の精度度が向上する効果も期待できる. 近傍探索索を効率率率化する 方法は 大きく以下の 2 通りに分類できる. a) 解の評価値の計算を 高速化する. b) 改善の可能性のない解の探索索を省省略略する. 42

43 解の評価値の計算の 高速化 近傍操作ではごく少数の変数のみ値が変化するため, 現在の解 x と近傍解 xʼ NB(x) の間で値が変化した変数に関わる部分のみ再計算すれば, 評価関数値の変化量量 Δz(x) = z(xʼ ) z(x) を 高速に計算できる場合が多い. 局所探索索法では, 近傍内の解を評価する回数に 比べて, 現在の解が移動する回数ははるかに少ないので, 補助記憶の更更新に多少時間がかかっても, 全体では 十分な 高速化が実現できる. 評価関数の変化量量 補助記憶 係数 行行列列 N 補助記憶を利利 用すれば 定数時間で評価できる M = 1 疎な 行行列列だと効率率率良良く 補助記憶が更更新できる 本来は 目的関数と制約条件の評価に 入 力力サイズの計算量量が必要 43

44 近傍の縮 小 巡回セールスマン問題の例例 : 現在の巡回路路から辺 {i 1,i 2 } と {i 3,i 4 } を除き, 辺 {i 2,i 3 } と {i 4,i 1 } を加える 2- opt 近傍の操作を考える. (1) 辺 {i 1,i 2 } を削除して {i 2,i 3 } を追加し,(2) 辺 {i 3,i 4 } を削除して {i 1,i 4 } を追加すると 2 段階に分ける. が成り 立立つためには, の少なくとも 一 方が成 立立しているはず. 削除する辺 {i 1,i 2 } を決めたら追加する辺 {i 2,i 3 } はを満たす辺に限定する. 44

45 最適巡回路路は近隣隣の都市間を繋ぐ枝を含む場合が多い. 近傍の縮 小 各都市に対して近隣隣にある都市を列列挙して隣隣接リストに保持する. 平 面上の巡回セールスマン問題であれば,k- d 木のデータ構造を 用いて近隣隣にある都市を 高速に検索索できる. ただし, 高次元空間における類似ベクトルの検索索には向かない. 1 1,3, ,4,5 4 2,3,5, cutdim=y cutval=y(2) cutdim=x cutval=x(14) cutdim=y cutval=y(6) 14 1,2,4,5 3,16,15,14 6,7,10,11 8,9,13,12 領領域分割を繰返して都市 生成されたk- d 木 をクラスタに分割する 45

46 変数間の関係による問題の縮 小 集合分割問題における2- flip近傍の例例 現在の解xが1- flip近傍の局所最適解ならば xj1=1 0 xj2=0 １と反転させる交換近傍のみ考慮すれば良良い 同時に反転すると改善解が得られる可能性の 高い変数の組み合わ せを効率率率良良く 見見付けたい 入 力力データから特殊な制約式に同時に現れる変数の組み合わせを 解析してネットワークを 生成する x782 x1087 x1193 x823 x948 x452 x316 x1194 x289 x915 x517 x783 x433 x615 x498 x562 x346 x1088 x960 x107 x669 x898 x11 x690 x779 x61 x955 x661 x494 x =1 x972 x395 x191 x999 x309 x1033 x623 x726 x121 x488 x617 x1095 x274 x185 x916 x442 x389 x246 x265 x247 x1077 x1 x290 x20 x605 x228 x564 x65 x978 x339 x901 x49 x454 x824 x500 x1163 x1176 x636 x332 x186 x809 x359 x933 x1132 x1089 x692 x1055 x765 x323 x852 x1090 x275 x402 x1005 x648 x656 x738 x142 x347 x130 x739 x374 x303 x501 x840 x3 x304 x811 x1072 x766 x1056 x825 x153 x482 x260 x418 x51 x438 x317 x712 x502 x437 x883 x1178 x242 x576 x600 x319 x1134 x629 x866 x630 x961 x928 x602 x989 x930 x549 x963 x579 x262 x1117 x422 x1119 x1026 x263 x245 x965 x1118 x604 x550 x869 x932 x633 x991 x1024 x632 x264 x886 x363 x1025 x439 x1138 x887 x54 x146 x505 x440 x485 x244 x631 x578 x634 x190 x202 x1137 x769 x321 x18 x660 x378 x53 x990 x362 x551 x19 x992 x1180 x420 x201 x603 x1136 x1060 x1181 x169 x113 x1010 x1075 x659 x504 x768 x1179 x1061 x158 x114 x336 x217 x813 x17 x1074 x484 x752 x812 x320 x548 x929 x1022 x988 x787 x305 x827 x419 x884 x931 x601 x546 x867 x145 x306 x216 x52 x261 x1116 x243 x1023 x318 x457 x377 x658 x111 x200 x751 x483 x198 x81 x156 x1059 x279 x753 x828 x1058 x203 x486 x754 x800 x788 x830 x829 x1044 x705 x844 x1043 x487 x322 x458 x232 x1093 x80 x189 x1105 x278 x771 x55 x364 x421 x716 x535 x970 x405 x335 x112 x715 x843 x144 x16 x503 x361 x767 x110 x713 x1135 x826 x15 x199 x714 x1073 x215 x360 x1115 x750 x1177 x1133 x376 x1057 x1041 x417 x109 x1114 x798 x584 x1154 x799 x1008 x786 x143 x1155 x1182 x755 x1076 x770 x814 x218 x5 x337 x280 x441 x685 x102 x392 x1104 x459 x1094 x789 x307 x523 x69 x522 x855 x524 x506 x394 x845 x406 x393 x1156 x857 x731 x801 x921 x856 x1167 x672 x68 x534 x277 x1042 x295 x1168 x536 x905 x41 x231 x334 x1092 x952 x671 x375 x133 x168 x379 x1011 x906 x938 x1106 x673 x904 x556 x101 x704 x293 x79 x456 x230 x1153 x167 x155 x683 x919 x1166 x100 x67 x842 x657 x980 x620 x903 x40 x854 x154 x229 x1103 x670 x214 x241 x865 x259 x566 x404 x703 x292 x78 x533 x1007 x882 x436 x213 x187 x918 x333 x66 x810 x14 x987 x1091 x471 x1165 x979 x455 x39 x50 x294 x639 x188 x920 x593 x741 x350 x1030 x369 x997 x1009 x131 x785 x1102 x981 x608 x729 x32 x996 x472 x638 x583 x132 x403 x797 x841 x1021 xj1=1 0 xj2=0 １と同時に反転 するとペナルティが打ち消される x349 x995 x166 x276 x853 x38 x1101 x1152 x1164 x532 x796 x531 x717 x935 x249 x555 x649 x971 x609 x1031 x1124 x684 x937 x969 x936 x492 x207 x473 x953 x1144 x998 x233 x893 x351 x250 x1032 x1045 x474 x352 x640 x650 x939 x6 x1082 x594 x557 x33 x427 x621 x892 x954 x982 x873 x42 x665 x1142 x60 x610 x493 x428 x585 x567 x150 x4 x445 x1125 x651 x269 x730 x59 x268 x124 x368 x178 x325 x592 x607 x521 x348 x469 x401 x968 x902 x1141 x391 x740 x719 x689 x1080 x90 x1123 x718 x872 x891 x444 x1029 x637 x510 x775 x694 x116 x22 x267 x367 x682 x115 x443 x470 x481 x1039 x871 x606 x565 x1028 x833 x426 x58 x462 x221 x31 x89 x324 x793 x777 x622 x208 x1143 x223 x446 x125 x312 x222 x664 x177 x490 x149 x206 x1079 x693 x554 x994 x520 x2 x1071 x582 x591 x176 x1040 x1006 x205 x248 x951 x1140 x1186 x157 x568 x511 x1187 x1081 x1188 x251 x24 x1016 x134 x91 x173 x341 x409 x311 x491 x381 x509 x832 x425 x21 x508 x291 x784 x197 x1063 x1185 x1122 x619 x266 x1113 x864 x818 x1014 x1048 x760 x819 x849 x1015 x85 x848 x1064 x327 x70 x874 x834 x23 x758 x804 x92 x118 x342 x1098 x326 x382 x792 x539 x1109 x728 x99 x702 x84 x136 x774 x366 x390 x88 x966 x302 x599 x816 x30 x967 x581 x77 x749 x172 x674 x720 x1050 x776 x742 x398 x117 x735 x1066 x541 x383 x835 x1160 x1110 x179 x695 x1049 x463 x744 x340 x123 x57 x380 x917 x1151 x552 x44 x675 x847 x757 x791 x743 x817 x489 x1062 x165 x553 x416 x635 x240 x803 x1108 x408 x135 x310 x890 x681 x647 x618 x950 x435 x258 x846 x407 x934 x43 x1013 x148 x220 x663 x1183 x13 x71 x122 x237 x1065 x464 x285 x759 x410 x194 x284 x676 x447 x805 x528 x1097 x411 x74 x540 x925 x160 x688 x573 x911 x1002 x1172 x10 x236 x397 x106 x283 x512 x161 x299 x985 x45 x860 x709 x756 x1184 x1121 x255 x211 x597 x958 x527 x9 x859 x861 x1036 x588 x272 x354 x72 x538 x1096 x478 x910 x137 x73 x1159 x235 x708 x1047 x1078 x831 x870 x519 x1129 x572 x355 x1001 x298 x234 x613 x745 x897 x1035 x734 x128 x569 x162 x944 x677 x654 x36 x1158 x497 x180 x226 x722 x477 x1171 x159 x353 x204 x590 x1139 x772 x1027 x815 x141 x727 x858 x773 x561 x957 x384 x696 x356 x626 x193 x909 x875 x614 x644 x1147 x877 x924 x571 x181 x1170 x297 x1019 x450 x879 x975 x515 x254 x974 x587 x526 x802 x1107 x790 x1012 x219 x942 x625 x697 x721 x138 x46 x432 x878 x1000 x1034 x678 x516 x943 x63 x762 x182 x896 x476 x171 x1191 x372 x984 x449 x837 x1128 x560 x1146 x152 x668 x328 x451 x496 x643 x746 x1148 x851 x329 x35 x93 x923 x431 x596 x612 x396 x652 x424 x507 x701 x98 x475 x537 x1046 x889 x308 x993 x8 x876 x595 x983 x105 x56 x423 x900 x127 x83 x26 x271 x687 x570 x282 x698 x94 x210 x345 x653 x412 x733 x192 x624 x908 x1157 x1085 x1018 x315 x62 x225 x371 x922 x281 x365 x29 x1120 x949 x1111 x253 x956 x224 x461 x1169 x147 x460 x1052 x385 x330 x1053 x467 x400 x514 x175 x724 x1069 x723 x1086 x386 x780 x119 x495 x525 x252 x296 x662 x338 x691 x87 x806 x1067 x1112 x139 x164 x763 x387 x288 x822 x795 x183 x95 x120 x1068 x747 x737 x344 x1127 x642 x559 x586 x611 x907 x97 x888 x1145 x895 x941 x973 x448 x170 x808 x466 x542 x530 x413 x1084 x370 x34 x104 x82 x47 x838 x27 x781 x679 x807 x862 x75 x761 x430 x1162 x680 x1192 x699 x414 x544 x163 x1038 x1100 x543 x140 x76 x914 x1004 x239 x212 x301 x196 x927 x529 x1017 x358 x863 x880 x287 x1173 x25 x209 x270 x707 x686 x300 x794 x850 x7 x1175 x836 x314 x1051 x513 x343 x126 x641 x429 x1099 x959 x667 x465 x558 x940 x103 x151 x732 x894 x286 x195 x86 x313 x12 x357 x821 x1083 x174 x1161 x399 x627 x575 x48 x947 x1070 x1174 x238 x1037 x479 x710 x666 x913 x480 x1131 x598 x725 x748 x616 x499 x257 x574 x1003 x1190 x711 x434 x227 x899 x388 x453 x589 x373 x926 x912 x706 x976 x256 x37 x415 x545 x655 x129 x736 x184 x977 x273 x108 x518 x700 x1150 x96 x628 x1020 x986 x778 x331 x764 x563 x945 x1189 x881 x946 x646 x64 x1149 x1130 x820 x839 x28 x1054 x468 x645 x580 x885 x868 x964 x547 x577 x962 変数間の関係ネットワーク 46

47 変数間の関係による問題の縮 小 各変数xjについて同じ割当制約に同時に現れる変数を列列挙 変数が 非常に多い問題例例は少なくない 組合せの数がn2(nは変数の数)となるので xjと同時に現れる頻度度 の 高い変数のみ(上位数%)残してネットワークを構成 多くの計算時間を要するので 変数xjを反転する際にネットワー クの必要な部分のみ遅延 生成する x1 x98 x2 x186 x3 x4 x100 x79 x809 x810 x811 x491 x701 x99 x303 x304 x85 x187 x1064 同じ制約に同時に x78 現れる変数を列列挙 x101 x782 x6 x493 x1066 x1189 x627 x666 x779 x195 x86 x313 x151 x732 x61 x641 x429 x955 x492 x686 x1126 x907 x191 x999 x309 x1033 x623 x121 x731 x488 x617 x494 x309 x104 x246 x605 x228 x978 x454 x824 x500 x1163 x1176 x87 x105 x708 x83 x636 x1113 x864 x1089 x1005 x496 x311 x106 x193 x84 x323 x1090 x275 x402 x142 x130 x194 x85 x497 x735 x1152 x1164 x739 x303 x455 x66 x108 x86 頻度度の 高い変数のみ残す x821 x566 x100 x304 x1056 x153 x482 x260 x418 x51 x438 x658 x629 x866 x630 x961 x928 x201 x989 x603 x930 x549 x963 x579 x18 x634 x887 x1119 x190 x54 x660 x1026 x886 x263 x363 x245 x440 x1118 x604 x485 x965 x550 x1117 x869 x932 x633 x991 x262 x551 x19 x422 x992 x1137 x769 x321 x244 x1024 x632 x264 x146 x53 x990 x362 x1136 x439 x1061 x158 x114 x202 x1025 x768 x1179 x631 x548 x929 x1022 x988 x812 x320 x578 x169 x113 x1010 x378 x505 x420 x504 x752 x827 x419 x884 x602 x931 x601 x546 x867 x830 x336 x217 x1075 x813 x1180 x659 x1074 x484 x52 x261 x1116 x243 x1023 x1178 x319 x305 x111 x200 x751 x483 x883 x242 x1134 x145 x1138 x156 x1059 x279 x753 x788 x828 x306 x1060 x1181 x800 x1043 x203 x486 x754 x322 x1044 x844 x1105 x278 x17 x487 x364 x829 x421 x716 x1182 x755 x771 x55 x458 x232 x1093 x80 x705 x112 x457 x216 x337 x280 x1076 x770 x81 x189 x335 x1154 x715 x843 x377 x787 x459 x1094 x307 x814 x5 x522 x855 x1058 x524 x506 x789 x441 x218 x1155 x1156 x857 x731 x394 x845 x102 x69 x392 x799 x144 x1168 x536 x801 x406 x535 x970 x405 x672 x68 x1104 x16 x503 x361 x767 x110 x713 x1135 x826 x15 x199 x502 x318 x293 x534 x1008 x714 x1073 x215 x360 x1115 x750 x1177 x437 x600 x584 x938 x921 x523 x685 x1167 x379 x1011 x295 x906 x905 x393 x856 x41 x101 x704 x1092 x811 x1072 x766 x825 x712 x576 x334 x277 x1042 x376 x1057 x1041 x417 x109 x1114 x198 x683 x919 x79 x456 x952 x671 x798 x168 x904 x556 x133 x231 x786 x143 x375 x241 x865 x317 x980 x620 x903 x230 x1153 x67 x842 x657 x1103 x670 x214 x882 x259 x404 x639 x167 x155 x188 x920 x294 x971 x1106 x673 x684 x981 x593 x369 x997 x892 x608 x729 x741 x1009 x40 x854 x154 x229 x1007 x50 x810 x14 x436 x703 x292 x78 x533 x333 x638 x131 x785 x1102 x213 x187 x918 x3 x39 x583 x1166 x403 x797 x841 x1091 x276 x853 x38 x501 x987 x1133 x11 x132 x1031 x1124 x473 x953 x650 x665 x1142 x32 x350 x1030 x1144 x998 x233 x893 x609 x351 x250 x567 x150 x4 x445 x996 x472 x649 x939 x1032 x1045 x474 x352 x640 x59 x268 x124 x368 x325 x249 x937 x969 x936 x349 x995 x166 x521 x555 x592 x607 x471 x1165 x979 x532 x374 x840 x1141 x740 x557 x33 x492 x6 x1082 x594 x982 x730 x42 x207 x621 x1080 x178 x1123 x718 x872 x891 x444 x391 x717 x935 x648 x347 x796 x1021 x10 x968 x902 x694 x90 x22 x267 x367 x682 x125 x427 x689 x954 x585 x873 x312 x510 x610 x493 x428 x60 x446 x719 x173 x341 x1186 x775 x116 x58 x462 x221 x31 x89 x324 x1029 x637 x348 x656 x469 x531 x1101 x1028 x443 x738 x401 x664 x177 x490 x115 x606 x565 x470 x481 x1039 x206 x1079 x693 x554 x871 x582 x994 x520 x1071 x852 x205 x248 x951 x1140 x591 x176 x2 x833 x426 x149 x1125 x651 x269 x777 x622 x208 x1143 x223 x134 x91 x222 x266 x508 x702 x692 x291 x1040 x1006 x425 x21 x99 x88 x1055 x765 x818 x409 x311 x491 x381 x509 x832 x390 x30 x967 x581 x77 x359 x966 x784 x1063 x1185 x1122 x619 x1064 x136 x1014 x1048 x728 x774 x366 x917 x749 x933 x197 x599 x9 x186 x1151 x552 x240 x302 x123 x57 x380 x890 x165 x332 x809 x635 x258 x1132 x743 x817 x489 x816 x1062 x1015 x85 x848 x1188 x157 x511 x1187 x793 x1081 x568 x819 x849 x742 x251 x24 x1016 x776 x834 x23 x758 x804 x1109 x340 x760 x835 x1160 x326 x327 x70 x874 x342 x1098 x179 x398 x117 x735 x382 x792 x92 x118 x1050 x759 x1110 x1097 x84 x744 x757 x791 x172 x539 x847 x310 x663 x681 x553 x416 x495 x122 x846 x407 x934 x647 x618 x950 x435 x8 x1184 x339 x901 x408 x135 x148 x220 x44 x675 x695 x1049 x463 x688 x709 x756 x1121 x564 x65 x49 x160 x397 x106 x283 x803 x1108 x720 x383 x464 x285 x805 x528 x410 x194 x674 x1065 x74 x925 x236 x1066 x541 x911 x299 x540 x1172 x10 x284 x676 x447 x161 x1002 x211 x985 x45 x860 x411 x237 x597 x958 x527 x9 x859 x538 x1096 x43 x1078 x831 x20 x272 x354 x72 x1047 x1013 x1036 x255 x910 x137 x73 x512 x573 x588 x1159 x235 x861 x745 x355 x1001 x298 x1158 x478 x654 x897 x1035 x734 x128 x569 x162 x944 x677 x613 x572 x722 x477 x1170 x234 x226 x36 x708 x497 x180 x877 x1171 x957 x384 x696 x356 x561 x626 x193 x909 x875 x614 x644 x1129 x924 x571 x181 x159 x1019 x1147 x254 x974 x587 x297 x353 x71 x204 x870 x1183 x13 x727 x858 x773 x247 x590 x519 x1 x290 x1107 x790 x1012 x1139 x86 x923 x942 x625 x697 x721 x878 x515 x450 x182 x879 x975 x851 x1000 x1034 x526 x652 x560 x678 x516 x138 x46 x432 x1128 x896 x93 x476 x451 x1148 x943 x63 x762 x372 x35 x387 x746 x386 x496 x643 x612 x984 x449 x1191 x329 x271 x668 x328 x837 x94 x431 x596 x724 x1069 x330 x1053 x345 x396 x802 x1046 x265 x1077 x772 x1027 x815 x141 x475 x537 x219 x442 x389 x8 x876 x595 x983 x171 x424 x507 x701 x98 x916 x83 x698 x210 x26 x653 x1146 x152 x105 x56 x889 x308 x993 x185 x127 x687 x570 x282 x281 x365 x423 x900 x274 x624 x908 x1157 x1095 x1018 x315 x62 x225 x412 x733 x192 x1085 x164 x763 x723 x1086 x780 x119 x922 x460 x29 x1120 x949 x224 x461 x1169 x147 x385 x1111 x253 x956 x1052 x175 x344 x525 x252 x296 x662 x338 x514 x288 x467 x400 x87 x371 x642 x559 x586 x395 x611 x97 x888 x691 x495 x1127 x1112 x139 x680 x838 x183 x95 x120 x822 x795 x1192 x699 x27 x781 x679 x1068 x747 x737 x806 x1067 x1017 x1145 x895 x941 x973 x494 x972 x170 x466 x542 x530 x413 x414 x1162 x807 x47 x544 x1038 x1100 x543 x163 x239 x212 x301 x196 x140 x76 x914 x1004 x862 x1084 x430 x209 x270 x34 x448 x12 x75 x1173 x25 x358 x863 x880 x927 x761 x850 x82 x808 x300 x794 x947 x1070 x287 x529 x370 x707 x104 x1175 x836 x314 x1051 x513 x343 x126 x1099 x959 x667 x465 x558 x940 x1161 x357 x821 x286 x575 x48 x480 x1131 x1174 x238 x399 x1083 x174 x499 x598 x913 x725 x748 x616 x257 x574 x899 x1037 x479 x710 x453 x434 x227 x373 x388 x415 x589 x1003 x1190 x711 x11 x690 x706 x976 x184 x977 x545 x655 x926 x518 x700 x1150 x96 x960 x273 x108 x912 x881 x331 x764 x628 x1020 x256 x37 x778 x898 x839 x946 x646 x563 x129 x736 x820 x107 x669 x726 x7 x1088 x986 x7 x705 x783 x28 x1054 x64 x1149 x1130 x103 x813 x1194 x289 x915 x615 x346 x945 x661 x102 x948 x452 x517 x468 x498 x562 x894 x5 x1087 x1193 x823 x316 x433 x645 x580 x885 x868 x964 x547 x577 x962 変数間の関係ネットワーク 遅延 生成すれば 高次元空間でも隣隣接リストを利利 用できる 47

48 集合被覆問題の例例 : 線形計画法による問題の縮 小 変数の数 n が 非常に多い事例例がしばしば現れる. x j =1 となる変数は 高々制約式の本数となる. 有望な変数のみを 用いた制限された集合被覆問題を解く. コスト係数 c j だけでは有望な変数が特定できない. 線形計画緩和問題 ( 各変数の整数制約を緩和した問題 ) の双対解 ui を利利 用して各変数を評価 価格法, 列列 生成法 被約費 用 m C C 乗務員スケジューリングの例例 制約式 4,284 本 変数 1,092,610 個 n 機械学習でもオンライン最適化や LP ブースティングなど類似した 手法が多く知られる. 48

49 線形計画法による問題の縮 小 LP 緩和問題ではその最適値と双対問題の最適値が 一致する. 主問題に変数を追加 = 双対問題に制約式を追加. 部分問題 C N の LP 緩和問題を解いた後に, 残りの変数の被約費 用 を計算し, となる変数を部分問題 C に追加. 主 LP 緩和問題 : 双対 LP 緩和問題 : 双対最適解 最適値を更更新 追加する制約式 実 行行可能領領域 実 行行可能領領域 49

50 組合せ最適化問題とその応 用 まとめ 巡回セールスマン問題, 集合分割問題, 長 方形詰込み問題 配送計画, 選挙区割り, 機械翻訳におけるフレーズ対応, 推薦商品の最適化, 人の移動履履歴の推定, 基板検査プローブの経路路計画, 電気 自動 車車の充放電計画 計算困難な組合せ最適化問題に対するアプローチ 易易しい問題と難しい問題 厳密解法と近似解法, 汎 用解法と専 用解法 大規模な組合せ最適化問題に対する発 見見的解法 メタヒューリスティクス, 貪欲法, 局所探索索法 探索索空間, 近傍探索索の効率率率化 解の評価値の計算の 高速化, 近傍の縮 小, 変数間の関係による問題の縮 小, 線形計画法による問題の縮 小 アルゴリズム設計の技術を上 手く取り 入れることで 大規模な組合せ最適化問題に対する効率率率的なアルゴリズムは実現できる さらには, データ, インターフェース, モデル, アルゴリズムなど全体を俯瞰した上で 最良良の解決策を 目指すことが 大事だとは思います. 50

51 参考 文献 組合せ最適化問題とその応 用 H.P.Williams, Model Building in Mathematical Programming (4 th edition),wiley, ( 前 田英次郎郎監訳, 小林林英三訳, 数理理計画モデルの作成, 産業図書,1995) 計算困難な組合せ最適化問題に対するアプローチ 宮代隆平, 整数計画ソルバー 入 門, オペレーションズ リサーチ,57(2012), 藤江哲也, 整数計画法による定式化 入 門, オペレーションズ リサーチ,57(2012), 久保幹雄,J.P. ペドロソ, 村松正和,A. レイス, あたらしい数理理最適化 Python 言語と Gurobi で解く, 近代科学社,2012. T.Berthold, A.M.Gleixner, S.Heinz, T.Koch, 品野勇治, SCIP Optimization Suite を利利 用した混合整数 ( 線形 / 非線形 ) 計画問題の解法, ZIB- Report 12-24, 大規模な組合せ最適化問題に対する発 見見的解法 柳柳浦睦憲, 茨 木俊秀, 組合せ最適化 メタ戦略略を中 心として, 朝倉書店,2001. 久保幹雄,J.P. ペドロソ, メタヒューリスティクスの数理理, 共 立立出版,2009. 梅 谷俊治, 柳柳浦睦憲, メタヒューリスティクス事始め : まずは局所探索索法から, オペレーションズ リサーチ,58(2013), 今堀慎治, 柳柳浦睦憲, 概説メタヒューリスティクス, オペレーションズ リサーチ, 58(2013), 梅 谷俊治, 問題構造の解析に基づく組合せ最適化アルゴリズムの 自動構成, オペレーションズ リサーチ,59(2014), S.Umetani, M.Yagiura, Relaxation heuristics for the set covering problem, Journal of Operations Research Society of Japan, 50(2007),