Balanced Academic Curriculum Problem
From CometPublic
Contents |
[edit] Definition of BACP
This problem consists in finding a schedule of a series of courses over a given number of periods. The schedule must be as well-balanced as possible (i.e. the maximum load over a period must be minimized). Each course is assigned with a number of credits, which is its academic load. Prerequisite constraints among courses must be satisfied.
Moreover, the load of each period must stand within a given range, as well as for the number of courses over each period.
[edit] Definition of the model
[edit] Variables
As the problem can be viewed as the assignment of a period to each course, there is an integer variable per course to associate it to its period.
These variables are grouped together in the incremental variables array coursePeriod. This array is initialized randomly at its creation to change the start point of the search at each instanciation.
[edit] Constraints
The domain of the variables in coursePeriod is limited to the valid periods number. This permits the constraint that each course must be scheduled to be implicitly satisfied.
To limit the number of courses taught in a given period, the atmost and atleast constraints are used. These constraints can restrain the number of times a value is assigned in a set of variables.
We can then define a constraint to restrict the number courses a period is linked to by
posting :
atleast(minNbCourses, coursePeriod) atmost(maxNbCourses, coursePeriod)
where minNbCourses and maxNbCourses are two arrays of size p that contain respectively courseLB and courseUB at each index.
But we have to bound the academic load of each period as well. To do so, we used a generalized version of atleast and atmost which is knapsack. This latter constraint is useful to weight each variable differently, which is exactly what we need to restrict the load. As a matter of fact, each course has a credit load which will be its weight in the knapsack constraint.
We then just have to post the following constraints :
knapsack(coursePeriod, minusCourseCredits, minPeriodLoad) knapsack(coursePeriod, courseCredits, maxPeriodLoad)
where courseCredits is an array linking each course to its credit load, minusCoursesCredits is the opposite of the former variable, minPeriodLoad and maxPeriodLoad are two arrays containing respectively loadLB and loadUB at each index.
The last constraint is the satisfaction of prerequisites between pairs of courses. To deal with it, we have to post a constraint per prerequisite. This constraint forces the period in which the first course is assigned to be inferior to the period of the second course.
NOTE: This model might not seem intuitive. Another way would have been to define an Objective function. This could be a more interesting approach, but is not developped here.
[edit] Search approach
[edit] Meta-search
To increase the probability of finding a solution, we used the concept of intensification. But restarting the search many times requires that the initial state be different each time. Otherwise the diversification of the search would not be important enough.
And to find a well balanced schedule over the periods, we have to solve it as an optimization problem. Branch-and-bound is an appropriate method for this purpose. It is an improvement of the intensification heuristics in which the model is adapted at each solution found to push the optimized criterion to its limit.
To optimize the balance of the schedule, we lower the load upper bound loadUB when
the program reaches a solution to the maximum load of all the periods minus one. The
halting condition of the meta-heuristics is restricted compared to the simple intensification because
it stops the search when the value of loadUB is inferior to 
where totalLoad is the sum of the loads of all the courses and nbPeriods is the number of periods. This avoids
a useless search because a smaller upper bound would lead to an inconsitent model.
[edit] Search
The choice of the variable is performed randomly. This leads to a great speed-up in the searches without compromising the probability to obtain a solution compared to a max-min search (experimentally speaking). This allows us to push the intensification further to improve the probability to obtain a solution.
As the variable is chosen randomly, the search can freely do useless work by retrying already tested value configuration. To limit this effect, we decide to implement a tabu heuristics in the choice of the variable.
[edit] Implementation in Comet
[edit] Variables
/* Problem data variables */
int nbCourses; // number of courses
int nbPeriods; // number of periods
int nbPrerequisites; // number of prerequisite rules
int loadLB; // lower bound for the load of a period
int loadUB; // upper bound for the load of a period
int courseLB; // lower bound for the number of courses in a period
int courseUB; // upper bound for the number of courses in a period
int minMaxLoad; // smallest possible upper bound for the loads
string[] courseNames; // name of the courses
int[] courseCredits; // credits of the courses
int[] minusCourseCredits; // opposite of the course credits
int[,] coursePrerequisites; // prerequisite rules
/* Problem search variables */
var{int}[] coursePeriod; // period assigned to each course
range periods; // set of the periods
range courses; // set of the courses
range prerequisites; // set of the prerequisite rules
LocalSolver m; // solver
ConstraintSystem S; // constraints
[edit] Model definition
void defineModel() {
m = new LocalSolver();
S = new ConstraintSystem(m);
/* Random initial period assigned to each course */
coursePeriod = new var{int}[courses](m, periods);
UniformDistribution distr(periods);
forall (c in courses)
coursePeriod[c] := distr.get();
/* Course number per period constraints */
int maxNbCourses[periods] = courseUB;
S.post(atmost(maxNbCourses, coursePeriod));
int minNbCourses[periods] = courseLB;
S.post(atleast(minNbCourses, coursePeriod));
/* Load per period constraints */
int maxPeriodLoad[periods] = loadUB;
S.post(knapsack(coursePeriod, courseCredits, maxPeriodLoad));
int minPeriodLoad[periods] = -loadLB;
S.post(knapsack(coursePeriod, minusCourseCredits, minPeriodLoad));
/* Prerequisite constraints */
forall(p in prerequisites)
S.post(coursePeriod[coursePrerequisites[p,0]] >= coursePeriod[coursePrerequisites[p,1]]);
m.close();
}
[edit] Search
int BACProblem::search(int maxIt) {
int tabu[courses] = 0;
int tabuLimit = 10;
int it = 0;
while (S.violations() > 0 && it < maxIt) {
select(course in courses : tabu[course] < it)
selectMin(period in periods)(S.getAssignDelta(coursePeriod[course],period)) {
coursePeriod[course] := period;
tabu[course] = it + tabuLimit;
}
it = it + 1;
}
return it;
}
[edit] Meta-search
[edit] Intensification
void BACProblem::intensifiedSearch(int maxIt, int maxTries) {
int tri = 0;
while (tri < maxTries) {
tri++;
defineModel(); // reinitialise the model
int it = search(maxIt*tri);
if (S.violations() == 0)
break;
}
}
[edit] Branch-and-bound
void BACProblem::searchDecreaseBound(int maxIt, int maxTries) {
int[] bestSolution;
do {
intensifiedSearch(maxIt, maxTries);
// get new maximum load
int maxLoad[periods] = 0;
forall(c in courses)
maxLoad[coursePeriod[c]] += courseCredits[c];
int maxL = 0;
forall (p in periods)
if (maxLoad[p] > maxL) maxL = maxLoad[p];
if (S.violations() == 0)
loadUB = maxL-1;
bestSolution = copySolution();
} while (S.violations() == 0 && loadUB >= minMaxLoad);
}
