実務で役に立つ100+の最適化問題に対する定式化とPython言語を用いた解決法を紹介する。
格言
本書は，以下の格言に基づいて書かれている．
・ 多項式時間の厳密解法にこだわるなかれ．言い換えればwell-solved special caseは，ほとんど役に立たない．
・ 最悪値解析にこだわるなかれ．最悪の場合の問題例（インスタンス; instance）というのは滅多に実務には現れない．そのような問題例に対して， 最適値の数倍という保証をもつ近似解法というのは，通常の問題例に対して良い解を算出するという訳ではない．我々の経験では，ほとんどの場合に役に立たない．
・ 確率的解析にこだわるなかれ．上と同様の理由による．実際問題はランダムに生成されたものではないのだ．
・ ベンチマーク問題に対する結果だけを信じるなかれ．特定のベンチマーク問題例に特化した解法というのは，往々にして実際問題では役に立たない．
・ 精度にこだわるなかれ．計算機内では，通常は，数値演算は有限の桁で行われていることを忘れてはいけない．
・ 手持ちの解法にこだわるのではなく，問題にあった解法を探せ．世の中に万能薬はないし，特定の計算機環境でないと動かない手法は往々にして役に立たない．
動作環境
poetryもしくはpipで以下のパッケージを入れる． 他にも商用ソルバーGurobi, OptSeq, SCOPなどを利用している．これらについては，付録1で解説する．
python = ">=3.8,<3.10"
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"
cvxpy = "^1.1.12"
Riskfolio-Lib = "^3.3"
yfinance = "^0.1.59"
gurobipy = "^9.1.1"
numba = "^0.53.1"
grblogtools = "^0.3.1"
PySCIPOpt = "^3.3.0"
HeapDict = "^1.0.1"
scipy = "1.7.0"
intvalpy = "^1.5.8"
lkh = "^1.1.0"data = """
線形最適化
(2次)錐最適化
整数最適化
- 栄養問題
- 混合問題（ロバスト最適化）
- 最短路問題
- 負の費用をもつ最短路問題
- 時刻依存最短路問題
- 資源制約付き最短路問題
- 第$k$最短路問題
- パスの列挙問題
- 最長路問題
- Hamilton閉路問題
- 多目的最短路問題
- 最小木問題
- 有向最小木問題
- 容量制約付き有向最小木問題
- Steiner木問題
- 賞金収集Steiner木問題
- 最大流問題
- 最小カット問題
- 多端末最大流問題
- 最小費用流問題
- 最小費用最大流問題
- 輸送問題
- 下限付き最小費用流問題
- フロー分解問題
- 多品種流問題
- 多品種輸送問題
- 多品種ネットワーク設計問題
- サービスネットワーク設計問題(SENDO)
- 割当問題
- ボトルネック割当問題
- 一般化割当問題
- 2次割当問題
- 線形順序付け問題
- 極大マッチング問題
- 最大マッチング問題
- 安定マッチング問題
- 安定ルームメイト問題
- グラフ分割問題
- グラフ多分割問題
- 最大カット問題
- グラフ彩色問題
- 枝彩色問題
- 極大クリーク列挙問題
最大クリーク問題
最大安定集合問題
クリーク被覆問題
- 巡回セールスマン問題
- 賞金収集巡回セールスマン問題
- オリエンテーリング問題
- 階層型巡回セールスマン問題
- 時間枠付き巡回セールスマン問題
Euler閉路問題
中国郵便配達人問題
田舎の郵便配達人問題
容量制約付き枝巡回問題
容量制約付き配送計画問題
時間枠付き配送計画問題
トレーラー型配送計画問題（集合分割アプローチ）
巡回セールスマン型配送計画問題（ルート先・クラスター後法）
分割配送計画問題
運搬スケジューリング問題
空輸送最小化問題
積み込み積み降ろし型配送計画問題
複数デポ配送計画問題(METRO)
集合被覆問題
集合分割問題
集合パッキング問題
数分割問題
複数装置スケジューリング問題
ビンパッキング問題
カッティングストック問題
d次元ベクトルビンパッキング問題
変動サイズベクトルパッキング問題
多次元ビンパッキング（長方形詰め込み）問題
オンラインビンパッキング問題
確率的ビンパッキング問題
0-1ナップサック問題
整数ナップサック問題
多制約ナップサック問題
Weber問題
複数施設Weber問題(MELOS-GF)
$k$-メディアン問題
容量制約付き施設配置問題
非線形施設配置問題
p-ハブ・メディアン問題
$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)