This page specifies the constraints appearing in the high school timetabling files used by HSEval.
Constraints in general
Assign resource constraints
Assign time constraints
Split events constraints
Distribute split events constraints
Prefer resources constraints
Prefer times constraints
Avoid split assignments constraints
Spread events constraints
Link events constraints
Order events constraints
Avoid clashes constraints
Avoid unavailable times constraints
Limit idle times constraints
Cluster busy times constraints
Limit busy times constraints
Limit workload constraints
A constraint is a condition that solutions should satisfy, if possible.
Each constraint has a set of points of application which are instance entities (such as resources or events). Recently, the specification was changed to require each constraint to have at least one point of application.
Given a solution, a non-negative integer cost is associated with each point of application. Each cost is calculated independently of the others, according to a formula defined on this page. A non-zero cost for some point of application indicates that the solution violates the constraint (fails to satisfy its condition) at that point.
Many types of constraints are defined, and more may be added in the future. Constraints of all types appear within the Constraints child category of the Instance category. Their syntax is
Constraints
*AssignResourceConstraint
*AssignTimeConstraint
*SplitEventsConstraint
*DistributeSplitEventsConstraint
*PreferResourcesConstraint
*PreferTimesConstraint
*AvoidSplitAssignmentsConstraint
*SpreadEventsConstraint
*LinkEventsConstraint
*OrderEventsConstraint
*AvoidClashesConstraint
*AvoidUnavailableTimesConstraint
*LimitIdleTimesConstraint
*ClusterBusyTimesConstraint
*LimitBusyTimesConstraint
*LimitWorkloadConstraint
For each constraint type there is a section of this page which describes the specifics of that constraint type. There are also several properties common to all constraint types, and those are described in the remainder of this section.
In general, a constraint has syntax
AnyConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
...
where AnyConstraint stands for any one of the child categories of Constraints listed above, and ... stands for additional child categories which vary with the constraint type. As usual, the Id attribute is used to reference the constraint from elsewhere in the file, while the Name child category is used when printing the constraint in human-readable form.
The evaluation of one constraint at one point of application (that is, the determination of a single cost) proceeds in two stages. In the first stage, a non-negative integer deviation is calculated. How this is done depends on the constraint type.
The second stage is common to all constraint types. It is influenced by the Required, Weight, and CostFunction child categories. All three have no attributes and no child categories, merely a body. The body of Required must be either true or false. The body of Weight must be an integer in the range 0 to 1000 inclusive. The body of CostFunction must be one of the three values in the table below.
The cost is calculated by the following formula:
That is, the cost function is applied to the deviation, producing an integer which is multiplied by the weight to obtain the cost. The permitted values for CostFunction are shown in this table:
CostFunction | Meaning |
Linear | The deviation, unchanged |
Quadratic | The square of the deviation |
Step | 1 if the deviation is non-zero, and 0 otherwise |
These values have changed recently. The table shows only the new values. The old values allowed a set of deviations to be defined at each point of application, whereas now the deviation at each point of application is a single integer, as stated above.
If Required is true, the constraint is a hard constraint and the cost is added to the infeasibility value of the solution. If Required is false, the constraint is a soft constraint and the cost is added to the objective value of the solution.
Instances should be encoded on the understanding that violations of hard constraints are serious defects, and that solvers aim to find solutions with very few hard constraint violations. Although the existence of such solutions is not guaranteed, realistic instances should have them. On the other hand, violations of soft constraints are normal and to be expected.
An assign resource constraint specifies that solution resources should be assigned resources. More importantly, it defines the cost of failing to make these assignments. It has syntax
AssignResourceConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Role
Its AppliesTo category has syntax
AppliesTo
+EventGroups
+Events
The syntax of EventGroups is
EventGroups
*EventGroup
where EventGroup has syntax
EventGroup Reference
and references an event group. The syntax of Events is
Events
*Event
where Event has syntax
Event Reference
and references an event. Together, these two child categories enumerate a set of events, namely the members of the event groups referenced plus the individual events referenced. It is not an error for an event to occur more than once in this enumeration, but such events are treated as having occurred only once. The compulsory Role child category has no attributes and no child categories, only a body.
For each event listed in the AppliesTo section that contains an unpreassigned event resource with the given Role (there can be at most one such event resource in each event), that event resource is one point of application of this constraint. It is not an error to include events in the AppliesTo section that do not have an event resource with the given Role, or that have a preassigned one, but such events are skipped by this constraint. However, as mentioned above, there must be at least one point of application.
Deviation. The deviation at one point of application of this constraint (one event resource) is the sum of the durations of the solution events that contain unassigned solution resources derived from the event resource. This deviation is converted into a cost as described above for constraints in general.
This constraint does not require an assigned resource to come from any particular set of resources (see the prefer resources constraint for that); it merely requires that some resource be assigned. Durations influence the cost on the principle that the longer a problem persists, the worse it is.
An assign time constraint specifies that solution events should be assigned times. More importantly, it defines the cost of failing to make these assignments. It has syntax
AssignTimeConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Its AppliesTo category has syntax
AppliesTo
+EventGroups
+Events
and defines a non-empty set of events in the same way as for the assign resource constraint above.
Each event listed in the AppliesTo section that does not contain a time preassignment is one point of application of this constraint. It is not an error to include events in the AppliesTo section that contain a time preassignment, but such events are skipped by this constraint. However, as mentioned above, there must be at least one point of application.
Deviation. The deviation at one point of application of this constraint (one instance event) is the total duration of those solution events derived from the instance event that are not assigned a time. This deviation is converted into a cost in the usual way.
This constraint does not require an assigned time to come from any particular set of times (see the prefer times constraint for that); it merely requires that some time be assigned.
A split events constraint places limits on the number of solution events that may be derived from a given instance event, and on their durations. It has syntax
SplitEventsConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
MinimumDuration
MaximumDuration
MinimumAmount
MaximumAmount
Its AppliesTo category has syntax
AppliesTo
+EventGroups
+Events
and defines a non-empty set of events in the same way as for the assign resource constraint above. These events are the points of application of this constraint. The MinimumDuration, MaximumDuration, MinimumAmount, and MaximumAmount child categories have no attributes and no child categories, only a body, whose value must be an integer.
Deviation. The deviation at one point of application of this constraint (one instance event) is the number of solution events derived from the instance event whose duration is less than MinimumDuration or greater than MaximumDuration, plus the amount by which the number of solution events falls short of MinimumAmount or exceeds MaximumAmount.
Further control over the durations assigned to solution events is provided by distribute split events constraints.
A distribute split events constraint places limits on the number of solution events of a particular duration that may be derived from a given instance event. It has syntax
AssignTimeConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Duration
Minimum
Maximum
Its AppliesTo category has syntax
AppliesTo
+EventGroups
+Events
and defines a non-empty set of events in the same way as for the assign resource constraint above. These events are the points of application of this constaint. As usual, there must be at least one point of application. The Duration, Minimum, and Maximum child categories have no attributes and no child categories, only a body, whose value must be an integer.
Deviation. The deviation at one point of application of this constraint (one instance event) is the amount by which the number of solution events derived from that instance event whose duration is Duration falls short of Minimum or exceeds Maximum.
Further control over the durations of solution events is provided by split events constraints.
A prefer resources constraint specifies that some resources are preferred for assignment to some solution resources. It has syntax
PreferResourcesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+ResourceGroups
+Resources
Role
Its AppliesTo category has syntax
AppliesTo
+EventGroups
+Events
and defines a non-empty set of events in the same way as for the assign resource constraint above. The compulsory Role child category has no attributes and no child categories, only a body. Exactly as for the assign resource constraint, the points of application of this constraint are those unpreassigned event resources which lie in the given events and have the given Role. As usual, there must be at least one point of application.
The syntax of the optional ResourceGroups child category is
ResourceGroups
*ResourceGroup
where ResourceGroup has syntax
ResourceGroup Reference
and references a resource group. The syntax of the optional Resources child category is
Resources
*Resource
where Resource has syntax
Resource Reference
and references a resource. Together, these two child categories enumerate a set of resources, namely the members of the resource groups referenced plus the individual resources referenced. These resources are the preferred resources. They must all have the same resource type. It is not an error for a resource to occur more than once in this enumeration, but such resources are treated as having occurred only once.
Deviation. The deviation at one point of application of this constraint (one event resource) is calculated by taking all the solution resources derived from the event resource that are assigned a resource that is not one of the preferred resources, and summing the durations of the solution events that those solution resources lie in.
This constraint ignores solution resources that are not assigned at all (the assign resource constraint handles those). The case of an event resource for which there is one set of acceptable resources and a smaller set of preferred resources may be modelled by having two prefer resource constraints that apply to that event resource. There is no need to use a prefer resources constraint merely to constrain assignments to be of resources of a certain type, since each event resource has a resource type, and the entire solution is rejected if a solution resource derived from it is assigned a resource of any other type.
A prefer times constraint specifies that some times are preferred for assignment to some solution events. It has syntax
PreferTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+TimeGroups
+Times
+Duration
Its AppliesTo category has syntax
AppliesTo
+EventGroups
+Events
and defines a non-empty set of events in the same way as for the assign resource constraint above. Exactly as for the assign time constraint, the points of application of this constraint are the members of this set of events that do not have a preassigned time.
The syntax of the optional TimeGroups child category is
TimeGroups
*TimeGroup
where TimeGroup has syntax
TimeGroup Reference
and references a time group. The syntax of the optional Times child category is
Times
*Time
where Time has syntax
Time Reference
and references a time. Together, these two child categories enumerate a set of times, namely the members of the time groups referenced plus the individual times referenced. These times are the preferred times. It is not an error for a time to occur more than once in this enumeration, but such times are treated as having occurred only once.
The optional Duration child category has no attributes and no child categories, only a body, whose value must be a positive integer.
Deviation. The deviation at one point of application of this constraint (one instance event) is the total duration of those solution events derived from that instance event that are assigned a time that is not one of the preferred times. If the optional Duration child category is present, solution events with durations other than Duration are ignored.
Solution events that are not assigned any time are ignored (the assign time constraint handles those). Restricting to solution events of a given duration is a practical necessity. For example, a solution event of duration 1 can be assigned the last time in a day, whereas a solution event of longer duration cannot. Thus, several prefer times constraints are typically needed, one for each duration. The prefer times constraint handles preferences arising from durations in this way, and also preferences for certain days or times of day, without distinguishing between them.
Each solution resource may be assigned only one resource, which attends the enclosing solution event for its full duration. However, when an instance event is split into solution events, each of its event resources is split into several solution resources, and a different resource may be assigned to each of these solution resources.
For a given event resource there are three cases:
An avoid split assignments constraint specifies that split assignments are undesirable for some event resources. It is needed to obtain the third case above. Its syntax is
AvoidSplitAssignmentsConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Role
Its AppliesTo category has syntax
AppliesTo
EventGroups
where EventGroups has syntax
EventGroups
*EventGroup
and EventGroup has syntax
EventGroup Reference
Each event group referenced is one point of application; the individual events of the event groups are not the points of application. The event groups referenced may be defined as Courses. Having event groups as points of application allows the constraint to coordinate resource assignments to a whole set of events, as needed when a course is defined as a set of separate events rather than as a single event that is expected to split.
The compulsory Role child category has no attributes and no child categories, only a body.
Deviation. The deviation at one point of application of this constraint (one event group) is calculated as follows. The events of the event group must all contain an event resource with the given Role, and the resource types of those event resources must be the same. The constraint examines all the solution resources derived from those event resources, and calculates the number of distinct resources assigned to them, ignoring unassigned solution resources (these are handled by the assign resource constraint). The deviation is the amount by which this number exceeds 1.
A spread events constraint specifies that the solution events of an event group should be spread out in time. Its syntax is
SpreadEventsConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
TimeGroups
Its AppliesTo category has syntax
AppliesTo
EventGroups
where the syntax of EventGroups is as for the avoid split assignments constraint above.
Each event group referenced is one point of application; the individual events of the event groups are not the points of application. The event groups referenced may be defined as Courses. Having event groups as points of application allows the constraint to evaluate the spread of times assigned to a whole set of events, as needed when a course is defined as a set of separate events rather than as a single event that is expected to split.
The syntax of TimeGroups is
TimeGroups
TimeGroup
where the syntax of TimeGroup is
TimeGroup Reference
Minimum
Maximum
Each TimeGroup category references a time group, but it also has two child categories which both have no attributes and no child categories of their own, just a body that must consist entirely of a non-negative integer, with Maximum not smaller than Minimum.
Deviation. The deviation at one point of application of this constraint (one event group) is calculated as follows. For each time group, find the number of solution events derived from the instance events of the event group that have a starting time (possibly preassigned) lying in the time group, and the amount by which this number falls short of the minimum or exceeds the maximum for the time group. The deviation for the event group is the sum, over all time groups, of these amounts. Solution events with no assigned time are ignored.
Note. Before Version 1.29, the result of evaluating a spread events constraint at one point of application was a set of deviations, one for each time group, not a single deviation. The single deviation used now is the sum of the old ones. This change does not change the cost of any solution to any instance expressed using the old versions of the current cost functions, since those old functions began by summing the deviations anyway.
A link events constraint specifies that certain events should be assigned the same times. Its syntax is
LinkEventsConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Its AppliesTo category has syntax
AppliesTo
EventGroups
where the syntax of EventGroups is as for the avoid split events constraint above. Each event group referenced is one point of application; the individual events of the event groups are not the points of application.
Deviation. The deviation at one point of application of this constraint (one event group) is calculated as follows. For each instance event of the event group, build the set of times that the solution events derived from that instance event are running (all their times, not just their starting times). Solution events with no assigned time are ignored. The deviation is the number of times that appear in at least one of these sets but not in all of them.
An order events constraint specifies that the times of two events should be constrained so that the first event ends before the second begins. Its syntax is
OrderEventsConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Its AppliesTo category has syntax
AppliesTo
EventPairs
where the syntax of EventPairs is
EventPairs
*EventPair
Each event pair is one point of application; its syntax is
EventPair
FirstEvent Reference
SecondEvent Reference
+MinSeparation
+MaxSeparation
FirstEvent and SecondEvent contain references to the two instance events whose times are to be constrained. MinSeparation and MaxSeparation have no attributes and no children, only a body, which must contain a single non-negative integer. MinSeparation is the minimum number of times that may separate the two events without incurring a cost. Its default value is 0. MaxSeparation is the maximum number of times that may separate the two events without incurring a cost. Its default value is infinity. For example, omitting both MinSeparation and MaxSeparation constrains FirstEvent to end before SecondEvent begins, nothing more.
Deviation. The deviation at one point of application of this constraint (one pair of instance events) is calculated as follows. If for either instance event there are no solution events, or there is a solution event whose time is unassigned, then the deviation is 0. Otherwise, find the maximum over all solution events derived from the first instance event of the time (considered here to be an integer, the position of the time in the chronological ordering) plus duration of that solution event, and find the minimum over all solution events derived from the second instance event of the time of that solution event. The amount by which the second of these two numbers minus the first exceeds MaxSeparation or falls short of MinSeparation is the deviation.
An avoid clashes constraint specifies that certain resources should have no clashes; that is, they should not attend two or more events simultaneously. Its syntax is
AvoidClashesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Its AppliesTo category has syntax
AppliesTo
+ResourceGroups
+Resources
The syntax of ResourceGroups is
ResourceGroups
*ResourceGroup
where ResourceGroup has syntax
ResourceGroup Reference
The syntax of Resources is
Resources
*Resource
where Resource has syntax
Resource Reference
Together, these two child categories enumerate a set of resources, namely the members of the resource groups referenced plus the individual resources referenced. These resources are the points of application of this constraint. It is not an error for a resource to occur more than once in this enumeration, but such resources are treated as having occurred only once.
Deviation. The deviation at one point of application of this constraint (one resource) is the sum, over all times when the resource is preassigned or assigned to two or more solution resources, of the number of solution resources it is preassigned or assigned to minus one. All times when the solution resources' solution events are running are included, not just their starting times.
Note. Before Version 1.29, the result of evaluating an avoid clashes constraint at one point of application was a set of deviations, one for each clashing time, not a single deviation. The single deviation used now is the sum of the old ones. This change does not change the cost of any solution to any instance expressed using the old versions of the current cost functions, since those old functions began by summing the deviations anyway.
An avoid unavailable times constraint specifies that certain resources are unavailable to attend any events at certain times. Its syntax is
AvoidUnavailableTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+TimeGroups
+Times
Its AppliesTo category has syntax
AppliesTo
+ResourceGroups
+Resources
They define a set of resources in the same way as for the avoid clashes constraint above. The syntax of the optional TimeGroups child category is
TimeGroups
*TimeGroup
where TimeGroup has syntax
TimeGroup Reference
and references a time group, which could be a Day or Week. The syntax of the optional Times child category is
Times
*Time
where Time has syntax
Time Reference
and references a time. Together, these two child categories enumerate a set of times, namely the members of the time groups referenced plus the individual times referenced. These times are the unavailable times. It is not an error for a time to occur more than once in this enumeration, but such times are treated as having occurred only once.
Deviation. The deviation at one point of application of this constraint (one resource) is the number of unavailable times during which the resource attends at least one solution event. Cases where the resource attends two or more solution events receive no special treatment (the avoid clashes constraint handles those).
A resource is busy at some time when it attends at least one solution event at that time. A resource is idle at some time (more precisely, idle with respect to a given time group) when it is not busy at that time but it is busy at some earlier time of the time group, and at some later time, taking the time group's times in the order in which they are defined in the file (chronological order).
For example, suppose the time group is the Wednesday times, and the resource is busy at the third and seventh times of that time group, and not busy at its other times. Then it is idle at the fourth, fifth, and sixth times of that time group, but not at its first or second times or after the seventh time.
A limit idle times constraint places limits on the number of times that resources may be idle. Its syntax is
LimitIdleTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
TimeGroups
Minimum
Maximum
Its AppliesTo category has syntax
AppliesTo
+ResourceGroups
+Resources
They define a set of resources in the same way as for the avoid clashes constraint above. The syntax of the TimeGroups child category is
TimeGroups
*TimeGroup
where TimeGroup has syntax
TimeGroup Reference
and references a time group, which could be a Day or Week. Each time group must be compact: that is, if it is non-empty then every time between the chronologically first and the chronologically last must be present. The Minimum and Maximum child categories have no attributes and no child categories of their own, just a body which must contain a single non-negative integer, with Minimum not exceeding Maximum.
Deviation. The deviation at one point of application of this constraint (one resource) is calculated as follows. For each time group, find the number of idle times with respect to that time group. The deviation is the amount by which the sum of these numbers exceeds Maximum or falls short of Minimum.
Note. This definition of the deviation has always been what was intended and what was implemented. But before Version 1.26, this documentation gave a different and therefore wrong definition of it. The compactness requirement was added recently, partly as a sanity measure and partly to keep things manageable for solvers.
A resource is busy at some time when it attends at least one solution event at that time, and busy during some time group if it is busy at one or more times of that time group. A cluster busy times constraint places limits on the number of time groups during which a resource may be busy. Its syntax is
ClusterBusyTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
TimeGroups
Minimum
Maximum
Its AppliesTo category has syntax
AppliesTo
+ResourceGroups
+Resources
They define a set of resources in the same way as for the avoid clashes constraint above. The syntax of the TimeGroups child category is
TimeGroups
*TimeGroup
where TimeGroup has syntax
TimeGroup Reference
and references a time group, which could be a Day or Week. The Minimum and Maximum child categories have no attributes and no child categories of their own, just a body which must contain a single non-negative integer, with Minimum not exceeding Maximum.
Deviation. The deviation at one point of application of this constraint (one resource) is the amount by which the number of given time groups during which the resource is busy falls short of Minimum or exceeds Maximum.
A resource is busy at some time when it attends at least one solution event at that time. A limit busy times constraint places limits on the number of times during certain time groups that a resource may be busy. Its syntax is
LimitBusyTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
TimeGroups
Minimum
Maximum
Its AppliesTo category has syntax
AppliesTo
+ResourceGroups
+Resources
They define a set of resources in the same way as for the avoid clashes constraint above. The syntax of the TimeGroups child category is
TimeGroups
*TimeGroup
where TimeGroup has syntax
TimeGroup Reference
and references a time group, which could be a Day or Week. The Minimum and Maximum child categories have no attributes and no child categories of their own, just a body which must contain a single non-negative integer, with Minimum not exceeding Maximum.
Deviation. The deviation at one point of application of this constraint (one resource) is the sum, over all time groups, of the amount by which the number of times that the resource is busy during that time group falls short of Minimum or exceeds Maximum. As a special case, when the number of times that the resource is busy is 0, the contribution to the deviation is 0. To enforce limits on the number of days when a resource is busy, use a cluster busy times constraint.
Note. Before Version 1.29, the result of evaluating a limit busy times constraint at one point of application was a set of deviations, one for each time group, not a single deviation. The single deviation used now is the sum of the old ones. This change does not change the cost of any solution to any instance expressed using the old versions of the current cost functions, since those old functions began by summing the deviations anyway.
The workload of an instance event is the value of its Workload child category if it has one, or its duration if not. The workload of an event resource is the value of its Workload child category if it has one, or the workload of the enclosing instance event if not. It is an integer. The workload of a solution resource sr lying in solution event se and derived from event resource er of event e is defined by the formula
where Duration(se) is the duration of se, Workload(er) is the workload of er, and Duration(e) is the duration of e. This value is a floating-point number.
A limit workload constraint places limits on the total workload of solution resources that certain resources are assigned to. Its syntax is
LimitWorkloadConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
Minimum
Maximum
Its AppliesTo category has syntax
AppliesTo
+ResourceGroups
+Resources
They define a set of resources in the same way as for the avoid clashes constraint above. The Minimum and Maximum child categories have no attributes and no child categories of their own, just a body which must contain a single non-negative integer, with Minimum not exceeding Maximum.
Deviation. The deviation at one point of application of this constraint (one resource) is the amount by which the total workload of the solution resources assigned that resource falls short of Minimum or exceeds Maximum, rounded up to the next integer.
Note. Before Version 1.13, this constraint was defined differently, in a way that avoided non-integral workloads. The new specification has been adopted because it is faster to evaluate, an important point for solvers, which must evaluate limit workload constraints many times while solving. Before Version 1.15, only events had workloads, not event resources. The change allows the workload associated with two event resources from the same event to differ.
Return to the HSEval home page.