Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待―

久保 幹雄(著)

久保 幹雄(著)

定価 3,300 円(本体 3,000 円+税)

A5判/224ページ
刊行日:2022年12月01日
ISBN:978-4-254-12273-2 C3004

ネット書店で購入する amazon e-hon 紀伊國屋書店 honto Honya Club Rakutenブックス くまざわ書店

書店の店頭在庫を確認する 紀伊國屋書店

内容紹介

Jupyter上で100強の最適化手法を実践。例題をとくことで,知識を使える技術へ。基礎的な問題からはじめ,ネットワーク,組合せ最適化など実用上重要なさまざまな手法を広くとりあげる。関連する解説動画も公開中。

編集部から

目次

1. 最適化問題
 1. 1 準備
 1. 2 最適化問題とは
 1. 3 最適化問題の分類
  1. 3. 1 連続か離散か
  1. 3. 2 線形か非線形か
  1. 3. 3 凸か非凸か
  1. 3. 4 大域的最適解か局所的最適解か
  1. 3. 5 不確実性の有無
  1. 3. 6 ネットワーク構造をもつか否か
 1. 4 線形最適化問題
 1. 5 錐最適化問題
 1. 6 整数最適化問題
 1. 7 ロバスト最適化
 1. 8 栄養問題
  1. 8. 1 実行不可能性の対処法(制約の逸脱を許すモデル化)
  1. 8. 2 逸脱最小化
  1. 8. 3 既約不整合部分系
 1. 9 混合問題
2. 最短路問題
 2. 1 準備
 2. 2 最短路問題
  2. 2. 1 (1 対1 の)最短路問題
  2. 2. 2 1 対全の最短路問題
  2. 2. 3 枝の費用が負のものがある場合
  2. 2. 4 全対全の最短路
 2. 3 道路ネットワークの最短路と前処理による高速化
 2. 4 ベンチマーク問題例の読み込みとDial 法
  2. 4. 1 最短路ヒープの比較
 2. 5 時刻依存の移動時間をもつ最短路問題
  2. 5. 1 区間,速度,距離から到着時刻関数を生成する関数arrival_func
  2. 5. 2 到着時刻関数arrival
  2. 5. 3 区分的線形な到着時刻関数をプロットする関数plot_arrival
 2. 6 資源制約付き最短路問題
3. 最短路の列挙
 3. 1 準備
 3. 2 第k 最短路
 3. 3 無向パス(閉路,森など)の列挙
  3. 3. 1 (最短)パスの列挙
  3. 3. 2 最長パスの列挙(最長路問題)
  3. 3. 3 閉路の列挙
  3. 3. 4 Hamilton 閉路の列挙
 3. 4 多目的最短路問題
4. 最小木問題
 4. 1 準備
 4. 2 最小木問題
  4. 2. 1 最小木問題
 4. 3 最小木問題の定式化
  4. 3. 1 閉路除去定式化
  4. 3. 2 カットセット定式化
  4. 3. 3 単品種流定式化
  4. 3. 4 多品種流定式化
 4. 4 networkX の利用
  4. 4. 1 ランダムに枝長を設定した格子グラフ
 4. 5 クラスター間の最短距離を最大にするk 分割問題
 4. 6 有向最小木
  4. 6. 1 最小有向木問題
5. 容量制約付き有向最小木問題
 5. 1 準備
 5. 2 容量制約付き有向最小木問題
  5. 2. 1 定式化
  5. 2. 2 データの読み込み
6. Steiner 木問題
 6. 1 準備
 6. 2 Steiner 木問題に対する定式化
 6. 3 Steiner 木問題に対する近似解法
 6. 4 賞金収集有向Steiner 木問題
7. 最小費用流問題
 7. 1 準備
 7. 2 最小費用流問題
  7. 2. 1 最小費用流問題
 7. 3 最小費用最大流問題
 7. 4 輸送問題
 7. 5 下限制約付き最小費用流問題
 7. 6 フロー分解問題
8. 最大流問題
 8. 1 準備
 8. 2 最大流問題
  8. 2. 1 最大流問題
 8. 3 最小カット問題
 8. 4 多端末最大流問題
9. 多品種流問題
 9. 1 準備
 9. 2 多品種流問題
  9. 2. 1 多品種流問題
 9. 3 多品種輸送問題
 9. 4 多品種ネットワーク設計問題
 9. 5 サービス・ネットワーク設計問題
10. グラフ分割問題
 10. 1 準備
 10. 2 グラフ2 分割問題
  10. 2. 1 タブーサーチ
  10. 2. 2 アニーリング法
  10. 2. 3 集中化と多様化を入れたタブーサーチ
 10. 3 グラフ多分割問題
 10. 4 最大カット問題
  10. 4. 1 線形定式化
  10. 4. 2 2 次錐最適化による定式化
  10. 4. 3 制約最適化ソルバーSCOP による求解
11. 最大クリーク問題
 11. 1 準備
 11. 2 最大クリーク問題と最大安定集合問題
  11. 2. 1 極大クリークの列挙
  11. 2. 2 近似解法
  11. 2. 3 タブーサーチ
  11. 2. 4 集中化・多様化を入れたタブーサーチ
  11. 2. 5 平坦探索法
 11. 3 クリーク被覆問題
12. グラフ彩色問題
 12. 1 準備
 12. 2 定式化
  12. 2. 1 標準定式化
  12. 2. 2 彩色数固定定式化
  12. 2. 3 半順序定式化
  12. 2. 4 代表点定式化
  12. 2. 5 制約最適化ソルバーによる求解
 12. 3 構築法
 12. 4 メタヒューリスティクス
  12. 4. 1 タブーサーチ
  12. 4. 2 遺伝的アルゴリズムとタブーサーチの融合法
 12. 5 枝彩色問題
A. 付録1: 商用ソルバー
 A. 1 商用ソルバー
 A. 2 Gurobi
 A. 3 SCOP
  A. 3. 1 SCOP モジュールの基本クラス
 A. 4 OptSeq
  A. 4. 1 OptSeq モジュールの基本クラス
 A. 5 METRO
 A. 6 MELOS
 A. 7 MESSA
 A. 8 OptLot
 A. 9 OptShift
 A. 10 OptCover
 A. 11 OptGAP
 A. 12 OptPack
 A. 13 CONCORDE
 A. 14 LKH
B. 付録2: グラフに対する基本操作
 B. 1 本章で使用するパッケージ
 B. 2 グラフの基礎
 B. 3 ランダムグラフの生成
 B. 4 グラフをnetworkX に変換する関数
 B. 5 networkX のグラフをPlotly の図に変換する関数
 B. 6 ユーティリティー関数群
索  引

執筆者紹介

関連情報

ジャンル一覧

ジャンル一覧

  • Facebook
  • Twitter
  • 「愛読者の声」 ご投稿はこちら 「愛読者の声」 ご投稿はこちら
  • EBSCO eBooks
  • eBook Library