最適化問題入門　錐最適化・整数最適化・ネットワークモデルの組合せによる

関連サイト

本書の関連ページが用意されています。

• 最適化問題入門（近代科学社ウェブサイト）

内容紹介

様々な問題をPythonで解くことを目指す「Pythonによる問題解決シリーズ」第2弾。最適化問題に焦点を当てる本書では、解き方が分かっている典型的な最適化問題（ナップサック問題や巡回セールスマン問題など）を組み合わせ、Pythonパッケージを用いるプログラミングに落とし込んで解へと導く。

パッケージとしてPyomoやPICOSなどを使い、また、Pythonで最適化問題を解くためのモデリング言語としてPuLPを使う。本書では、それらのツールの使い方はもちろん、解法プログラムについても丁寧に解説する。

書誌情報

• 著者: 小林 和博
• 発行日: 2020-06-27 (紙書籍版発行日: 2020-06-27)
• 最終更新日: 2020-06-27
• バージョン: 1.0.0
• ページ数: 233ページ(PDF版換算)
• 対応フォーマット: PDF, EPUB
• 出版社: 近代科学社

対象読者

Python,OR,最適化問題,NetworkX,PICOS,PuLP,Pyomo,線形最適化問題,錐線形最適化問題,混合整数最適化問題,集合分割問題,ナップサック問題,ネットワーク最適化問題,巡回セールスマン問題,配送計画問題,半正定値最適化問題,混合整数線形最適化問題,制約付き最短路問題に興味がある人

著者について

小林 和博

1998年 東京大学工学部計数工学科卒業
2000年 東京大学大学院工学系研究科計数工学専攻修士課程修了，修士（工学）
2009年 博士（理学）
現在 青山学院大学理工学部准教授

主要著書: 『サプライチェーンリスク管理と人道支援ロジスティクス』（共著），近代科学社(2015)、『航海応用力学の基礎』（共著），成山堂書店(2015)、『Python 言語によるビジネスアナリティクス|実務家のための最適化・統計解析・機械学習』（共著），近代科学社(2016)

目次

はじめに

目次

第1章 Pythonで最適化を行うための環境構築

• 1.1 Pythonのインストール
• 1.2 パッケージのインストール
• 1.3 実行環境

第2章 数理最適化問題の分類方法

• 2.1 数式のかたちによる分類
• 2.1.1 線形最適化問題
• 2.1.2 錐線形最適化問題
• 2.1.3 混合整数最適化問題
• 2.2 解こうとする対象による分類
• 2.2.1 集合分割問題
• 2.2.2 ナップサック問題
• 2.2.3 ネットワーク最適化問題
• 2.2.4 巡回セールスマン問題
• 2.2.5 配送計画問題

第3章 Pythonパッケージによる数理最適化問題のモデリング

• 3.1 線形最適化問題
• 3.1.1 様々なモデリングインターフェイス
• 3.1.2 PuLPの使い方
• 3.1.3 Pyomoの使い方
• 3.2 錐線形最適化問題
• PICOSの使い方
• 3.3 ネットワーク最適化問題
• NetworkXの使い方
• 3.4 混合整数最適化問題
• PICOSの使い方

第4章 数式のかたちで分けられる最適化問題

• 4.1 線形最適化問題の解き方
• 4.1.1 栄養問題
• 4.1.2 列生成および切除平面
• 4.2 二次錐最適化問題の解き方
• 4.2.1 回転つき二次錐制約
• 4.2.2 ロバスト線形最適化問題
• 4.3 半正定値最適化問題の解き方
• 4.3.1 最大カット問題に対する緩和
• 4.3.2 多項式最適化
• 4.4 混合整数最適化問題の解き方
• 4.4.1 緩和問題と凸包
• 4.4.2 施設配置問題
• 4.4.3 Perspectiveを用いた定式化

第5章 解こうとする対象による分類

• 5.1 集合分割問題の解き方
• 5.1.1 0-1整数線形最適化問題としての定式化
• 5.1.2 PuLPによるモデル化
• 5.2 ナップサック問題の解き方
• 5.2.1 0-1整数線形最適化問題としての定式化
• 5.2.2 分枝限定法
• 5.2.3 動的計画法
• 5.3 ネットワーク最適化問題の解き方
• 5.3.1 最短路問題の解き方
• 5.3.2 最大流問題の解き方
• 5.3.3 時間枠付き最短路問題の解き方
• 5.3.4 OpenStreetMapによる道路データの利用
• 5.4 巡回セールスマン問題の解き方
• 5.4.1 0-1整数線形最適化問題としての定式化
• 5.4.2 PuLPとNetworkXによるモデル化
• 5.5 配送計画問題の解き方
• 5.5.1 集合分割問題としての定式化
• 5.5.2 PuLPによる列生成法の実装

参考文献

索引

著者紹介