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:
- 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.
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:
- 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.
No comments:
Post a Comment