You are here

Balanced Academic Curriculum Problem

The Balanced Academic Curriculum Problem (BACP) is recurrent in Universities. The goal is to schedule the courses that a student must follow in order to respect the prerequisite constraints between courses and to balance as much as possible the workload of each period. Each period also has a minimum and maximum number of courses.

The largest of the three instances available on CSPLIB (http://www.csplib.org) with 12 periods, 66 courses having a weight between 1 and 5 (credits) and 65 prerequisites relations was modified in [1] to generate 100 new instances by giving each course a random weight between 1 and 5 and by randomly keeping 50 out of the 65 prerequisites. Each period must have between 5 and 7 courses. Note that as was shown in [2], a better balance property is obtained by minimizing the variance instead of the maximum load (with spread constraint). This constraint is available in OscaR solver.

For an instance:

66 12 1 5 50

2 4 1 4 1 3 1 2 3 2 3 1 1 1 1 1 5 4 1 5 4 2 2 4 1 1 3 1 2 1 4 5 1 2 1 5 2 3 1 1 1 4 3 5 5 5 2 5 2 2 5 5 1 1 4 1 1 1 4 2 5 2 4 3 2 1 6 0 7 5 10 4 10 5 11 6 12 7 12 10 13 2 15 8 16 10 17 9 17 10 18 7 19 8 22 16 22 17 23 12 23 18 25 12 25 22 29 8 32 26 33 16 34 8 34 17 36 29 36 34 37 32

38 34 40 8 40 16 40 17 42 19 43 15 44 37 46 41 47 33 47 34 48 31 52 46 53 49 54 42 54 37 55 50 56 33 57 27 60 47 61 30 62 47 64 58

The format is the following: 60= number of courses, 12 = number of periods, 1 = mincredit, 5 = maxcredit, 50 = number of prerequisites 2 4 1 4 … are the credit of each course course 38 pust come becore course 34, 40 before 8, … Although not indicated in the files, there must be between 5 and 7 courses in each period.

[1]:

@phdthesis{schaus2009thesis, title={Solving balancing and bin-packing problems with constraint programming}, author={Schaus, Pierre and others}, year={2009}, school={PhD thesis, Universit catholique de Louvain Louvain-la-Neuve} }

[2]:

@inproceedings{monette2007cp, title={A {C}{P} approach to the balanced academic curriculum problem}, author={Monette, Jean-No{"e}l and Schaus, Pierre and Zampelli, St{'e}phane and Deville, Yves and Dupont, Pierre}, booktitle={Seventh International Workshop on Symmetry and Constraint Satisfaction Problems}, volume={7}, year={2007} }

AttachmentSize
bacp.zip34.07 KB