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.

  • 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).


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

buyer1 ,    buyer2 ,    buyer3 ,    buyer4 ,    buyer5 ,    buyer6 ,    buyer7 ,    buyer8 ,    buyer9 ,    buyer10


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

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


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

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

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

 


No comments:

Post a Comment