title: “The story of the Gromov-Wasserstein optimal transport for the seating arrangement of a wedding party” emoji: “🥂” type: “tech” # tech: technical article / idea: idea topics: [“optimaltransport”, “optimal transport”, “python”, “wedding”] published: true

My wife and I had a small wedding party this spring. Among the various preparations, I could nitpick about the seating arrangement endlessly, so I used mathematical optimization to decide on it. ! I want to come up with a seating arrangement that looks good, taking into account inter-guest relationships

tl;dr

Had a wedding party.
Connected social graph of guests and long connected tables make seating arrangement difficult.
- The combinatorial explosion is real. After more than a week of struggling with the placement of only 20 people, it seemed to be quicker to employ mathematical optimization
The problem of “placing people who know each other in close proximity” is a non-convex quadratic problem that cannot be solved successfully with general-purpose solvers.
Solving it with a type of optimal transport by considering the guests as “transports” to their seats worked well.
- The approach of utilizing a distance structure that is nonconvex in nature, but still non-convex, may have been successful.
- Colab for reproduction is available.
Combinatorial optimization, even on a small scale, is surprisingly difficult to solve by hand. Let machines solve the problems that can be formalized, and let us humans think about problems outside of them.

Background

In short, we wanted to make it guest-centered. Since we would have limited time to talk to each guest in person, we selected guests and their seating arrangements in such a way as to loosely connect the entire group through “friend of friend” relationships, hoping that new interactions would happen among the guests, as in banquets of academic conferences. This led to the optimization problem of embedding the nearly connected guest-relationship graph into a continuous long table as shown in the header image.

Straightforward formulation: quadratic programming

To let the computer solve this as an optimization problem, we need to define the goodness of seating.

People who know each other are to be close to each other.

This can be formulated as follows.

$$ \begin{align*} \operatorname{maximize} \sum_{i,i’} &\text{Friendship } S(\text{guest }i, \text{guest }i’) &\times \text{Closeness } C(\text{Seat of guest } i, \text{Seat of guest }i’) \end{align*} $$

Find the seating assignment that optimizes the above $\pi: [\text{number of people}] \to [\text{number of seats}]$. Hereafter, the number of people $=$seats$=:N$. This problem is called the quadratic allocation problem and is NP-hard in general, so we have to take an approximate solution.

As a solution space, we define a “degree” $x_{i,j}\in [0,1]$ that assigns guest $i$ to seat $j$. Let $x=(x_{0,0},\ldots,x_{i,j},x_{i,j+1},\cdots)^\top$ be a vector of these lined up. ! [](/images/seatopt_xspace.jpg =480x) Representation of Guest-Seat Allocation.

The optimization problem can be expressed as follows.

$$ \begin{align*} &\operatorname{maximize}{x \in \mathbb R^{N^2}} &&x^\top (\underbrace{S\otimes C}{=:P}) x \ &\operatorname{subjectto} && x_{i,j} \geq 0\ &&&\sum_i x_{i,j}=\sum_j x_{i,j}=1/N \end{align*} $$ The second constraint is the normalization to allow one seat per person.

Now that the problem is defined, all we have to do is to let the general-purpose solver solve it…but it did not work as far as we tried.

Solving it as a real-valued quadratic programming problem that allows soft allocation outputs soft allocation. - Like Schrodinger’s cat state where all the gests are seated at 5% in all the seats
CVXPY+CBC exists as a free solver for Integer QP constrained to a discrete solution space $x \in {0,1}^{N^2}$, but it only accepts convex problems
- If non-convex, you’ll get an error
```
  DCPError Traceback (most recent call last)
```
- Added a diagonal component to $P$ to make it convex ($+ α I$) and it worked, but the solution did not converge.
```
  ArpackNoConvergence: ARPACK error -1: No convergence (4001 iterations, 0/1 eigenvectors converged)
```
Perhaps a commercial solver such as Gurobi would work, but we can have another wedding party within the same cost.

I decided to take a specialized approach, thinking that the problem is generally too difficult to solve with a general-purpose solver.

Reformulation: Gromov-Wasserstein optimal transport

In fact, it seems that this problem can be well viewed as an optimal transport problem.

The usual optimal transport is the problem of optimizing the assignment between two sets or probability distributions so as to minimize the “transport volume” by considering the distance between the elements. ! [optimal and non-optimal transport](/images/seatopt_optimal_and_not_optimal_transport.png =500x) Find the correspondence between the red point group and the blue point group that minimizes the transportation cost (Figure: Introduction to Optimal Transportation)

Gromov-Wasserstein (GW) extends this framework to situations where two sets each contain different distance structures. Since no distance is defined between elements between those sets, the assignment is determined so as to preserve the distance between elements within each set. In this problem, since the distance between guests and seats (good allocation) is not directly defined, but the distance between guests and seats can be defined, it is equivalent to thinking that the allocation that minimizes the “difference between (guest-to-guest relationships) distance and (seat-to-seat) distance” is a good allocation.

! [seatopt_gw_matching.png](/images/seatopt_gw_matching.png =300x) <! – ! seatopt_gw_matching.png –> Gromov-Wasserstein optimal transport finds the assignment that minimizes distance vs. distance (Figure: GW introductory slide)

Predefine the distance between guests (degree of acquaintance) and the distance between seats (whether they are close enough to talk). When the $i$th guest is assigned to the $j$th seat and the $i’$th guest is assigned to the $j’$th seat, if guest $i$ and guest $i’$ are acquainted (distance between guests $d_{i,i’}=$small), their seats $j,j’$ are also close ($\bar d_{j,j’}$=$small) and the reverse is also true We determine the seat assignment $x \in [0,1]^{N^2}$ so that That is, the difference between the distance between guests $d_{i,i’}$ and the distance between seats $\bar d_{j,j’}$ $|d_{i,i’}-\bar d_{j,j’}|$ is minimized by weighting the sum of the correspondence between guests and seats $x_{i,j}, x_{i’,j’}$ to obtain the following formula.

$$ \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’}| \in{maximize} &&&\operatorname{subjectto} && x_{i,j} \geq 0\ &&&\sum_i x_{i,j}=\sum_j x_{i,j}=1/N {align*} $$ If one of the distances $D$ and $\bar d$ is multiplied by a constant, the solution will change, so it is better to define each distance so that they are approximately equally distributed, or to use the percentile value of the distance instead of the distance itself.

Once the problem is defined, it can be passed to the solver in the Python-OT package and solved in a few seconds. The process flow can be summarized as follows The reproduction notebook is available at Google Colab.

! seatopt_gw_alg_flow.png Gromov-Wasserstein optimal transport finds the assignment that minimizes the distance between distances.

The general outline is above, but several minor adjustments have been made.

Defining the distance between guests one by one is hard to adjust, so we define the degree of affiliation $G \in [0,1]^{number of people \times number of groups}$ for the group to which each position belongs. If guest $i$ and guest $i’$ belong to the same group, they are considered to be close, and the distance matrix between guests $D := - G G^\top (+ constant)$ is set as follows
Since it was not possible to fix the groom’s seat in the library implementation, we used the initial solution to control the groom’s seat somewhat.
I felt that the original QP objective function was somewhat more intuitive, so I further optimized QP using the greedy method from the GW solution (with only about 4 solution updates occurring) ^[Some may argue that the greedy method should be used from the beginning. It may be a matter of taste, but I had the impression that the greedy method actually sometimes produces quite good objective function values, but the quality of the solution is not stable depending on the initial values, and the solution itself is not stable, so it is difficult to “change a little and see variations of similar solutions”]. [QP

Evaluating the quality of the solution with the objective function $x^\top P x$ of the original QP, we got the following: the GW solution looks somewhat good in the sense of the objective function of QP^[The original QP is similarity maximization, GW is distance minimization, and they solve similar problems. Therefore, it is assumed that the solution of one can be in the sense of the other.] .

Random	GW	GW+Greedy Method
0.097 $\pm$ 0.02	0.242	0.300

Participants also commented that it was so natural that they could not believe it was decided mechanically.

Discussion: Why does it work?

As mentioned above, such quadratic assignment problems are computationally complex and could not be solved with standard QP solvers. In particular, general-purpose solvers often take advantage of convexity to solve it, but in this case it is not inherently convex. Because it is a long desk, there is symmetry in the seating arrangement, and the optimal arrangement remains optimal even if the optimal arrangement is rotated 180 degrees or mirror-image flipped, but at the midpoint $0.5 x + 0.5 x’$ of those solutions $x, x’$, there are people nearby (only half) or overlapping who should have been placed farther away. The problem is nonconvex because the intermediate solution is worse than the average of the endpoint solutions, making it difficult to approach in a generic way.

The GW solver also does not give a globally optimal solution. I believe that by treating the non-convex problem as non-convex and making good use of the good properties of the assignment problem with the distance structure, a fairly good solution can be obtained at high speed. The specific algorithm is described in GW introductory slides and elsewhere, but I am not sure why it solves fast. Personally, I have the rough impression that it often works well when distance structures can be used^[For example, it is [known] that the traveling salesman problem can also be solved fast when distances can be used, especially low-dimensional Euclidean distances (https://en.wikipedia. org/wiki/Travelling_salesman_problem#Euclidean)]

Summary

Although we spent two full weekends on the method study and implementation, we are glad we used the optimization solver. In general, I found the following advantages to the approach of using an optimization problem solver to solve the problem instead of human labor.

Easier to shake your head It is hard to stick to a tentative solution and change it significantly when it is thought by human. We tend to think that we can get by with minor replacements without changing the big picture, such as which group to place in which area. With solvers, fine-tuning the distance definitions of the inputs can change the results significantly and create many patterns that say, “Surprisingly, this one is also possible,” which makes thinking more flexible.
It opens your eyes to larger issues. Issues outside of seating optimization, such as seat allocation patterns for groom’s and bride’s guests and who to invite in the first place, should also be variable in nature. However, when searching manually, it is difficult to shake off the suspicion that there may be a better way to allocate seats if one thinks about it more carefully, or it is tedious to change the external specifications and rethink the whole process again, so it is easy to turn away from the big external problems and get caught up in narrow problems. With solvers, it is easy to think about the outer problem, because even if many solutions are created, if they are all subtle, it can be dismissed as inevitable, and optimization itself can be done quickly even if the specifications are changed. In fact, we adjusted the border between the groom’s and bride’s side seats based on the optimization results.
Free from the greed of all sides. One of the drawbacks of human-powered search is that it is practically full of constraints when numerous eight-sided viewpoints like “This allocation is too subtle for that person…” enter into the process. I think the advantage of leaving it to the machine is that it is easier to boldly pursue the overall optimum, since the excuse “I optimized it” can be made in the end.

This was the first time for me to use a mathematical optimization solver by myself, but I learned the following lessons.

Problems that require thinking about combinations are difficult Problems in which the goodness of this person in this seat is affected by other seating situations are combinatorial. Combinatorial problems are difficult because they are generally non-convex, even in the second order, and forcing to convert them into convex problems is not a good idea because the structure will collapse. It is important to determine whether the problem is combinatorial in nature or not, whether it is convex or not, and if you can put it into a good typology, you can rely on the solver.
Therefore, it is important to know the type of the problem. The optimization of the allocation (correspondence) considered this time is a rather common problem, and if the distance structure can be used, the optimal transport tends to be solved quickly, so it is important to know the problem type. I think it is worth remembering.

References

I see that a textbook on optimal transport is coming out next month. Rumor has it that Gromov-Wasserstein will be explained in an easy-to-understand manner. Optimal transport is a hot technology, not only for pure optimization like this one, but also increasingly used in machine learning such as GAN and causal inference. The book is written by a young leading Japanese expert who also gave the tutorial listed below, so I think it is a good book to have.

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

Here are some study materials for those who can’t wait.

Wedding Seat Optimization using Simulated Annealing
- Simulated annealing is employed for a similar setting.
Introduction to integer programming problem by using pulp (pulp) - Qiita
- Simple objective function: “I want to put this person in this seat. So it can be solved by LP.
- In this case, I thought of a combination of people, “I want to put people I know in seats near each other.
Introducing Circle Semi-Automatic Placement - Gijutsu Shosetsu Blog
- I was mentioned as a similar case on Twitter, but the circle placement problem is certainly larger in scale and more rewarding to solve. This person seems to have solved a similar QP using the group partitioning + greedy method. Since this method is basically $O(N^6)$, the