Speed Networking. [source] |

**speed dating**(or

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

- There are 10
**buyers**, - 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).

#### Data

---- 13 SETbbuyersbuyer1 , buyer2 , buyer3 , buyer4 , buyer5 , buyer6 , buyer7 , buyer8 , buyer9 , buyer10 ---- 13 SETssellersseller1 , seller2 , seller3 , seller4 , seller5 , seller6 , seller7 , seller8 , seller9 seller10 ---- 13 SETrroundsround1, round2, round3, round4, round5, round6, round7, round8 ---- 13 SETwantMeetinga meeting has been requestedseller1 seller2 seller3 seller4 seller5 seller6 seller7 seller8 seller9 buyer1 YES YES buyer2 YES YES buyer3 YES YES buyer4 YES YES buyer5 YES YES YES buyer6 YES YES YES buyer7 YES YES YES YES buyer8 YES YES buyer9 YES YES YES buyer10 YES YES + seller10 buyer8 YES

#### Model

**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}\]

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} \] |

- Objective. We minimize the number of rounds we need, in order to form a compact schedule.
- This constraint makes sure that any pair that wants a meeting, gets one.
- A seller \(s\) can not be double booked during a round.
- Similarly, a buyer \(b\) can only do one meeting per round.
- Implication: \(x_{b,s,r}=1 \Rightarrow \mathit{round}_r=1\),
- Order the used rounds. I.e. the first used round is number one.
- Calculate the number of used rounds.

#### Results

---- 47 VARIABLEx.Lmeetingsround1 round2 round3 round4 buyer1 .seller1 1 buyer1 .seller9 1 buyer2 .seller5 1 buyer2 .seller7 1 buyer3 .seller3 1 buyer3 .seller4 1 buyer4 .seller1 1 buyer4 .seller3 1 buyer5 .seller2 1 buyer5 .seller4 1 buyer5 .seller6 1 buyer6 .seller5 1 buyer6 .seller6 1 buyer6 .seller9 1 buyer7 .seller1 1 buyer7 .seller2 1 buyer7 .seller5 1 buyer7 .seller6 1 buyer8 .seller3 1 buyer8 .seller8 1 buyer8 .seller10 1 buyer9 .seller2 1 buyer9 .seller5 1 buyer9 .seller6 1 buyer10.seller7 1 buyer10.seller9 1 ---- 47 VARIABLEround.Lround is usedround1 1, round2 1, round3 1, round4 1 ---- 47 VARIABLEnumRounds.L = 4number of rounds needed

#### Capacity constraint

---- 47 VARIABLEx.Lmeetingsround1 round2 round3 round4 round5 round6 buyer1 .seller1 1 buyer1 .seller9 1 buyer2 .seller5 1 buyer2 .seller7 1 buyer3 .seller3 1 buyer3 .seller4 1 buyer4 .seller1 1 buyer4 .seller3 1 buyer5 .seller2 1 buyer5 .seller4 1 buyer5 .seller6 1 buyer6 .seller5 1 buyer6 .seller6 1 buyer6 .seller9 1 buyer7 .seller1 1 buyer7 .seller2 1 buyer7 .seller5 1 buyer7 .seller6 1 buyer8 .seller3 1 buyer8 .seller8 1 buyer8 .seller10 1 buyer9 .seller2 1 buyer9 .seller5 1 buyer9 .seller6 1 buyer10.seller7 1 buyer10.seller9 1 ---- 47 VARIABLEround.Lround is usedround1 1, round2 1, round3 1, round4 1, round5 1, round6 1 ---- 47 VARIABLEnumRounds.L = 6number of rounds needed

#### GAMS model

$ontext erwin@amsterdamoptimization.com1. we
have 10 buyers and 10 sellers2.
given is a set with wanted meetings between buyers and sellers3. up
to 8 rounds4. find
the most compact schedule for this problem$offtext setb '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';equationsdoMeet(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; |

**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.

- If the maximum number of rounds is not sufficient, try to allocate as many meetings as possible.
- 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)?
- Can we order the solution by the number of meetings in a round (say busy rounds with most meetings first)?
- The display of the solution can be improved. E.g. more compact is:

This is not a standard GAMS output.

#### References

- Automated meetings schedule planner, https://stackoverflow.com/questions/63662477/automated-meetings-schedule-planner
- Speed networking, https://en.wikipedia.org/wiki/Speed_networking
- Speed Dating, https://en.wikipedia.org/wiki/Speed_dating
- 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.

## No comments:

## Post a Comment