披露宴の席次を Gromov-Wasserstein 最適輸送で決めた話
数理最適化 Advent Calendar 2022の9日目です。 新緑の頃、新型コロナ流行の合間をぬって、ささやかな結婚披露宴を表参道の式場にて催しました。諸々の準備の中でも席次はこだわるとキリがなく、数理最適化を使って決めました。人間関係をできるだけ保つようなゲスト集合から座席集合への写像を考えます。 ゲスト間人間関係を考慮して良い感じの配席を考えたい tl;dr 披露宴をしました 知り合い関係が複雑かつ長机でゲストの席配置が難しい 組合せ爆発は本物。高々20人の配置に1週間以上悩んだ結果、数理最適化した方が早いと結論 「知り合い同士を近くに配席する」問題は非凸な二次計画になり汎用ソルバでうまく解けない ゲストを席に"輸送"すると考えて最適輸送の一種で解くとうまくいった 本質的に非凸な問題を非凸のまま、しかし性質の良い距離構造を活用するアプローチが奏功したのではないか 再現用Colab
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Mathematical Optimization in 60 minutes
