Constrain Modeling with multidimensional binary variable

[Ijakor]

Hey,

I want to extend a model used to create timetables for stundents. I would be very grateful for any help I can get. Given the binary decision variable X(c, r, t, s, h, d) which is 1, when class c in room r is taught by teacher t in subject s at hour h on day d and a parameter teaching requirement tr(s, c), which tells you the amount of hours a class c has to be taught in subject s. hl is an alias to h.

I want to:
1.) Limit the amount of hours taught on each subject per day to 2.

2.) Limit the amount of days a subject is taught to the ceil(teaching requirement / 2) -> Example: 3 hours of subject s are taught in class c: Max 2 days per class c and week where s is taught , 4 Hours -> max two days, 5 hours -> max 3 days and so on.

3.) If 2 hours per subject and day are assigned to a class, the teaching is supposed to be in block form, without interruption and in the same room by the same teacher.

My ideas:
1.):

Code: Select all

MaxTwo(c, s, d).. sum((t, h, r), X(c, r, t, s, h, d)) =l= 2;

<- this works I think
2.)

Code: Select all

MaxDays(s,c).. sum((r, t, h, d), X(c,r,t,s,h,d)) =l= ceil(tr(s,c)/2);

<- that does not make any sense, because it limits the amount of hours taught per week, not the amount of days taught, but I do not have a better idea.

3.)

Code: Select all

DoubleHours(c, r, t, s, h, d).. 2*(1-X(c, r, t, s, h, d)) =G= sum(hl$(ord(hl)>(ord(h)+1)), X(c, r, t, s, hl, d));

<- that does not work as intended as it does not prevent, that a different teacher teaches the same subject on the same day or that the room is changed

Do you have any idea how I can modify these equations so that they work as intended? Would be extremely thankful for any help.

Best Regards

[abhosekar]

2. you need another variable that is 1 if a subject is taught on a day x1(c,r,t,s,d)
To say that when x1 is 1 x is greater than 0, you can use the following constraint.

Code: Select all

 sum(h, x(c,r,t,s,h,d)) =l= M*(x1(c,r,t,s,d) )

3. You need a constraint that says if x(c,r,t,s,h,d) is 1 then all x except for t-1 and t+1 are 0.

Code: Select all

alias(t, tt)
 sum(tt $(ord(tt) > ord(t) + 1 and ord(tt) < ord(t) - 1), x(c,r,t,s,h,d)) =l= M*(1-x(c,r,t,s,h,d) )

This constraint along with the constraint you have in 1 ensures what you need. You will have to work out the details for border cases where t is 1 or card(t) and may be some syntax but this is an idea

- Atharv

[Ijakor]

Hey,

Thanks for the answer. Still stuck with 3 though, I have to say I do not really understand the constraint you gave, would you maybe try to explain further? I assume you meant to sum over all hours h, with alias(h,hh). I do not see the difference to my equation.

How is it achived, that the teacher t and room r have to stay the same for each double hour, if a double hour is assigned?

Going back to my original equation:

Code: Select all

alias (h,hh);
DoubleHours(c, r, t , s, h, d)..2*( 1- X(c,r, t,s h, d)) =g= sum(hh$(ord(hh)>ord(h+1), X(c, r, t, s, h, d));

i still do not see that every room and every teacher per subject, class and day stays the same.

I'll try and explain my point:
Lets assume, that class 1a is taught in room r001 by teacher t1 in subject s1 at hour h1 and day MO.
-> left side:
2*(1-1) = 0
-> right side:
X('1a','r001','t1','s1', 'h3','MO') + ... + X('1a','r001','t1','s1', 'h8','MO')
what means:
beginning in h3, subject s1 can't be taught by t1 to class 1a in r001 on MO anymore. What does t1 stop from switching rooms? What does the teacher stop from being swapped?

Thank you very much in advance. Really appreciate the help!

[abhosekar]

ahh. I see your point. The teacher assignment is free. Also you are right that i meant hh and not tt.

There are many ways to approach such problems. For example, you can declare a variable u(c,r,t,s,h,d) which forces iboth x(c,r,t,s,h-1,d) and x(c,r,t,s,h,d) to be equal (1).

x(c,r,t,s,h-1,d) =l= x(c,r,t,s,h,d) + M * (1-u(c,r,t,s,h,d) )
x(c,r,t,s,h-1,d) =g= x(c,r,t,s,h,d) - M * (1-u(c,r,t,s,h,d) )

You can do the same for subject s.

Now you can link `u` with the other binary variables to add more complexity to your formulation.
I don't think this is the only or best way, this is just one way.

I am getting too confused because t is not time. The problem you are solving is not easy, you will need to improve your formulation iteratively before you reach a satisfactory one.
Good luck.
- Atharv