Link Search Menu Expand Document
PyCSP3
Models & Data GitHub XCSP3 About
Documentation
XCSP web site is provided by CRIL
This site uses Just the Docs, a documentation theme for Jekyll.
download notebook
COP  medium 

Problem BACP

From CSPLib (Problem 30): The goal of BACP is to design a balanced academic curriculum by assigning periods to courses in a way that the academic load of each period is balanced, i.e., as similar as possible. An academic curriculum is defined by a set of courses and a set of prerequisite relationships among them. Courses must be assigned within a maximum number of academic periods. Each course is associated to a number of credits or units that represent the academic effort required to successfully follow it.”

The curriculum must obey the following regulations:

  • minimum academic load: a minimum number of academic credits per period is required to consider a student as full time
  • maximum academic load: a maximum number of academic credits per period is allowed in order to avoid overload
  • minimum number of courses: a minimum number of courses per period is required to consider a student as full time
  • maximum number of courses: a maximum number of courses per period is allowed in order to avoid overload

The goal is to assign a period to every course in a way that the minimum and maximum academic load for each period, the minimum and maximum number of courses for each period, and the prerequisite relationships are satisfied. An optimal balanced curriculum minimizes the maximum academic load for all periods.

Getting Diploma. Diploma

To build a COP (Constraint Optimization Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data. When analyzing this problem, we identify its parameters as being the number of periods (an integer), the minimum and the maximum number of credits (two integers), the minimum and the maximum number of courses (two integers), the credits for each course (a one-dimensional array of integers) and the prerequisites (a two-dimensional array of integers, with each row indicating a prerequisite).

Here is an example of data:

nPeriods = 4
minCredits = 2
maxCredits = 5
minCourses = 2
maxCourses = 3
credits = [2,3,1,3,2,3,3,2,1]
prerequisites = [[2,0], [4,1], [5,2], [6,4]]
nCourses = len(credits)

We start our COP model by introducing an array $x$ of variables.

# x[c] is the period (schedule) of course c
x = VarArray(size=nCourses, dom=range(nPeriods))

We can display the structure of the array, as well as the domain of the first variable (note that all variables have the same domain).

print("Array x: ", x)
print("Domain of any variable: ", x[0].dom)

Array x:  [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8]]
Domain of any variable:  0..3

Concerning the constraints, we start by posting a group of arithmetic constraints (Intension) so as to impose the prerequisite relationships.

satisfy(
   # handling prerequisites
   x[c1] < x[c2] for (c1, c2) in prerequisites
);

We can display the internal representation of the posted constraints; this way, although a little bit technical, we can see that the constraints are correctly defined (note that ‘lt’ stands for ‘strictly less than’).

print(posted())

intension(function:lt(x[2],x[0]))
intension(function:lt(x[4],x[1]))
intension(function:lt(x[5],x[2]))
intension(function:lt(x[6],x[4]))

Interestingly, by calling the function solve(), we can check that the problem, in its current state, is satisfiable (SAT). We can also display the found solution. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
    print("Periods of courses: ", values(x))

Periods of courses:  [2, 2, 1, *, 1, 0, 0, *, *]

In the found solution, the symbol ‘*’ may appear for some variables indicating that any value can be chosen (this is because no constraints involve such variables).

To be able to count the number of credits per period, we introduce a two-dimensional array $y$ of variables.

# y[c][p] is 0 if the course c is not planned at period p, the number of credits for c otherwise
y = VarArray(size=[nCourses, nPeriods], dom=lambda c, p: {0, credits[c]})

We display the structure of the new array of variables as well as some representative domains.

print("Array y: ", y)
for c in range(nCourses):
    print(f"Domain of variables related to course {c}: {y[c][0].dom}")

Array y:  [
  [y[0][0], y[0][1], y[0][2], y[0][3]]
  [y[1][0], y[1][1], y[1][2], y[1][3]]
  [y[2][0], y[2][1], y[2][2], y[2][3]]
  [y[3][0], y[3][1], y[3][2], y[3][3]]
  [y[4][0], y[4][1], y[4][2], y[4][3]]
  [y[5][0], y[5][1], y[5][2], y[5][3]]
  [y[6][0], y[6][1], y[6][2], y[6][3]]
  [y[7][0], y[7][1], y[7][2], y[7][3]]
  [y[8][0], y[8][1], y[8][2], y[8][3]]
]
Domain of variables related to course 0: 0 2
Domain of variables related to course 1: 0 3
Domain of variables related to course 2: 0 1
Domain of variables related to course 3: 0 3
Domain of variables related to course 4: 0 2
Domain of variables related to course 5: 0 3
Domain of variables related to course 6: 0 3
Domain of variables related to course 7: 0 2
Domain of variables related to course 8: 0 1

To make the connection between the arrays $x$ and $y$, we introduce the following function:

def table(c):
    return [(p,) + (0,) * p + (credits[c],) + (0,) * (nPeriods - p - 1) for p in range(nPeriods)]

This function returns a set (list) of 5-tuples where, for each tuple, the first value indicates the number $p$ of the period, and the other values give the corresponding credits (they are all set to 0 except when the position of the value corresponds to $p$). For example, if we print the table for the period 0, we can see that :

  • if the period is 0, 2 is set to the first next value in the tuple
  • if the period is 1, 2 is set to the second next value in the tuple
  • if the period is 2, 2 is set to the third next value in the tuple
  • if the period is 3, 2 is set to the fourth next value in the tuple
print(table(0))

[(0, 2, 0, 0, 0), (1, 0, 2, 0, 0), (2, 0, 0, 2, 0), (3, 0, 0, 0, 2)]

To compute $y$ from $x$ (and vice versa), we post a group of constraints Extension. Technically, note that (x[c],y[c]) is automatically transformed into (x[c],*y[c]).

satisfy(
   # channeling between arrays x and y
   (x[c],y[c]) in table(c) for c in range(nCourses)
);

To control things, we display the internal representation of the 3 last posted constraints.

print(posted()[-3:])

extension(list:[x[6], y[6][0], y[6][1], y[6][2], y[6][3]], supports:(0,3,0,0,0)(1,0,3,0,0)(2,0,0,3,0)(3,0,0,0,3))
extension(list:[x[7], y[7][0], y[7][1], y[7][2], y[7][3]], supports:(0,2,0,0,0)(1,0,2,0,0)(2,0,0,2,0)(3,0,0,0,2))
extension(list:[x[8], y[8][0], y[8][1], y[8][2], y[8][3]], supports:(0,1,0,0,0)(1,0,1,0,0)(2,0,0,1,0)(3,0,0,0,1))

We can run the solver.

if solve() is SAT:
    print("Periods of courses: ", values(x))
    print("Assignments of credits per periods: ", values(y))

Periods of courses:  [2, 2, 1, 0, 1, 0, 0, 0, 0]
Assignments of credits per periods:  [
  [0, 0, 2, 0]
  [0, 0, 3, 0]
  [0, 1, 0, 0]
  [3, 0, 0, 0]
  [0, 2, 0, 0]
  [3, 0, 0, 0]
  [3, 0, 0, 0]
  [2, 0, 0, 0]
  [1, 0, 0, 0]
]

If we want to count the number of courses and credits per period, we can write:

if solve() is SAT:
    print("Periods of courses: ", values(x))
    print("Number of courses per periods: ", [sum(x[i].value == p for i in range(nCourses)) for p in range(nPeriods)])
    print("Number of credits per periods: ", [sum(values(y[:,p])) for p in range(nPeriods)])  
    

Periods of courses:  [2, 2, 1, 0, 1, 0, 0, 0, 0]
Number of courses per periods:  [5, 2, 2, 0]
Number of credits per periods:  [12, 3, 5, 0]

One can observe that the academic curriculum is not very well balanced.

This is why we post this objective function:

minimize(
   # minimizing the maximum number of credits in periods
   Maximum(Sum(y[:, p]) for p in range(nPeriods))
);

We can run the solver, with this optimization task. Note that we need to check now that the status returned by the solver is OPTIMUM.

if solve() is OPTIMUM:
    print("Periods of courses: ", values(x))
    print("Number of courses per periods: ", [sum(x[i].value == p for i in range(nCourses)) for p in range(nPeriods)])
    print("Number of credits per periods: ", [sum(values(y[:,p])) for p in range(nPeriods)])  
    print("Bound: ", bound())

Periods of courses:  [3, 2, 2, 3, 1, 1, 0, 0, 2]
Number of courses per periods:  [2, 2, 3, 2]
Number of credits per periods:  [5, 5, 5, 5]
Bound:  5

This is far better.

Finally, we give below the model in one piece. Here, the data is expected to be given by the user (in a command line).

from pycsp3 import *

nPeriods, minCredits, maxCredits, minCourses, maxCourses, credits, prereq = data
nCourses = len(credits)

# x[c] is the period (schedule) for course c
x = VarArray(size=nCourses, dom=range(nPeriods))

# y[c][p] is 0 if the course c is not planned at period p, the number of credits for c otherwise
y = VarArray(size=[nCourses, nPeriods], dom=lambda c, p: {0, credits[c]})

def table(c):
    return [(p,) + (0,) * p + (credits[c],) + (0,) * (nPeriods - p - 1) for p in range(nPeriods)]

satisfy(
   # channeling between arrays x and y
   [(x[c], y[c]) in table(c) for c in range(nCourses)],

   # handling prerequisites
   [x[c1] < x[c2] for (c1, c2) in prerequisites]
)

minimize(
   # minimizing the maximum number of credits in periods
   Maximum(Sum(y[:, p]) for p in range(nPeriods))
);