Vincent Barichard
email: vincent.barichard@univ-angers.fr

Corentin Behuet
email: corentin.behuet@univ-angers.fr

David Genest
email: david.genest@univ-angers.fr

Marc Legeay
email: marc.legeay@univ-angers.fr

David Lesaint
email: david.lesaint@univ-angers.fr

A Constraint Language For University Timetabling Problems

Keywords: University Timetabling, Domain-Specific Modeling Language, Constraint Programming, Resource Scheduling

We present a domain-specific modeling language for a class of university timetabling problems (UTP) that involve course scheduling, resource allocation and student sectioning. The UTP language combines a formal domain model and a rules formalism to state constraints. The model is based on a multi-scale schedule horizon (i.e., weeks, weekdays and daily slots), a hierarchical course structure (i.e., course parts, part classes and class sessions), and an extended set of resources (i.e., rooms, lecturers, students and student groups). Student groups must be formed to populate classes and class sessions are to be scheduled individually and allocated single or multiple rooms and lecturers. The model encodes sectioning constraints on classes, core scheduling constraints on sessions as well as compatibility, capacity and cardinality constraints on resource allocation. Rules allow to state conjunctions of constraints on selected sets of entities and sessions using a catalog of timetabling predicates and a syntax to group, filter and bind entities and sessions. As for implementation, the UTP language is based on XML and comes with a tool chain that flattens rules into constraints and converts instances to solver-compatible formats. We present here the abstract syntax of the UTP language and alternative constraint programming models developed in MiniZinc and CHR together with preliminary experiments on a real case study.

Introduction

Course and exam organization in universities involves strategic, tactical and operational decisions relating to curriculum design, student sectioning, course staffing, room planning, class scheduling and resource allocation [START_REF] Lindahl | Quality recovering of university timetables[END_REF]. These computational tasks and their overall coordination vary between countries and educational institutions as does the level of process automation and decision tool support [START_REF] Vrielink | Practices in timetabling in higher education institutions: a systematic review[END_REF]. In French universities for instance (see Figure 1), curricula are conventionally revisited every 5 years and students enroll in courses prior to each teaching period in the course of the academic year. Demand is matched by sectioning courses into classes, partitioning students into fixed groups, and populating classes with groups. Eligible groups, lecturers, rooms and equipment are then identified for each course before class sessions get scheduled and allocated the necessary resources. Each stage involves different stakeholders with their own requirements (faculty departments, administrative units, course owners, lecturers, tutors, etc.) and the workflow naturally allows for deviations and contingencies (marginal amendments to curricula on a yearly basis, late student registrations, staff absences, etc.). Various problem formulations together with data formats and algorithms have been proposed in the literature to tackle specific aspects of university timetabling including curriculum balancing [START_REF] Castro | Variable and Value Ordering When Solving Balanced Academic Curriculum Problems[END_REF]17,[START_REF] Rubio | Solving the Balanced Academic Curriculum Problem Using the ACO Metaheuristic[END_REF], student sectioning [START_REF] Müller | Comprehensive approach to student sectioning[END_REF]34], examination timetabling [13,[START_REF] Battistutta | Local search and constraint programming for a real-world examination timetabling problem[END_REF][START_REF] Mccollum | Setting the research agenda in automated timetabling: The second international timetabling competition[END_REF], curriculum-based or post-enrolmentbased course timetabling [START_REF] Mccollum | Setting the research agenda in automated timetabling: The second international timetabling competition[END_REF]10,[START_REF] Lewis | Post enrolment based course timetabling: A description of the problem model used for track two of the second international timetabling competition[END_REF]12,[START_REF] Goh | Improved local search approaches to solve the post enrolment course timetabling problem[END_REF][START_REF] Chen | A Survey of University Course Timetabling Problem: Perspectives, Trends and Opportunities[END_REF], tutor allocation [14], and minimal timetabling perturbation [START_REF] Lindahl | Quality recovering of university timetables[END_REF][START_REF] Lemos | Disruptions in timetables: A case study at universidade de lisboa[END_REF]. Modeling languages have also been developed, notably the XML language used in the 2019 international timetabling competition [START_REF] Müller | University course timetabling and International Timetabling Competition[END_REF][START_REF]ITC19: International Timetabling Competition[END_REF] (which we refer to as the ITC-2019 language) which pro-vides a catalog of constraints and supports model variability. We adopt a similar approach in this paper and introduce a class of university timetabling problems called UTP that involve course scheduling, resource allocation and student sectioning. We present a domain-specific language to model UTP instances (UTP language) which is designed around a formal domain model and a rules language to state constraints. Each instance is decomposed into a model of entities, a rule set and a solution component. Rules express collections of timetabling constraints on model entities and the solution component lists assignment decisions. The latter may be void, partial or inconsistent to accommodate different contexts (e.g., a solution for student sectioning to turn into a complete timetable, an outdated solution that must be revised or repaired).

Similarly to the ITC-2019 language, the UTP language adopts a multiscale schedule horizon (i.e., weeks, weekdays and daily slots), a mixed set of resources (i.e., students, student groups, rooms and lecturers), and a hierarchical course structure (i.e., course parts, part classes and class sessions). In our approach however, class sessions (a.k.a., class meetings) are considered as first-class objects that must be scheduled individually alongside resources. The model supports single-resource sessions (e.g., single lecturer) as well as multi-resource sessions (e.g., hybrid teaching), and encodes core constraints relating to student sectioning, session scheduling and resource allocation. All resources are assumed cumulative (i.e., rooms, lecturers and students may host, teach and attend overlapping sessions) but this policy may be overridden with disjunctive scheduling rules. The rules language effectively allows to enforce additional constraints on selected sets of sessions and entities (i.e., resources and course elements). Rules are expressed using a catalog of timetabling predicates and a comprehension syntax to group, filter and bind sessions and entities. Specifically, each rule denotes a conjunction of UTP constraints sharing the same predicate (e.g., periodicity of all lecture classes of a course) and constraints are technically generated through a rule flattening process.

Note that all constraints are handled as hard constraints and each UTP instance is reduced to a hard constraint satisfaction problem (CSP). The ability to model preferences and multi-criteria objectives by the means of soft constraints is paramount in course timetabling and will be the subject of future extensions. Likewise, the catalog of UTP predicates still lacks important constraints (e.g., gap, distribution and pattern constraints -see e.g. [START_REF] Aziz | University course timetabling and the requirements: Survey in several universities in the east-coast of Malaysia[END_REF][START_REF] Chen | A Survey of University Course Timetabling Problem: Perspectives, Trends and Opportunities[END_REF]) which will be gradually added in future versions.

As for implementation, the UTP language is based on XML and embedded in two constraint modeling languages, namely, MiniZinc [START_REF] Nethercote | Minizinc: Towards a standard cp modelling language[END_REF]3] and CHR [18]. We developed a tool chain consisting of a XML parser, a rule processor to flatten rules into constraints, and an encoder to convert the resulting instances to solver-compatible formats (see Figure 2). Beyond MiniZinc and CHR, constraint-based UTP instances may be used as inputs to any solver implementing the model and predicates of the UTP language. We do not discuss here the XML syntax of the language (the reader is referred to [1] which provides access to the detailed specification, the MiniZinc and CHR models, the Fig. 2 The UTP toolchain.

tool suite, and a benchmark of instances). Rather, we present the abstract syntax of the UTP language and provide semantics for the key components.

The remainder of the paper is organized as follows. Section 2 introduces the UTP language and draws a comparison with the ITC-2019 schema. Section 3 presents a generic constraint-based UTP model. Section 4 discusses its implementation using MiniZinc and CHR and the cross-validation of the models on a real instance. Section 5 concludes and discusses extensions of this work.

University Timetabling Problem

A UTP instance is defined by an entity model and a rules set. A solution to a UTP instance is a list of choices made for all the decisions at stake that satisfies the core constraints of the entity model and the constraints expressed by the rules. We provide in this section an informal description and set-theoretic semantics for the UTP language components, namely the entity model (Section 2.1), constraints (Section 2.2), rules (Section 2.3) and solution (Section 2.4). Section 2.5 draws a comparison between the UTP language and the ITC-2019 schema.

Entity model

The entity model of a UTP instance defines its schedule horizon, course structure and resources, as well as properties of entities and relational maps (see Figure 3 for a sketch of the meta-model and Figure 4 for a toy example). First, the entity model uses a time grid that decomposes into weeks, weekdays and daily slots. Weeks share the same weekdays and weekdays the same daily slots. The latter make up 24 hours and have the same duration. Note that neither successive weeks nor successive weekdays are assumed to be consecutive. The schedule horizon is implicitly defined by the series of time slots mapping to week, weekday and daily slot combinations. Slots hence serve as time points to represent start and end times of course sessions and to measure session duration, travel time and any gap between sessions.

Courses have a tree-structure wherein each course (e.g., Algorithms) decomposes into parts (e.g., Lecture and Lab), parts into classes (e.g., lecture classes A and B), and classes into sessions (e.g., sessions 1 to 10 for each lecture class). Class sessions are the elementary tasks to schedule when solving a UTP instance and the model fixes their number, duration and sequencing. First, the classes of a course part are decomposed into an identical number of sessions of equal duration, both constants being part-specific. Although this approach forbids classes using different session durations in a course part, it is paramount to capture requirements that rely on clear-cut sessions (e.g., starting lab classes after 2 lecture sessions, synchronizing the 5th sessions of the lab classes for a joint examination). Second, the sessions of a class are ranked in the model and must be sequenced accordingly in any solution (session 1 before session 2 . . . ). Note that sessions are considered uninterruptible and, in particular, may not overlap two days. UTP resources fall into 4 types, namely, rooms, lecturers, students and (student) groups. All the resources of an instance, except groups (see Section 2.4), are declared and typed in the entity model. In practice, upstream processes and decisions determine the suitable rooms, eligible lecturers, candidate students and allowed times for the different courses (e.g., faculties prescribing degree-specific time grids, departments implementing room pooling policies and naming lecturers for courses, students registering to courses). These compatibility constraints are modeled by associating sets of possible start times, rooms and lecturers to each course part and a set of registered students to each course. Each session then inherits the sets of allowed resources from the course part and the course it belongs to.

The entity model also encodes flow constraints that govern the distribution of resources over courses based on student registrations and capacity planning decisions (e.g., workload distribution between lecturers). First, each lecturer is allocated a fixed number of sessions in each course part he is eligible for, leaving lecturer-to-session assignment decisions to solvers. Second, each room allowed in a course part may be freely allocated to any session of the part (possibly none) but the model provides the flexibility to mark a room as mandatory in which case it will host or co-host all the sessions. As for students, the sectioning policy is implicit and complies with the course structure, i.e., each student must be assigned to a single class in each part of a course he has registered to and attend all sessions of these classes. In addition, the model supports group nesting constraints between classes to implement course-specific policies (e.g., aggregating student groups bottom-up from labs to lectures) or cross-course sectioning (e.g., imposing the same groups between classes of different courses of a curriculum).

Resource utilization is naturally subject to demand and capacity constraints. Since modalities differ from one environment to the next, the language supports disjunctive and cumulative resources. The default policy is to consider all students, groups, lecturers and rooms as cumulative resources, i.e., they can attend, teach or host simultaneous sessions. Note though that rules may be stated to make some resources fully disjunctive or to prevent specific sessions from overlapping. Support for cumulative resources is paramount to address flexible attendance requirements (e.g., students assigned optional tutoring sessions that may overlap with compulsory courses) or to handle multiclass events (e.g., rooms hosting several classes for an exam or a conference). The model imposes no limits on the number of parallel sessions lecturers and students may attend. Rooms however may only host class sessions whose cumulated headcount is within their capacity. Upper bounds on room capacity and class size are encoded for all rooms and classes and the model also allows uncapacitated rooms to cater for the case of virtual rooms.

The language also supports sessions using multiple resources of the same type. The need for multiple rooms or lecturers arises in practical situations (e.g., multi-room sessions for hybrid teaching, joint supervision of practical work sessions, exams requiring several monitors). To this end, the model associates to each course part the number of lecturers required per session and indicates whether the sessions are single-or multi-rooms. Note that sessions without lecturers or rooms are allowed (e.g., unsupervised student project sessions). The model enforces specific constraints to handle multi-room sessions which override the default room allocation policy. Specifically, students attending the session may be freely dispatched in rooms irrespectively of the group structure, the cumulated capacity of the allocated rooms is taken into account for hosting, uncapacitated rooms cannot be allocated, and the allocated rooms are considered disjunctive for the time of the session.

Note finally that the language provides users with the ability to label resources and course elements to define their own classes of entities (e.g., teams of lecturers, blocks of rooms). Labels together with built-in entity types and identifiers are used to filter entities and to scope rules appropriately.

We formalize below the entity model and introduce notations that will be used thereafter. Let E denote the set of entities and S the set of sessions. E is partitioned into a set of courses C, a set of course parts P , a set of classes K, a set of students U , a set of lecturers L, a set of rooms R, and the singleton domain of courses C * (C * = {C}). Let E = {C * , C, P, K, U, L, R} denote the set of entity types (E = ∪ X∈E X) and ≺ = {(C * , C), (C, P ), (P, K), (K, S), (U, C), (L, P ), (R, P )} denote the relation over E ∪ {S} that models the course hierarchy and the distribution of resource types over course components.

≺ * denotes the transitive closure of ≺ over E ∪ {S} and d X,Y : X → 2 Y denotes the function mapping each element of X to its set of compatible elements in Y for each pair X≺ * Y . For instance, d R,P represents the distribution of rooms over course parts, d P,K the decomposition of course parts into classes, d K,S the decomposition of classes into sessions, and d R,S the inferred distribution of rooms over sessions. The functions corresponding to the pairs of ≺ are directly encoded in the entity model and the remaining functions are defined inductively using recursive aggregation.

We shall denote by d X,Y i the image of entity i of type X over 2 Y and by d Y,X the inverse of d X,Y . Equation (1) below models the hierarchical decomposition of course elements 1 , Equation ( 2) is the closure rule over ≺ * , and Equation (3) models inverse maps.

∀(X, Y ) ∈ {(C * , C), (C, P ), (P, K), (K, S)} : Y = ⊔ i∈X d X,Y i (1) ∀X, Y, Z ∈ E ∪ {S} : X ⪯ * Y ⪯ * Z ⇒ (∀i ∈ X : d X,Z i = ⊔ j∈d X,Y i d Y,Z j ) (2) ∀X, Y ∈ E : X ⪯ * Y ⇒ (∀i ∈ X, j ∈ Y : j ∈ d X,Y i ⇔ i ∈ d Y,X j ) (3)
Table 1 provides the full list of constants, sets, properties and relational maps encoded in the entity model. 2

Predicates and constraints

UTP constraints apply to pairs, called e-maps, which associate an entity with a non-empty subset of its compatible sessions. Constraints are built with predicates whose signature includes e-map variables, the number of which is referred to as the arity of the predicate. Note that some predicates may also accept parameters. Let F = ∪ X∈E {(e, S ′ ) | e ∈ X, S ′ ⊆ d X,S e ∧ S ′ ̸ = ∅} denote the set 1 ⊔ denotes the disjoint union operation, i.e. set union over pairwise disjoint sets. 2 The following rules apply. Every predicate may be used indistinctly with e-maps defined on course elements or on resources. E-maps defined on resources are interpreted as conditional session-to-resource assignments when checking constraints whereas e-maps defined on course elements are unconditional assignments since they model constitutive sessions. In other words, a constraint is only evaluated on the sessions for which its e-map arguments and the considered solution propose the same entity assignment. 3 3 Formally, let x E,S e be the variable denoting the set of sessions assigned to entity e and S ′ 1 , . . . , S ′ m be sets of sessions, the conditionality of a constraint c is stated as follows:

H = {i.d.m + j.m + k | 0 ≤ i < w, 0 ≤ j < d, 1 ≤ k ≤ m}. For each class k in part p, {rank S s | s ∈ d K,S k } = {1, . . . , |d K,S k |}, and parents K,K k ̸ ⊂ d P,K p . For each pair of sessions s, s ′ , (s, s ′ ) ∈ O iff d S,K s = d S,K
(x E,S e 1 = S ′ 1 ∧ . . . ∧ x E,S em = S ′ m ) ⇒ (c((e 1 , S 1 ), . . . , (em, Sm), p 1 , . . . , pn) ⇔ c((e 1 , S 1 ∩ S ′ 1 ), . . . , (em, Sm ∩ S ′ m ), p 1 , . . . , pn)).
It follows that a constraint is evaluated on every session that is mapped to a course element by one of its e-map arguments. Constraints that apply exclusively to course elements are therefore unconditional. Note also that the use of e-maps that model the whole set of sessions compatible with an entity will necessarily constrain any session that may be assigned to this entity. Table 2 lists the predicates of the language and indicates which are variadic or parametric. The first predicates same daily slot, . . . , same slot enforce common restrictions on the start times of the targeted sessions (e.g., sessions starting the same day). Additionally, any start time interval may be forbidden by passing its start and end points as parameters to predicate forbidden period. Predicates at most daily and at most weekly upperbound the number of sessions scheduled daily or weekly within the given time interval. sequenced is a n-ary predicate (n ≥ 2) which constrains the latest session of the i-th e-map to end before the earliest session of i + 1th e-map (i = 1..n -1). Predicate weekly ensures sessions are scheduled weekly without presuming any particular sequencing. Predicate no overlap ensures sessions do not overlap in time and is typically used to model disjunctive resources. Predicate travel factors in any travel time incurred between consecutive sessions hosted in distant rooms. The travel time matrix is a parameter of the predicate. same rooms, same students and same lecturers require that sessions be assigned to the same set of rooms, students or lecturers. Predicate adjacent rooms require that sessions be hosted in adjacent rooms based on an adjacency graph passed as a parameter. Lastly, predicate lecturer distribution distributes the volumes of sessions represented by the different e-map arguments among different lecturers. Lecturers and session volumes are parameters of the predicate.

Rules

Rules are used to state conjunctions of constraints and in particular single constraints. Each rule is defined by a universally quantified formula which bounds the domains of the e-map variables of a given predicate. The collection of constraints hence represented is derived by instantiating the predicate with each tuple of e-maps belonging to the cross-product of the prescribed domains. E-map domains are not given in extension but represented using a language of selectors allowing to generate and filter e-maps. Let F denote the language of e-map domain selectors, a UTP rule has the form

c(F 1 , . . . , F m , p 1 , . . . , p n ) ( 5
)
and is interpreted by the formula

∀(e 1 , S 1 ) ∈ F 1 , . . . , (e m , S m ) ∈ F m : c((e 1 , S 1 ), . . . , (e m , S m ), p 1 , . . . , p n ) ( 6
)
where c is a predicate symbol of arity m, F 1 , . . . , F m are selectors (F i ∈ F, i = 1 . . . m), F i denotes the domain of e-maps represented by selector F i ∈ F, and p 1 , . . . p n are values for the parameters of c (n ≥ 0), .

The language of selectors allows to target entities based on type, label or identifier and to filter their sets of sessions based on session rank and mutual compatibility with other entities. It is complete in the sense that it allows to construct any domain of e-maps whose entities share the same type. For instance, one may construct the e-maps which associate any of the rooms labeled Building-A with the compatible sessions of rank 2 or 4 that are also constitutive of course course-1 or class class-3. A selector combines a generator and an optional list of filters. Generators and filters are triples (T i , L i , O i ) consisting of an entity type T i , an entity label or identifier L i and a subset of session ranks O i (a.k.a., session mask), the latter two elements being optional. A selector matches any e-map whose entity satisfies the type, label and identifier constraints of the generator and whose image includes any compatible session satisfying the mask of the generator and one of the filters. Note that rules featuring null selectors are discarded during the flattening stage.

Let

F = ∪ n≥1 (E × L * × 2 O ) n . Each selector d = ((T 1 , L 1 , O 1 ), . . . , (T k , L k , O k )) decomposes into a generator (T 1 , L 1 , O 1 )
d Ti,S [L i ] d O,S [O 1 ∩ O i ] ∧ S ′ ̸ = ∅ where d X,Y [X ′ ] = i∈X ′ d X,Y i with X ′ ⊆ X .

Solution

The solution component includes assignment decisions relating to the choice of slots and resources for sessions, the placement of students in groups and the assignment of groups to classes. The solution hence represented may be partial, even empty, and does not have to be consistent with the constraints built in the entity model or entailed by the rules. The support for partial solutions allows to tackle subproblems using separate UTP instances and solution seeds. For instance, a scheduling instance may be defined on the basis of partial and consistent solutions pre-generated for the student sectioning and resource allocation subproblems. Likewise, the support for inconsistent solutions is paramount to repair solutions that have become inconsistent due to unforeseen changes. Student groups are considered a by-product of student sectioning. For this reason, groups may only be listed in the solution component, not in the entity model, and defined both by the students they include and the classes they are assigned to. This sectioning process is subject to different constraints. First, students are partitionned into groups and students are inextricably bound to their group. Second, a group may only include students with identical course registrations. Third, group-to-class assignments must comply with any subgroup inclusion constraint stated in the entity model.

Related work

We highlight here the main differences between the UTP language and the ITC-2019 language (ITC-2019 for short).

A first difference between the two frameworks lies in the representation of the possible times a class can meet. In UTP, a class is defined by a single sequence of sessions of equal duration and the problem is to schedule each session. In ITC-2019, a class is given alternative fixed session schedules (times elements in the XML schema) and the problem is to choose one of the schedules for the class. A schedule is the repetition over a set of weeks of one or more sessions that have the same duration and start on specific days of the week at the same predefined time (daily slot). The two representations are not reducible to one another. For instance, alternative schedules using different session durations cannot be modeled in UTP. Conversely, class schedules where sessions do not necessarily start on the same daily slot cannot be modeled in ITC-2019. Nevertheless, basic class schedules may be represented in either approach by stating ITC-2019 constraints or UTP rules on classes. For instance, a class meeting every week on the same day and the same daily slot, both being subject to time restrictions, may be modeled using same daily slot, weekly and forbidden period constraints. The implementation of a more comprehensive reduction method will be the subject of future work.

Second, ITC-2019 represents alternative course configurations by introducing an intermediate layer in the course hierarchy that sits between courses and parts. The configurations of a course typically differ in their number of (sub)parts and are mutually exclusive from a student sectioning standpoint, that is, a registered student must be assigned a single configuration and attend all of its parts. This feature is not currently supported in UTP. As for resources, UTP explicitly represents lecturers on par with rooms whereas ITC-2019 only models rooms. UTP also provides the flexibility to allocate different resources within a class (and specify lecturer workload in particular) whereas the same room must be allocated in ITC-2019. Additionally, UTP supports multi-resource sessions whereas ITC-2019 is restricted to single-room sessions.

Lastly, the two constraint languages present important differences. While ITC-2019 constraint predicates apply to classes, UTP predicates apply to any set(s) of sessions and may be used in particular on individual sessions, hence granting finer-grained control. Besides, UTP rules and the selector language allows to constrain any class of resources or course elements in a concise way.

Lastly, the ITC-2019 schema addresses the timetabling problem as a combinatorial optimization problem. It includes a cost function weighting 4 criteria which respectively penalize the choice of sessions and rooms for the classes, the violations of constraints and the overlapping of sessions per student. In its current version, the UTP language addresses the problem as a hard constraint satisfaction problem. The integration of soft constraints and the possibility of aggregating penalties or preferences, either in solution generation or repair contexts, is under investigation.

A Constraint-Based Model for UTP

We introduce in this section a constraint-based model for UTP instances. The model of an instance combines the constraints associated to the entity model and the constraints resulting from the flattening of the rules, if any. The former are decomposed into 4 fragments relating to student sectioning, resource distribution, session scheduling and resource allocation. We present each fragment in turn by reusing notations of Table 1, illustrate the modeling of some predicates before discussing opportunities for model reformulations on a perinstance basis. Note that some constraints are given a naive formulation to clarify semantics and more efficient implementations using MiniZinc and CHR will be discussed in Section 4. Table 3 The decision variables.

Student Sectioning

The sectioning constraints partition students into groups and assign groups to classes while satisfying sectioning rules and class size upper-bounds. Constraint (1) ensures the groups partition the set of students. Constraint (2) prevents the clustering of students who register to different courses. Constraint (3) ensures that classes of a course part have no shared groups and Constraint (4) that the group of a student attends each part of a course he is registered to. Constraint [START_REF] Abdennadher | CHR: A Flexible Query Language[END_REF] implements the parent relationships between classes. Constraint ( 6) ensures maximum class size is never exceeded by the number of students in its groups. Note that expressions (g

∈ x K,G k
) in this contraint denote pseudo-boolean variables. The same notation is used for convenience in other constraints.

U = g∈G x G,U g (1) ∀u, u ′ ∈ U, d U,C u ̸ = d U,C u ′ , g ∈ G : {u, u ′ } ⊈ x G,U g (2) ∀p ∈ P, k, k ′ ∈ d P,K p , k ̸ = k ′ : x K,G k x K,G k ′ = ∅ (3) ∀u ∈ U, g ∈ G : (u ∈ x G,U g ) → p∈d U,P u k∈d P,K p (g ∈ x K,G k ) (4) ∀k ∈ K, k ′ ∈ parents K,K k : x K,G k ⊆ x K,G k ′ (5) ∀k ∈ K : maxsize K k ≥ g∈G |x G,U g |.(g ∈ x K,G k ) (6)

Resource Distribution

Resource distribution involves domain, cardinality and basic summation constraints. Constraint [START_REF] Barichard | Quantified constraint handling rules[END_REF] defines the allowed rooms and allowed lecturers per session. Constraint (8) models single-room sessions and Constraint ( 9) models mandatory rooms of course parts. Constraint (10) 15) models multi-room class sessions and enforces exclusive access to their rooms. This constraint is formulated using auxiliary predicate split(w, S 1 , S 2 ) (18) which ensures no session of S 1 overlaps with a session of S 2 if both are assigned to resource w. We provide a naive decomposition of this predicate using Predicate [START_REF] Frühwirth | Constraint Handling Rules[END_REF]. Constraints ( 16) and ( 17) model room utilization and capacity limits and use auxiliary variables y r,k,s,h . y r,k,s,h models the number of students attending session s of class k in room r at time h and is defined using auxiliary constraint [START_REF]Constraint Handling Rules: Compilation, Execution, and Analysis[END_REF]. Constraint ( 16) is the default cumulative constraint which applies to non-virtual rooms when allocated to single-room sessions. Constraint (17) handles the specific case of multi-room sessions and ensures the cumulated capacity of the rooms used by a multiroom session exceeds the number of students attending the session. Note that the constraint is purely quantitative and allows each individual group to be distributed over different rooms. x S,H s

+ length S s ≤ x S,H s ′ (14) ∀k ∈ d P,K [M ] : r∈d K,R k split(r, d K,S k , d R,S r \ d K,S k ) (15) ∀r ∈ R \ V : h∈H capacity R r ≥ p∈d R,P r \M k∈d P,K p s∈d K,S k y r,k,s,h (16) ∀p ∈ M : h∈H k∈d P,K p s∈d K,S k r∈d P,R p (r ∈ x S,R s ).capacity R r ≥ max r∈d P,R p y r,k,s,h (17)
Let W ∈ {R, L, U }, w ∈ W, S 1 , S 2 ⊆ S :

split(w, S 1 , S 2 ) ↔ s1∈S1,s2∈S2 s1̸ =s2 (w ∈ x S,W s1 ∩ x S,W s2 → split(s 1 , s 2 )) (18)
Let s, s ′ ∈ S :

split(s, s ′ ) ↔ (x S,H s + length S s ≤ x S,H s ′ ∨ x S,H s ′ + length S s ′ ≤ x S,H s ) (19) Let r ∈ R, k ∈ K, s ∈ S, h ∈ H : y r,k,s,h = (r ∈ x S,R s ).(x S,H s ≤ h ∧ h ≤ x S,H s + length S s ) . g∈G |x G,U g |.(g ∈ x K,G k ) (20)

UTP Predicates

We present a subset of UTP constraint predicates, namely, forbidden period (21), same weekday [START_REF] Goh | Improved local search approaches to solve the post enrolment course timetabling problem[END_REF], same rooms [START_REF] Hentenryck | Constraint logic programming[END_REF], no overlap (24) and sequenced [START_REF] Jaffar | Constraint logic programming: A survey[END_REF]. Note that forbidden period accepts start and end point parameters. Predicate no overlap uses auxiliary predicate split for resources (18) and a variant for course elements [START_REF] Lemos | Disruptions in timetables: A case study at universidade de lisboa[END_REF].

Let X ∈ E, e ∈ X, S ′ ⊆ d X,S e , h, h ′ ∈ H (h < h ′ ). f orbidden period((e, S ′ ), h, h ′ ) ↔ s∈S ′ (x S,H s + length S s ≤ h ∨ h ′ < x S,H s ) (21)
same weekday((e, S ′ ))

↔ s∈S ′ x S,H s /d = (x S,H s + length S s )/d (22)
same rooms((e, S ′ ))

↔ s,s ′ ∈S ′ (x S,R s = x S,R s ′ ) (23)
no overlap((e, S ′ )) ↔ split(e, S ′ , S ′ ) (

Let i ∈ {1, . . . , n}, X i ∈ E, e i ∈ X i , S i ⊆ d Xi,S ei : sequenced((e 1 , S 1 ), . . ., (e n , S n ))

↔ j=1...n-1 max s∈Sj (x S,H s + length S s ) ≤ min s∈Sj+1 x S,H s (25)
Let X ∈ {C * , C, P, K}, e ∈ X, S 1 , S 2 ⊆ S :

split(e, S 1 , S 2 ) ↔ s1∈S1,s2∈S2 s1̸ =s2 (e ∈ d S,X s1 ∩ d S,X s2 → split(s 1 , s 2 )) (26)

Reformulation

The model presented above is generic and may be adapted on a per instance basis depending on the features and rules at stake. We discuss here a few variants of the UTP problem which provide opportunities for model reformulation.

When instances only involve single-room sessions (M = ∅), one may adopt integer or enumerated room allocation variables instead of set variables x S,R s and rewrite constraints accordingly. In the same way, lecturer assignment variables and constraints may be adapted when a single lecturer is required per session. Note that hybrid models mixing single or multi-resource session variables may be considered too. The temporal model may also be simplified when the time grid is coarse-grain and guarantees no session can span over consecutive start times (∀s ∈ S, length S s ≤ min({h

′ -h | h, h ′ ∈ d P,H [P ] ∧ h < h ′ }
). This situation occurs in institutions that impose a common time grid to ensure sessions (with any travel time incurred) necessarily fit in each time slot. If so, sessions may be handled as time points rather than time intervals and temporal predicates and constraints may be adapted. Capacity constraints may also be simplified for disjunctive rooms. A room is disjunctive if a no overlap constraint is stated on the whole set of its compatible sessions (r ∈ D ↔ no overlap(r, d R,S r ) where D ⊆ R denotes the set of disjunctive rooms). If so, the default cumulative constraint ( 16) may be overridden by Constraint [START_REF] Lewis | Post enrolment based course timetabling: A description of the problem model used for track two of the second international timetabling competition[END_REF].

∀r ∈ D : h∈H k∈d R,K r capacity R r ≥ max s∈d K,S k y r,k,s,h (27)
4 Constraint Programming Implementation

In this section, we present two constraint-based models for UTP instances developed in MiniZinc and CHR. The two models use the same arrays, functions and constants for representing input data. We do not list them here but they are easily understandable such as part sessions which gives the set of sessions constitutive of a part, session rooms which gives the set of allowed rooms for a session, week which gives the week of a slot, and nr weekly slots which is the number of slots in a week.

MiniZinc model

MiniZinc is a high-level language to model constrained optimization problems [START_REF] Nethercote | Minizinc: Towards a standard cp modelling language[END_REF]3]. MiniZinc models are translated into Flatzinc [4] which allows to interface different types of solvers including solvers on finite domain CSPs such as Gecode [START_REF]Generic Constraint Development Environment[END_REF]. The MiniZinc model for UTP is presented in Table 5 and based on the decisions variables listed in Table 4. The model uses some of the global constraints supported in MiniZinc which are dedicated to scheduling problems.

array[U] of var G:

x group group assigned to a student array[K] of var set of G: x groups set of groups assigned to a class array[S] of var set of R:

x rooms set of rooms allocated to a session array[S] of var set of L:

x lecturers set of lecturers allocated to a session array[S] of var H:

x slot starting slot of a session Sectioning constraints partition students into groups and assign each group to a class according to sectioning rules and class size thresholds. Constraint (1) allows students to be part of the same group only if they are registered to the same courses. [START_REF]Generic Constraint Development Environment[END_REF] imposes that every student attends all the part of the courses to which he is registered. (3) ensures that classes from the same part do not have any common group. (4) implements the parent-child relation between classes. Lastly, [START_REF] Abdennadher | CHR: A Flexible Query Language[END_REF] checks that the groups fit in the class they have been assigned to.

Resource distribution relies on domain, cardinality and sum constraints. Constraints ( 6) and ( 7) define available rooms and lecturers for each session. [START_REF] Battistutta | Local search and constraint programming for a real-world examination timetabling problem[END_REF] forces the number of rooms allocated to a session according to the specific requirements of the course part (i.e., no room, single-room or multi-room). ( 9) allocates the required number of lecturers to a session and (10) checks that every lecturer has the right number of sessions in a part.

Session scheduling and resource allocation involves positioning, sequencing, non-overlaping and capacity constraints. Constraint [START_REF] Betz | Linear-logic based analysis of constraint handling rules with disjunction[END_REF] defines the allowed slots for each session. (12) forbids a session to be on two days. (13) sequences the sessions of a class according to their rank. Constraints ( 14) and (15) model multi-room sessions and the exclusive access to their rooms. (14) makes disjunctive any resource that is allocated to a multi-room session while it is hosting the session. [START_REF] Castro | Variable and Value Ordering When Solving Balanced Academic Curriculum Problems[END_REF] ensures that the number of students attending a multi-room session do not exceed the cumulated capacity of the allocated rooms. ( 16) models the mandatory rooms to be allocated. ( 17) models the default cumulative capacity constraint controlling the allocation of non-virtual rooms to single-room sessions. This constraint uses the cumulative global constraint of MiniZinc (see [START_REF] Beldiceanu | A new multi-resource cumulatives constraint with negative heights[END_REF] for the Gecode implementation) which MiniZinc also reuses to rewrite the global disjunctive constraint.

Table 5 also presents some UTP predicates when the targeted resources are rooms. (18) implements the forbidden period predicate that takes the start and end time slots of the period as parameters. [START_REF] Frühwirth | Constraint Handling Rules[END_REF], [START_REF]Constraint Handling Rules: Compilation, Execution, and Analysis[END_REF] and ( 21) model same weekday, same rooms and sequenced predicates, respectively. ( 22) implements the no overlap predicate that relies on the disjunctive global constraint.

4.2 CHR model CHR (for Constraint Handling Rules) [18,[START_REF] Frühwirth | Theory and practice of constraint handling rules[END_REF][START_REF] Frühwirth | Constraint Handling Rules[END_REF][START_REF]Constraint Handling Rules: Compilation, Execution, and Analysis[END_REF] are a committed-choice language consisting of multiple-heads guarded rules that replace constraints by more simple constraints until they are solved. CHR are a special-purpose language concerned with defining declarative constraints in the sense of Constraint logic programming [START_REF] Hentenryck | Constraint logic programming[END_REF][START_REF] Jaffar | Constraint logic programming: A survey[END_REF]. CHR are a language extension that allows to introduce user-defined constraints, i.e. first-order predicates, into a given host language as Prolog, Lisp, Java, or C/C++. CHR have been extended to CHR ∨ [START_REF] Abdennadher | CHR: A Flexible Query Language[END_REF] that introduces the don't know nondeterminism in CHR [START_REF] Betz | Linear-logic based analysis of constraint handling rules with disjunction[END_REF]. This nondeterminism is freely offered when the host language is Prolog and allows to specify easily problems from the NP complexity class.

To model and solve UTP instances with the CHR language, we use the CHR++ solver [START_REF] Barichard | Quantified constraint handling rules[END_REF] (for Constraint Handling Rules in C++), which is an efficient integration of CHR in the programming language C++.

The full model for CHR++ is too long to be detailed here4 . We give in Table 7 the list of constraints taken into account by the solver. The decision variables to be instantiated are given in Table 6. They are similar to those of the MiniZinc model, only the end-of-session variables are added. To simplify its implementation, the model is partly non-cumulative and some resources such as lecturers cannot be shared. It also considers that the sectioning and allocation of students to groups is done beforehand. Thus, computing a solution amounts to finding a consistent resource allocation while placing the schedules for all sessions.

Several constraints can be set at the instance analysis stage. This is the case for constraints (1) to (9) of Table 7. Constraints (2), (3) and (4) filter the domains by removing the rooms, lecturers or time slots which are impossible by construction of the instance. Constraint [START_REF] Abdennadher | CHR: A Flexible Query Language[END_REF] ensures that a session starts and ends on the same day by removing from the domain values that contradict it.

Other constraints are set and managed by rules which monitor modifications to the domains of variables. This is the case for Constraint (1) which ensures the integrity of the start and end of session variables. The same is true for (6) which ensures that the number of lecturers teaching a session is

]) ≥ 1 (7) ∀k ∈ K, ∀s, s ′ ∈ class sessions[k], s.t. rank(s) < rank(s ′ ) : before(s, s ′ ) (8) ∀k 1 , k 2 ∈ K, s.t. ∃g 1 ∈ class groups[k 1 ], ∃g 2 ∈ class groups[k 2 ], avec g 1 = g 2 : ∀s 1 ∈ class sessions(k 1 ), s 2 ∈ class sessions(k 2 ) : disjunct(s 1 , s 2 ) (9) Static predicates : f orbidden period((e, S ′ ), h, h ′ ) = ∀i ∈ S ′ : (x slot start[i] + length(i) ≤ h) ∨ (x slot start[i] > h ′ ) (10
] ∩ x lecturers[s 2 ] ̸ = ∅ ⇒ disjunct(s 1 , s 2 ) (17) ∀k 1 , k 2 ∈ K, ∀s 1 ∈ class sessions[k 1 ], ∀s 2 ∈ class sessions[k 2 ] s.t. s 1 ̸ = s 2 : x rooms[s 1 ] ∩ x rooms[s 2 ] ̸ = ∅ ⇒ disjunct(s 1 , s 2 ) ( 18
)
Table 7 Constraints and predicates of the CHR model.

valid and (7) which checks that the number of rooms allocated to a session corresponds to what is required in the instance. We give as an example the CHR++ rule which checks the integrity of the variables of beginning and end of session. The rule uses a plus propagator to ensure consistency of the constraint. This is triggered as soon as a domain of a variable is updated: session_slot(_, S_Start, S_End, S_Length) =>> CP::Int::plus(S_Start, (*S_Length)-1, S_End);;

We use CHR++ which allows us to manipulate values associated with logical variables and to wake up the corresponding rules as soon as a modification of the value occurs. This mechanism combined with the forward chaining of CHR allows us to implement an efficient rule wake-up and domain propagation mechanism in the manner of a CSP solver.

Constraints ( 8) and ( 9) add new CHR constraints to the model. Indeed, constraints before and disjunct are constraints ensuring the precedence and non-overlapping of two sessions. They are accompanied by rules verifying the coherence of the disjunctive graph created implicitly by the addition of all these constraints. The static predicates correspond to those read from the instance. They are processed and some new constraints (filtering constraints, CHR constraints or unification of variables) are added.

Dynamic constraints ranging from ( 13) to ( 18) are only triggered under certain conditions. CHR guarded rules are used for this purpose. (13) checks that a lecturer teaches the expected number of sessions in each course part. (14) ensures that the capacity of the rooms is respected and [START_REF] Castro | Variable and Value Ordering When Solving Balanced Academic Curriculum Problems[END_REF] verifies that the rooms marked as mandatory are indeed found in the solution. Predicate [START_REF] Chen | A Survey of University Course Timetabling Problem: Perspectives, Trends and Opportunities[END_REF] ensures that sessions subject to the same constraint same weekday are set on the same day of the week.

Constraints ( 17) and ( 18) add constraints when certain conditions are verified. Thus, (17) adds a disjunct between two sessions when the same lecturer participates. (18) adds a constraint between two sessions if they take place in the same room. These constraints enrich the disjunctive graph representing the sequencing of all the sessions.

It should be noted that the CHR model performs domain filtering but also analyses the disjunctive graph in order to eliminate non-solutions. The edges of the disjunctive graph are oriented as the resolution progresses and the decision variables are instantiated.

Experimentations

We carried out preliminary experiments on a real-life instance modeling the second semester of the last year of Bachelor in Computer Sciences at Université d'Angers (available at [1]). The main objective was to validate the solvers and assess their ability to generate solutions in a reasonable time.

The instance contains 5 mandatory courses and 2 courses to choose among 4 additional courses. The instance thus consists of 9 courses decomposed into 24 parts, 45 classes and 241 sessions. Courses are taught during 12 weeks, 5 days a week (Monday to Friday), where each day is divided into 1440 slots. At the Faculty of Sciences of Université d'Angers, course sessions last 1h and 20 minutes or 2 hours and start at regular intervals every 90 minutes starting at 8h00 and finishing at 19h50. The 90 minutes interval includes a 10 minutes break allowing students and lecturers to change rooms.

The instance contains 8 rooms, 12 lecturers and 67 students. In our case, student sectioning was performed in advance and prepartitioned the students into 4 groups. Lecturers are either course owners involved in all the parts of a course (lecture, tutorial and lab) or tutors that are involved in labs of different courses. There are 47 rules defined in the instance: 13 weekly, 17 sequenced, 2 same slot, 5 same week, 5 same rooms and 5 same lecturers. The 47 rules were flattened into 216 constraints and the order of 1000 decision variables.

The MiniZinc and CHR solvers presented in Section 3 were used to solve the instance with an Intel Core i7-10875H 2.30GHz. Both solvers generate a valid solution in less than 5 seconds. The solutions are different due to the two resolution strategies but compliant with each solver which shows the convergence of both models and solvers.

Conclusion and Perspectives

We introduced in this paper a domain-specific language for university course timetabling. The language allows to model a wide variety of course timetabling problems such as those encountered in French universities. It provides support for typical timetabling entities (students, sessions, lecturers, rooms, groups) and features (student sectioning, resource distribution, session scheduling, resource allocation) and includes a rules language to easily express constraints (sequencing, periodicity, etc.). Rules allow to target any subset of domain entities and sessions and enforce timetabling-specific predicates.

We used the language to encode a real instance (Bachelor courses of a French university) and implemented a tool chain to convert the XML instance files into solver-compatible formats. In order to validate our approach, we implemented a CSP model in MiniZinc and CHR and produced solutions for the considered instance.

We are currently working on different extensions of the language and the back-end solvers. First, we intend to represent preferences and priorities in order to support timetable optimization and repair tasks. Second, the current CP models may be improved using dedicated scheduling constraints, search strategies and heuristics and take advantage of model simplication and reformulation techniques. Another objective is to improve scalability by testing our solvers on large-scale instances aggregating different curriculae or converted from academic benchmarks. Lastly, we intend to investigate the revision of timetables to manage unexpected events (e.g. unavailability of a lecturer, late registration of students) or to support incremental solution construction.

Fig. 1

 1 Fig. 1 Conventional workflow for course organization in French universities.

Fig. 3

 3 Fig. 3 Entity meta-model.

  of e-maps, a UTP constraint has the form c((e 1 , S 1 ), . . . , (e m , S m ), p 1 , . . . , p n ) (4) where c is a predicate symbol of arity m, (e 1 , S 1 ), . . . , (e m , S m ) are e-maps ((e i , S i ) ∈ F , i = 1 . . . m) and p 1 , . . . , p n are values for the parameters of c (n ≥ 0). Three constraints (C1, C2, C3) are illustrated in Figure 4.

  O denote the range of session ranks, d O,S : O → 2 S the rank-based partitioning of sessions (s ∈ d O,S o iff rank S s = o), and L * = L∪{E}∪{{e} | e ∈ E} the set of labels completed with the whole set of entities to mock label optionality and singleton entities to support identity-based selection, the language of selectors is the set

  and a possibly empty list of filters ((T 2 , L 2 , O 2 ), . . . , (T k , L k , O k )). d matches any e-map whose entity has type T 1 and label L 1 and whose image includes any compatible session satisfying mask O 1 and any of the filters. The set of e-maps d matched by d is defined by d = e∈T1∩L1 (e, S ′ ) | S ′ = d T1,S e i=2...k

Fig. 4

 4 Fig.4Rules flattening and corresponding constraints on a toy example.

Figure 4

 4 Figure4illustrates the rules flattening process on a toy example. Course algorithms is split into a lecture part algoLec and a lab part algoLab. The lecture part has a single class of 4 sessions taught by lecturer1 and the lab part has 2 classes of 2 sessions each taught by lecturer1 or lecturer2. Rule R1 requires that lecturer2 has no session between slots 9120 and 9240, corresponding for instance to 8am and 10am on Tuesday of week 2. The selector includes no mask and no filter hence matches with all possible sessions of lecturer2 as indicated with diamonds on Figure4. The resulting domain of e-maps is the singleton {(lecturer2, d L,S lecturer2 )} and the rule is flattened into a single forbidden period constraint (C1). Rule R2 requires that the first sessions of the labs start after the third lecture. The two selectors include a filter. The first selector matches with all class sessions of rank 3 in part algoLec, and the second matches with all class sessions of rank 1 in part algoLab as indicated with stars on the figure. The rule is flattened into 2 sequenced constraints (C2 and C3) corresponding to the cross product of the e-map domains

⊆

  L the set of lecturers assigned to session s x R,S r ⊆ S the set of sessions assigned to room r x S,H s ∈ H the start slot assigned to session s

  , s ′ ) ∈ O :

  ∀s ∈ S : x rooms[s] ⊆ R set of rooms allocated to a session ∀s ∈ S : x lecturers[s] ⊆ L set of lecturers allocated to a session ∀s ∈ S : x slot start[s] ∈ H starting slot allocated to a session ∀s ∈ S : x slot end[s] ∈ H ending slot allocated to a session

  Integrity constraint : ∀s ∈ S : x slot end[s] = x slot start[s] + length(s) (1) Static constraints (instance input filtering)) : ∀s ∈ S : x rooms[s] ⊆ part rooms[session part(s)] (2) ∀s ∈ S : x lecturers[s] ⊆ part lecturers[session part(s)] (3) ∀p ∈ P, ∀s ∈ part sessions(p) : week(x slot start[s]) ∈ weeks[p] ∧ weekday(x slot start[s]) ∈ days[p] ∧ dailyslot(x slot start[s]) ∈ dailyslots[p] (4) ∀s ∈ S : x slot start[s]/nr slots per day = x slot end[s]/nr slots per day (5) ∀s ∈ S : card(x lecturers[s]) = team[session part[s]] (6) ∀k ∈ K, ∀s ∈ class sessions[k] : If part room use[class part(k)] = none then card(x rooms[s]) = 0 If part room use[class part(k)] = single then card(x rooms[s]) = 1 If part room use[class part(k)] = multiple then card(x rooms[s

Table 2

 2 Catalog of UTP predicates.

Table 3

 3 lists the decision variables of the model. All, except time slot variables, are set variables.

Table 4

 4 Decision variables (MiniZinc).

Table 6

 6 Decision variables (CHR).

)

  sequenced((e 1 , S 1 ), (e 2 , S 2)) = ∀i 1 ∈ S 1 , ∀i 2 ∈ S 2 : before(i 1 , i 2 ) (11) same rooms((e, S ′ )) = ∀s 1 , s 2 ∈ S ′ , s.t. s 1 < s 2 : x rooms[s 1 ] ∼ x rooms[s 2 ]

			(12)
	Dynamic constraints :
	∀p ∈ P, ∀l ∈ part lecturers[p] :	{x | x ∈ part sessions(p), l ∈	(13)
	x lecturers[x]} = service[l, p]
			(14)
	capacity[r]
	∀s ∈ S, s.t. has mandatory room(s) : session mandatory[s] ⊆ x rooms[s]	(15)
	Dynamic predicate :
	same weekday((e, S

∀s ∈ S, ∀r ∈ session rooms

(s)

:

{group students[g] | g ∈ session room group(s, r), r ∈ x rooms[s]} ≤ ′ )) = ∀s 1 , s 2 ∈ S ′ ,

s.t. s 1 < s 2 : x slot start[s 1 ]/nr weekly slots = x slot start[s 2 ]/nr weekly slots (16) Introspective constraints : ∀k 1 , k 2 ∈ K, ∀s 1 ∈ class sessions[k 1 ], ∀s 2 ∈ class sessions[k 2 ], s.t. s 1 ̸ = s 2 : x lecturers[s 1

The interested reader can download the sources of the model [1].

This work has been funded by a research grant from Université d'Angers.