# Package org.cpsolver.coursett.constraint

University Course Timetabling: Constraints.

See: Description

- Interface Summary
  Interface | Description
  --- | ---
  GroupConstraint.AssignmentPairCheck | Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), only need to implement this interface.
  GroupConstraint.AssignmentParameterPairCheck<P> | Group constraints that can have parameters need to implement this interface instead of `GroupConstraint.AssignmentPairCheck` or `GroupConstraint.PairCheck`.
  GroupConstraint.ConstraintTypeInterface | Constraint type interface
  GroupConstraint.PairCheck | Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), only need to implement this interface.

- Class Summary
  Class | Description
  --- | ---
  BreakFlexibleConstraint | The Break constraint checks for instructor lunch break or a break in general in between the given classes.
  ClassLimitConstraint | Class limit constraint.
  DepartmentSpreadConstraint | Departmental ballancing constraint.
  DiscouragedRoomConstraint | Discouraged room constraint.
  ExtendedStudentConflicts | An experimental global constraint that does not allow any two classes that can be attended by the same student to have a conflict.
  FlexibleConstraint | Flexible constraint.
  FlexibleConstraint.PlacementTimeComparator | Placement comparator: earlier placement first, shorter placement first if both start at the same time.
  GroupConstraint | Group constraint.
  GroupConstraint.ParametrizedConstraintType<P> | Constraint type with a parameter
  IgnoreStudentConflictsConstraint | Ignore student conflicts constraint.
  InstructorConstraint | Instructor constraint.
  JenrlConstraint | Join student enrollment constraint.
  MaxBlockFlexibleConstraint | The MaxBlock constraint checks for too big blocks of back-to-back classes of an instructor.
  MaxBreaksFlexibleConstraint | The MaxBreaks constraint limits the number of blocks of non back-to-back classes of an instructor on a day.
  MaxConsecutiveDaysFlexibleConstraint | The MaxConsecutiveDays constraint limits the number of consecutive days of week during which the given set of classes are taught.
  MaxDaysFlexibleConstraint | The MaxDays constraint limits the number of days of week during which the given set of classes are taught.
  MaxHalfDaysFlexibleConstraint | The MaxHalfDays constraint limits the number of half-days of week during which the given set of classes are taught.
  MaxHolesFlexibleConstraint | The MaxHoles constraint limits the number of free time (holes) for an instructor on a day.
  MaxWeeksFlexibleConstraint | The MaxWeeks constraint limits the number of weeks during which the given set of classes are taught.
  MinimizeNumberOfUsedGroupsOfTime | Minimize number of used groups of time within a set of classes.
  MinimizeNumberOfUsedRoomsConstraint | Minimize number of used rooms within the set of classes.
  NoStudentOnlineConflicts | An experimental global constraints that prohibits cases where a student has an online and in-person class on the same day.
  RoomConstraint | Room constraint.
  SoftInstructorConstraint | Soft version of the instructor constraint.
  SpreadConstraint | Spread given set of classes in time as much as possible.

- Enum Summary
  Enum | Description
  --- | ---
  FlexibleConstraint.FlexibleConstraintType | Flexible constraint types
  GroupConstraint.ConstraintType | Group constraint type.
  GroupConstraint.Flag | Group constraint building blocks (individual constraints that need more than `GroupConstraint.PairCheck`)

## Package org.cpsolver.coursett.constraint Description

University Course Timetabling: Constraints.
There are two types of basic hard constraints: resource constraints (expressing that only one course can be taught by an instructor or in a particular room at the same time), and group constraints (expressing relations between several classes, e.g., that two sections of the same lecture can not be taught at the same time, or that some classes have to be taught one immediately after another).
Except the constraints described above, there are several additional constraints which came up during our work on this lecture timetabling problem. These constraints were defined in order to make the automatically computed timetable solution acceptable for users from Purdue University.
First of all, if there are two classes placed one after another so that there is no time slot in between (also called back-to-back classes), distances between buildings need to be considered. The general feeling is that different rooms in the same building are always reasonable, moving to the building next door is to be discouraged, a couple of buildings away strongly discouraged, and any longer distance prohibited.
Each building has its location defined as a pair of coordinates [x,y]. The distance between two buildings is estimated by Euclides distance in such two dimensional space, i.e., (dx^2 + dy^2)^(1/2) where dx and dy are differences between x and y coordinates of the buildings. As for instructors, two subsequent classes (where there is no empty slot in between, called also back-to-back classes) are infeasible to teach when such difference is more than 200 meters (hard constraint). The other options (soft constraints) are:

- if the distance is zero (same building), then no penalty,
- if the distance is above zero, but not more than 50 meters, then the placement is discouraged,
- if the distance is between 50 and 200 meters, the placement is strongly discouraged

Our concern for distance between back-to-back classes for students is different. Here it is simply a question of whether it is feasible for students to get from one class to another during the 10-minute passing period. At present, the distance between buildings not more than 670 meters is considered as an acceptable travel distance. For the distance above 670 meters, the classes are considered as too far. If there is a student attending both classes, it means a student conflict (same as when these classes are overlapping in time).
Next, since the automatic solver tries to maximize the overall accomplishment of soft time and room constraints (preferences), the resultant timetable might be unacceptable for some departments. The problem is that some departments define their time and room preferences more strictly than others. The departments which have not defined time and room preferences usually have most of their classes taught in early morning or late evening hours. Therefore, we introduced the departmental time and room preferences balancing mechanism. The solver is trying to fulfill the time and room preferences as well as to balance the used times between individual departments. This means that each department should use each time unit (half-hour, e.g., Monday 7:30 - 8:00) in a similar portion to the other time units used by the department.
At first, for each department and time unit, there is a number stating how many times each time unit can be used (i.e., how many placements of all classes from the department can be placed over the time unit). For instance, if there are two 1 hour x 2 days per week classes, the time unit Wednesday 8:00 - 8:30 can be used four times, i.e., each of these classes can be placed either on Monday-Wednesday or Wednesday-Friday from 8:00 till 9:00. Than, an average fill factor is computed for each department and time unit. It is a ratio between the computed number of placements using the time unit and the total number of placements of all classes from the department (it is sixty for the above example with two classes, each class can be placed in thirty different times if all possible times are allowed). So, this factor states the overall usage of a time unit for a department. The reason for computing such number is the fact that some times are used much more than others (e.g., if the department has most of the classes in n hours hour x 3 days per week, Tuesday and Thursday are used much less than Monday, Wednesday and Friday). The initial allowance, which states how many times each time unit can be used by a department is computed from this maximal fill factor: it is increased by the given percentage (20% is used in our tests) and rounded upwards to the first integer number. The overall department balancing penalty of a solution is the sum of overruns of this initial allowance over all time units and departments. The intention is to keep this number as low as possible.
Finally, since all of the classes are at least two time slots long (60 minutes), an empty time slot of a room which is surrounded by classes on both sides (i.e., the room is not used for 30 minutes between two consecutive classes) is considered useless if no other class can use it. The number of such useless half-hours should be minimized. Also the situation when a room is occupied by a class which is using less than 2/3 of its seats is discouraged. Both these soft constraints are considered much less important than all the constraints described above.

Version:
  IFS 1.4 (Instructor Sectioning)
  Copyright (C) 2024 Tomáš Müller
  muller@unitime.org
  http://muller.unitime.org
  This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
  This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
  You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.
Author:
  Tomáš Müller