二千十三年五月 あたらしい数理最適化 出版記念セミナー 主催 近代科学社 オクトーバースカイ 共催 構造計画研究所

Presentation on theme: "二千十三年五月 あたらしい数理最適化 出版記念セミナー 主催 近代科学社 オクトーバースカイ 共催 構造計画研究所"— Presentation transcript:

1 二千十三年五月 あたらしい数理最適化 出版記念セミナー 主催 近代科学社 オクトーバースカイ 共催 構造計画研究所

2 まずは自己紹介 久保幹雄 東京海洋大学 サプライ・チェイン最適化工学 フェイスブック：
ホームページ：

3 アジェンダ 13:00-13:50 「あたらしい数理最適化」概説 16:00-16:50 数理最適化の応用例 と実験的解析

4 前半 「あたらしい数理最適化」概説 この本のどこが新しいのか 数理最適化の基本の基本 定式化のコツ

5 あたらしい 数理最適化って 本が出たらしいけど 何があたらしいの？

6 あたらしいこと 0 数理最適化 (Mathematical Optimization) Since 2010

7 Programming) Up to 2010 its name
昔は．．． 数理計画 (Mathematical Programming) Up to 2010 its name was "Mathematical Programming Society みんなの投票で改名！（最適化に1票！）

8 Dantzig (1947) Programming in linear structure
Koopmans (1948) Linear Programming Dorfman (1949) Mathematical Programming

9 あたらしいこと　１ 他のテキストとは違って 解法の中身より 使いこなすためのテク

10 ピボット選択 有限収束の証明 改訂単体法 などは一切なし

11 双対性 分枝限定法 列生成 分枝カット法 そして二次錘最適化まで！ きちんと解説

12 あたらしいこと　２ Python言語ですぐ解ける 原案：PythonとGurobi でぐんぐん解ける！（小山社長）

13 Pythonとは When he began implementing Python, Guido van Rossum was also reading the published scripts from “Monty Python’s Flying Circus”, a BBC comedy series from the 1970s. Van Rossum thought he needed a name that was short, unique, and slightly mysterious, so he decided to call the language Python.

14 MITの講義の 表紙

15 import すれば何でもできる！ import gurobipy #数理最適化 import scop #制約最適化 import optseq #スケジューリング import antigravity (空を飛ぶ?)

16 あたらしいこと　３ 色々なソルバーを紹介 数理最適化 Gurobi 制約最適化 SOCP スケジューリング OptSeq

17 Gurobiとは Zonghao Gu, Edward Rothberg，Robert Bixby

18 Gurobiとは Zonghao Gu Edward Rothberg Robert Bixby

19 なぜGurobi ? （他にもたくさんあるじゃない） 混合整数 線形，凸二次，二次錘最適化 において（たぶん）最速
（MIPソルバーの限界を見極めたい！） これでダメなら，他でもダメ

20 なぜGurobi ? マルチコア対応 長時間まわしても壊れない（安定性抜群） Pythonからの呼び出しが“容易”
（他のソルバーは，呼び出し“可”レベル） 会議中でも実装可能！

21 なぜGurobi ? その３ プロ仕様の出力（とある実際問題のログ）
Optimize a model with 4794 rows, 4777 columns and nonzeros Presolve removed 4483 rows and 2877 columns Presolve time: 0.05s Presolved: 311 rows, 1900 columns, 4467 nonzeros Variable types: 25 continuous, 1875 integer (1863 binary) Found heuristic solution: objective Found heuristic solution: objective Root relaxation: objective e+02, 351 iterations, 0.01 seconds

22 SCOPとは 野々部先生，茨木先生作 Tabu Searchに基づく制約最適化ソルバー Gurobiでダメな問題でも大丈夫
（でも最適性の保証はなし！）

23 SCOP & OptSeq 野々部先生 茨木先生

24 時間割作成 看護婦スケジューリングの 国際コンペで好成績！ 後で,野々部先生が詳しくお話 してくれると思います

25 Shift Master （構造計画研究所様）でも採用！

26 OptSeqとは 野々部先生，茨木先生作 Tabu Searchに基づく 汎用」スケジューリング最適化ソルバー
Gurobiでダメな問題でも大丈夫 モデル化の工夫で実務問題の多くをカバー

27 SCOP, OptSeqともに Pythonインターフェイスあり！ （しかもPythonのソース開示！） 上手なメタヒューリスティクス => 汎用なのに高性能！

28 あたらしいこと　4 色々な実用的＋代表的な 問題例で比較 後半の講演でお話しします．

29 あたらしいこと 5 二次錘最適化 (second order cone optimization )
あたらしいこと　5 二次錘最適化 (second order cone optimization ) 後で,村松先生が詳しくお話してくれると思います

30 数理最適化とは？ お金を儲けたいんだよね－ でも，色々としがらみがあってね－．

31 数理最適化とは？ maximize 　お金 subject to しがらみ 目的関数 制約条件

32 数理最適化とは？ maximize f(x) subject to g(x)≧0 x ∈ X

33 線形最適化とは？ max. cx s.t. Ax≦b x は実数

34 解法 目的関数 内点法 単体法

35 使い分け 基本はデフォルト（双対単体法）で 単体法が遅いときには，内点法！

36 どこまで解ける？ -- GUROBI-5.5.0 内点法
秒 rail4284 4284行 列 非ゼロ L1_d10_40 80477行 420366列 非ゼロ 非ゼロ要素数   (Mittelmannによる実験)

37 整数最適化とは？ max. cx s.t. Ax≦b x は整数

38 目的関数 解法：分枝限定法＝基本は線形最適化

39 目的関数 上界 整数解 実行可能解 下界 分枝操作

40 コツ　１ 整数最適化に対しては， 良い定式化をしよう！ 上界と下界のギャップが 小さい定式化

41 そのためには 大きな数Mを用いた 実数変数≦M・整数変数 はなるべく避ける！

42 コツ　2 解が対称性をもつ場合 には注意！

43 対称性とは？ グラフ彩色問題 「点」に色を塗る！枝の両端点は別色．

44 対称性とは？ グラフ彩色問題の解（の１つ） 「点」に色を塗る！枝の両端点は別色．

45 対称性とは？ 赤，青，黄を交換しても同じ解！

46 分枝限定法の基本 X1,黄色 = 0.5 緩和問題 点１は黄色 に塗る 点１は黄色に 塗らない X1,黄色 = 1 X1,黄色 = 0

47 分枝しても限定できない！ 点１は黄色に塗らない

48 分枝しても限定できない！ 点１は青色に塗らない

49 やっと限定操作 点１は黄色に塗らない 点１は赤色に塗らない

50 解決法：対称性を除去 無記名の「色」に優先順序を付加 例： 赤使用 ≧ 青使用 ≧ 黄使用 でも，あまり効かない（実験は後ほど）

51 対称性の例２ ビンパッキング問題 色々なアイテムを「同じ大きさ」の箱（ビン）に詰める！ 箱の数を最小に！（＝すきまを最小に！）

52 対称性の例２ 最適解（の１つ） 箱の番号を変えても同じ解！

53 X1,箱１ = 1 X1,箱１ = 0 分枝限定法を使うと．．． X1,箱１ = 0.5 緩和問題 アイテム１は 箱１に入れる アイテム１は
箱１に入れない X1,箱１ = 1 X1,箱１ = 0

54 分枝しても限定できない！ アイテム１ 箱１ アイテム１は箱２に入れない アイテム１ アイテム１ アイテム１は箱１に入れない

55 解決法：パターンの列挙 ・・・・ アイテムをちょうど１つ含むように （たくさんの）パターンから選択

56 コツ　3 （パターン）変数の数が 非常に多い => 列生成法

57 min. cx s.t. Ax=b 列生成法 c A 行列 Aが超横長 必要な「列」だけ生成！

58 コツ　4 制約の数が非常に 多い=> 切除平面法 もしくは分枝カット法

59 min. cx s.t. Ax=b 切除平面法 A b 行列 Aが超縦長 必要な「行」だけ生成！ 切除平面（カット）

60 分枝カット法 A b 分枝する度にカットを追加！

61 例： 巡回セールスマン問題 すべての点をちょうど1回通過する最短巡回路

62 巡回セールスマン問題 の最適解 すべての点をちょうど1回通過する最短巡回路

63 定式化 点に接続する枝の本数＝２ for all 点 （次数制約）

64 定式化 点に接続する枝の本数＝２ for all 点 （次数制約）

65 足りない制約を付加 枝の本数＜点の数 for all 点の部分集合 （部分巡回路除去制約） この中の枝の本数 2本以下！

66 コツ　5 特殊順序集合 Special Ordered Setを 使いこなそう！

67 A>0 or B>0 or C>0 => 変数 A,B,C はSOSと宣言
SOS Type 1 変数のうちの高々１つが正 特殊な分枝操作で高速化 A>0 or B>0 or C>0 => 変数 A,B,C はSOSと宣言

68 SOS Type 2 連続する高々2つの変数が正 [0 0 0 0.5 0.4 0 0] => OK
[ ] => NG [ ] => OK 区分的線形関数の宣言で使用

69 線分の表現

70 区分的線形関数の表現 はSOS Type 2

71 コツ　6 最大値を最小化する 目的関数には注意！

72 線形最適化での 常套手段 min. max. f(x,y) y x

73 線形最適化での 常套手段 min. max. f(x,y) y x =zと置いて

74 線形最適化での 常套手段 min. max. f(x,y) y x =zと置いて min. z s.t. f(x,y)≦z

75 （混合）整数最適化では， これをやると終わらない！ 問題に応じた工夫（二分探索） もしくは他の手法を用いる！

76 謝辞 Acknowledgement

77 主催 近代科学社　　小山社長，大塚様 オクトーバースカイ　 　　　　　　　　和多田社長，中村様

78 共催　＆　会場提供 構造計画研究所　斉藤 様 池水 様

79 SCOP & OptSeq 野々部先生 茨木先生

80 Experimental Analysis
All Python Codes Experimental Analysis ジョアン（ジョン）・ペドロ・ペドロソ先生 「ジョア」ではないらしい

81 村松先生＠電通大 Another Co-Author Abdur

82 樋口（ペドロソ）真美さん 綺麗な表紙をありがとう！

83 ご来場の皆様 懇親会もあります！