Is there a well understood algorithm or solution model for this meeting scheduling scenario?

Question

I have a complex problem and I want to know if an existing and well understood solution model exists or applies, like the Traveling Salesman problem.

Input:

• A calendar of N time events, defined by starting and finishing time, and place.
• The capacity of each meeting place (maximum amount of people it can simultaneously hold)
• A set of pairs (Ai,Aj) which indicates that attendant Ai wishes to meet with attendat Aj, and Aj accepted that invitation.

Output:

• For each assistant A, a cronogram of all the events he will attend. The main criteria is that each attendants should meet as many of the attendants who accepted his invites as possible, satisfying the space constraints.

So far, we thought of solving with backtracking (trying out all possible solutions), and using linear programming (i.e. defining a model and solving with the simplex algorithm)

Update: If Ai already met Aj in some event, they don't need to meet anymore (they have already met).

Answer 1

Your problem is as hard as minimum maximal matching problem in interval graphs, w.l.o.g Assume capacity of rooms is 2 means they can handle only one meeting in time. You can model your problem with Interval graphs, each interval (for each people) is one node. Also edges are if A_i & A_j has common time and also they want to see each other, set weight of edges to the amount of time they should see each other, . If you find the minimum maximal matching in this graph, you can find the solution for your restricted case. But notice that this graph is n-partite and also each part is interval graph.

P.S: note that if the amount of time that people should be with each other is fixed this will be more easier than weighted one.

Answer 2

If you have access to a good MIP solver (cplex/gurobi via acedamic initiative, but coin OR and LP_solve are open-source, and not bad either), I would definitely give simplex a try. I took a look at formulating your problem as a mixed integer program, and my feeling is that it will have pretty strong relaxations, so branch and cut and price will go a long way for you. These solvers give remarkably scalable solutions nowadays, especially the commercial ones. Advantage is they also provide an upper bound, so you get an idea of solution quality, which is not the case for heuristics.

Formulation:

Define z(i,j) (binary) as a variable indicating that i and j are together in at least one event n in {1,2,...,N}. Define z(i,j,n) (binary) to indicate they are together in event n. Define z(i,n) to indicate that i is attending n. Z(i,j) and z(i,j,m) only exist if i and j are supposed to meet.

For each t, M^t is a subset of time events that are held simulteneously. So if event 1 is from 9 to 11, event 2 is from 10 to 12 and event 3 is from 11 to 13, then M^1 = {event 1, event 2) and M^2 = {event 2, event 3}. I.e. no person can attend both 1 and 2, or 2 and 3, but 1 and 3 is fine.

Max sum Z(i,j)                      

z(i,j)<= sum_m z(i,j,m)   
(every i,j)(i and j can meet if they are in the same location m at least once)

z(i,j,m)<= z(i,m)   (for every i,j,m) 
(if i and j attend m, then i attends m)

z(i,j,m)<= z(j,m)     (for every i,j,m) 
(if i and j attend m, then j attends m)

sum_i z(i,m) <= C(m)   (for every m) 
(only C(m) persons can visit event m)

sum_(m in M^t) z(i,m) <= 1  (for every t and i)  
(if m and m' are both overlapping time t, then no person can visit them both. )