"Frenemies," or How to Make Teenagers Happy at a Birthday Party

Question

I have a combinatorial optimization problem that I am struggling with. The technical details of the problem are cumbersome, so I translated something from the point of view of a fictitious sweet birthday 16. Obviously, NP teenagers are difficult, but this is separate from the actual problem that I am trying to solve.

Let's say I have a son who is about to turn 16 years old. He invites all his friends to his birthday, but not all of his friends as each other. In fact, every friend of my son has at least one person whom they do not like, and some have more. These frenemies refuse to sit at the same table if one or more jury frenemy sit at the same table. My son has provided me with a list of all his invited friends, as well as who do not like who. This information is symmetrical (if friend A does not like friend B, friend B does not like friend A), but he is NOT transitive (if friend A does not like friend B, but loves friend C, friend C is still free to love or not love friend B) . My question is: how to determine the minimum number of tables that satisfy the condition that two "frenemies" are not in the same table?

Answer 1

This is a combinatorial optimization problem, not a machine learning problem.

This is actually a coloring problem: create a graph G , where each vertex corresponds to a person. An edge (u, v) exists if two people u and v do not like each other. Now you are asking for the smallest k so that G k -colorable. The coloring c(v) tells which person of table v sitting.

Now you need to choose an algorithm .

Answer 2

This is more like a problem with a limited optimization problem than a machine learning problem. I would model it as follows.

• One variable for a friend, the value is a table,
• additional restrictions (on the list) of the form friendX !- friendY , to say that the two cannot sit at the same table.

This is a basic model that you can solve using the constraint resolver of your choice (I recommend Minion ). You can either minimize the highest table number (which will require some additional restrictions), or simply try to find a solution with a given number of tables (i.e. values ​​in variable domains) until you go to the one where there is no solution.

Depending on the size of the problem (i.e. the number of friends and tables), this may or may not work. Something you might have to consider is the symmetry of the problem (i.e., people in table A can go to table B and vice versa and this is still a solution), which can be broken with additional restrictions.