Which algorithm could solve my wedding table issue?

Question

I have x guests for my wedding and y tables with z seats. Guest A can sit on the same table as guest B and guest C can not sit on the same table as guest D, ....

Given a dataset of all connection between all guests , is there a known algorithm which can solve this kind of issue?

I am sure this kind of problem has an abstract parent known as "problem x" or something or maybe it's a composition of problem a and problem b which can be solved by combining algorithm y and z

Any point in the right direction is appreciated.

Answer 1

This problem is NP-hard in the general case, so you shouldn't expect to find a general solution to it that's efficient if the number of tables or guests is large. This problem is a variation on this earlier problem which asks about divvying people up into different houses based on their preferences, and you can reduce that problem (which is NP-hard) to this one by simply giving each table enough capacity to hold every single guest.

If the number of people per table is small and the number of guests is small, you could just brute-force the solution by trying every possible assignment. Another option would be to try randomly guessing a few solutions and then incrementally modifying them to try to find a solution that works (for example, using a hill-climbing algorithm).

Hope this helps!

Answer 2

If you require an exact solution, formulate it as an 0-1 integer program and use GLPK to solve it.

Let x_ij be 1 if person i is assigned to table j and 0 otherwise. Consider the following constraint set:

(i) sum_{j=1...y} x_ij = 1 for i=1...x

(ii) sum_{i=1...x} x_ij <= z for j=1...y

(iii) x_ij + x_kj <=1 for j=1...y

(iv) x_ij is binary

Constraints (i) make sure everyone is assigned. Constraints (ii) prevents overloading a table. Constraints (iii) are defined for each person pair (i,k) that can't sit together.

Plug it into GLPK, CPLEX, or GUROBI and you're in business, provided that the problem is not too large. As the others have mentioned, NP-hardness means things could get ugly.