HSEval Version 2.8 (March 2023)

High School Timetable File Format Specification: Constraints

This page specifies the constraints appearing in the high school timetabling files used by HSEval.

Constraints in general

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:

Cost = Weight * CostFunction(deviation)

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

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.

Assign resource constraints

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. Multiple occurrences of events cause constraint violations to be counted multiple times. 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.

Note. Before Version 1.38, this specification incorrectly stated that multiple occurrences of events were ignored.

Assign time constraints

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.

Split events constraints

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.

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.

Prefer resources 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.

Prefer times constraints

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.

Avoid split assignments constraints

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:

The event resource is preassigned. Then the solution resources derived from it are preassigned too, and there is nothing more to say about it. This case is typical of event resources of student group type.

The event resource is not preassigned, and it is acceptable for the value assigned to the solution resources derived from it to vary. This case might occur with event resources of room type: it may not matter if a class meets in a different room for each of its lessons.

The event resource is not preassigned, and it is preferable for the value assigned to the solution resources derived from it not to vary. This requirement, which has been called resource stability, is typical of event resources of teacher type: a class wants to meet the same teacher for all of its lessons, not different teachers for different lessons. When resource stability is wanted but not achieved, a split assignment is said to have been made.

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.

Spread events constraints

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.

Link events constraints

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.

Order events constraints

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.

Avoid clashes constraints

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. Multiple occurrences of resources cause constraint violations to be counted multiple times.

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.38, this specification incorrectly stated that multiple occurrences of resources were ignored.

Avoid unavailable times constraints

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

Limit idle times constraints

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.

Cluster busy times constraints

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.

Limit busy times constraints

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

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.

Limit workload constraints

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

Workload(sr) = Duration(se) * Workload(er) / Duration(e)

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. Each amount is rounded up to the next integer before being added to the sum.

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.

CostFunction	Meaning
`Linear`	The deviation, unchanged
`Quadratic`	The square of the deviation
`Step`	1 if the deviation is non-zero, and 0 otherwise