数理最適化の応用例と 実験的解析 東京海洋大学 久保 幹雄.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

情報基盤アルゴリズムとして のメタヒューリスティクスの 研究 茨木俊秀、巳波弘佳、藤原洋志、 千葉英史、関口良行(関西学院大 学)、 藤重悟(京都大学)、 柳浦睦憲(名古屋大学)、 野々部宏司(法政大学)、 梅谷俊治(電気通信大学)
第 5 章 2 次元モデル Chapter 5 2-dimensional model. Contents 1.2 次元モデル 2-dimensional model 2. 弱形式 Weak form 3.FEM 近似 FEM approximation 4. まとめ Summary.
Python を用いた Gurobi 入門 久保 幹雄. Why Python? モジュールを読み込めば何 でもできる! 最適化もできる! import gurobipy (MIP) import SCOP (CP) グラフも描ける! import networkX import matplotlib.
サプライ・チェイン最適化 ー収益管理を中心としてー 東京海洋大学 久保 幹雄
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
Pythonを用いた お気楽最適化とその実践
制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d (7, 15) (9,4) (12,4)
ロジスティクス工学 第6章 動的ロットサイズ決定モデル 東京商船大学 久保 幹雄
コンピュータビジョン特論B - Graph Cuts - 永橋知行.
緩和+分解+調整による 分散協調問題解決 神戸大学大学院海事科学研究科 平山 勝敏.
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
サプライ・チェインにおける様々な最適化問題を解くための 統一言語
二千十三年五月 あたらしい数理最適化 出版記念セミナー 主催 近代科学社 オクトーバースカイ 共催 構造計画研究所
組合せ最適化問題と厳密解法 最小木、ナップサック問題、ビンパッキング、巡回セールスマン問題 LPによる上界・下界 分枝限定法
最短路問題をGurobiで解こう! 流通最適化工学 補助資料.
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
An Algorithm for Enumerating Maximal Matchings of a Graph
最適化ソルバーのための Python言語入門
Approximation of k-Set Cover by Semi-Local Optimization
モード付き並列機械における オンラインスケジューリング
サプライ・チェイン最適化の最新動向 久保 幹雄 東京商船大学 江東区越中島2ー1ー6 流通情報工学 流通管理工学講座 流通経営工学 助教授
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
第 七 回 双対問題とその解法 山梨大学.
1章前半.
2018/8/8 ロットサイズ最適化 東京海洋大学 久保 幹雄.
Selfish Routing and the Price of Anarchy 第2回
アルゴリズム入門.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
Linear Relaxation for Hub Network Design Problems
ロジスティクス工学 第9章 スケジューリングモデル 補助資料:OptSeqによるスケジューリング入門 logopt
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
大阪市立大学 学術情報総合センター 大西克実
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
決定木とランダムフォレスト 和田 俊和.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
第14章 モデルの結合 修士2年 山川佳洋.
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
第3回 アルゴリズムと計算量 2019/2/24.
トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
Introduction to Soft Computing (第11回目)
スケジューリング最適化システム WebSeqのご紹介
運搬スケジューリング問題と その周辺 東京商船大学 流通情報工学 久保 幹雄.
計算量理論輪講 chap5-3 M1 高井唯史.
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
First Course in Combinatorial Optimization
Nightmare at Test Time: Robust Learning by Feature Deletion
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
配送計画最適化システム WebMETROのご紹介
制約最適化モジュール SCOP   東京海洋大学 久保幹雄.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
ロジスティクスにおける 最適化の応用 東京商船大学   流通システム 久保 幹雄.
サプライ・チェイン最適化について 研究者・実務家が知っておくべきこと
サプライ・チェイン最適化における モデリングについて
直並列グラフの連続多重彩色 西関研究室 吉田進太郎.
Max Cut and the Smallest Eigenvalue 論文紹介
情報工学概論 (アルゴリズムとデータ構造)
分枝カット法に基づいた線形符号の復号法に関する一考察
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題
東京工業大学情報理工学研究科 小島政和 第1回横幹連合コンファレンス 2005年11月25,26日 JA 長野県ビル
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

数理最適化の応用例と 実験的解析 東京海洋大学 久保 幹雄

実験対象 施設配置問題(k-median, k-center) グラフ関連(グラフ分割,グラフ彩色) 巡回路(巡回セールスマン) ロットサイズ決定 非線形施設配置 スケジューリング

k-median問題 min-sum型の施設配置問題 顧客数 n=200,施設数 k=20 (顧客上から選択) Euclid距離,x,y座標は一様ランダム n=200, k=5 の例

定式化 I: 顧客の集合 J: 施設候補地点の集合 Big M 弱い定式化

弱い定式化での結果 n=200,k=20 Optimize a model with 401 Rows, 40200 Columns and 80400 NonZeros 中略 Explored 1445 nodes (63581 simplex iterations) in 67.08 seconds Thread count was 2 (of 2 available processors) Optimal solution found (tolerance 1.00e-04) Best objective 1.0180195861e+01, best bound 1.0179189780e+01, gap 0.0099% Opt.value= 10.1801958607

上界と下界の変化 (弱い定式化)

強い定式化での結果 Optimize a model with 40401 Rows, 40200 Columns and 160400 NonZeros 中略 Explored 0 nodes (1697 simplex iterations) in 3.33 seconds (分枝しないで終了!) Thread count was 2 (of 2 available processors) Optimal solution found (tolerance 1.00e-04) Best objective 1.0180195861e+01, best bound 1.0180195861e+01, gap 0.0% Opt.value= 10.1801958607

知見 Big Mを用いない強い定式化が望ましい. この程度の式なら,必要な式のみを切除平面として追加するような小細工は必要なし.

k-center問題 min-max型の施設配置問題 100顧客,10施設(顧客上から選択) Euclid距離,x,y座標は一様ランダム k-center (n=30,k=3) k-median (n=30,k=3)

定式化

上界と下界の変化(n=100,k=10) min-max型の目的関数には注意!

k-被覆問題 被覆されていない(距離がθより大きい)顧客数 =1 顧客 i が被覆されていない パラメータ:=1 顧客iから施設jへの距離が θ以下

k-被覆問題を用いた二分探索法 UB:=距離の最大値, LB:=0 while UB – LB >ε: θ= (UB+LB)/2 if k-被覆問題の最適値= 0 then UB = θ else LB = θ

実験結果 k= ceil( n/10 ) k-center min-max k-median k-center 2分探索

知見 k-center問題(min-max型の最適化問題)に対しては100点あたりで組合せ爆発が起きる. k-center問題に対しては,k-cover問題を用いた二分探索が有効

グラフ分割問題 無向グラフ G=(V,E)が与えられたとき,|L|=|R|を満たすVの分割(L,R)で,LとRの間の枝の本数を最小にするものを求める問題. 応用 VLSI 設計, プログラム分割 JohnsonらがSimulated Annealing法の実験のために採用した第1の問題. 16

グラフ分割問題 半分に分けたい! 仲良し! 17

グラフ分割問題 目的関数値=2 18

二次最適化定式化 凸二次でないので通常は解けない(がGurobiだと解ける) 0-1 変数を二乗して凸関数に変換する方が良い

Google 3D Graph x*(1-y)+(1-x)*y x^2+y^2-2*x*y

線形化定式化 変数 y を追加して線形化

二次錘定式化 二次最適化定式化 線形化定式化

知見 Gurobiは,非凸二次最適化でも0-1変数なら自動的に凸最適化に変換 線形化した方が高速 二次錘最適化も有効であるが,線形化が簡単で有効 100点を超えるような問題例には,適用すべきでない.

最大クリーク問題 (最大安定集合問題) 応用 1993年度DIMACSチャレンジ問題の一つ 無向グラフ G=(V,E)が与えられたとき,最大位数の安定集合 S (Vの部分集合で間に枝のないもの)を求める問題. 応用 プリント基板テスト,パターンマッチング,符号理論,考古学および生物学のデータ解析,グラフ彩色問題の近似アルゴリズムおよび下界,多面体論(Kellerの予想),故障診断,etc. 1993年度DIMACSチャレンジ問題の一つ 24

最大クリーク問題 なるべく大人数でピクニックに行きたい! 仲良し! 25

最大クリーク問題 26

最大安定集合問題 仲が悪い! 27

最大安定集合問題の定式化

グラフ彩色問題 無向グラフG=(V,E)が与えられたとき,Vの安定集合への分割で分割数最小のものを求める問題. 応用 時間割作成,スケジューリング,周波数割当,レジスタ配分,プリント基板テスト,パターンマッチグ. 1993年度DIMACSチャレンジ問題の一つ Johnsonらの実験的解析の第2の問題 30

グラフ彩色問題 ・・・ クラス分けしたい! 仲が悪い! 31

グラフ彩色問題 32

定式化 弱い定式化

グラフ彩色問題に対する実験 目的:解の対称性を調べる 点数 n=40,彩色数上限 Kmax=10 ランダムグラフ G(n,p=0.5) 彩色数 8 が最適値

上界と下界の変化(原定式化) 点数 n=40,彩色数上限 Kmax=10 Optimize a model with 3820 Rows, 410 Columns and 11740 NonZeros Explored 17149 nodes (3425130 simplex iterations) in 1321.63 seconds

定式化の改良 model.addSOS(1,変数リスト) 対称性の除去(番号の小さい方の色を優先して使う!) 特殊順序集合(SOS: Special Ordered Set) Type 1 (いずれか 1つの変数が正になることの宣言)の追加 model.addSOS(1,変数リスト)

上界と下界の変化(対称性除去) Optimize a model with 3829 Rows, 410 Columns and 11758 NonZeros Explored 4399 nodes (1013290 simplex iterations) in 384.53 seconds MIPFocus=2(最適性保証優先) で67秒,MIPFocus=3(下界優先) で70秒

上界と下界の変化(+SOS) Optimize a model with 3829 Rows, 410 Columns and 11758 NonZerosExplored 109 nodes (58792 simplex iterations) in 22.02 seconds MIPFocus=2(最適性保証優先) で65秒,MIPFocus=3(下界優先) で126秒

彩色数 K を固定した定式化 悪い枝の数を最小化 (0だとK彩色) 枝の両端点 i,j が同色だと 0-1変数 zij が 1

K固定問題を用いた二分探索 UB, LB := 彩色数 K の上界と下界 while UB – LB >1: K= [ (UB+LB)/2 ] if Kを固定した問題の最適値 = 0 then UB := K else LB := K

対称性除去 +SOS 原定式化 二分探索 対称性除去

知見 解の対称性のある問題は,下界の改善がしにくいので,分枝限定法では解きにくい 対称性を除く工夫を入れると多少は改善 SOS(Special Ordered Set)制約でさらに改善 彩色数に対する二分探索は有効

巡回セールスマン問題(TSP) すべての点をちょうど1回通る最短巡回路 切除平面法で85,900点の実際問題(対称TSP)の最適解

Miller-Tucker-Zemlinの定式化

上界と下界の変化 (80点,Euclid TSP) 強化した式 でないと... 1日まわして Out of Memory!

結果 Optimize a model with 6480 Rows, 6400 Columns and 37762 NonZeros 中略 Cutting planes: Gomory: 62 Implied bound: 470 MIR: 299 Zero half: 34 Explored 125799 nodes (2799697 simplex iterations) in 359.01 seconds Optimal solution found (tolerance 1.00e-04) Best objective 7.4532855108e+00, best bound 7.4525704995e+00, gap 0.0096% Opt.value= 7.45328551084

非対称巡回セールスマンのベンチマークに対する結果(時間) 多品種フロー 単一品種フロー 強化MTZ MTZ

非対称巡回セールスマンのベンチマークに対する結果(成功数) 多品種フロー MTZ 強化MTZ 単一品種フロー

知見 式を持ち上げ操作で強化すると,高速化され,大きな問題例が解けるようになる. 多品種フロー定式化は下界は強いが求解時間は悪い 単品種フロー定式化は安定して良い. 問題例によっては1000点まで解ける!

対称巡回セールスマンのベンチマークに対する結果(時間) 分枝カット法 II (分枝時にカット追加) 分枝カット法 I (整数解のとき カット追加) 分枝限定+ 切除平面法

対称巡回セールスマンのベンチマークに対する結果(成功数) 分枝カット法 II (分枝時にカット追加) 分枝カット法 I (整数解のとき カット追加) 分枝限定+ 切除平面法

知見 分枝時に切除平面を追加する分枝カット法は遅い. 整数解を発見したタイミングで切除平面を加える分枝カット法が推奨される. 分枝限定法で整数解を出した後で,切除平面を加える簡便法も悪くない.

多品目ロットサイズ決定問題 段取り費用と在庫費用のトレードオフを最適化する多期間生産計画 多品目で共通の資源を使う容量制約付き問題は,MIPソルバーには難問(と言われてきた) T=30期,P=24品目:Trigeiro, Thomas, McClain (1989年)の最大のベンチマーク

ロットサイズ決定問題 標準定式化のフローモデル 生産量(t) 在庫量(t) 在庫量(t-1) 期 t 需要量(t) 弱い定式化の原因 生産量(t)≦大きな数 “Large M” ×段取りの有無(t) 在庫量(t-1)+生産量(t)=需要量(t)+在庫量(t) 0-1変数

ロットサイズ決定問題 施設配置定式化のフローモデル s期に生産してt期まで在庫される量 期 s 期 t 需要量(t) s期に生産してt期まで在庫される量 ≦需要量(t)×段取りの有無(s) s期に生産してt期まで在庫される量 = 需要量(t)

アルゴリズムと定式化の関係 (特殊形に対する) 強い定式化 or 多項式時間アルゴリズム 多項式時間で破っている 妥当不等式の同定 追加制約+つなぎ制約 容量制約なしロットサイズ決定 Wagner-Whitin 動的計画アルゴリズム 施設配置定式化 最短路定式化 (S,l)不等式 1機械重み付き完了 時刻和最小化スケジューリング どん欲解法(Simth’s rule) Super-modular不等式

定式化のサイズと強さの比較 標準定式化 施設配置定式化 変数の数 変数の数 弱い定式化 強い定式化 =線形計画緩和が 整数多面体と一致 制約の数 制約の数 (S,l)不等式 切除平面 追加した 制約の数 n: 期数 強い定式化

上界と下界の変化(標準定式化) 1800秒で最適解;これ以上大きな問題例は無理!

上界と下界の変化(施設配置定式化) 40秒で最適解;T=100でも大丈夫!

切除平面 標準 施設配置

切除平面 標準 施設配置

知見 従来では難問と言われてきたロットサイズ決定問題でもある程度までは大丈夫 施設配置定式化を推奨 分枝カット法は悪い 実務的には「打ち切り分枝限定法」を推奨(緩和固定法と比べて簡単で高性能)

非線形施設配置問題 (色々な定式化の比較) 多重選択 非集約型凸結合 対数個の変数を用いた非集約型凸結合 集約型凸結合 対数個の変数を用いた集約型凸結合 SOS : タイプ2の特殊順序集合

集約型凸結合 対数個非集約型凸結合 対数集約型凸結合 非集約型凸結合 多重選択 sos

知見 単純なタイプ2の特殊順序集合 (SOS Type 2)を用いたものが最も良い. 次いで,対数個の変数を用いた集約型凸結合定式化,対数個の変数を用いた非集約型凸結合定式化,集約型凸結合定式化. 多重選択を使うケースをよくみるが,使うべきではない.

スケジューリング問題 1機械リリース時刻付き総納期遅れ最小化問題 比較する定式化 線形順序付け定式化 時刻添え字定式化 離接定式化 (Big M使用)

時刻添え字 線形順序付け 離接定式化

知見 比較的簡単な1機械問題でも200ジョブ程度で組合せ爆発 他のスケジューリング問題で実験したが,ベンチマーク問題例は全滅 現状では,スケジューリングは混合整数最適化では無理

Multi-objective Optimization Generate a set of non-inferior (Pareto) solutions by using Gurobi (that can find multiple solutions by one run of B&B) Make one objective by a linear combination of multiple objective functions Change objective functions to constraints and sliding the right-hand sides of the constraints Minimize the distance from ideal points

Non-inferior (Pareto) solutions Second Obj. Function Solutions in the region are dominated by solution A Linear Obj. Func. A Missed non-inferior point First Obj. Function

Best solution Under the time const. Generated solutions by the constraint sliding method (2-obj. TSP)

Constraint sliding (segmentation) and ideal point methods