披露宴の席次を Gromov-Wasserstein 最適輸送で決めた話

数理最適化 Advent Calendar 2022の9日目です。 新緑の頃、新型コロナ流行の合間をぬって、ささやかな結婚披露宴を表参道の式場にて催しました。諸々の準備の中でも席次はこだわるとキリがなく、数理最適化を使って決めました。人間関係をできるだけ保つようなゲスト集合から座席集合への写像を考えます。 ゲスト間人間関係を考慮して良い感じの配席を考えたい tl;dr 披露宴をしました 知り合い関係が複雑かつ長机でゲストの席配置が難しい 組合せ爆発は本物。高々20人の配置に1週間以上悩んだ結果、数理最適化した方が早いと結論 「知り合い同士を近くに配席する」問題は非凸な二次計画になり汎用ソルバでうまく解けない ゲストを席に"輸送"すると考えて最適輸送の一種で解くとうまくいった 本質的に非凸な問題を非凸のまま、しかし性質の良い距離構造を活用するアプローチが奏功したのではないか 再現用Colab

[TakamoriTarou]

同じ数理最適化を扱うのに、披露宴を表参道のおされなRestaurantで開き、恐らくそれをネタにして笑いが取れる環境にいる著者と、小生。いったいどこで差が出たのだろうか。たぶん前世かなあ…。ぢっと手を見る。幸あれ

[anmin7]

こういうのを賢い人たちばかりが使うんでなく一般的な問題解決に適用できるようになってほしいねぇ。学問をやるのも身分がモノを言う世の中だから難しいかねぇ。

[ssids]

こういう集まりでありがちな「あの人とあの人は絶対に近くに配置しちゃダメ」は知り合い度を負の値にするときっちりと対角線上に行くのだろうか / 言われてみればただのラグランジュ緩和だなこれ

[havanap]

数理最適化で「あの人とあの人は絶対に近くに配置しちゃダメ」は一般的にはペナルティ項で与えるはず（このソルバ&方式でできるのかはしらない）

[houyhnhm]

何というか、ネタならいいけど、安心の為に数式使ってるイメージ。で、実際にはデータ不足の為の失敗とかが諸々発生しているが気付いてないとかありそうで。

[marmot1123]

“その費用でもう1回披露宴ができてしまう”草。

[casm]

「ゲストを席に"輸送"すると考えて最適輸送の一種で解くとうまくいった」

[agricola]

組合せ最適化ならNECのベクトルエンジンを使用してシミュレーテッドアニーリングしてほしかった（無茶を言うな）。

[knok]

「Gurobiのような商用ソルバーを使うともしかするとうまくいくのかもしれないが、その費用でもう1回披露宴ができてしまう」これすき

[hesopenn]

許されるか調べてないけど、AMPL / GAMSでコード書いてNEOS serverに突っ込めば、Gurobiとかも使える。Courseraで離散最適化の素晴らしい授業があるのでそれもおススメ。https://jp.coursera.org/learn/discrete-optimization

[yhara]

“高々20人の配置に1週間以上悩んだ結果、数理最適化した方が早いと結論”

[Windfola]

「まとめ」が本題かな。ふんわりとした「この並びだめだなあ」的な引っ掛かりが無意識の制約になるというのはわかる気がする

[narukami]

長机はなー

[jerryb]

最初の図の「友人（ロボ）」で、ロボットまで動員したのかと（違）　商用ソルバーを使うと「その費用でもう1回披露宴ができてしまう」からと自分で工夫して解くのすごい。

[didididigda]

ゲスト間に新たな交流が生まれるといいなと考え →この結果を知りたい！n=1でもいいから知りたい！

[kou-qana]

あー、上下関係じゃなくて、仲良しを近くにって方向なのね。

[mohri]

結婚式場に「席次配置オプション」とかあったりするのかな？ そういうビジネスに使えたりするとおもしろい

[napsucks]

セントグレースやらアニヴェルセルやらルアンジェやらいっぱいあるのよねあの辺。なんでなんだろ。

[Windymelt]

良すぎる > “「知り合い同士を近くに配席する」問題は非凸な二次計画になり汎用ソルバでうまく解けない”

[maketexlsr]

これはいいね、社会実装どんどんしていくの好き。“最適化したので、という言い訳が最終的にはできるので、思い切って全体最適を追求しやすい” そうだよね笑 / 人力派多いけど、組合せ最適化はまじハマるっすよ

[perl-o-pal]

年齢とか肩書の順じゃないんだな…

[tk_musik]

理屈は全くわからんけど「意外とこっちもアリだな」を出してくれるってのはこういうのに一番求めたいことだね。

[fukken]

"人間関係をできるだけ保つようなゲスト集合から座席集合への写像を考えます"

[t_motooka]

結婚するには新郎または新婦のいずれか1人以上に数理最適化のスキルが必須（過言）（それはさておき、これは良い記事）

[masashisalvador]

おもろいw

[linus_peanuts]

こうやって決めても始まっちゃうと勝手に動き回ってその席にはいないしねえ。仮置きみたいなもんだわな

[htnmiki]

こんなアドベントカレンダーがあるんだな……　＞数理最適化 Advent Calendar

[call_me_nots]

知り合い度ベクトルせつなす

[Shinwiki]

牛刀割鶏

[samu_i]

“議論: なぜうまくいくのか？ ” 最適輸送で席を決めると披露宴がうまくいくらしい。活用できそうだな！

[Insite]

n=20なら頭蓋内のニューラルシステムで解を出せばよいのでは、と野暮なことを考えたのでした。いわゆる文系頭の人の方が向いてるかも。

[cartman0]

席の近さをマンハッタン距離かユークリッド距離にするかでだいぶ変わりそう