## Monday, August 31, 2020

### Speed dating

 Speed Networking. [source]

In [1] a speed dating (or speed networking [2]) problem is proposed, where parties representing buyers and sellers can have a short meeting with different parties.

• and 10 sellers.
• Data is available telling us which buyers/sellers are interested in talking to each other.
• Meetings are organized in 15-minute rounds, with a limited number of rounds (say 8 or 10).
Interestingly, the single word "SpeedDating" is trade-marked, while "Speed Dating" is (still) free to use [3].

#### Data

I generated some random data so we have something to solve:

----     13 SET b  buyers

----     13 SET s  sellers

seller1 ,    seller2 ,    seller3 ,    seller4 ,    seller5 ,    seller6 ,    seller7 ,    seller8 ,    seller9
seller10

----     13 SET r  rounds

round1,    round2,    round3,    round4,    round5,    round6,    round7,    round8

----     13 SET wantMeeting  a meeting has been requested

seller1     seller2     seller3     seller4     seller5     seller6     seller7     seller8     seller9

+    seller10



#### Model

To model this we can use the following binary variable: $x_{b,s,r} = \begin{cases} 1 & \text{if buyer b meets seller s in round r}\\ 0 & \text{otherwise}\end{cases}$ Instead of using a fully allocated variable, it is better to use a sparse variant: $x_{b,s,r} = \begin{cases} 1 & \text{if buyer b meets seller s in round r} && \forall b,s,r|\mathit{wantMeeting}_{b,s} \\ 0 & \text{if buyer b does not meet seller s in round r} &&\forall b,s,r|\mathit{wantMeeting}_{b,s} \\ \text{not allocated} & && \forall b,s,r| \bf{not }\mathit{wantMeeting}_{b,s} \end{cases}$

With this, we can formulate the model:

MIP model
\large\begin{align} \min \> & \color{darkred}{\mathit{numRounds}} && && (1) \\ & \sum_r \color{darkred}x_{b,s,r} = 1 && \forall b,s|\color{darkblue}{\mathit{wantMeeting}}_{b,s} && (2) \\ & \sum_{b|\color{darkblue}{\mathit{wantMeeting}}(b,s)} \color{darkred}x_{b,s,r} \le 1 && \forall s,r&& (3)\\ & \sum_{s|\color{darkblue}{\mathit{wantMeeting}}(b,s)} \color{darkred}x_{b,s,r} \le 1 && \forall b,r && (4) \\ & \color{darkred}{\mathit{round}}_r \ge \color{darkred}x_{b,s,r} && \forall b,s,r| \color{darkblue}{\mathit{wantMeeting}}_{b,s} && (5) \\ & \color{darkred}{\mathit{round}}_r \ge \color{darkred}{\mathit{round}}_{r+1} && \forall r \in \{1,\dots,R-1\} && (6) \\ &\color{darkred}{\mathit{numRounds}} = \sum_r \color{darkred}{\mathit{round}}_r && &&(7) \\ & \color{darkred}x_{b,s,r} \in \{0,1\} \\ & \color{darkred}{\mathit{round}}_r \in \{0,1\} \end{align}

Some explanation for each equation:
1. Objective. We minimize the number of rounds we need, in order to form a compact schedule.
2. This constraint makes sure that any pair that wants a meeting, gets one.
3. A seller $$s$$ can not be double booked during a round.
4. Similarly, a buyer $$b$$ can only do one meeting per round.
5. Implication: $$x_{b,s,r}=1 \Rightarrow \mathit{round}_r=1$$,
6. Order the used rounds. I.e. the first used round is number one.
7. Calculate the number of used rounds.
Note that every reference to $$x_{b,s,r}$$ is protected: only for possible combinations $$(b,s)$$ this variable is used.

#### Results

----     47 VARIABLE x.L  meetings

round1      round2      round3      round4

----     47 VARIABLE round.L  round is used

round1 1,    round2 1,    round3 1,    round4 1

----     47 VARIABLE numRounds.L           =            4  number of rounds needed


We can verify that every buyer and every seller is not assigned multiple times to a meeting during the same round.

#### Capacity constraint

In the model above we assumed no limit on the available tables. In practice there may be such a limit. This can easily be fixed by adding the constraint $\sum_{b,s|\mathit{wantMeeting}(b,s)} x_{b,s,r} \le \mathit{numTables} \> \forall r$

Using $$\mathit{numTables}=5$$ we see:

----     47 VARIABLE x.L  meetings

round1      round2      round3      round4      round5      round6

----     47 VARIABLE round.L  round is used

round1 1,    round2 1,    round3 1,    round4 1,    round5 1,    round6 1

----     47 VARIABLE numRounds.L           =            6  number of rounds needed


As expected, fewer tables will lead to a longer schedule.

#### GAMS model

Here is the GAMS representation of the MIP model.

 $ontext small demo model for designing a schedule for a speed dating event erwin@amsterdamoptimization.com 1. we have 10 buyers and 10 sellers 2. given is a set with wanted meetings between buyers and sellers 3. up to 8 rounds 4. find the most compact schedule for this problem$offtext set   b 'buyers' /buyer1*buyer10/   s 'sellers' /seller1*seller10/   r 'rounds'  /round1*round8/ ; scalar numTables 'number of available tables' /5/; set wantMeeting(b,s) 'a meeting has been requested'; wantMeeting(b,s)$(uniform(0,1)<0.2) = yes; option wantMeeting:0; display b,s,r,wantMeeting; binary variable x(b,s,r) 'meetings'; binary variable round(r) 'round is used'; variable numRounds 'number of rounds needed'; equations doMeet(b,s) 'all wanted meetings are required' SellerBusy(s,r) 'seller can do 0 or 1 meetings in a single round' BuyerBusy(b,r) 'byuer can do 0 or 1 meetings in a single round' MaxTables(r) 'capacity constraint' useRound(b,s,r) 'implication: x=1 => round=1' order(r) 'ordering of rounds' obj 'objective' ; doMeet(wantMeeting(b,s)).. sum(r, x(b,s,r)) =e= 1; SellerBusy(s,r).. sum(wantMeeting(b,s),x(b,s,r)) =l= 1; BuyerBusy(b,r).. sum(wantMeeting(b,s),x(b,s,r)) =l= 1; MaxTables(r)$numTables.. sum(wantMeeting(b,s), x(b,s,r)) =l= numTables; useRound(wantMeeting(b,s),r).. round(r) =g= x(b,s,r); order(r+1).. round(r) =g= round(r+1); obj.. numRounds =e= sum(r, round(r)); model m /all/; option optcr=0; solve m minimizing numRounds using mip; option x:0,round:0,numrounds:0; display x.l,round.l,numrounds.l;

Notes:
• option optcr=0 sets the allowed gap to zero, So we search for a proven optimal solution.
• equation order drops the last r from consideration. Somewhat of a minor detail: the model would still work without this precaution.
• Notice how the body of the constraints 2, 3, and 4 are the same. The meaning is determined by the for-all construct.
• An alternative is to write:  sum(b$wantMeeting(b,s),x(b,s,r))sum(s$wantMeeting(b,s),x(b,s,r)), and sum((b,s)\$wantMeeting(b,s),x(b,s,r))
• If numTables=0, we skip the capacity constraint.
• In GAMS we just declare x(b,s,r). Only variables referenced in the constraints are actually generated and passed on to the solver. Not all modeling tools use this approach. For instance, CVXPY allocates all declared variables and is not very good at handling sparse variables. Furthermore, CVXPY does not support 3-dimensional variables.

Some remaining questions or experiments:
1. If the maximum number of rounds is not sufficient, try to allocate as many meetings as possible.
2. Can we integrate this into one model, or do we need two models (if feasible, minimize the number of rounds, and if infeasible maximize the number of meetings)?
3. Can we order the solution by the number of meetings in a round (say busy rounds with most meetings first)?
4. The display of the solution can be improved. E.g. more compact is:

This is not a standard GAMS output.

#### References

1. Automated meetings schedule planner, https://stackoverflow.com/questions/63662477/automated-meetings-schedule-planner
2. Speed networking, https://en.wikipedia.org/wiki/Speed_networking
3. Speed Dating, https://en.wikipedia.org/wiki/Speed_dating
4. Speed dating scheduling, https://yetanothermathprogrammingconsultant.blogspot.com/2018/04/speed-dating-scheduling.html This is a model for a related problem. In this problem, the participants are not from two different groups but form one big pool. This makes the problem larger, as we have more possible meetings to consider.