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

- 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

## No comments:

## Post a Comment