Processing math: 100%

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:xi,j,t={1if persons i and j meet in round t0otherwise Obviously, we have ij. 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 ij 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


  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

No comments:

Post a Comment