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