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:xi,j,t={1if persons i and j meet in round t0otherwise Obviously, we have i≠j. This will give rise to a very large number of variables: 140×139×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 xi,j,t and xj,i,t. Let's try to make our restriction i≠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. ∑jxi,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