## Friday, March 6, 2009

### A conference scheduling problem

From: GagoX <elgrang...@gmail.com>
Date: Mar 3, 11:43 am
Subject: scheduling problem optimizing preferences
To: sci.math

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

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",preferences``

We 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.000t2        4.000       5.000t3        6.000       7.000t4        8.000       9.000t5       10.000      11.000t6       12.000      13.000t7       14.000      15.000t8       16.000t9       17.000t10      18.000t11      19.000t12      20.000t13      21.000``

This 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.000p2        4.000       6.000       7.000                   8.000       1.000       5.000                   3.000p3        2.000       3.000       8.000       1.000                   4.000       6.000                   7.000p4        1.000       3.000       5.000                   2.000       6.000       8.000       7.000p5        3.000       5.000       4.000       2.000       1.000       7.000       6.000                   8.000p6        4.000       7.000       1.000       8.000                   5.000       2.000       3.000       6.000p7        3.000       7.000       2.000       1.000       8.000                               6.000       5.000p8        7.000       1.000       2.000       4.000                                           8.000       5.000p9        1.000       6.000       7.000       3.000       4.000       2.000       5.000p10       2.000       5.000       3.000       1.000       7.000       6.000                               8.000p11       7.000       6.000                   3.000       5.000       2.000       4.000p12       7.000       1.000       5.000                   8.000                   2.000       6.000       3.000p13       8.000       1.000                   4.000                   6.000       2.000                   3.000p14       2.000       1.000                               5.000       3.000                   4.000       6.000p15       2.000       3.000       6.000       5.000       8.000       1.000       7.000p16       5.000       7.000                   1.000                   3.000       8.000                   2.000p17       4.000                               1.000       8.000       6.000       5.000p18       3.000                   1.000                   2.000       5.000       7.000       6.000       4.000p19       6.000       8.000                               7.000       5.000       1.000                   4.000p20       5.000       1.000       6.000                   8.000                               4.000p21       1.000                   2.000       5.000       3.000                   7.000p22       4.000       1.000       8.000       5.000       3.000                               6.000       7.000p23       2.000                               5.000       6.000       8.000       3.000p24       1.000       4.000       5.000       7.000       6.000       2.000       3.000       8.000p25       2.000       4.000                   6.000                   5.000       1.000       7.000p26       3.000       5.000       7.000                   8.000       4.000                               6.000p27       2.000       6.000       8.000       1.000       4.000       3.000       7.000p28       4.000       1.000       3.000       6.000       7.000                               8.000p29       2.000       3.000       4.000                   8.000       1.000       5.000       6.000p30       4.000                   1.000       3.000       8.000       2.000                   6.000       5.000p31       5.000                   6.000                   2.000                   7.000       1.000       4.000p32                   6.000       3.000                   4.000       5.000       7.000                   8.000p33       2.000                   4.000       6.000       5.000       1.000                               8.000p34       7.000       4.000       3.000                               6.000                   5.000p35       1.000       7.000       8.000       2.000       6.000       4.000       3.000p36       2.000       5.000                   3.000       6.000       1.000       7.000p37       1.000                   3.000       5.000       4.000       6.000                   2.000p38                               7.000       3.000       8.000       6.000       2.000                   1.000p39       2.000                               1.000       4.000       8.000       7.000       5.000p40       5.000       1.000       4.000       8.000       7.000       2.000                   3.000p41                   4.000                   7.000       2.000       3.000       5.000                   6.000p42       2.000       8.000       7.000       5.000                   4.000       6.000p43       5.000       2.000       7.000       6.000       1.000       3.000p44                                                       4.000       7.000       1.000       3.000       5.000p45       3.000       7.000                   1.000       4.000       5.000       8.000                   2.000p46       2.000       5.000       6.000                   8.000       4.000                   7.000p47       7.000       5.000       3.000       8.000       2.000                   1.000p48       5.000       7.000       8.000       6.000       3.000p49       2.000       5.000       1.000       3.000                               8.000p50       2.000       5.000       1.000       3.000       4.000                                           7.000  +         t10         t11         t12         t13 p1        2.000                               8.000p2                                            2.000p3        5.000p4                    4.000p7                                4.000p8                                6.000       3.000p9                                8.000p10                               4.000p11                               1.000       8.000p12                               4.000p13       5.000                               7.000p14       8.000                               7.000p15                               4.000p16                               4.000       6.000p17       7.000       3.000       2.000p18                                           8.000p19       3.000                               2.000p20       2.000       7.000                   3.000p21       4.000       6.000       8.000p22                               2.000p23       7.000       1.000       4.000p25       3.000                   8.000p26       2.000                               1.000p27                               5.000p28       5.000                   2.000p29       7.000p30                               7.000p31                   3.000                   8.000p32                   2.000                   1.000p33       3.000                               7.000p34                   8.000       2.000       1.000p35                               5.000p36       8.000                               4.000p37       8.000                   7.000p38                   4.000                   5.000p39       3.000                   6.000p40                   6.000p41       8.000                               1.000p42       1.000                   3.000p43       8.000       4.000p44       6.000                   8.000       2.000p45                   6.000p46                   1.000                   3.000p47                   6.000       4.000p48       2.000       1.000       4.000p49       6.000                   4.000       7.000p50                   6.000                   8.000``

Of 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 xtpxts.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) = 0defxts1(t,s).. xts(t,s) =L= sum(p, x(t,p,s));* any x(t,p,s)=1 => xts(t,s) = 1defxts2(t,p,s).. xts(t,s) =G= x(t,p,s); * p visits talk t in any sdefxtp(t,p).. xtp(t,p) =E= sum(s, x(t,p,s)); * each talk happens exactly ntalk timestalkcount(t).. sum(s, xts(t,s)) =E= ntalk(t); * timeslot can only hold up to 5 talksslotcount(s).. sum(t, xts(t,s)) =L= rooms; * p can only visit one talk in each time periodlisten(p,s)..  sum(t,x(t,p,s)) =E= 1; * we don't allow here (t,p) combinations without preferencextp.fx(t,p)\$(preferences(p,t)=0) = 0; * objective: maximizezdef.. 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.optthreads 4\$offecho``

Note 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 reservedLicensee: 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 WindowsCplex 11.2.1, GAMS Link 34Cplex licensed for 1 use of lp, qp, mip and barrier, with 4 parallel threads. Reading parameter(s) from "C:\projects\test\cplex.opt">>  threads 4Finished 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.64Parallel 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 solutionFixing 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.000000Absolute gap:            0.000000Relative 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.817``

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

1. `` 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). ``

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

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

3. Hey, I have a VRP Problem and i dont know hoe to solve.

Need 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