5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks for your input. Do you by any chance already have a working model for a solver? $\endgroup$ – raymi Aug 24 '13 at 18:11
  • $\begingroup$ 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. $\endgroup$ – adrianN Aug 26 '13 at 8:06
  • $\begingroup$ 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 :-) $\endgroup$ – raymi Aug 27 '13 at 7:21
  • $\begingroup$ I used GLPK and it works reasonably well, but is much slower than Gurobi. See here $\endgroup$ – adrianN Aug 27 '13 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.