Seating Chart Optimization

I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized.

Each seat has neighbors. A person on a seat can talk to persons on neighboring seats (note that these neighbors normally sit next to each other or on the opposite side of the table).

Example of a table with 4 seats on each side:

1 2 3 4
8 7 6 5


6 has neighbors 2, 3, 4, 5 and 7, 8 has neighbors 1, 2, 7

There's a matrix describing how well two persons get along with each other. This is a value between 0 and 9 (the relation value). Relations are symmetrical.

Example of a relation matrix with four people:

  A B C D
A 0 2 0 5
B 2 0 3 6
C 0 3 0 1
D 5 6 1 0


The happiness of a single person is the sum of the relation values of all neighboring persons.

How would you find a solution that maximizes the overall happiness?

I use an ILP. I hope there are better solutions available.

Let H be your $n\times n$ happiness matrix. I use $n^2$ 0-1-variables $uv_{ij}$ per edge $uv$ in the seating graph. $uv_{ij}$ is 1 if person $i$ sits at place $u$ and person $j$ sits at place $v$.

maximize $\sum_{uv\in E} h_{ij} \cdot uv_{ij}$
s.t.
$\sum_{i,j} uv_{ij}=1$ for all $uv$, each edge gets exactly one neighbor configuration
$\sum_{j} ux_{ij} = \sum_{j} uy_{ij}$ for all edges $ux$ $uy$ that share an endpoint and all i, if $i$ sits at $u$ according to $ux$, they must also sit at $u$ according to $uy$

• Thanks for your input. Do you by any chance already have a working model for a solver? Commented Aug 24, 2013 at 18:11
• No, I used pencil and paper, sorry. However, I can recommend Gurobi. It's very fast, has a free academic licence and is reasonably well documented. I shouldn't take more than an afternoon or two to translate this LP to Gurobi's syntax. Commented Aug 26, 2013 at 8:06
• Thanks for your hint. I was thinking of using GLPK or lp_solve, since these libraries are completely free. However, I'm new to ILP, so I suppose it takes me more than two afternoons to model the problem :-) Commented Aug 27, 2013 at 7:21
• I used GLPK and it works reasonably well, but is much slower than Gurobi. See here Commented Aug 27, 2013 at 7:27