実務で役に立つ100超の最適化問題に対する定式化とPython言語を用いた解決法を紹介する。
格言
・ 多項式時間の厳密解法にこだわるなかれ．言い換えれば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"data = """
線形最適化
(2次)錐最適化
整数最適化
- 栄養問題
- 混合問題（ロバスト最適化）
- 最短路問題
- 負の費用をもつ最短路問題
- 時刻依存最短路問題
- 資源制約付き最短路問題
- 第$k$最短路問題
- パスの列挙問題
- 最長路問題
- Hamilton閉路問題
- 多目的最短路問題
- 最小木問題
- 有向最小木問題
- 容量制約付き有向最小木問題
- Steiner木問題
- 賞金収集Steiner木問題
- 最大流問題
- 最小カット問題
- 多端末最大流問題
- 最小費用流問題
- 最小費用最大流問題
- 輸送問題
- 下限付き最小費用流問題
- フロー分解問題
- 多品種流問題
- 多品種輸送問題
- 多品種ネットワーク設計問題
- サービスネットワーク設計問題(SENDO)
- 割当問題
- ボトルネック割当問題
- 一般化割当問題
- 2次割当問題
- 線形順序付け問題
- 極大マッチング問題
- 最大マッチング問題
- 安定マッチング問題
- 安定ルームメイト問題
- グラフ分割問題
- グラフ多分割問題
- 最大カット問題
- グラフ彩色問題
- 枝彩色問題
- 極大クリーク列挙問題
最大クリーク問題
最大安定集合問題
クリーク被覆問題
- 巡回セールスマン問題
- 賞金収集巡回セールスマン問題
- オリエンテーリング問題
- 階層型巡回セールスマン問題
- 時間枠付き巡回セールスマン問題
Euler閉路問題
中国郵便配達人問題
田舎の郵便配達人問題
容量制約付き枝巡回問題
容量制約付き配送計画問題
時間枠付き配送計画問題
トレーラー型配送計画問題（集合分割アプローチ）
巡回セールスマン型配送計画問題（ルート先・クラスター後法）
分割配送計画問題
運搬スケジューリング問題
空輸送最小化問題
積み込み積み降ろし型配送計画問題
複数デポ配送計画問題(METRO)
集合被覆問題
集合分割問題
集合パッキング問題
数分割問題
複数装置スケジューリング問題
ビンパッキング問題
カッティングストック問題
d次元ベクトルビンパッキング問題
変動サイズベクトルパッキング問題
多次元ビンパッキング（長方形詰め込み）問題
オンラインビンパッキング問題
確率的ビンパッキング問題
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)