Adding side constraints

How to add a set of constraints to control the search.

In order to produce a more realistic schedule, you can add a set of constraints that constrain the search to follow room preferences and teacher skills, and to produce more practical time tables.

To add side constraints:

Make sure that the chosen room handles the discipline taught.

  forall(r in InstanceSet)
    room[r] in PossibleRoomIds[r.discipline];

where PossibleRoomIds is a table of integer sets defined as:

{int} PossibleRoomIds[d in Discipline] = 
  {i | i in RoomId, z in Room
   :  (PossibleRoom[d,z] == 1) && (i == ord(Room,z))};

and PossibleRoom is a bi-dimensional table of Boolean values specifying which room can support which discipline.

int PossibleRoom[d in Discipline, x in Room] = 
  <x,d> in DedicatedRoomSet 
  || 0 == card({<z,k> | z in Room, k in Discipline
               : (<x,k> in DedicatedRoomSet) 
                 || (<z,d> in DedicatedRoomSet)});

Ensure that a given teacher has the required skills to teach a course.

  forall(r in InstanceSet) 
    teacher[r] in PossibleTeacherIds[r.discipline];

where PossibleTeacherIds is defined as:

{int} PossibleTeacherIds[d in Discipline] =
{i | i in TeacherId, z in Teacher 
   : i == ord(Teacher, z) 
     && d in PossibleTeacherDiscipline[z] };

and maps discipline names to the set of the indices for teachers who are capable of teaching this discipline, and PossibleTeacherDiscipline is defined as:

{string} PossibleTeacherDiscipline[x in Teacher] = {d | <x,d> in TeacherDisciplineSet };

and maps each teacher to the set of disciplines he can teach.

Ensure that, for a given class and a given discipline, the teacher remains the same.

  forall(c in Class, d in Discipline, r in InstanceSet 
         : r.Class == c && r.discipline == d) 
    teacher[r] == classTeacher[c, d];

where the additional classTeacher array is modeled as:

dvar int classTeacher[Class,Discipline] in TeacherId; // teacher working once per time point

Ensure that, if a course spans more than one unit of time, it does not cross half-day boundaries.
```
  forall(i in InstanceSet : i.Duration > 1)
    (Start[i] div HalfDayDuration) == ((End[i]-1) div HalfDayDuration);
```
Because the model contains only classes that fit half days, it is not necessary to write a similar “same day” constraint.

To also avoid having one discipline taught immediately after another, the data file contains a set of <discipline,discipline > tuples named NeedBreak.
```
NeedBreak =  { 
   <"Maths","Physics">,
   <"Biology","Physics">,
   <"Economy","Biology">,
   <"Geography","Economy">,
   <"History", "Geography"> 
};
```

Using this set, state exclusion constraints.

  forall(ordered i, j in InstanceSet, a,b in Discipline
         : (<b,a> in NeedBreak || <a,b> in NeedBreak)
         && i != j
         && i.Class == j.Class
         && ((i.discipline == a && j.discipline == b)
             || (i.discipline == b && j.discipline == a)))
    // courses do not belong to the same day
    ((Start[i] div DayDuration) != (Start[j] div DayDuration)) ||
    // courses do not belong to the same halfday
    ((Start[i] div HalfDayDuration) != (Start[j] div HalfDayDuration)) ||
    // courses are separated by BreakDuration
    ((Start[i] > End[j])*(Start[i] - End[j]) + 
     (Start[j] > End[i])*(Start[j] - End[i])) >= BreakDuration;

Along the same line, make sure the same discipline is not taught more than once a day.

  forall(ordered i,j in InstanceSet: i.discipline == j.discipline && i.Class == j.Class) 
    (Start[i] div DayDuration) != (Start[j] div DayDuration);

State that a discipline (such as Sport) is preferably taught in the morning.

  forall(d in MorningDiscipline, i in InstanceSet
         : i.discipline == d) 
    (Start[i] % DayDuration) < HalfDayDuration;

You can also add a symmetry-breaking constraint which ensures that course numbers, for a given requirement, appear in chronological order.
```
  forall(i, j in InstanceSet 
         : i.id < j.id 
           && i.requirementId == j.requirementId) 
    Start[i] < Start[j];
```