This is a simple problem from [1]:
I'm rusty on constraint optimization and am looking for help in this particularuse case. There are individuals who are each member to several teams. This is afixed many-to-many relationship and is determined a-priori. There are 3 timeslots where the teams can be scheduled to conduct a business meeting, but if anindividual is a member of more than one team which are both meeting at a giventime slot, they'll only be able to attend one. The objective is to schedule theteams into the time slots, minimizing the number of overlaps of individuals.
- Formulate a mathematical model (on a piece of paper)
- Implement the model in code
---- 23 SET member team membership
team1 team2 team3 team4 team5 team6
individual1 YES YES
individual2 YES
individual3 YES YES
individual4 YES YES
individual5 YES
individual6 YES YES
individual7 YES
individual8 YES YES
individual10 YES YES YES
individual11 YES YES YES YES
individual12 YES YES
individual13 YES YES
individual14 YES YES YES
individual15 YES YES
individual17 YES YES YES YES
individual18 YES
individual19 YES YES
individual20 YES YES
We are missing some individuals: they are not in any of the teams. This is just a result of how the random set member was generated. We could remove those from the set \(i\), but I decided to leave them in. It is a good check to see if the model is robust enough to handle this.
---- 46 VARIABLE x.L schedule team meetings at time slot timeslot1 timeslot2 timeslot3 team1 1 team2 1 team3 1 team4 1 team5 1 team6 1 ---- 46 VARIABLE y.L individual is in meeting at time slot timeslot1 timeslot2 timeslot3 individual1 1 1 individual2 1 individual3 1 1 individual4 1 1 individual5 1 individual6 1 individual7 1 individual8 1 1 individual10 1 1 1 individual11 1 1 1 individual12 1 1 individual13 1 1 individual14 1 1 1 individual15 1 1 individual17 1 1 1 individual18 1 individual19 1 1 individual20 1 1
---- 51 PARAMETER meetingcount number of meetings timeslot1 timeslot2 timeslot3 individual1 1 1 individual2 1 individual3 1 1 individual4 1 1 individual5 1 individual6 2 individual7 1 individual8 1 1 individual10 1 1 1 individual11 1 2 1 individual12 1 1 individual13 1 1 individual14 1 1 1 individual15 1 1 individual17 2 1 1 individual18 1 individual19 1 1 individual20 1 1
Minimizing overbookings
---- 86 VARIABLE x.L schedule team meetings at time slot timeslot1 timeslot2 timeslot3 team1 1 team2 1 team3 1 team4 1 team5 1 team6 1 ---- 86 VARIABLE y2.L rest of y (part that represents >=2) timeslot2 individual11 1 individual14 1 individual17 1 ---- 86 PARAMETER meetingcount number of meetings timeslot1 timeslot2 timeslot3 individual1 1 1 individual2 1 individual3 1 1 individual4 1 1 individual5 1 individual6 1 1 individual7 1 individual8 1 1 individual10 1 1 1 individual11 1 2 1 individual12 1 1 individual13 1 1 individual14 1 2 individual15 1 1 individual17 1 2 1 individual18 1 individual19 1 1 individual20 1 1
Conclusions
- Writing down the mathematical model is a useful exercise. Coding is much easier afterward. A math model is a blue print for the code.
- Instead of minimizing double bookings, we can maximize the number of meetings attended. Both give similar solutions.
- This is a nice little example with some interesting modeling angles. With a little bit of thought, we can create quite compact models.
- Of course this problem is small enough for complete enumeration. Question: how many ways are there to assign 6 team meetings to three days?
- The models have a lot of symmetry. E.g., we can fix the first team (or the largest team) to time slot 1.
References
- Google-OR Tools: Assignment minimizing overlapping members, https://or.stackexchange.com/questions/11115/google-or-tools-assignment-minimizing-overlapping-members
Appendix: GAMS Model
$onText
I'm rusty on constraint optimization and am looking for help in this particular use case. There are individuals who are each member to several teams. This is a fixed many-to-many relationship and is determined a-priori. There are 3 time slots where the teams can be scheduled to conduct a business meeting, but if an individual is a member of more than one team which are both meeting at a given time slot, they'll only be able to attend one. The objective is to schedule the teams into the time slots, minimizing the number of overlaps of individuals.
https://or.stackexchange.com/questions/11115/google-or-tools-assignment-minimizing-overlapping-members
$offText
*--------------------------------------------------------------- * data *---------------------------------------------------------------
set i 'individuals' /individual1*individual20/ t 'teams' /team1*team6/ s 'time slot' /timeslot1*timeslot3/ member(i,t) 'team membership' ; member(i,t) = uniform(0,1)<0.25; display member;
* we miss some individuals in member set parameter numindiv(*) 'number of individuals'; numindiv('in set i') = card(i); numindiv('team members') = sum(i$sum(member(i,t),1),1); option numindiv:0; display numindiv;
*--------------------------------------------------------------- * model 1: maximize number meetings for each individual *---------------------------------------------------------------
binary Variables x(t,s) 'schedule team meetings at time slot' y(i,s) 'individual is in meeting at time slot' ;
variable total 'total number of meeting participation';
equations obj 'objective' schedule_teams(t) 'exactly one time' schedule_indiv(i,s) 'bound' ;
schedule_teams(t).. sum(s,x(t,s)) =e= 1; schedule_indiv(i,s).. y(i,s) =l= sum(member(i,t),x(t,s)); obj.. total =e= sum((i,s),y(i,s));
model schedule /all/; solve schedule maximizing total using mip;
option x:0,y:0; display x.l,y.l;
parameter meetingcount(i,s) 'number of meetings'; meetingcount(i,s) = sum(member(i,t), x.l(t,s)); option meetingcount:0; display meetingcount; *--------------------------------------------------------------- * model 2: minimize number of double bookings *---------------------------------------------------------------
positive variables y1(i,s) 'first part of y (0 or 1)' y2(i,s) 'rest of y (part that represents >=2)' ; y1.up(i,s) = 1; variable overbookings;
Equations nummeet 'number of meetings' obj2 'minimize double bookings' ; nummeet(i,s).. y1(i,s) + y2(i,s) =e= sum(member(i,t),x(t,s)); obj2.. overbookings =e= sum((i,s),y2(i,s));
model schedule2 /obj2,nummeet,schedule_teams/; solve schedule2 minimizing overbookings using mip;
meetingcount(i,s) = sum(member(i,t), x.l(t,s)); option y2:0; display x.l,y2.l,meetingcount;
*--------------------------------------------------------------- * model 3: variant of model 2 *---------------------------------------------------------------
Equations nummeet2 'number of meetings (bound)' ; nummeet2(i,s).. 1 + y2(i,s) =g= sum(member(i,t),x(t,s));
model schedule3 /obj2,nummeet2,schedule_teams/; solve schedule3 minimizing overbookings using mip;
meetingcount(i,s) = sum(member(i,t), x.l(t,s)); display x.l,y2.l,meetingcount; |
Thanks
ReplyDeleteI solved it in Googlw OR-Tools
https://or.stackexchange.com/a/11165/4775
Your code has an upper bound of 2 on the number of duplicates. (I.e. this problem with just 1 time period will be infeasible). I assume this code was copy-pasted which is almost always a recipe for disaster. Better than copy-paste is to copy the concepts but enter the code by typing. It forces you to pay attention to the details.
Delete