実務で役に立つ100超の最適化問題に対する、定式化とPython言語を用いた解決法を紹介する。

作者のページ

My HP

指針

  • 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。
  • 近似解法に対しては、近似誤差の指針を与える。
  • 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。
  • 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。
  • 解説ビデオもYoutubeで公開する.
  • 主要な問題に対してはアプリを作ってデモをする. 以下,デモビデオ:

注意

  • 基本的には,コードも公開するが, github自体はプライベート
  • そのうち本にするかもしれない(予約はしているが, 保証はない).
  • プロジェクトに参加したい人は,以下の技量が必要(github, nbdev, poetry, gurobi); ページはnbdevで自動生成している.

格言

・ 多項式時間の厳密解法にこだわるなかれ.言い換えればwell-solved special caseは役に立たない.

・ 最悪値解析にこだわるなかれ.最悪の場合のインスタンスというのは滅多に実務には現れない.そのようなインスタンスに対して,最適値の数倍という保証をもつ近似解法というのは,通常のインスタンスに対して良い解を算出するという訳ではない.我々の経験では,ほとんどの場合に役に立たない.

・ 確率的解析にこだわるなかれ.

・ ベンチマーク問題に対する結果だけを信じるなかれ.

・ 精度にこだわるなかれ.計算機内では,通常は,数値演算は有限の桁で行われていることを忘れてはいけない.

・ 手持ちの解法にこだわるのではなく,問題にあった解法を探せ.

動作環境

Poetry で以下を入れる.(他にも商用ソルバーGurobi, OptSeq, SCOPを利用)

[tool.poetry.dependencies]
python = "^3.8"
mypulp = "^0.0.11"
networkx = "^2.5"
matplotlib = "^3.3.3"
plotly = "^4.13.0"
numpy = "^1.19.4"
pandas = "^1.1.4"
requests = "^2.25.0"
seaborn = "^0.11.0"
streamlit = "^0.71.0"
scikit-learn = "^0.23.2"
statsmodels = "^0.12.1"
pydot = "^1.4.2"
Graphillion = "^1.4"
cspy = "^0.1.2"
ortools = "^8.2.8710"

[tool.poetry.dev-dependencies]
nbdev = "^1.1.5"
jupyterlab = "^2.2.9"

100+の最適化問題

data = """
線形最適化
(2次)錐最適化
整数最適化
- 栄養問題
- 混合問題(ロバスト最適化)
- 最短路問題
- 負の費用をもつ最短路問題
- 時刻依存最短路問題
- 資源制約付き最短路問題
- 第$k$最短路問題
- パスの列挙問題
- 最長路問題
- Hamilton閉路問題
- 多目的最短路問題
- 最小木問題
- 有向最小木問題
- 容量制約付き有向最小木問題
- Steiner木問題
- 賞金収集Steiner木問題
- 最大流問題
- 最小カット問題
- 多端末最大流問題
- 最小費用流問題
- 最小費用最大流問題
- 輸送問題
- 下限付き最小費用流問題
- 多品種流問題
- 多品種輸送問題
- 多品種ネットワーク設計問題
- サービスネットワーク設計問題(SENDO)
- 割当問題
- ボトルネック割当問題
- 一般化割当問題
- 2次割当問題
- 線形順序付け問題
- 極大マッチング問題
- 最大マッチング問題
- 安定マッチング問題
- 安定ルームメイト問題
- グラフ分割問題
- グラフ多分割問題
- 最大カット問題
- グラフ彩色問題
- 枝彩色問題
- 極大クリーク列挙問題
最大クリーク問題
最大安定集合問題
クリーク被覆問題
- 巡回セールスマン問題
- 賞金収集巡回セールスマン問題
- オリエンテーリング問題
- 階層型巡回セールスマン問題
- 時間枠付き巡回セールスマン問題
Euler閉路問題
中国郵便配達人問題
田舎の郵便配達人問題
容量制約付き枝巡回問題
容量制約付き配送計画問題
時間枠付き配送計画問題
トレーラー型配送計画問題(集合分割アプローチ)
巡回セールスマン型配送計画問題(ルート先・クラスター後法)
分割配送計画問題
運搬スケジューリング問題
空輸送最小化問題
積み込み積み降ろし型配送計画問題
複数デポ配送計画問題(METRO)
集合被覆問題
集合分割問題
集合パッキング問題
数分割問題
複数装置スケジューリング問題
ビンパッキング問題
カッティングストック問題
多次元ビンパッキング(長方形詰め込み)問題
オンラインビンパッキング問題
確率的ビンパッキング問題
0-1ナップサック問題
整数ナップサック問題
多制約ナップサック問題
Weber問題
複数施設Weber問題(MELOS-GF)
$k$-メディアン問題
容量制約付き施設配置問題
ハブ立地問題
容量制約なし$r$-割当$p$-ハブ・メディアン問題
ロジスティックスネットワーク設計問題(MELOS)
$k$-センター問題
被覆立地問題
経済発注量問題
多品目経済発注量問題
新聞売り子問題
安全在庫配置問題(MESSA)
複数エシェロン在庫最適化問題(MESSA)
動的ロットサイズ決定問題
多品目動的ロットサイズ決定問題
多段階多品目動的ロットサイズ決定問題(OptLot)
シフト最適化問題
業務割り当てを考慮したシフトスケジューリング問題(OptShift)
ポーフォリオ最適化問題
1機械リリース時刻付き重み付き完了時刻和最小化問題
1機械総納期遅れ最小化問題
順列フローショップ問題
資源制約付きスケジューリング問題(OptSeq)
ジョブショップスケジューリング問題
起動停止問題
$n$クイーン問題
重み付き制約充足問題(SCOP)
時間割決定問題
"""
L = data.split()
problem =[]
for i in L:
    if i=="-": continue
    try:
        float(i)
    except:
        problem.append(i)
for i,p in enumerate(problem):
    print(str(i+1)+".", p)
1. 線形最適化
2. (2次)錐最適化
3. 整数最適化
4. 栄養問題
5. 混合問題(ロバスト最適化)
6. 最短路問題
7. 負の費用をもつ最短路問題
8. 時刻依存最短路問題
9. 資源制約付き最短路問題
10. 第$k$最短路問題
11. パスの列挙問題
12. 最長路問題
13. Hamilton閉路問題
14. 多目的最短路問題
15. 最小木問題
16. 有向最小木問題
17. 容量制約付き有向最小木問題
18. Steiner木問題
19. 賞金収集Steiner木問題
20. 最大流問題
21. 最小カット問題
22. 多端末最大流問題
23. 最小費用流問題
24. 最小費用最大流問題
25. 輸送問題
26. 下限付き最小費用流問題
27. 多品種流問題
28. 多品種輸送問題
29. 多品種ネットワーク設計問題
30. サービスネットワーク設計問題(SENDO)
31. 割当問題
32. ボトルネック割当問題
33. 一般化割当問題
34. 2次割当問題
35. 線形順序付け問題
36. 極大マッチング問題
37. 最大マッチング問題
38. 安定マッチング問題
39. 安定ルームメイト問題
40. グラフ分割問題
41. グラフ多分割問題
42. 最大カット問題
43. グラフ彩色問題
44. 枝彩色問題
45. 極大クリーク列挙問題
46. 最大クリーク問題
47. 最大安定集合問題
48. クリーク被覆問題
49. 巡回セールスマン問題
50. 賞金収集巡回セールスマン問題
51. オリエンテーリング問題
52. 階層型巡回セールスマン問題
53. 時間枠付き巡回セールスマン問題
54. Euler閉路問題
55. 中国郵便配達人問題
56. 田舎の郵便配達人問題
57. 容量制約付き枝巡回問題
58. 容量制約付き配送計画問題
59. 時間枠付き配送計画問題
60. トレーラー型配送計画問題(集合分割アプローチ)
61. 巡回セールスマン型配送計画問題(ルート先・クラスター後法)
62. 分割配送計画問題
63. 運搬スケジューリング問題
64. 空輸送最小化問題
65. 積み込み積み降ろし型配送計画問題
66. 複数デポ配送計画問題(METRO)
67. 集合被覆問題
68. 集合分割問題
69. 集合パッキング問題
70. 数分割問題
71. 複数装置スケジューリング問題
72. ビンパッキング問題
73. カッティングストック問題
74. 多次元ビンパッキング(長方形詰め込み)問題
75. オンラインビンパッキング問題
76. 確率的ビンパッキング問題
77. 0-1ナップサック問題
78. 整数ナップサック問題
79. 多制約ナップサック問題
80. Weber問題
81. 複数施設Weber問題(MELOS-GF)
82. $k$-メディアン問題
83. 容量制約付き施設配置問題
84. ハブ立地問題
85. 容量制約なし$r$-割当$p$-ハブ・メディアン問題
86. ロジスティックスネットワーク設計問題(MELOS)
87. $k$-センター問題
88. 被覆立地問題
89. 経済発注量問題
90. 多品目経済発注量問題
91. 新聞売り子問題
92. 安全在庫配置問題(MESSA)
93. 複数エシェロン在庫最適化問題(MESSA)
94. 動的ロットサイズ決定問題
95. 多品目動的ロットサイズ決定問題
96. 多段階多品目動的ロットサイズ決定問題(OptLot)
97. シフト最適化問題
98. 業務割り当てを考慮したシフトスケジューリング問題(OptShift)
99. ポーフォリオ最適化問題
100. 1機械リリース時刻付き重み付き完了時刻和最小化問題
101. 1機械総納期遅れ最小化問題
102. 順列フローショップ問題
103. 資源制約付きスケジューリング問題(OptSeq)
104. ジョブショップスケジューリング問題
105. 起動停止問題
106. $n$クイーン問題
107. 重み付き制約充足問題(SCOP)
108. 時間割決定問題