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

数理最適化 Advent Calendar 2022の9日目です。

新緑の頃、新型コロナ流行の合間をぬって、ささやかな結婚披露宴を表参道の式場にて催しました。諸々の準備の中でも席次はこだわるとキリがなく、数理最適化を使って決めました。人間関係をできるだけ保つようなゲスト集合から座席集合への写像を考えます。

ゲスト間人間関係を考慮して良い感じの配席を考えたい

tl;dr

• 披露宴をしました
• 知り合い関係が複雑かつ長机でゲストの席配置が難しい
  • 組合せ爆発は本物。高々20人の配置に1週間以上悩んだ結果、数理最適化した方が早いと結論
• 「知り合い同士を近くに配席する」問題は非凸な二次計画になり汎用ソルバでうまく解けない
• ゲストを席に"輸送"すると考えて最適輸送の一種で解くとうまくいった
  • 本質的に非凸な問題を非凸のまま、しかし性質の良い距離構造を活用するアプローチが奏功したのではないか
  • 再現用Colabあり
• 組合せ最適化は小規模でも人手では意外と大変。定義できる問題は機械に解かせて人間はその外側の問題を考えよう

背景

席決めが数理最適化を持ち出さなければならないほど複雑になった背景について披露宴のコンセプトから4,000字ほど書いたのですが、本筋から逸れるので別の機会にします。要するにゲスト中心としたく、とはいえ個々人と直接話す時間は限られるので、学会の懇親会のようにゲスト間に新たな交流が生まれるといいなと考え、「知り合いの知り合い」関係を通して全体が緩く繋がるようにゲストとその席配置を選ぶことにしました。これにより、冒頭の図のようなほぼ連結したゲスト関係グラフを連続的な長机に埋め込む最適化問題が発生しました。

素直な定式化: 二次計画法

最適化問題として計算機に解かせるには、席次の良さを定義する必要があります。

• 知り合い同士が近くなるように

ということを中心的に考えたいと思います。これは次のように定式化できます。

$$\begin{align*} \operatorname{maximize} \sum_{i,i'} &\text{知り合い度}S(\text{ゲスト}i, \text{ゲスト}i') \\ &\times 席の近さC(ゲストiの席, ゲストi'の席) \end{align*}$$

上記を最適化する席次割当 $\pi: [\text{人数}] \to [\text{席数}]$ を求めます。以後、人数 $=$席数$=:N$とします。この問題は二次割当問題と呼ばれ、一般にNP困難なので近似解を求めます。

解空間として、ゲスト$i$を席$j$に割り当てる「度合い」$x_{i,j}\in [0,1]$を定義します。これを並べたベクトルを$x=(x_{0,0},\ldots,x_{i,j},x_{i,j+1},\cdots)^\top$とします。

ゲスト-席割当の表現

最適化問題は以下のように表現できます。

$$\begin{align*} &\operatorname{maximize}_{x \in \mathbb R^{N^2}} &&x^\top (\underbrace{S\otimes C}_{=:P}) x \\ &\operatorname{subject~to~} && x_{i,j} \geq 0\\ &&&\sum_i x_{i,j}=\sum_j x_{i,j}=1/N \end{align*}$$

ただし$\otimes$はクロネッカー積、問題定義の行列表現は$S_{i,i'}=S(i,i')$などとします。2つめの制約は一人一席とする正規化です。

問題が定義できたので、あとは汎用ソルバに解かせるだけ･･･のはずでしたが、試した限りではうまく解けませんでした。

• ソフトな割当を許す実数値二次計画問題として解くとソフトな割当が出力される
  • 全ての人が全ての席に5%ずつ着席するシュレディンガーの猫状態
• 離散的な解空間 $x \in \{0,1\}^{N^2}$ に制約した Integer QP の無償ソルバとしてはCVXPY+CBCが存在するが、これは凸な問題しか受け付けてくれない
  • 凸じゃないと怒られる

    DCPError                                  Traceback (most recent call last)
    

  • 凸になるように$P$に対角成分を加えた（ $+ α I$ ）ところ動いたが解が収束せず

    ArpackNoConvergence: ARPACK error -1: No convergence (4001 iterations, 0/1 eigenvectors converged)
    

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

そもそも汎用ソルバで解くには問題が一般には難しいのだと考え、別の方策をとることにしました。

再定式化: Gromov-Wasserstein 最適輸送

実はこの問題は最適輸送問題としてもうまく捉えることができそうです。

通常の最適輸送は2つの集合や確率分布間で要素間の距離を考慮して「輸送量」を最小化するように割当てを最適化する問題です。

輸送コストを最小化する赤点群と青点群の対応関係を求める (図: 最適輸送入門)

Gromov-Wasserstein (GW) はこれを拡張し、2つの集合に異なる距離構造がそれぞれ入っている状況に対する枠組みです。それらの集合間の要素間には距離が定義されないので、それぞれの集合内の要素間距離を保存するように割当てを決めます。今回の問題では、ゲストと席の距離（割当の良さ）は直接定義されないがゲスト間の距離と座席間の距離が定義できるので、「（ゲスト間人間関係）距離と（座席間）距離の差」を最小化する割当てが良い割当てなのではないか、と考えることに相当します。

Gromov-Wasserstein最適輸送は距離と距離の距離を最小化する割当てを求める （図: GW紹介スライド)

ゲスト間の距離（知り合い度）と、席間距離（話せる距離かどうか）を予め定義しておきます。$i$番目のゲストを$j$番目の席に、$i'$番目のゲストを$j'$番目の席に配席したとき、ゲスト$i$とゲスト$i'$が知り合いであれば(ゲスト間距離$d_{i,i'}=$小)、彼らの席$j,j'$も近く($\bar d_{j,j'}$=小)、その裏もまた真となるように席の割当て $x \in [0,1]^{N^2}$ を決めていきます。即ち、ゲスト間距離$d_{i,i'}$と席間距離$\bar d_{j,j'}$の差 $\|d_{i,i'}-\bar d_{j,j'}\|$ を、ゲストと席の対応度 $x_{i,j}, x_{i',j'}$ について重み付けした和の最小化として次式を得ます。

$$\begin{align*} &\operatorname{maximize}_{x \in \mathbb R^{N^2}} &&\sum_{i,i',j,j'} x_{i,j} x_{i',j'}\|d_{i,i'}-\bar d_{j,j'}\| \\ &\operatorname{subject~to~} && x_{i,j} \geq 0\\ &&&\sum_i x_{i,j}=\sum_j x_{i,j}=1/N \end{align*}$$

ここで距離$d$と$\bar d$のうち片方を定数倍すると解が変わってしまうので、それぞれの距離がおおよそ同じくらいの分布になるように定義するか、距離そのものではなく距離のパーセンタイル値を用いるなどするとよいです。

問題を定義したらあとは Python-OT パッケージのソルバに渡せば数秒で解けます。処理の流れをまとめると以下のようになります。再現用ノートブックをGoogle Colabにて公開しています。

Gromov-Wasserstein最適輸送は距離と距離の距離を最小化する割当てを求める

大筋は以上ですが、細かな調整を何点か行っています。

• ゲスト間距離を一つずつ定義すると調整が大変なので、各位が所属するグループに対する所属度合い $G \in [0,1]^{人数 \times グループ数}$ を定義。ゲスト$i$とゲスト$i'$が同じグループに属していれば距離が近いと考え、ゲスト間距離行列 $D := - G G^\top (+定数)$ のように設定
• 新郎席を固定することがライブラリの実装上できなかったので初期解によって多少制御した
• 元のQPの目的関数の方がやや直観に近い気がしたので、GWの解からさらに貪欲法でQP最適化（解の更新は4回程度しか発生せず）^[1]。

解の質を元のQPの目的関数 $x^\top P x$ で評価すると以下のようになりました。GWの解はQPの目的関数の意味でもある程度よさそうです^[2]。

ランダム	GW	GW+貪欲法
0.097 $\pm$ 0.02	0.242	0.300

参加者からも「機械的に決めたとは思えないくらい自然」との評価を頂きました。

議論: なぜうまくいくのか？

前述のようにこのような二次割当問題は計算的に複雑であり、標準的なQPソルバでは解けませんでした。特に、汎用ソルバは凸性を活用して解くことが多いですが、今回は本質的に凸ではありません。長机なので席配置に対称性があり、最適な配置を180度回転させたり鏡像反転させても最適な配置のままですが、それらの解$x, x'$の中間点$0.5 x + 0.5 x'$では遠くに配置すべきだった人が近くに（半分だけ）居たり、重なり合ったりしています。中間解が端点解の平均より悪いので非凸であり、汎用的なアプローチが難しい問題です。

GWソルバも大域的最適解を出してくれるわけではありません。非凸な問題を非凸のまま扱い、距離構造を持つ割当問題の性質の良さをうまく活用することで高速にかなり良い解を得ているのではないかと思います。具体的なアルゴリズムは GW紹介スライド などに記載がありますが、なぜ高速に解けるのかはよくわかりません。個人的には、「距離構造が使えるとうまくいくことが多い」というざっくりした印象を持っています^[3]。

まとめ

方式検討と実装に週末丸2日を費やしましたが、最適化ソルバを使ってよかったです。人力ではなく最適化問題ソルバで解くアプローチ一般に以下のメリットが言えると感じました。

• 大なたを振いやすい
  人が考えると一度決めた暫定解に固執して大きく変えづらいです。どのグループをどの辺りに配置するか、などの大枠を変えずに、細かな入れ替えでなんとかなるのではないかと考えてしまいがちです。ソルバを使うと入力の距離定義を微調整することで結果が大きく変わり、「意外とこっちもアリだな」というパターンを数多く作れるので、考えが柔軟になります。
• より大きな問題に目が向く
  新郎ゲストと新婦ゲストの席の割当パターンや、そもそも誰を呼ぶかなど、席次最適化の外側の問題も本来は可変であるはずです。しかし人手で探索していると、「もっとよく考えればうまい配席方法があるのでは」という疑念が拭えなかったり、外側の仕様を変えてまた全体を考え直すのが面倒で、外側の大きな問題から目を背け、狭い問題にとらわれがちになります。ソルバを使うと、多数の解を作っても全部微妙なら仕方ないのだろうと割り切れますし、仕様を変えても最適化自体はすぐできるので、外側の問題を考えやすいです。実際、最適化結果をもとに新郎側席と新婦側席の境目を調整しました。
• 八方美人欲から解放される
  この割当はあの人にとって微妙だな･･･みたいな八方美人的な多数の観点が入り込むと実質的に制約だらけになることも人力探索の難点です。最適化したので、という言い訳が最終的にはできるので、思い切って全体最適を追求しやすい点は機械に任せることのメリットといえると思います。

数理最適化ソルバを自分でしっかり使うのは初めてだったのですが、次のような学びがありました。

• 組合せを考える必要がある問題は難しい
  この人をこの席に配席した場合の良さが、他の配席状況に影響を受けるような問題は組合せ的です。組合せ的な問題は二次でも一般には非凸であり難しく、無理に凸な問題に変換すると構造が崩れてしまってまずいです。問題が本質的に組合せ的かどうか、凸かどうかといった性質の見極めが重要で、うまく類型に落とし込めればソルバは頼りになります。
• よって問題の類型を知っておくことは重要
  今回考えた割当て（対応関係）の最適化はわりとよくある問題であり、かつ距離構造が使えそうなら最適輸送は高速に解けがちなので重要です。覚えておく価値はあるのではないでしょうか。

宣伝

来週 12/16(金)夜、因果推論の話をします。最適輸送も少し活躍します。

https://twitter.com/tanimoto_akira/status/1598843376509784064

参考文献

来月最適輸送の教科書が出るようですね。噂では Gromov-Wasserstein についても分かりやすく解説されているとか。最適輸送は今回のような純粋な最適化だけでなく、GANや因果推論など機械学習の中で使われることも増えてきており、注目技術です。下に挙げたチュートリアルも行った国内若手第一人者が書いているので持っておいて損のない一冊だと思います。

https://www.amazon.co.jp/dp/4065305144/

以下待ちきれない方のための勉強資料です。

• 最適輸送入門 (Slideshare)
• 最適輸送の解き方 (Slideshare)
• How to leverage optimal transport (Speaker Deck)

Related work

• 席替え問題による整数計画問題入門(pulp) - Qiita
  • 「この人をこの席にしたい」というシンプルな目的関数。なのでLPで解ける
  • 今回は「知り合い同士を近くの席にしたい」という、人の組合せを考えたのでQPになった

脚注

1. 初めから貪欲法でいいのではというツッコミがあるかもしれません。好みの問題かもしれませんが、貪欲法は実際結構良い目的関数値を出すこともあるのですが、解の質が初期値によって安定しないのと、解自体も安定しないので「ちょっと変えて似た解のバリエーションを見る」ことがしづらい印象がありました。

2. 元のQPは類似度最大化、GWは距離最小化であり、似た問題を解いています。よって片方の解がもう片方の意味でも良いのは想定通り。

3. たとえば巡回セールスマン問題も距離が使える、特に低次元のユークリッド距離が使えると高速に解けることが知られています