数理最適化 Advent Calendar 2022の9日目です。 新緑の頃、新型コロナ流行の合間をぬって、ささやかな結婚披露宴を表参道の式場にて催しました。諸々の準備の中でも席次はこだわるとキリがなく、数理最適化を使って決めました。人間関係をできるだけ保つようなゲスト集合から座席集合への写像を考えます。 ゲスト間人間関係を考慮して良い感じの配席を考えたい tl;dr 披露宴をしました 知り合い関係が複雑かつ長机でゲストの席配置が難しい 組合せ爆発は本物。高々20人の配置に1週間以上悩んだ結果、数理最適化した方が早いと結論 「知り合い同士を近くに配席する」問題は非凸な二次計画になり汎用ソルバでうまく解けない ゲストを席に"輸送"すると考えて最適輸送の一種で解くとうまくいった 本質的に非凸な問題を非凸のまま、しかし性質の良い距離構造を活用するアプローチが奏功したのではないか 再現用Colab
![披露宴の席次を Gromov-Wasserstein 最適輸送で決めた話](https://cdn-ak-scissors.b.st-hatena.com/image/square/7dc92410643f3c47963903de405500d0524795f2/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--VHP0e-ZP--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3A%2525E6%25258A%2525AB%2525E9%25259C%2525B2%2525E5%2525AE%2525B4%2525E3%252581%2525AE%2525E5%2525B8%2525AD%2525E6%2525AC%2525A1%2525E3%252582%252592%252520Gromov-Wasserstein%252520%2525E6%25259C%252580%2525E9%252581%2525A9%2525E8%2525BC%2525B8%2525E9%252580%252581%2525E3%252581%2525A7%2525E6%2525B1%2525BA%2525E3%252582%252581%2525E3%252581%25259F%2525E8%2525A9%2525B1%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3AAkira%252520Tanimoto%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyL2JiNWY5M2YzNGUuanBlZw%3D%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)