The Generalized Balanced Academic Curriculum Problem

The Generalized Balanced Academic Curriculum Problem

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching periods satisfying prerequisites and balancing students' load. This problem has been originally proposed by Castro and Manzano and is listed as problem n. 30 of CSPlib.

However, the problem is actually simpler than the real problem that universities have to solve in practice, therefore we propose a generalization of the problem which applies, among others, to our institution (the School of Engineering at the University of Udine).

The formulation of the Generalized BACP consists of the following entities and constraints:

Courses
Each course has an integer number of credits and it has to be taught during the planning horizon of the university degree.

Periods
The planning horizon is composed by a given number of teaching periods that have to be assigned to courses. Periods are divided in years, and each year is divided in a fixed number of terms. For example, a 3-year degree organized in four trimesters per year has 12 periods.

Load limits
For each period there is a minimum and a maximum number of courses that can be assigned to it. Further, there are minimum and maximum limits also on the number of total credits per period.

Prerequisites
Based on their content, some courses have to be taught before other courses. This means that we are given a set of pairs of courses, such that the period assigned to the first course has to be strictly less than the period assigned to the second. Obviously, prerequisite relation is transitive and cannot contain cycles.

Curricula
First of all, in the formulation it is implicitly assumed that a student takes all courses without personal choices, whereas in practice a student can select among alternatives. Calling curriculum a set of courses representing a possible complete selection, we extend the problem by considering many curricula. Different curricula can share some of the courses.

Preferences
Professors can express preferences about their teaching periods. Specifically, a teacher can express preferences not for the year but for a specific term of the year. A preference of a course for a given term results in a penalty for any assignment of the course to a period which is not in that term. Preferences are not strict, and therefore they contribute to the objective function (soft constraints).

The problem consist in finding an assignment of courses to periods that satisfies the load limits and prerequisites. The objective function is a composition of preference violations and unbalanced load. In order to adhere more precisely to the real situation, the load component that we consider sums up all the deviations (positive and negative) from the average number of credits per period for each curriculum.

The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes

We propose and solve a further extension of the problem, obtained by relaxing one implicit assumption. In the original GBACP, courses are assigned to periods; for the GBACP-HC, instead, each course is assigned to a term and each course/curriculum pair is assigned to an academic year. As a result, the course is assigned to different periods in the various curricula, but it is taught once in the year in a single specific term.

It is also introduced a measure of how much heterogeneous are the students attending the same course. This is computed as the difference between the maximum and the minimum academic year in which the course is taught.

A solution of the GBACP-HC problem is an assignment of terms to courses and of academic years to course/curriculum pairs such that load limits and prerequisites are satisfied and the violations relating to load balancing, preferences, and heterogeneity are minimized. For the heterogeneity component, given that its importance can be subjective, we experiment with two different settings. In the first one, we set w_h = 1 so that its level of importance is the same as the balancing component (w_bl = 1) and five times less than the preference component (w_p = 5). In the second setting, instead, we considerably lower the impact of heterogeneity and we set w_h = 1/5.

Publications

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes

Instances

The benchmark instances employed in our study consist of:

  • the three original CSPLib instances (translated in the GBAC format) called bcap8, bcap10, bcap12
  • ten new instances, called UD1-UD10, which are real cases from our university.
  • a toy example (for testing)

The following table summarizes the features of the instances and allow to download them. The file format is described in this page.

Instance Courses Periods (Years x Terms) Curricula Prerequisites Preferences Best solution of
HM-2008
Best solution of
Chiarandini et al.
Obtained by
IP = Integer Programming
LS = Local Search
bcap8 46 8 (4 x 2) 1 33 0 0 0 IP/LS
bacp10 42 10 (5 x 2) 1 33 0 0 0 IP/LS
bacp12 66 12 (6 x 2) 1 65 0 0 0 IP/LS
UD1 307 9 (3 x 3) 37 1383 90 397 258 LS
UD2 268 6 (2 x 3) 20 174 79 179 146 LS
UD3 236 9 (3 x 3) 31 1092 66 217 160 LS
UD4 139 6 (2 x 3) 16 188 40 396 396 IP/LS
UD5 282 6 (3 x 2) 31 397 54 278 211 LS
UD6 264 4 (2 x 2) 20 70 55 100 55 IP
UD7 302 9 (3 x 3) 37 1550 83
189 LS
UD8 208 6 (2 x 3) 19 149 60
42 LS
UD9 303 9 (3 x 3) 37 1541 85
202 LS
UD10 188 6 (2 x 3) 15 214 55
44 LS
toy 6 4 (2 x 2) 3 3 2 191 IP/LS

Solution validator

You can download the C++ source code of a solution validator.

AMPL files of the IP solver

You can download the source files of the IP solver.

The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes

For the GBACP-HC, we test our algorithm on the same ten benchmarks (UD1-UD10) already used for GBACP. The table reports our best results for the two different weight settings.

Instance Courses Periods (Years x Terms) Curricula Prerequisites Preferences Best solution of Ceschia et al.
w_lb = 1 w_p = 5 w_h = 1
Best solution of Ceschia et al.
w_lb = 1 w_p = 5 w_h = 1/5
UD1 307 9 (3 x 3) 37 1383 90 262 242.0
UD2 268 6 (2 x 3) 20 174 79 149 136.2
UD3 236 9 (3 x 3) 31 1092 66 167 162.2
UD4 139 6 (2 x 3) 16 188 40 325 324.2
UD5 282 6 (3 x 2) 31 397 54 101 60.6
UD6 264 4 (2 x 2) 20 70 55 52 40.8
UD7 302 9 (3 x 3) 37 1550 83 221 188.6
UD8 208 6 (2 x 3) 19 149 60 41 34.0
UD9 303 9 (3 x 3) 37 1541 85 216 182.8
UD10 188 6 (2 x 3) 15 214 55 44 39.4