数理最適化: Optimization Night #4に参加しました

「数理最適化: Optimization Night #4」に参加したので(オンライン)、まとめました。
間違っている箇所がある場合、指摘いただけると助かります。

目次

どんなイベント？

数理最適化に興味のある人達であつまって、わいわいがやがや議論する会です！

今回は、NTTデータ数理システムの大槻さんをお招きして、「動的計画法を活用した問題解決の概観」についてお話いただきます。 前回同様、後半の議論セッションで、お話いただいた内容をベースにみんなで議論できたらと思います。

optimization.connpass.com

発表

以下の2件の発表がありました 議論・Q&Aに関しては割愛します

動的計画法を活用した問題解決の概観

導入

数理最適化:与えられた制約条件下で目的関数の値を最適にする解を求める

• アプローチの方法
  • 数理計画ソルバーの活用
    • 線形計画問題、整数計画問題への定式化
  • 山登り法、メタヒューリティクス
    • NP困難な問題への汎用的なアプローチ
    • 最適解を求めるのが難しい問題に対してもまず解を求めて改善を繰り返していく
  • 様々なアルゴリズム
    • 貪欲法
    • 動的計画法:実務で使う機会多かった
    • 最短路アルゴリズム等
• 数理最適化の精神
  • モデリング+理論+アルゴリズム
    • 発表で言及があった資料
  • 様々な問題がモデリングを通して統一的に扱える

動的計画法

• 動的計画法とは

  • 問題を一連の部分問題に分割し、各部分問題の解をメモ化しながら順に求める手法
  • 数多くの問題を分野横断的に解決できる

• 動的計画法による解法

  • 問題を一連の部分問題に分割
  • メモ化しながら、各部分問題の解を順に求める
  • 汎用的で多くのパターンがある

• 着目する点:動的計画法の遷移パターン

  • 漸化式と考えられ、その遷移パターンに着目すると、典型的なパターンをいくつか抽出できる

代表的な遷移パターン例

• ナップサック問題
  • 解き方:全アイテムN個についていきなり考える訳ではなく、最初のi個のみを部分問題として考える(この際に重さも変数として加える)
  • N個の要素をシーケンシャルに処理するDPとなる
    • 似ている例:
      • 隠れマルコフモデル(潜在変数が上記重さに該当)等
• 編集距離
  • 文字列Sに変更・削除・挿入の操作を繰り返す事で対象の文字列Tに変換→その最小回数
  • 2次元DPという観点だとナップサック問題と同じように見えるが、遷移図として表すと大きく異なる
  • 二系列データの類似度を考える問題全般に適用される
    • diffコマンド
    • スペルチェッカー
    • 音声、画像、空間認識(DPマッチング)
    • バイオインフォマティクス(系列アラインメント:例2つのDNA配列の類似度)
• 区間分割
  • 系列データをいくつかの空間に分ける。その分割の仕方を最適化したい
  • (1つのノードを更新する時に過去の履歴を寄せ集める事が多いため)計算量は大きくなりがち→様々な高速化手法がある
  • 例
    • 分かち書き
    • 発電計画問題:発電on・offのタイミングを最適化。制約が需要供給バランスの考慮や連続時間稼働という事もあり各区間のコスト関数が複雑になる
    • タイムスケジューリング(配送計画):休憩が必要な制約あり
    • タイル合わせ

まとめ

• 動的計画法で解決できる問題のほとんどが共通の遷移パターンで扱える
• 共通の問題構造に着目することで明快に解ける
• 共通の理論と問題に特有の事情に分離することで、見通しの良い問題解決が出来る

ローカル線全駅下車の最適化

ローカル線の旅の難点:全駅下車して回ろうとすると時間がかかる→効率的に回る方法はないものか？

問題整理

• 目的
  • 特定の路線の全駅を訪問
  • 最初の出発駅・時刻を固定したうえで最終駅到着時刻を最も早くする
• 制約
  • 最終的に出発駅に戻る
  • 各駅で最低D分滞在
• 特別な制約の巡回セールスマン問題

解法

• 2ステップ
  • 列車データを使いやすい形に変換
    • 各駅のペアについて出発時刻をずらしつつ乗り換え検索を走らせる
  • Bit DP

結果

• 人口データと実際のデータで検証
  • 無駄な動きがあるので抑えたい
  • 1日で回りきるのが不可能な場合の考慮も行いたい