Friday, April 6, 2018

Speed Dating Scheduling

Speed Networking at Cité Internationale Universitaire de Paris [source]

In [1] a question is posed about a speed dating like problem. Here is my version of this:
There are 140 people. Each of them has stated some preference (or dis-preference) to meet specific persons. There are 5 rounds. Create a schedule such that the total sum of preferences is maximized.

The obvious encoding would be:$x_{i,j,t} = \begin{cases} 1 & \text{if persons i and j meet in round t}\\ 0 & \text{otherwise}\end{cases}$ Obviously, we have $$i\ne j$$. This will give rise to a very large number of variables: $$140\times 139 \times 5= 97,300$$, so we want to be as stingy as possible. One way is to exploit symmetry: if person $$i$$ meets person $$j$$ we don't want to use both $$x_{i,j,t}$$ and $$x_{j,i,t}$$. Let's try to make our restriction $$i\ne j$$ tighter: we only look at the lower-triangular part: $$i > j$$. This will save about half of the number of variables. However, this also means that summations become a bit more complicated. E.g. $$\sum_j x_{i,j,t}$$ now has to become two summations:

The model can look like:

Prefs is just a parameter, and can contain positive and negative values (or zero for "indifferent"). For 140 persons and 5 rounds we get a very large MIP problem:

MODEL STATISTICS

BLOCKS OF EQUATIONS           3     SINGLE EQUATIONS       10,431
BLOCKS OF VARIABLES           2     SINGLE VARIABLES       48,651
NON ZERO ELEMENTS       155,086     DISCRETE VARIABLES     48,650


Usually this means: forget about this. However, this is an easy MIP, it solves very fast: Cplex Time: 40.64sec. The optimal solution was found while doing preprocessing and generating cuts in node 0.

Of course in a real model we may have additional considerations: are there big winners or losers in this assignment? Do we want more equitable solutions?

Although this was a simple model, cooked up quickly, there are two interesting observations:

• Exploit symmetry, at the expense of making the constraints more complicated
• Some very large MIP models solve very quickly.

References

1. Excel: Matching names based on a matrix of options (Employees provide a list of people they want to meet with), https://stackoverflow.com/questions/49678171/excel-matching-names-based-on-a-matrix-of-options-employees-provide-a-list-of