組合せ最適化

• 初学者向けの組合せ最適化の学習用の導入課題です。

目的

• 数理最適化、特に組合せ最適化の基本や適用方法ついて習得する。

課題と進め方

事前の準備

1. はじめに

最適化（数理最適化）とは、応用数学に関する幅広い分野であり、問題に対する最適な解を求める方法です。

変数（二次関数の"X"や、商品の個数とか）が実数値の問題を連続最適化問題、 整数値のような離散的なものを組み合わせ最適化（離散最適化）問題と分類します。

例）

• 連続最適化問題：
  • 高校数学の二次関数の最小最大値を求める問題
  • 機械学習での最適化関数（SGD, Adamなど）
• 組み合わせ最適化（離散最適化問題）：
  • ナップザック問題、巡回セールスマン問題など

大学のオープンキャンパスでの最適化資料

1. 連続最適化

物理学のポテンシャルエネルギーの最小値（平衡状態）見つけたり、機械学習の損失関数の最適化などを扱います。とても数学的です。

3. 組み合わせ最適化

売り上げを最大にするには、材料の数ををどの組み合わせで用意すればいいかなど、現実に関連した問題が多いです。

オープンキャンパス資料

組み合わせ最適化　概要

アルゴリズム一覧

実施する課題

最適化の有名な問題をピックアップしました。

例題に目を通して解き方を理解してください。

そして例題で学んだことを元に、問題を解いてみてください。

コラム的な感じで参考も読んでみてください。

連続最適化

• 簡単な連続最適化
  • 例題(pulp)
  • 参考　4次関数の最小値(焼きなまし法)
  • 参考　円の最小値(粒子群最適化)

組み合わせ最適化

• 簡単な組み合わせ最適化（最小化問題）

  • 例題(貪欲法)

• ナップザック問題

  • 問題(動的計画法)
  • 問題　サイゼリアで1000円最大カロリー メニュー（参考　量子アニーリング）
  • 参考　少し複雑なナップザック(動的計画法)
  • 参考(線形計画)
  • 参考　paiza (動的計画法)

• 巡回セールスマン問題

  • 例題(ダイクストラ)
  • 問題　スタンプラリー
    • 各店舗間の距離データ(数が少ない)
  • 問題 デートコースを決める(pulpを使わずに解く)
  • 参考(局所探索2-opt、多スタート戦略)
  • 参考　paiza（ビームサーチ）（ダイクストラ）（貪欲法）

• スケジューリング問題

  • 例題　区間スケジューリング (貪欲法)
  • 問題　ナーススケジューリング （遺伝的アルゴリズム）(deapを使わずに解いても良い)
    • 参考　遺伝的アルゴリズムの簡単な例題
    • 参考 deapの使い方
  • 参考　ジョブショップ問題（遺伝的アルゴリズム）（イラスト、コード付きですが中国語なのでGoogle翻訳等使ってください）

• N Queen問題

  • 例題　8queen （遺伝的アルゴリズム）

• 4色問題（映画　「容疑者Xの献身」でも扱われた）

  • 例題　都道府県を塗る (pulp)(ortoolpyは使わなくても良い)
    • 参考 ortoolpyのちょっとした説明
  • 参考　グラフ的な考え方

• マッチング問題

  • 例題(グラフ理論)
  • 問題　写真の復元
    • 参考　小槻さんのコード(networkxのバージョンアップで関数max_weight_matching返り値の型が変わっている)
  • 参考　2部マッチング問題の解説

• 割り当て問題

  • 例題（ハンガリアン法）

• 最短路問題

  • 例題(ダイクストラ)

• 集合被覆問題

  • 例題　コミケ（貪欲法）

• 最大フロー問題

  • 例題(Ford-Fulkerson)

    (queueと言いながら，stackを使っており，説明とコードが食い違っている)

• 輸送問題

  • 参考　「python データ分析100本ノック50~70」 （ページ抜けが多い）

• 長方形詰め込み問題

  • 参考　paiza

• 網羅的な問題集

  • 参考　paiza リアルイベント

役に立ちそうなリンク集

最初の課題？

• https://www.yamagata-univ-derp.org/wp-content/uploads/2019/04/%E6%9C%80%E9%81%A9%E5%8C%96%E5%95%8F%E9%A1%8C%E3%82%92Python%E3%81%A7%E8%A7%A3%E6%B1%BA%E3%81%99%E3%82%8B%EF%BC%81-1.pdf　（※問題が書籍を参照しないと分からないものが多い）

組合せ最適化

• https://www.chuo-computer.co.jp/archives/11441

• https://www.slideshare.net/sady_nitro/ss-110421272

• http://research.nii.ac.jp/~uno/plan.htm

• http://research.nii.ac.jp/~uno/approx.htm

• http://research.nii.ac.jp/~uno/combi_3.htm

• https://www-or.amp.i.kyoto-u.ac.jp/files/open-campus-04.pdf

• http://www-or.amp.i.kyoto-u.ac.jp/files/%e9%9b%a2%e6%95%a3%e6%95%b0%e7%90%86%e5%88%86%e9%87%8e2016(%e5%b0%82%e6%94%bbHP).pdf (グラフ理論について)

• マッチング問題

• 貪欲法

• 動的計画法

• bit 演算

• しゃくとり法　(https://nashidos.hatenablog.com/entry/2020/02/02/165319)

• ダイクストラ

• A*

• ビームサーチ

• ベイズ的最適化

• 遺伝的アルゴリズム

• 局所探索 2-opt

• 焼きなまし法

• 粒子群最適化

• アントコロニー最適化

• 蜂コロニー最適化

• 量子アニーリング

• オンライン最適化

• 最新論文を交えたレビュー

最適化100本ノック的な課題？

• https://data-scientist.hatenadiary.jp/entry/2019/02/24/210100
• http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf
• https://qiita.com/shouta-dev/items/1970c2746c3c30f6b39e
• https://books.google.co.jp/books?id=rXzlDwAAQBAJ&pg=PA172&lpg=PA172&dq=python%E3%80%80%E6%9C%80%E9%81%A9%E5%8C%96+%E7%94%9F%E7%94%A3%E8%A8%88%E7%94%BB&source=bl&ots=BX4SreBxBu&sig=ACfU3U2CpDAfQFK18hjjfNVUbBf5NXujXg&hl=ja&sa=X&ved=2ahUKEwjltNSz8abqAhWbHXAKHRgYDMoQ6AEwCXoECAsQAQ#v=onepage&q=python%E3%80%80%E6%9C%80%E9%81%A9%E5%8C%96%20%E7%94%9F%E7%94%A3%E8%A8%88%E7%94%BB&f=false

書籍

• 数理最適化の実践ガイド（連続最適化について整理されています。ただしプログラミングのコードは載っていません）