最適化ソリューションにおける モデリングツールAMPLの活用

最適化ソリューションにおける モデリングツールAMPLの活用
第1回 数理最適化データサイエンス研修会(2025年6月14・15日)
野々部 宏司
法政大学デザイン工学部 株式会社MOAI Lab

Transcript

1. 最適化ソリューションにおける モデリングツールAMPLの活用 野々部 宏司 法政大学デザイン工学部 株式会社MOAI Lab 第1回 数理最適化データサイエンス研修会（2025年6月14・15日）
2. 2 種々の制約のもと，何らかの関数を最小化／最大化 minimize 𝑓𝑓(𝑥𝑥) 𝑓𝑓(𝑥𝑥)：目的関数 subject to 𝑥𝑥 ∈ 𝐹𝐹 𝐹𝐹：実行可能領域 最適化問題 問題例（インスタンス） 「モデル」＋「データ」  ある特定の問題を与える  具体的な数値を用いて表 される 問題 「モデル」  同様の構造を有する問題例 の集合を与える  集合・パラメータを用いて 表される 一般化・抽象化 具現化 ＋「データ」
3. 3 数理最適化による問題解決 （最適化ソリューション） モデル／データの見直し モ デ ル の 世 界 ソルバー／アルゴリズムの 変更・改良 （主に導入時） 実問題 結論・意思決定 (近似)最適解 最適化モデル モデリング データ設定 解釈 分析・検証 最適化計算
4. 4 数理最適化による問題解決 （最適化ソリューション） モデル／データの見直し モ デ ル の 世 界 ソルバー／アルゴリズムの 変更・改良 （主に導入時） 実問題 結論・意思決定 (近似)最適解 最適化モデル モデリング データ設定 解釈 分析・検証 最適化計算 どのような実問題を扱うか どのようにモデリングするか どのようにデータを収集するか どのように最適化計算を行うか どのように計算結果を解釈するか どのように結論を実行に移すか …
5. 5 方法１．既存のソルバー（数理最適化ソルバー）を利用  問題によっては，定式化の見直し，問題の分割・階層化， 制約緩和，ソルバーの変更などが必要 方法２．ソルバーを個別に開発  既存ソルバーでは十分な性能（速度・解の精度）が得られない 場合や既存ソルバーの利用が困難である場合など  アルゴリズム設計＋実装 → 時間的・予算的負担  考慮すべき事項 問題構造，データの規模・特徴，実務上の要求事項， 運用時の利用方法，人の介在有無 など 最適化計算の実現
6. 6 方法１．既存のソルバー（数理最適化ソルバー）を利用  問題によっては，定式化の見直し，問題の分割・階層化， 制約緩和，ソルバーの変更などが必要 方法２．ソルバーを個別に開発  既存ソルバーでは十分な性能（速度・解の精度）が得られない 場合や既存ソルバーの利用が困難である場合など  アルゴリズム設計＋実装 → 時間的・予算的負担  考慮すべき事項 問題構造，データの規模・特徴，実務上の要求事項， 運用時の利用方法，人の介在有無 など 最適化計算の実現 主に方法１の場合における ・ソリューション開発プロセスの効率化 ・導入時／導入後の保守性・拡張性の向上
7. 7  AMPL (A Mathematical Programming Language)  GAMS (General Algebraic Modeling System)  Pyomo (Python-based, open-source optimization modeling language)  PuLP (LP modeler written in Python)  JuMP (Julia for Mathematical Optimization)  MiniZinc (A high-level constraint modelling language) など モデリングツール
8. 8  A Mathematical Programming Language 数理最適化問題を記述し，解決するための代数的モデリング言語 （および これをベースとしたモデリングツール）  1980年代後半，ベル研究所の Robert Fourer，David M. Gay，Brian W. Kernighan によって開発  長年の実績と技術的蓄積  学術界および産業界で広く利用  宣言的 「何を」最適化するかを記述することに焦点を当て， 最適化問題を「どのように」解くか（アルゴリズム）はソルバーに 委任 AMPLとは
9. 9  代数的な表現・高い記述能力：直感的かつ豊富な構文  sum, prod, if-then-else, and, or, forall, exists, abs, log, …  モデルとデータの分離：同じモデルを異なるデータセットで 再利用可能  .mod ファイル：モデル構造（変数，目的関数，制約など）  .dat ファイル：具体的な値やデータ（集合要素，パラメータ値）  ソルバー非依存：様々な最適化ソルバーと連携可能  Gurobi, CPLEX, MINOS, Knitro, CBC など  強力なスクリプト機能：求解プロセスや結果分析を自動化  スケーラビリティ：小規模な教育用問題から，非常に大規模 で複雑な実務問題まで対応 AMPLの主な特徴
10. 10 基本的な構成 ソルバー  Gurobi  CPLEX  Xpress  COPT  Knitro  MINOS  CBC  SCIP モデル .mod ファイル AMPL 集合・パラメータ， 変数・目的関数・制約を 代数的に記述 モデルで使用する 集合・パラメータの 具体的な要素・値を記述 データ .dat ファイル データ .dat ファイル データ .dat ファイル インスタンス モデル ＋ データ ↓ 計算結果 最適解，双対情報など ソルバー 選択 オプション 設定 … …
11. 11  効率性・生産性 わかりやすい記法と高い記述能力によりモデル開発を迅速化  可読性・保守性 モデルの構造が明確で理解しやすい  柔軟性・拡張性 様々なタイプの最適化問題（線形最適化，整数最適化，非線形最適化 など）に対応／独自のソルバーや関数との連携も可能  再利用性 モデル・データ・ソルバーの分離により，モデルの再利用が容易  信頼性・成熟性 長年の利用実績による強力なコミュニティ，豊富なドキュメント AMPLの利点
12. 12  ダウンロード  公式サイト（ampl.com）  ライセンス  ライセンスなし：変数・制約数，機能に制限あり  Community Edition：無料．商用利用不可／開発目的可  オープンソース・ソルバーがバンドル  商用ソルバーのトライアル版も利用可能  商用ライセンス：各種ライセンス形態あり  アカデミックライセンス：教育・研究目的で無料／割引  インストール  インストーラ for Windows, Linux, MacOS  Pythonパッケージ (amplpy)，Dockerコンテナ 準備
13. 13  AMPL IDE  コマンドラインインタフェース  VS Code 拡張機能  各種API：Python, R, …（後述） など 開発・実行環境
14. 14  統合開発環境（Integrated Development Environment）  コードエディタ（シンタックスハイライト付き）， モデル・データ・実行の管理機能，結果表示機能などを提供  初心者や視覚的なインタフェースを好むユーザ向け  公式サイトからダウンロード可能 AMPL IDE
15. 15  ターミナル上で起動  WindowsのコマンドプロンプトやLinux/macOSのターミナル などで ampl と入力して起動  対話的にコマンドを入力してモデルを操作・求解  スクリプティングとの親和性が高い コマンドラインインタフェース
16. 16 VS Code 拡張機能
17. 17 AMPLモデリング ―入門編―
18. 18 1. モデルファイルとデータファイルを用意  「diet.mod」「diet.dat」 2. モデルとデータの読み込み  model diet.mod;  data diet.dat; 3. ソルバーの選択  option solver gurobi; 4. 求解  solve; 5. 結果の表示  display Buy; 基本的な流れ（コマンドラインの場合）
19. 19 モデルファイルとデータファイル
20. 20 モデルファイルとデータファイル モデルファイル (.mod)  モデルの構造を定義  集合，パラメータ，変数，目的関数，制約の宣言を行う  一般的・抽象的な記述 データファイル (.dat)  モデルで宣言された集合やパラメータの要素や値を定義  具体的なデータを記載  特定のインスタンス（問題例）に対応
21. 21  モデル内の要素の集合を表す  例：製品，期間，場所，原材料  各要素は「文字列」または「数値」  モデルの基本的なインデックス（添え字）を定義する  多くのパラメータ，変数，制約等は，何らかの集合上で インデックス付けされる 集合 set # --- In model file (model.mod) --- set PRODUCTS; # Set of products set RESOURCES; # Set of resources # --- In data file (data.dat) --- set PRODUCTS := Steel Screws Bolts ; set RESOURCES := Labor MachineA MachineB ;
22. 22  モデル内の既知の定数を表す  例：コスト，容量，需要，係数  主に「数値」であるが，「文字列」も可（symbolic）  スカラーまたはインデックス付きとして定義  複数のインデックス（多次元）も可 パラメータ param # --- In model file (model.mod) --- set PRODUCTS; param production_capacity; # production capacity: scalar param demand {j in PRODUCTS}; # Demand for each product #param demand {PRODUCTS}; # index j can be omitted # --- In data file (data.dat) --- param production_capacity := 500 ; param demand := Steel 100 Screws 150 Bolts 300 ;
23. 23  同じ集合上でインデックス付けされた， 複数のパラメータのデータをまとめて指定できる パラメータ param # --- In model file (model.mod) --- param rate {PROD} > 0; param profit {PROD}; param market {PROD} >= 0; # --- In data file (data.dat) --- set PROD := bands coils plate; param: rate profit market := bands 200 25 6000 coils 140 30 4000 ;
24. 24  ２次元データの指定方法 パラメータ param # --- In model file (model.mod) --- param rate {PROD,STAGE} > 0; # --- In data file (data.dat) --- set PROD := bands coils plate; set STAGE := reheat roll; param rate: reheat roll := bands 200 200 coils 200 140 plate 200 160 ; param rate (tr): bands coils plate := reheat 200 200 200 roll 200 140 160 ;
25. 25  モデルが決定すべき未知の値を表す  例：生産量，輸送量，割当て（0 または 1）  最適化計算によって値が定まる  インデックス付けが可能（パラメータと同様） 決定変数 var # --- In model file (model.mod) --- set PRODUCTS; set LOCATIONS; set CUSTOMERS; var Produce {PRODUCTS}; # Amount of each product to produce var Transport {PRODUCTS, LOCATIONS, CUSTOMERS}; # Amount transported
26. 26  型指定：整数変数（integer），バイナリ変数（binary）  上下限制約：  >= lower_bound：下限  <= upper_bound：上限  = fixed_value：固定値（通常はパラメータで表現） 決定変数 var # --- In model file (model.mod) --- param max_production {PRODUCTS}; param min_batch_size {PRODUCTS}; var Produce {p in PRODUCTS} >= min_batch_size[p], <= max_production[p]; var Build {LOCATIONS} binary; var NumWorkers {LOCATIONS} integer, >= 0;
27. 27  最適化（最大化または最小化）したい指標  変数とパラメータを用いた数式で表現される 目的関数 maximize/minimize # --- In model file (model.mod) --- set PRODUCTS; param unit_profit {PRODUCTS}; param unit_cost {PRODUCTS}; var Produce {PRODUCTS} >= 0; # Example 1: Maximize total profit maximize TotalProfit: sum {p in PRODUCTS} unit_profit[p] * Produce[p]; # Example 2: Minimize total cost minimize TotalCost: sum {p in PRODUCTS} unit_cost[p] * Produce[p];
28. 28  式の表現  算術演算子（+, -, *, /, ^ など）  組み込み関数（exp, log, sqrt, abs, sin, cos など）  総和（sum {index_set} expression）  積（prod {index_set} expression）  条件（if condition then expr1 else expr2） 目的関数 maximize/minimize maximize ComplexObjective: sum {i in I} profit[i] * X[i] - sum {j in J} cost[j] * Y[j]^2; minimize PenaltyCost: sum {t in PERIODS} if Inventory[t] < min_level then penalty * (min_level - Inventory[t]) else 0;
29. 29  モデルの解が満たすべき条件や制限  例：リソースの制限，需要の充足，物理的な制約  インデックス付けが可能 制約 subject to # Simple equality constraint subject to ProductionTarget: sum {p in PRODUCTS} Produce[p] = total_production_target; # Resource availability constraint for each resource subject to ResourceLimit {r in RESOURCES}: sum {p in PRODUCTS} usage[r,p] * Produce[p] <= availability[r];
30. 30  show：モデル要素の宣言の確認  単に show とすればすべての要素名が表示される  expand：データによって具現化された式の確認  単に expand とすればモデル全体（インスタンス）が表示される モデル要素の確認 ampl: show Diet_Min; subject to Diet_Min{i in MINREQ} : sum{j in FOOD} amt[i,j]*Buy[j] >= n_min[i]; ampl: expand Diet_Min; subject to Diet_Min['A’]: 60*Buy['BEEF'] + 8*Buy['CHK'] + 8*Buy['FISH'] + 40*Buy['HAM'] + 15*Buy['MCH'] + 70*Buy['MTL'] + 25*Buy['SPG'] + 60*Buy['TUR'] >= 700; subject to Diet_Min['B1']: …
31. 31  利用可能な代表的なソルバー  線形最適化（LP），混合整数最適化（MIP）  商用：Gurobi, CPLEX, Xpress, COPT  オープンソース：HiGHS, SCIP, GCG, CBC  非線形最適化（NLP）  商用：Knitro, CONOPT, SNOPT, MINOS  オープンソース：Ipopt  大域的最適化  商用：Baron  制約プログラミング  商用：ILOG CP ソルバーの選択
32. 32  display：最適化計算後，変数の値や目的関数値などを表示  制約を指定すれば，潜在価格が表示される  パラメータ，集合などの具体的な値も確認できる 結果の確認 ampl: display Total_Cost; Total_Cost = 74.2738 ampl: display Diet_Min; Diet_Min [*] := A 0 B1 0 B2 0 C 0.00670787 CAL 0.00447191 ; ampl: display Buy; Buy [*] := BEEF 2 CHK 10 FISH 2 HAM 2 MCH 2 MTL 6.23596 SPG 5.25843 TUR 2 ;
33. 33 AMPLモデリング ―基礎～応用編―
34. 34  多次元（複数インデックス）データの指定  表形式での記述が可能 多次元パラメータ # --- In model file (model.mod) --- param cost {ORIG,DEST,PROD} >= 0; # --- In data file (data.dat) --- set ORIG := GARY CLEV PITT ; set DEST := FRA DET LAN WIN STL FRE LAF ; set PROD := bands coils plate ; param cost := [*,*,bands]: FRA DET LAN WIN STL FRE LAF := GARY 30 10 8 10 11 71 6 CLEV 22 7 10 7 21 82 13 PITT 19 11 12 10 25 83 15 …
35. 35  集合のデータと，その集合でインデックス付けされる パラメータのデータを同時に指定できる 集合・パラメータの同時指定 # --- In model file (model.mod) --- set ORIG; param supply {ORIG} >= 0; # --- In data file (data.dat) --- param: ORIG: supply := GARY 1400 CLEV 2600 PITT 2900 ;
36. 36  他の集合の要素によってインデックス付けされる集合  例：各製品を製造するために必要な部品の集合 インデックス付き集合 # --- In model file (model.mod) --- set PRODUCTS; set PARTS; set PARTS_NEEDED {PRODUCTS}; # For each product, # a set of parts needed # --- In data file (data.dat) --- set PRODUCTS := Car Bike ; set PARTS := Wheel Frame Seat Chain ; set PARTS_NEEDED[Car] := Wheel Frame Seat ; set PARTS_NEEDED[Bike] := Wheel Frame Seat Chain ;
37. 37  要素に順序のある集合  例：期間，ステップ  first(), last(), next(), prev(), ord() などの関数が 利用可能  循環構造をもたせることも可能（circular） 順序付き集合 ordered # --- In model file (model.mod) --- set PERIODS ordered; # Time periods param initial_inventory {PRODUCTS}; var Inventory {PRODUCTS, PERIODS}; subject to InventoryBalance {p in PRODUCTS, t in PERIODS: t != first(PERIODS)}: Inventory[p,t] = Inventory[p, prev(t)] + ... ; # --- In data file (data.dat) --- set PERIODS := Jan Feb Mar Apr ;
38. 38  順序対を要素とする集合  例：ODペア  ３つ組以上を要素とすることも可能 順序対集合 set ORIG; # origins set DEST; # destinations set LINKS = {ORIG,DEST}; #set LINKS dimen 2; param cost {LINKS} >= 0; # shipment costs per unit var Trans {LINKS} >= 0; # units to be shipped minimize Total_Cost: sum {(i,j) in LINKS} cost[i,j] * Trans[i,j];
39. 39 順序対集合：データ指定 (1) # --- In model file (model.mod) --- set LINKS dimen 2; # --- In data file (data.dat) --- set LINKS := (GARY,DET) (GARY,LAN) (GARY,STL) (GARY,LAF) (CLEV,FRA) (CLEV,DET) (CLEV,LAN) (CLEV,WIN) (CLEV,STL) (CLEV,LAF) (PITT,FRA) (PITT,WIN) (PITT,STL) (PITT,FRE) ; set LINKS := GARY DET GARY LAN GARY STL GARY LAF CLEV FRA CLEV DET CLEV LAN CLEV WIN CLEV STL CLEV LAF PITT FRA PITT WIN PITT STL PITT FRE ;
40. 40 順序対集合：データ指定 (2) set LINKS := (GARY,*) DET LAN STL LAF (CLEV,*) FRA DET LAN WIN STL LAF (PITT,*) FRA WIN STL FRE ; set LINKS FRA DET LAN WIN STL FRE LAF := GARY - + + - + - + CLEV + + + + + - + PITT + - - + + + - ; set LINKS := (*,FRA) CLEV PITT (*,DET) GARY CLEV (*,LAN) GARY CLEV (*,WIN) CLEV PITT (*,LAF) GARY CLEV (*,FRE) PITT (*,STL) GARY CLEV PITT ;
41. 41  順序対によってインデックス付けされたパラメータの データの指定 順序対集合上のパラメータ # --- In model file (model.mod) --- param cost {LINKS} >= 0; # --- In data file (data.dat) --- param cost := GARY DET 14 GARY LAN 11 GARY STL 16 GARY LAF 8 CLEV FRA 27 CLEV DET 9 CLEV LAN 12 CLEV WIN 9 CLEV STL 26 CLEV LAF 17 PITT FRA 24 PITT WIN 13 PITT STL 28 PITT FRE 99 ; param cost := [GARY,*] DET 14 LAN 11 STL 16 LAF 8 [CLEV,*] FRA 27 DET 9 LAN 12 WIN 9 STL 26 LAF 17 [PITT,*] FRA 24 WIN 13 STL 28 FRE 99 ;
42. 42  集合演算  union：和集合  inter：積集合 (共通部分)  diff：差集合  symdiff：対称差集合 集合に関する演算 set A := 1 2 3; set B := 3 4 5; display A union B; # Displays {1, 2, 3, 4, 5} display A inter B; # Displays {3} display A diff B; # Displays {1, 2} display B diff A; # Displays {4, 5} display A symdiff B; # Displays {1, 2, 4, 5}
43. 43  パラメータの値を，他のパラメータや定数から計算に よって定めることができる  データファイルで値を上書きすることはできない パラメータ：計算パラメータ # --- In model file (model.mod) --- param unit_cost; param tax_rate default 0.05; param total_cost := unit_cost * (1 + tax_rate); # --- In data file (data.dat) --- param unit_cost := 12.0 ; param tax_rate := 0.10 ; # After loading data, total_cost will be calculated: # total_cost = 12.0 * (1 + 0.10) = 13.2
44. 44  宣言時にデフォルト値を指定できる（default）  同じデータ（値）を指定する手間の削減 パラメータ：デフォルト値 # --- In model file (model.mod) --- set PRODUCTS; param tax_rate {PRODUCTS} default 0.05; # Default tax rate is 5% # --- In data file (data.dat) --- param tax_rate := WidgetA 0.08 ; # WidgetA has 8% tax # WidgetB will use the default 5% tax rate
45. 45  インデックス付けやsum等の演算において， 対象とするインデックスを条件で絞ることができる  算術・論理演算  if-then-else, or, and, exists, forall, not, in, not in  <, <=, =, <>, >, >=  sum, prod, min, max  +, -, *, /, div, mod, ^ 条件付きインデックス set NUTREQ = {i in NUTR: i in MAXREQ or n_min[i] > 0}; #set NUTREQ = MAXREQ union {i in MINREQ: n_min[i] > 0}; subject to Balance {p in PROD, t in WEEKS: ord(t) > 1}: Make[p,t] + Inv[p,prev(t)] = Sell[p,t] + Inv[p,t];
46. 46  宣言時指定  within：集合が，別の集合の部分集合であることを明示  in：パラメータが，ある集合の要素であることを明示 データの整合性を保つのに役立つ データの整合性 # --- In model file (model.mod) --- set LOCATIONS; set ORIGINS within LOCATIONS; param ORIGIN symbolic in LOCATIONS; # --- In data file (data.dat) --- set LOCATIONS := London Paris Berlin ; set ORIGINS := London Tokyo ; # Error param ORIGIN := Tokyo; # Error
47. 47  データが満たすべき条件を記載（check） データ読み込み時にチェックが行われる データの妥当性チェック # --- In model file (model.mod) --- param supply {ORIG} >= 0; param demand {DEST} >= 0; check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j]; param S > 0; param prob {1..S} >= 0, <= 1; check: 0.99999 < sum {s in 1..S} prob[s] < 1.00001;
48. 48  変数の初期値を指定することができる  主に非線形最適化問題の初期解を与えるために使用される  モデルファイル または データファイル で指定 省略した場合はデフォルトの初期値（通常は0）が設定される 変数の初期値 # --- In model file (model.mod) --- var X >= 0, := 1.0; var Y {i in 1..5} := i; # Initial value of Y[i] is i
49. 49  reset;  現在設定されているモデルとデータを削除する  reset data;  現在設定されているデータのみを削除する  特定の要素のデータのみを削除することも可能  update data;  現在設定されているデータを上書き可能にする （削除はしない） モデル・データの削除・更新
50. 50  よく用いられるオプション  solver：使用するソルバー  presolve：ソルバーが前処理を行うか否か  times：CPU時間などの情報を表示するか否か  show_stats：問題の統計情報（変数，制約の数など）を 表示するか否か  display_width：displayコマンドの出力幅  ソルバー固有オプション： option cplex_options ‘mipgap=0.01 timelimit=300‘; など オプション設定
51. 51 AMPLモデリング ―応用編―
52. 52  線形最適化問題において，制約の右辺値や目的関数の係数が 少し変化したときの，最適値の変化量や，現在の最適基底が 維持される範囲などを分析すること  潜在価格 （constraint.dual）  制約を緩和することで最適値を改善できる（可能性がある） かどうかの判定に利用できる  被約費用（variable.rc）  被約費用が負（最小化問題の場合／最大化問題の場合は正）の 変数が存在する場合，最適値を改善できる（可能性がある）  列生成法において不可欠な情報 ※ 整数最適化問題においては，潜在価格や被約費用の直接的な 解釈は限定的 感度分析
53. 53  一連のAMPLコマンドをファイルにまとめて記載し， 自動実行することができる for, if-then-else, let コマンドなどが利用可能  定型モデルのデータ読み込み・求解・結果表示を自動化  パラメータを変えながら複数回の求解を実行  複雑なデータの前処理や後処理  条件に応じた求解プロセスの制御 例：列生成法の実行 主問題，列生成子問題を交互に解く  主問題の双対情報を列生成子問題のデータに反映  列生成子問題の最適解を主問題に反映（変数を追加） スクリプティング
54. 54  モデリングにおける多様な表現を実現 ソルバーが対応していない場合，適宜，自動的に再定式化 が行われる（一部）  条件演算子：if-then-else, ==>, <==, <==>  論理演算子：or, and, not, exists, forall  区分線形関数・演算子：<<breakpoints; slopes>>, abs, min, max  計数演算子：count, atmost, atleast, exactly, numberof  比較演算子：>, <, !=, alldiff  相補性演算子：complements  非線形演算子・関数：*, /, ^, exp, log, sin, cos, tan  離散領域：in MPライブラリ Fourer, Belov, Brandão, Advances in Model-Based Optimization with AMPL, ICCOPT2022.
55. 55 固定費用がある場合  線形定式化 例：ネットワークフロー var Flow {PRODUCTS,ARCS} >= 0; var Use {ARCS} binary; sum {(i,j) in ARCS} fix_cost[i,j] * Use[i,j]; subject to Capacity {(i,j) in ARCS}: sum {p in PRODUCTS} Flow[p,i,j] <= capacity[i,j] * Use[i,j];  より自然な定式化―バイナリ変数不要 sum {(i,j) in ARCS} if exists {p in PRODUCTS} Flow[p,i,j] > 0 then fix_cost[i,j]
56. 56 一定量に満たない量を流すことが許されない場合  線形定式化 例：ネットワークフロー sum {p in PRODUCTS} Flow[p,i,j] >= min_ship * Use[i,j]; sum {p in PRODUCTS} Flow[p,i,j] <= capacity[i,j] * Use[i,j]; sum {p in PRODUCTS} Flow[p,i,j] = 0 or min_ship <= sum {p in PRODUCTS} Flow[p,i,j] <= capacity[i,j]  より自然な定式化―バイナリ変数不要
57. 57 流量が正のアークの本数に制限がある場合  線形定式化 例：ネットワークフロー sum {(i,j) in ARCS} Use[i,j] <= max_arcs; atmost max_arcs {(i,j) in ARCS} (sum {p in PRODUCTS} Flow[p,i,j] > 0);  より自然な定式化―バイナリ変数不要
58. 58  if-then-else  ==>, <==, <==> 条件演算子 minimize TotalCost: sum {j in JOBS, k in MACHINES} if MachineForJob[j] = k then cost[j,k]; subject to Multi_Min_Ship {i in ORIG, j in DEST}: sum {p in PROD} Trans[i,j,p] >= 1 ==> minload <= sum {p in PROD} Trans[i,j,p] <= limit[i,j];
59. 59 論理演算子 subject to NoMachineConflicts {m1 in 1..nMach, m2 in m1+1..nMach, j in 1..nJobs}: Start[m1,j] + duration[m1,j] <= Start[m2,j] or Start[m2,j] + duration[m2,j] <= Start[m1,j]; subject to HostNever {j in BOATS}: isH[j] = 1 ==> forall {t in TIMES} H[j,t] = j;  or, and, not  exists, forall
60. 60 区分線形関数・演算子  <<breakpoint-list; slope-list>>  abs, min, max minimize Total_Cost: sum {i in ORIG, j in DEST} <<{p in 1..npiece[i,j]-1} limit[i,j,p]; {p in 1..npiece[i,j]} rate[i,j,p]>> Trans[i,j]; maximize WeightSum: sum {t in TRAJ} max {n in NODE} weight[t,n] * Use[n]; Trans[i,j] limit[i,j,1] limit[i,j,2] rate[i,j,1] rate[i,j,2] rate[i,j,3]
61. 61 計数演算子  count  atmost, atleast, exactly  numberof-in subject to Limit_Used: count {(i,j) in ARCS} (sum {p in PRODUCTS} Flow[p,i,j] > 0) <= max_arcs; subject to CapacityOfMachine {k in MACHINES}: numberof k in ({j in JOBS} MachineForJob[j]) <= cap[k];
62. 62 比較演算子  !=, >, <  alldiff subject to Different_Colors {(c1,c2) in Neighbors}: Color[c1] != Color[c2]; subject to OnePersonPerPosition: alldiff {i in 1..nPeople} Pos[i];
63. 63 相補性演算子  complements subject to Pri_Compl {i in PROD}: max(500.0, Price[i]) >= 0 complements sum {j in ACT} io[i,j] * Level[j] >= demand[i]; subject to Lev_Compl {j in ACT}: level_min[j] <= Level[j] <= level_max[j] complements cost[j] - sum {i in PROD} Price[i] * io[i,j];
64. 64 非線形演算子・関数  *, /, ^  exp, log, sin, cos, tan subject to Eq {i in J} : X[i+neq] / (b[i+neq] * sum {j in J} X[j+neq]/b[j+neq]) = c[i]*X[i] / (40*b[i] * sum {j in J} X[j]/b[j]); minimize Chichinadze: X[1]^2 - 12*X[1] + 11 + 10*cos(pi*X[1]/2) + 8*sin(pi*5*X[1]) - exp(-(X[2]-.5)^2/2)/sqrt(5);
65. 65 離散領域  var-in var Buy {f in FOODS} in {0,10,30,45,55}; var Ship {(i,j) in ARCS} in {0} union interval[min_ship,capacity[i,j]]; var Work {j in SCHEDS} integer in {0} union interval[least, max{i in SHIFT_LIST[j]} req[i]];
66. 66  ネットワークフロー問題の構造を効率的に記述できる （node, arc, net_in, net_out, from, to, obj）  最小費用流問題，最大流問題，輸送問題などを自然に表現できる  一部のソルバーは，ネットワーク構造を認識し，特殊なアルゴリズム によって最適解を高速に求めることができる ネットワークフロー set CITIES; set LINKS within (CITIES cross CITIES); param supply {CITIES} >= 0; param demand {CITIES} >= 0; param cost {LINKS} >= 0; param capacity {LINKS} >= 0; minimize Total_Cost; node Balance {k in CITIES}: net_in = demand[k] - supply[k]; arc Ship {(i,j) in LINKS} >= 0, <= capacity[i,j], from Balance[i], to Balance[j], obj Total_Cost cost[i,j];
67. 67  １つのAMPLモデル内で，複数の目的関数を定義できる  最適化対象とする目的関数の切り替えが容易  以下の２つのアプローチが可能（要オプション指定）  線形結合（重み付き和） 各目的関数に重み（.objweight）を設定  階層化（辞書式順序） 各目的関数に優先順位（.objpriority）を設定 多目的最適化 minimize total_cost {s in STORE}: sum {j in FOOD} cost[s,j] * Buy[j]; minimize total_number: sum {j in FOOD} Buy[j];
68. 68  amplpyパッケージ AMPLの機能をPythonから利用するための公式インタフェース  AMPLとのシームレスな連携  PythonからAMPLのモデルを直接構築・修正できる  ソルバー実行や結果取得をPython側からシームレスに行える  データ連携と後処理の容易さ  リストや辞書，Pandas DataFrameなど，Pythonの標準的な データを直接AMPLに渡せる  最適化結果や双対情報などをPython側に取り込み，NumPyや Pandasを用いて後処理や可視化を行うことが容易にできる  柔軟な制御  Python側で効率的かつ柔軟なワークフローを構築できる 例：複数シナリオ実行，パラメータスイープ，モデルやオプショ ン設定の動的変更など Pythonとの連携
69. 69 amplpy from amplpy import AMPL m = AMPL(env) m.read("diet.mod") m.set_data(data=food_df, set_name= "FOODS") m.set_data(nutr_df, "NUTRIENTS") m.param["amount"] = amt_df m.option["solver"] = "highs" m.solve() print("TotalCost=", m.get_value("TotalCost")) m.display("buy") import pandas as pd food_df = pd.DataFrame( [("BEEF", 3.59),("CHK", 2.59),("FISH", 2.29), ("HAM", 2.89),("MCH", 1.89),("MTL", 1.99), ("SPG", 1.99),("TUR", 2.49), ], columns=["FOODS", "cost"], ).set_index("FOODS")
70. 70 AMPL on Streamlit
71. 71  AMPL公式サイト（https://ampl.com/）  各種ドキュメント，ダウンロード，ブログ，例題など  AMPL: A Modeling Language for Mathematical Programming, by R. Fourer, D.M.Gay and B.W. Kernighan  AMPLのバイブル．詳細な解説と多数の例題  AMPL公式サイトからダウンロード可能  AMPL Discourse（https://discuss.ampl.com/）  質問したり，他のユーザーと議論したりする場 学習リソース