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

As pointed out by @SaeedAmiri, this looks like a complex problem.

My guess would be that the backtracking and linear programming options you are considering will explode as soon as the number of assistants grows a bit (maybe in the order of tens of assistants).

Maybe you should consider a (meta)heuristic approach if optimality is not a requirement, or constraint programming to build an initial model and see how it scales.

To give you a more precise answer, why do you need to solve this problem? what would be the typical number of attendees? number of rooms?