From: GagoX <elgrang...@gmail.com>
Date: Mar 3, 11:43 am
Subject: scheduling problem optimizing preferences
To: sci.mathHi everyone,
this is a real life problem and I have no idea even how to start!
I need to organize a small conference:
Np=50 participants (P1 to P50) and Nt=13 talks (T1 to T13).
There are 5 time spots each with 5 rooms available.
T1 will be given 3 times, T2 to T7 will be given 2 times each and T8
to T13 will be given only once. Consequently there are 22 talks. The
constraint is that the repeated talks should not be scheduled in the
same time slot.Each participant has given his preference to which talk to attend,
from 1st preference to 8th preference. And each participant should
attend 5 talks, one in each time slot.Problem: What talks should be scheduled in each time slot so to
optimize the preferences?The optimum solution would be to fulfill that each participand attend
their 5 first preferences.How is this problem called and is it possible to solve...what should
be the strategy.Or even better, does someone know the solution?I guess if I knew how to ennumerate each possibility (I do not know),
I could then quantify the fulfilling of the preferences and then take
the best one (brute force) (of course programming the whole
thing)...but I am afraid that there are too many possibilities!Thaks a lot in advance!!!!
This is a task that is sometimes very well suited to be implemented as mixed integer programming problem. (If they become too big, scheduling problems can be better implemented using different techniques.)
Lets try to do this quickly in GAMS. We start with the sets, and the basic data:
set
p 'participants' /p1*p50/
t 'presenter' /t1*t13/
n 'talk number' /n1*n3/
s 'timeslot' /slot1*slot5/
;
scalar rooms 'number of parallel sessions' /5/
set talk(t,n) 'each presenter can give several talks' /
t1.(n1,n2,n3)
(t2*t7).(n1,n2)
(t8*t13).n1
/;
scalar numtalk 'total number of talks';
numtalk=card(talk);
display talk,numtalk;
** actually the count is 21
** abort$(numtalk<>22) "oops, check your sets";
parameter ntalk(t) 'numbers of times a talk is given';
ntalk(t) = sum(talk(t,n),1);
display ntalk;
We see that the total number of talks is actually 21.
The preferences can be modeled as a parameter preferences(p,t). We assume eight of each row has numbers 1,..,8 and the rest is zero (no preference). We assume further 8 is highest preference so we will maximize. To be able to run a model we need to simulate some data. We can use random data, but need to consider that talks t1 and t2 through t7 are a little bit more popular (they are repeated a few times). The algorithm is a little bit complicated, but here it is:
parameter italk(t,n) 'number all talks (all 21 of them)';
scalar counter/0/;
loop(talk(t,n),
counter=counter+1;
italk(talk)=counter;
);
display italk;
parameter preferences(p,t) 'preference = 0..8, 8 is highest preference';
preferences(p,t)=0;
scalar kk,kt;
alias(t,tt);
set tcurrent(t);
loop((p,tt)$(ord(tt)<=8),
repeat
* draw from 1..numtalk
kk = UniformInt(1,numtalk);
kt = sum(talk(t,n)$(italk(t,n)=kk),ord(t));
* preferences(p,'element with ord kt') = ord(t)
tcurrent(t)$(ord(t)=kt) = yes;
if (sum(tcurrent,preferences(p,tcurrent))=0,
preferences(p,tcurrent) = ord(tt);
else
kk = 0
);
tcurrent(tcurrent) = no;
until kk<>0;
);
display "after",preferencesWe renumber talks in italks as follows:
---- 84 PARAMETER italk number all talks (all 21 of them)
n1 n2 n3
t1 1.000 2.000 3.000
t2 4.000 5.000
t3 6.000 7.000
t4 8.000 9.000
t5 10.000 11.000
t6 12.000 13.000
t7 14.000 15.000
t8 16.000
t9 17.000
t10 18.000
t11 19.000
t12 20.000
t13 21.000This allows us to draw from unique talks 1..21, which gives a better distribution than if we would have drawn from 1..13 (e.g. we would generate too few attendants for the popular talk t1 which is given three times). Using this we can generate some data for preferences:
---- 110 PARAMETER preferences preference = 0..8, 8 is highest preference
t1 t2 t3 t4 t5 t6 t7 t8 t9
p1 6.000 1.000 4.000 5.000 7.000 3.000
p2 4.000 6.000 7.000 8.000 1.000 5.000 3.000
p3 2.000 3.000 8.000 1.000 4.000 6.000 7.000
p4 1.000 3.000 5.000 2.000 6.000 8.000 7.000
p5 3.000 5.000 4.000 2.000 1.000 7.000 6.000 8.000
p6 4.000 7.000 1.000 8.000 5.000 2.000 3.000 6.000
p7 3.000 7.000 2.000 1.000 8.000 6.000 5.000
p8 7.000 1.000 2.000 4.000 8.000 5.000
p9 1.000 6.000 7.000 3.000 4.000 2.000 5.000
p10 2.000 5.000 3.000 1.000 7.000 6.000 8.000
p11 7.000 6.000 3.000 5.000 2.000 4.000
p12 7.000 1.000 5.000 8.000 2.000 6.000 3.000
p13 8.000 1.000 4.000 6.000 2.000 3.000
p14 2.000 1.000 5.000 3.000 4.000 6.000
p15 2.000 3.000 6.000 5.000 8.000 1.000 7.000
p16 5.000 7.000 1.000 3.000 8.000 2.000
p17 4.000 1.000 8.000 6.000 5.000
p18 3.000 1.000 2.000 5.000 7.000 6.000 4.000
p19 6.000 8.000 7.000 5.000 1.000 4.000
p20 5.000 1.000 6.000 8.000 4.000
p21 1.000 2.000 5.000 3.000 7.000
p22 4.000 1.000 8.000 5.000 3.000 6.000 7.000
p23 2.000 5.000 6.000 8.000 3.000
p24 1.000 4.000 5.000 7.000 6.000 2.000 3.000 8.000
p25 2.000 4.000 6.000 5.000 1.000 7.000
p26 3.000 5.000 7.000 8.000 4.000 6.000
p27 2.000 6.000 8.000 1.000 4.000 3.000 7.000
p28 4.000 1.000 3.000 6.000 7.000 8.000
p29 2.000 3.000 4.000 8.000 1.000 5.000 6.000
p30 4.000 1.000 3.000 8.000 2.000 6.000 5.000
p31 5.000 6.000 2.000 7.000 1.000 4.000
p32 6.000 3.000 4.000 5.000 7.000 8.000
p33 2.000 4.000 6.000 5.000 1.000 8.000
p34 7.000 4.000 3.000 6.000 5.000
p35 1.000 7.000 8.000 2.000 6.000 4.000 3.000
p36 2.000 5.000 3.000 6.000 1.000 7.000
p37 1.000 3.000 5.000 4.000 6.000 2.000
p38 7.000 3.000 8.000 6.000 2.000 1.000
p39 2.000 1.000 4.000 8.000 7.000 5.000
p40 5.000 1.000 4.000 8.000 7.000 2.000 3.000
p41 4.000 7.000 2.000 3.000 5.000 6.000
p42 2.000 8.000 7.000 5.000 4.000 6.000
p43 5.000 2.000 7.000 6.000 1.000 3.000
p44 4.000 7.000 1.000 3.000 5.000
p45 3.000 7.000 1.000 4.000 5.000 8.000 2.000
p46 2.000 5.000 6.000 8.000 4.000 7.000
p47 7.000 5.000 3.000 8.000 2.000 1.000
p48 5.000 7.000 8.000 6.000 3.000
p49 2.000 5.000 1.000 3.000 8.000
p50 2.000 5.000 1.000 3.000 4.000 7.000
+ t10 t11 t12 t13
p1 2.000 8.000
p2 2.000
p3 5.000
p4 4.000
p7 4.000
p8 6.000 3.000
p9 8.000
p10 4.000
p11 1.000 8.000
p12 4.000
p13 5.000 7.000
p14 8.000 7.000
p15 4.000
p16 4.000 6.000
p17 7.000 3.000 2.000
p18 8.000
p19 3.000 2.000
p20 2.000 7.000 3.000
p21 4.000 6.000 8.000
p22 2.000
p23 7.000 1.000 4.000
p25 3.000 8.000
p26 2.000 1.000
p27 5.000
p28 5.000 2.000
p29 7.000
p30 7.000
p31 3.000 8.000
p32 2.000 1.000
p33 3.000 7.000
p34 8.000 2.000 1.000
p35 5.000
p36 8.000 4.000
p37 8.000 7.000
p38 4.000 5.000
p39 3.000 6.000
p40 6.000
p41 8.000 1.000
p42 1.000 3.000
p43 8.000 4.000
p44 6.000 8.000 2.000
p45 6.000
p46 1.000 3.000
p47 6.000 4.000
p48 2.000 1.000 4.000
p49 6.000 4.000 7.000
p50 6.000 8.000Of course in practice we have his data available and we don't have to worry about this step (actually the most complicated part of the whole model). The rest of the model was implemented as follows:
variable z 'objective variable';
binary variables
x(t,p,s) 'assign talk/person/slot'
xts(t,s) 'assign talk/slot'
xtp(t,p) 'assign talk/person'
;
* we can relax xts and xtp
xts.prior(t,s) = INF;
xtp.prior(t,p) = INF;
equations
defxts1(t,s) 'calculate xts: all x=0 => xts = 0'
defxts2(t,p,s) 'calculate xts: any x=1 => xts = 1'
defxtp(t,p) 'calculate xtp'
talkcount(t) 'talk can be repeated ntalk times'
slotcount(s) 'up to 5 talks each period'
listen(p,s) 'p can visit only one talk in each time period'
zdef 'objective: maximize preferences'
;
* x(t,p,s)=0 for all p => xts(t,s) = 0
defxts1(t,s).. xts(t,s) =L= sum(p, x(t,p,s));
* any x(t,p,s)=1 => xts(t,s) = 1
defxts2(t,p,s).. xts(t,s) =G= x(t,p,s);
* p visits talk t in any s
defxtp(t,p).. xtp(t,p) =E= sum(s, x(t,p,s));
* each talk happens exactly ntalk times
talkcount(t).. sum(s, xts(t,s)) =E= ntalk(t);
* timeslot can only hold up to 5 talks
slotcount(s).. sum(t, xts(t,s)) =L= rooms;
* p can only visit one talk in each time period
listen(p,s).. sum(t,x(t,p,s)) =E= 1;
* we don't allow here (t,p) combinations without preference
xtp.fx(t,p)$(preferences(p,t)=0) = 0;
* objective: maximize
zdef.. z =e= sum((t,p), preferences(p,t) * xtp(t,p));
model scheduling /all/;
option mip=cplex;
scheduling.optfile=1;
scheduling.iterlim=100000;
scheduling.optcr=0;
solve scheduling using mip maximizing z;
$onecho > cplex.opt
threads 4
$offechoNote that variables xts and xtp are automatically integer, so we relax them by assigning a priority of infinity to them.
Cplex solves this quite quickly:
--- Job conference2.gms Start 03/05/09 17:58:00 WEX-VIS 23.0.2 x86/MS Windows
GAMS Rev 230 Copyright (C) 1987-2009 GAMS Development. All rights reserved
Licensee: Erwin Kalvelagen G090213/0001CV-WIN
Amsterdam Optimization Modeling Group DC4572
--- Starting compilation
--- conference2.gms(177) 3 Mb
--- Starting execution: elapsed 0:00:00.003
--- conference2.gms(169) 4 Mb
--- Generating MIP model scheduling
--- conference2.gms(170) 5 Mb
--- 4,234 rows 3,966 columns 17,496 non-zeroes
--- 3,250 discrete-columns
*** 465 relaxed-columns WARNING
--- Executing CPLEX: elapsed 0:00:00.034
ILOG CPLEX Feb 14, 2009 23.0.2 WIN 9101.9411 VIS x86/MS Windows
Cplex 11.2.1, GAMS Link 34
Cplex licensed for 1 use of lp, qp, mip and barrier, with 4 parallel threads.
Reading parameter(s) from "C:\projects\test\cplex.opt"
>> threads 4
Finished reading from "C:\projects\test\cplex.opt"
Reading data...
Starting Cplex...
Tried aggregator 1 time.
MIP Presolve eliminated 1501 rows and 1501 columns.
Reduced MIP has 2733 rows, 2465 columns, and 10595 nonzeros.
Reduced MIP has 2000 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec.
Clique table members: 650.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: opportunistic, using up to 4 threads.
Parallel mode: opportunistic, using up to 4 threads for concurrent optimization.
Tried aggregator 1 time.
No LP presolve or aggregator reductions.
Using devex.
Using devex.
Total real time on 4 threads = 0.17 sec.
Root relaxation solution time = 0.17 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap
0 0 1500.0000 906 1500.0000 5
* 0+ 0 1272.0000 1500.0000 5 17.92%
0 0 1500.0000 779 1272.0000 Fract: 1 3652 17.92%
* 0+ 0 1308.0000 1500.0000 3652 14.68%
* 0+ 0 1353.0000 1500.0000 3652 10.86%
* 0+ 0 1446.0000 1500.0000 3652 3.73%
0 2 1500.0000 779 1446.0000 1500.0000 3652 3.73%
* 4+ 0 1460.0000 1500.0000 10828 2.74%
* 4+ 0 1471.0000 1500.0000 10683 1.97%
* 40+ 33 1472.0000 1498.0000 37861 1.77%
100 95 1492.8125 568 1472.0000 1498.0000 54702 1.77%
* 127+ 120 1478.0000 1498.0000 58492 1.35%
200 194 1487.6000 458 1478.0000 1498.0000 74738 1.35%
300 291 1492.6364 499 1478.0000 1498.0000 88945 1.35%
* 346+ 323 1483.0000 1498.0000 101352 1.01%
* 374+ 323 1488.0000 1498.0000 108821 0.67%
400 253 1493.0667 555 1488.0000 1498.0000 115116 0.67%
500 153 1495.0000 654 1488.0000 1498.0000 148604 0.67%
600 159 1491.4444 448 1488.0000 1497.3333 208207 0.63%
700 205 1492.8333 526 1488.0000 1496.6667 247331 0.58%
800 243 1494.6667 438 1488.0000 1496.6667 263583 0.58%
900 312 cutoff 1488.0000 1496.5000 282888 0.57%
1000 385 1494.9375 465 1488.0000 1496.0000 309440 0.54%
Elapsed real time = 32.45 sec. (tree size = 0.49 MB, solutions = 10)
1100 457 1492.1875 579 1488.0000 1495.7500 326655 0.52%
1200 524 cutoff 1488.0000 1495.5000 347873 0.50%
1300 588 1490.5000 386 1488.0000 1495.3333 371387 0.49%
1400 655 1489.4286 429 1488.0000 1495.0000 394081 0.47%
1500 706 cutoff 1488.0000 1495.0000 418373 0.47%
1600 760 cutoff 1488.0000 1494.9167 445114 0.46%
1700 810 1489.5000 355 1488.0000 1494.7500 466940 0.45%
1800 865 cutoff 1488.0000 1494.6667 487877 0.45%
1900 924 1490.3333 385 1488.0000 1494.5000 510279 0.44%
2000 972 1492.5000 523 1488.0000 1494.3333 536279 0.43%
Elapsed real time = 43.77 sec. (tree size = 1.27 MB, solutions = 10)
2100 1022 cutoff 1488.0000 1494.1429 561289 0.41%
* 2127 391 integral 0 1491.0000 1494.0714 567476 0.21%
2200 380 cutoff 1491.0000 1494.0000 590101 0.20%
2300 363 1492.0000 530 1491.0000 1493.6667 627287 0.18%
2400 358 cutoff 1491.0000 1493.5000 652433 0.17%
2500 326 cutoff 1491.0000 1493.2000 684303 0.15%
2600 272 1492.5625 605 1491.0000 1493.0000 722077 0.13%
2700 245 cutoff 1491.0000 1493.0000 749425 0.13%
2800 191 1492.0000 334 1491.0000 1492.5000 771850 0.10%
2900 107 cutoff 1491.0000 1492.2609 793601 0.08%
3000 15 cutoff 1491.0000 1492.0000 808231 0.07%
Elapsed real time = 57.28 sec. (tree size = 0.05 MB, solutions = 11)
Root node processing (before b&c):
Real time = 2.64
Parallel b&c, 4 threads:
Real time = 54.99
Sync time (average) = 2.47
Wait time (average) = 0.00
-------
Total (root+branch&cut) = 57.63 sec.
MIP status(101): integer optimal solution
Fixing integer variables, and solving final LP...
Parallel mode: opportunistic, using up to 4 threads for concurrent optimization.
Tried aggregator 1 time.
LP Presolve eliminated 4234 rows and 3966 columns.
All rows and columns eliminated.
Total real time on 4 threads = 0.00 sec.
Fixed MIP status(1): optimal
Proven optimal solution.
MIP Solution: 1491.000000 (814080 iterations, 3023 nodes)
Final Solve: 1491.000000 (0 iterations)
Best possible: 1491.000000
Absolute gap: 0.000000
Relative gap: 0.000000
--- Restarting execution
--- conference2.gms(170) 0 Mb
--- Reading solution for model scheduling
--- conference2.gms(170) 3 Mb
--- GDX File C:\projects\test\x.gdx
*** Status: Normal completion
--- Job conference2.gms Stop 03/05/09 17:58:58 elapsed 0:00:57.817Note that we found a proven global optimum in less than a minute here. The complete schedule looks like:
It is often the simplest to start with a single large multidimensional “cube” (our variable x(t,p,s)), and then derive auxiliary variables from that cube (our variables xts, xtp). If the problem becomes very large, this may not be possible (x just becomes too large). However, if this structure fits, in many cases the performance is very good. In this case we have 3250 binary variables. This is a large number. Is is quite a feat that we can solve this quickly to optimality.
See also [follow-up].
`` It is often the simplest to start with a single large multidimensional “cube” (our variable x(t,p,s)), and then derive auxiliary variables from that cube (our variables xts, xtp). ``
ReplyDeleteInteresting and clear explanation - thanks!
I have a question concerning this formulation, how would you model that the timeslots have to be conseconsecutive? E.g. a person visits four talks in his/her five available slots (one talk each slot), then timeslots {1,2,3,4} and {2,3,4,5} are valid, but {1,2,4,5} is not. Is there a straightforward method to formulate this using binary variables?
Yes there are standard formulations for this. Basically, count the number of times the binary variable switches from 0 to 1. This number should be <= 1.
ReplyDeleteHey, I have a VRP Problem and i dont know hoe to solve.
ReplyDeleteNeed to develop a MILP model that returns the minimum total travel time.
is a chain of supermarkets that are serviced daily by a single distribution center. A fleet
of 4 trucks with 20000 pounds of capacity is used to make these deliveries. The daily demand and
travel times between distribution center and other store points are as follows. Note that the travel
times’ matrix is symmetric. A dash in the table indicates that the connection is not possible.
Daily demand (pounds)
Store 1 2 3 4 5 6 7 8 9
DC 6000 3000 4000 7000 5000 2000 3000 8000 10000
Travel times (minutes)
Store 1 2 3 4 5 6 7 8 9
DC 0 10 20 - 5 20 25 25 30 5
1 0 5 10 5 10 15 15 20 10
2 0 20 15 - 10 10 15 15
3 0 5 20 25 - 30 10
4 0 15 25 25 25 5
5 0 10 - 15 15
6 0 5 - 20
7 0 5 20
8 0 25
9 0
Can you help
Talk to your teacher or supervisor. He/she is getting paid to help you.
ReplyDelete