ＯＲ学会チュートリアルはじめよう整数計画

Size: px

Start display at page:

Download "ＯＲ学会チュートリアルはじめよう整数計画"

かねろうかむら
5 years ago
Views:

1 OR 学会春季研究発表会チュートリアル数理計画法 (RAMP) 研究部会企画はじめよう整数計画法藤江哲也兵庫県立大学大学院経営研究科 04 年 3 月 7 日 ( 金 ) 大阪大学豊中キャンパス

2 OR 学会誌 0 年 4 月号

楽しくラリーが続けられることを目指しますラリーを少しつなげられる方のコースです各ショットのレベルアップを目指します

3 本チュートリアルの目指すところはじめてコース初級コース初中級コース中級コース上級コース初めてラケットを持つ方のコースです簡単なルールやマナーなども覚えます基本からしっかりと学びたいという方のコースです楽しくラリーが続けられることを目指しますラリーを少しつなげられる方のコースです各ショットのレベルアップを目指しますストロークボレーサーブスマッシュがある程度コントロールできるという方のコースですダブルスにおける攻守を理解し一通り実践できる方のコースです 3

4 本チュートリアルの目指すところはじめてコース初級コース初めてラケットを持つ方のコースです簡単なルールやマナーなども覚えます基本からしっかりと学びたいという方のコースです楽しくラリーが続けられることを目指します. 整数計画とは何か. 今なぜ整数計画なのか 3. 整数計画をはじめよう道具をそろえよう道具を使ってみよう 4

5 線形計画問題 (LP: Linear Programming) テーブルとチェアを製造販売個当たり所要時間利益および製造工程の使用可能時間テーブルチェア使用可能時間工程 3 時間 3 時間時間工程時間 7 時間 4 時間利益千円 5 千円利益を最大にするテーブルとチェアの製造数は? 5

6 線形計画問題 (LP: Linear Programming) テーブルチェア使用可能時間工程 3 時間 3 時間時間工程時間 7 時間 4 時間利益千円 5 千円最大化条件 z z.33 z 0 最大化最適解 ( ) = (7/3 4/3) z = 34/3 =.33 z z 5 0 O 3 6

7 整数計画問題整数線形計画問題 IP (Integer Programming) ILP (Integer Linear Programming) 最大化条件 z : 整数最大化最適解 ( ) = (0 ) z = 0 O 3 7

8 混合整数計画問題 MIP (Mied Integer Programming) 整数条件 : 一部またはすべての変数最大化条件 z : 整数最大化最適解 ( ) = ( 0/7) z = 78/7=.4 O 3 8

9 バイナリ変数 (0- 変数 ) j = 0 またはバイナリ変数も線形不等式 + 整数変数で記述できる j = 0 または 0 j j 整数しかしバイナリ変数は整数変数と区別されるのが一般的高い表現能力 0- の特性に基づくアルゴリズム開発 9

10 バイナリ変数の例 : ナップサック問題 A ポテトチップス B チョコレート C マシュマロ D アメ E ガム F せんべい満足度 5 点 7 点 4 点点 3 点 8 点値段 00 円 30 円 80 円 50 円 70 円 0 円おかしの合計金額は 300 円まで B C D ナップサックの容量 c = 300 各種類つまで満足度の合計が最大とするには? 合計金額 = = 60 <= 300 満足度の合計 = = 3 0

11 バイナリ変数の例 : ナップサック問題 A B C D E F 満足度 5 点 7 点 4 点点 3 点 8 点値段 00 円 30 円 80 円 50 円 70 円 0 円 0 Aを選ぶとき Aを選ばないときなどとすると最大化条件または = のとき 00 =0 のとき 0

12 バイナリ変数の例 : 部分和問題 A ポテトチップス B チョコレート C マシュマロ D アメ E ガム F せんべい値段 00 円 30 円 80 円 50 円 70 円 0 円合計金額 300 円以内で 300 円に最も近い組み合わせは? 最大化条件または

13 バイナリ変数 (0- 変数 ) を用いた表現組合せ最適化問題巡回セールスマン問題集合分割問題集合被覆問題スケジューリング問題施設配置問題非線形関数の線形近似離接 (disjunctive) 制約 + または + どちらが選ばれるか? どの線分が選ばれるか? O 3

14 バイナリ変数 (0- 変数 ) を用いた表現整数変数 0 5 整数 = 3 の場合 = y + y + y 3 y y y 3 = 0 または 0 = y + y + 3y 3 + 4y 4 + 5y 5 y + y + y 3 + y 4 + y 5 y y y 3 y 4 y 5 = 0 または = y + y + y 3 + y 4 + y 5 y y y 3 y 4 y 5 = 0 または 4

15 線形計画 LP と整数計画 MIP LP MIP 応用例生産スケジューリング配送施設配置 DEA 交通ネットワーク流詰込み切出し金融シフトスケジューリング時間割作成選挙区割応用範囲広い整数条件でさらに広がる!! 知名度高い低い? はじめようの理由 5

16 線形計画 LP と整数計画 MIP 代表的解法 LP 単体法内点法 MIP 切除平面法分枝限定法分枝カット法解きやすさ ( 理論的 ) ( 実際的 ) 947 年単体法 (Dantzig) easy (P) 大規模問題も解ける 957~60 年分枝限定法 (Markowitz-Manne Eastman Land-Doig) 切除平面法 (Gomory) hard (NP) 解ける問題規模が拡大中はじめようの理由 6

17 線形計画 LP CPLEX LP (6 年 ) アルゴリズム 3300 倍計算機 600 倍トータル 58 万倍 R. E. Biby ``A Brief History of Linear and Mied-Integer Programming Computation In: Grötschel M. (ed.) Optimization Stories pp.07- (0) Xpress-MP (8 年 ) 制約式変数計算時間主単体法双対単体法内点法 R. Ashford ``Mied Integer Programming: A Historical Perspective with Xpress-MP Annals of Operations Research (007) 7

整数計画 MIP CPLEX MIP 99 007(6 年 ) 問題数 89 タイムリミット 30000 秒 =8.3 時間少なくとも一方で解けた問題を比較速度比の幾何平均バージョンアップによるスピード比 5.5 倍 0.0 倍累積スピード比 99 007 R.

18 整数計画 MIP CPLEX MIP (6 年 ) 問題数 89 タイムリミット秒 =8.3 時間少なくとも一方で解けた問題を比較速度比の幾何平均バージョンアップによるスピード比 5.5 倍 0.0 倍累積スピード比 R. E. Biby ``A Brief History of Linear and Mied-Integer Programming Computation In: Grötschel M. (ed.) Optimization Stories pp.07- (0) 8

整数計画 MIP CPLEX MIP 998 0(4 年 ) 問題数 753 タイムリミット 0000 秒 =.8 時間解けなかった問題数解けた問題の計算時間の幾何平均解けなかった問題数 5 問累積スピード比 55 問 998 0 T. Achterberg and R.

19 整数計画 MIP CPLEX MIP 998 0(4 年 ) 問題数 753 タイムリミット 0000 秒 =.8 時間解けなかった問題数解けた問題の計算時間の幾何平均解けなかった問題数 5 問累積スピード比 55 問 T. Achterberg and R. Wunderling ``Mied Integer Programming: Analyzing Years of Progress In: M. Jünger and G. Reinelt (eds.) Facets of Combinatorial Optimization pp (03) 9

20 整数計画 MIP MIPLIB00 ( の一部 Easy : 商用ソルバで時間以内に解ける Hard : 解かれてはいるが時間や手間がかかる Open : 未解決制約式変数整数バイナリ連続 Easy Open 0

21 今なぜ整数計画 MIP なのか非常に! 整数条件で応用範囲が広がる組合せ最適化 ( 離散最適化 ) を含む汎用的なモデル汎用的ゆえに実用性は絶望視されていたしかし MIPソルバーが高速化 LP ソルバーの進化切除平面法の併用高速化のための技術以外と? 整数計画をはじめるのは難しくない次の話題百万円数千円アカデミックフリーのソフトも! MIP ではフリーソフトも充実十分高性能で使いやすさも向上

22 Ecelソルバー Microsoft Office または Ecel をインストールすると利用できるアドイン Ecelソルバーの解説書籍解説高井真鍋 ( 編著 ) 問題解決のためのオペレーションズリサーチ入門日本評論社 000 年柏木 Ecelで学ぶ意思決定論オーム社 006 年阿部 Ecelで学ぶ統計解析ソシム 006 年藤澤後藤安井 Ecelで学ぶOR オーム社 0 年後藤 : Ecelで学ぶ数理最適化オペレーションズリサーチ Vol.57 No.4 pp.75-8 (0)

23 Ecel ソルバー最大化条件 z : 整数最大化 O 3 データの入力解を書き入れるセル (B:C) 3

24 Ecel ソルバー最大化条件 z : 整数最大化 O 3 数式の入力または 4

25 Ecel ソルバー最大化最大化条件 z : 整数 O 3 見当たらない場合はファイルオプションアドインからソルバーの起動 5

26 Ecel ソルバーソルバーの起動目標値最大値目的セル D3 変数セル B:C 制約条件 ( 次スライド ) 変数の非負条件 (0 以上 ) シンプレックス LP 6

27 Ecel ソルバー制約条件 : 整数 7

28 Ecel ソルバーソルバーの起動と実行最適性を 0 に 8

29 Ecel ソルバー最大化条件 z : 整数最大化 O 3 最適解最適解最適値 9

30 MIPソルバー商用 FICO Xpress (Fair Isaac Corporation) Gurobi Optimizer (Gurobi Optimization) IBM ILOG CPLEX (IBM) LINDO (LINDO Systems) NUOPT (NTTデータ数理システム ) SOPT (Saitech Inc.) 等非商用 COIN/CBC GNU GLPK lp_solve SCIP 等 30

31 問題ファイルの作成最大化条件 z : 整数 CPLEX LP 形式 (sample.lp) maimize + 5 subject to <= + 7 <= 4 general end MPS 形式 (sample.mps) NAME sample.mps ROWS N z L r L r COLUMNS M 'MARKER' 'INTORG' z - r 3 r z -5 r 3 r 7 M 'MARKER' 'INTEND' RHS RHS r r 4 BOUNDS PL BOUND PL BOUND ENDATA 3

32 GUSEK(GLPK の IDE) による実行 sourceforge.jp 等からダウンロード zip ファイルを解凍解凍ダブルクリック 3

33 GUSEK(GLPK の IDE) による実行 33

34 GUSEK(GLPK の IDE) による実行ソルバー起動解出力ファイルの生成 34

35 GUSEK(GLPK の IDE) による実行最適値最適解 35

$floor(log_n); param a{j in..n} := ** (k + n + ) + ** (k + n + - j) + ; param b := 0.$

36 モデリング言語 (MathProg) eamples todd.mod ( ナップサック問題 ) param n > 0 integer; param log_n := log(n) / log(); param k := floor(log_n); param a{j in..n} := ** (k + n + ) + ** (k + n + - j) + ; param b := 0.5 * floor(sum{j in..n} a[j]); var {..n} binary; maimize obj: sum{j in..n} a[j] * [j]; s.t. cap: sum{j in..n} a[j] * [j] <= b; data; param n := 5; 変数目的関数制約式 end; 36

37 ここまでのまとめ. 整数計画 MIPとは何か. 今なぜ整数計画なのか応用範囲が広いソルバーが劇的に高速化 3. 整数計画をはじめよう道具をそろえよう道具を使ってみよう意外と身近意外と容易 4. 定式化について 37

38 線形計画 LP と整数計画 MIP 実行可能解集合の形 LP 多面体 MIP 格子点 ( 全整数の場合 ) 38

39 整数計画 MIP 様々な定式化が可能理想的な定式化 ( 凸包 ) これがわかれば MIP = LP しかし一般に知ることは困難わかったとしても膨大な数の制約式になる可能性が大きい Better Best 39

40 定式化について定式化は複数ありうる変数の定義も複数ありうる 40

41 定式化の例 : 数独あいているマスに -9 までのどれかの数字を入れる縦横の各列及び太線で囲まれた 3 3 のブロックに同じ数字が入ってはいけない Wikipedia の数独より 4

42 数独の定式化方法 ij :( i j) マスに入る数字 ( つまり 9) ij 方法 ijk ( i j) マスに入る数字が k 0 そうでないときのとき T. Koch "Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a Few Seconds" Operations Research Proceedings 005 4

43 方法 6 =

44 方法 6 = =

45 定式化 : 方法 n j i k n j i k j i k j i k i n k j i j n j i arbitrarily ij ij ij c k r j c i r kj ij i ij k j i : ) ( ; ; ; ) ( ) 3( ) 3( ) 3( ) 3( 整数条件最小化のときマスが初期配置で n = 9 ) りマスに入る数字 ( つま 9 ) ( : ij ij j i 45

46 定式化 : 方法または b b b b b b b b i ij i ij 注注 ) ( ent all_differ in i という表現をすることも多い 46

47 定式化 : 方法 n k j i n k c r n k j n k i n j i arbitrarily ijk ijk r r i c c j ijk n i ijk n j ijk n k ijk k j i 0 3; ) ( 3 ) 3( 3 ) 3( またはのときマスが初期配置で条件最小化そうでないときのときマスに入る数字が 0 ) ( k j i ijk 47

48 定式化の比較定式化変数 3970( 一般整数変数変数 944) 制約固定制約数計算時間 4.5 秒 (Intel Core Duo メモリ.0GB CPLEX.5) Kochの論文によると CPLEX9.03では6 時間経っても解けなかった定式化変数 79(0- 変数 79) 制約 346+ 固定制約数計算時間 0.0 秒 48

49 定式化について定式化は複数ありうる変数の定義も複数ありうる MIPとLPがかけ離れている (LP 緩和が弱い ) 定式化は望ましくない big-m を含む表現 49

50 バイナリ変数 (0- 変数 ) を用いた表現組合せ最適化問題巡回セールスマン問題集合分割問題集合被覆問題スケジューリング問題施設配置問題非線形関数の線形近似離接 (disjunctive) 制約 + または + どちらが選ばれるか? どの線分が選ばれるか? O 50

51 O + + Big-M を含む問題例 5 0 y y 0 3 z または条件最大化 0 0 ) ( 3 または条件最大化 y My y M z 0 M または M 0

52 最大化条件 z 3 M ( My y) 0 y 0 または 0 y M 0000 y ( 0 ) y ( 0 0 ) (0 ) ( 0 0 0) (0 0) ( ) ( ) ( 0 0) y 0 MIP の最適値 z = 6 LP の最適値 z = 0004 最適値の差が大きい数値的に不安定 5

53 定式化について定式化は複数ありうる変数の定義も複数ありうる MIPとLPがかけ離れている (LP 緩和が弱い ) 定式化は望ましくない big-m を含む表現緩和の強さ vs 変数制約式の数といろいろ話はありますがまずははじめよう定式化! 53

54 OR 学会誌 0 年 4 月号はじめてコース初級コース初中級コース中級コース後藤宮代藤江宮本小林吉瀬上級コース 54

55 補足 :MIP ソルバーの利用方法問題ファイルを作成しコマンドラインから実行 IDE( 統合開発環境 ) の使用モデリング言語商用 AIMMS AMPL GAMS LINGO MOSEL MPL OPL Simple... フリー MathProg ZIMPL... API(Application Interface) プログラムから呼び出す C C++ Java Ecel Matlab python... 55

56 補足 : 整数計画いろいろ線形計画二次計画 ( 線形制約 ) 二次計画 ( 二次制約 ) 二次錐計画半正定値計画非線形計画 56

57 参考情報整数計画法メモ ( 東京農工大宮代先生 ) 57

58 参考情報 OR 学会誌特集号 ( 最適化 ) 0 年 5 月号最適化技術の深化と広がり 03 年月号はじめようメタヒューリスティクス 04 年月号研究の楽しさ 04 年 3 月号新世代が切り拓く連続最適化さらに同誌には整数計画の適用事例を扱った論文解説多数 58

59 参考情報 RAMP シンポジウム 59

OR#5.key

OR#5.key オペレーションズリサーチ１ Operations Research 前学期月曜３限(3:00-4:30) 8 整数計画モデル Integer Programming 経営Ａ棟１０６教室山本芳嗣筑波大学大学院システム情報工学研究科整数計画問題 2 凸包最小の凸集合線形計画問題変数の整数条件 ctx Ax b x 0 xj は整数 IP LP 3 4 Bx d!!!!!? P NP

ＯＲ学会チュートリアル はじめよう整数計画

ＯＲ学会チュートリアルはじめよう整数計画