本書は，筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである．本書は，Jupyter Laboで記述されたものを自動的に変換したものであり，以下のサポートページで公開している．コードも一部公開しているが，ソースコードを保管した Github 自体はプライベートである．本を購入した人は，サポートページで公開していないプログラムを
でダウンロードすることができる． ダウンロードしたファイルの解凍パスワードは<本に記述>である．
Pythonによる実務で役立つ最適化問題100+ (1)―グラフ理論と組合せ最適化への招待―
本書は，以下の格言に基づいて書かれている．
・ 多項式時間の厳密解法にこだわるなかれ．言い換えれば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=[]foriinL:ifi=="-":continuetry:float(i)except:problem.append(i)fori,pinenumerate(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. 多品種ネットワーク設計問題31. サービスネットワーク設計問題(SENDO)32. 割当問題33. ボトルネック割当問題34. 一般化割当問題35. 2次割当問題36. 線形順序付け問題37. 極大マッチング問題38. 最大マッチング問題39. 安定マッチング問題40. 安定ルームメイト問題41. グラフ分割問題42. グラフ多分割問題43. 最大カット問題44. グラフ彩色問題45. 枝彩色問題46. 極大クリーク列挙問題47. 最大クリーク問題48. 最大安定集合問題49. クリーク被覆問題50. 巡回セールスマン問題51. 賞金収集巡回セールスマン問題52. オリエンテーリング問題53. 階層型巡回セールスマン問題54. 時間枠付き巡回セールスマン問題55. Euler閉路問題56. 中国郵便配達人問題57. 田舎の郵便配達人問題58. 容量制約付き枝巡回問題59. 容量制約付き配送計画問題60. 時間枠付き配送計画問題61. トレーラー型配送計画問題（集合分割アプローチ）62. 巡回セールスマン型配送計画問題（ルート先・クラスター後法）63. 分割配送計画問題64. 運搬スケジューリング問題65. 空輸送最小化問題66. 積み込み積み降ろし型配送計画問題67. 複数デポ配送計画問題(METRO)68. 集合被覆問題69. 集合分割問題70. 集合パッキング問題71. 数分割問題72. 複数装置スケジューリング問題73. ビンパッキング問題74. カッティングストック問題75. d次元ベクトルビンパッキング問題76. 変動サイズベクトルパッキング問題77. 多次元ビンパッキング（長方形詰め込み）問題78. オンラインビンパッキング問題79. 確率的ビンパッキング問題80. 0-1ナップサック問題81. 整数ナップサック問題82. 多制約ナップサック問題83. Weber問題84. 複数施設Weber問題(MELOS-GF)85. $k$-メディアン問題86. 容量制約付き施設配置問題87. 非線形施設配置問題88. p-ハブ・メディアン問題89. $r$-割当$p$-ハブ・メディアン問題90. ロジスティックス・ネットワーク設計問題(MELOS)91. $k$-センター問題92. 被覆立地問題93. 経済発注量問題94. 複数品目経済発注量問題95. 新聞売り子問題96. 途絶を考慮した新聞売り子問題97. 安全在庫配置問題(MESSA)98. 複数エシェロン在庫最適化問題(MESSA)99. 適応型在庫最適化問題100. 動的ロットサイズ決定問題101. 多品目動的ロットサイズ決定問題102. 多段階多品目動的ロットサイズ決定問題(OptLot)103. シフト最適化問題104. 看護婦スケジューリング問題105. 業務割り当てを考慮したシフトスケジューリング問題(OptShift)106. ポーフォリオ最適化問題107. 1機械リリース時刻付き重み付き完了時刻和最小化問題108. 1機械総納期遅れ最小化問題109. 順列フローショップ問題110. 資源制約付きスケジューリング問題(OptSeq)111. ジョブショップスケジューリング問題112. 起動停止問題113. $n$クイーン問題114. 重み付き制約充足問題(SCOP)115. 時間割決定問題