% The balanced academic curriculum problem: see
% http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob030/spec.html
%
% A curriculum is a set of courses with prerequisites.
%
% Each course must be assigned within a set number of periods.
%
% A course cannot be scheduled before its prerequisites.
%
% Each course confers a number of academic credits (it's "load").
%
% Students have lower and upper bounds on the number of credits
% they can study for in a given period.
%
% Students have lower and upper bounds on the number of courses
% they can study for in a given period.
%
% The goal is to assign a period to every course satisfying these
% criteria, minimising the load for all periods.

include "globals.mzn";




%curriculum.mzn.model
n_courses = 50;
n_periods = 10;
load_per_period_lb = 2;
load_per_period_ub = 100;
courses_per_period_lb = 2;
courses_per_period_ub = 10;
course_load = [6, 3, 5, 3, 7, 8, 1, 9, 4, 9, 8, 8, 4, 5, 6, 3, 2, 1, 3, 1, 1, 2, 6, 7, 6, 10, 10, 1, 7, 3, 4, 2, 7, 9, 7, 4, 6, 7, 2, 2, 5, 9, 9, 10, 4, 6, 4, 5, 6, 6, ];
constraint prerequisite(3, 1);
constraint prerequisite(4, 1);
constraint prerequisite(5, 1);
constraint prerequisite(6, 1);
constraint prerequisite(7, 1);
constraint prerequisite(6, 2);
constraint prerequisite(8, 2);
constraint prerequisite(11, 3);
constraint prerequisite(11, 4);
constraint prerequisite(16, 4);
constraint prerequisite(16, 5);
constraint prerequisite(11, 6);
constraint prerequisite(14, 6);
constraint prerequisite(16, 8);
constraint prerequisite(13, 9);
constraint prerequisite(14, 9);
constraint prerequisite(17, 11);
constraint prerequisite(19, 11);
constraint prerequisite(17, 12);
constraint prerequisite(19, 12);
constraint prerequisite(18, 13);
constraint prerequisite(17, 14);
constraint prerequisite(18, 14);
constraint prerequisite(23, 17);
constraint prerequisite(21, 19);
constraint prerequisite(26, 21);
constraint prerequisite(27, 21);
constraint prerequisite(30, 22);
constraint prerequisite(24, 23);
constraint prerequisite(25, 23);
constraint prerequisite(27, 23);
constraint prerequisite(33, 25);
constraint prerequisite(34, 27);
constraint prerequisite(35, 27);
constraint prerequisite(35, 28);
constraint prerequisite(33, 29);
constraint prerequisite(34, 29);
constraint prerequisite(35, 30);
constraint prerequisite(36, 31);
constraint prerequisite(38, 31);
constraint prerequisite(39, 31);
constraint prerequisite(40, 31);
constraint prerequisite(43, 31);
constraint prerequisite(40, 32);
constraint prerequisite(37, 33);
constraint prerequisite(38, 33);
constraint prerequisite(40, 33);
constraint prerequisite(38, 34);
constraint prerequisite(41, 34);
constraint prerequisite(41, 35);
constraint prerequisite(42, 35);
constraint prerequisite(44, 36);
constraint prerequisite(45, 36);
constraint prerequisite(45, 37);
constraint prerequisite(44, 40);
constraint prerequisite(45, 40);
constraint prerequisite(47, 40);
constraint prerequisite(44, 41);
constraint prerequisite(45, 41);
constraint prerequisite(46, 41);
constraint prerequisite(46, 42);
constraint prerequisite(47, 42);
constraint prerequisite(44, 43);
constraint prerequisite(45, 43);
constraint prerequisite(49, 46);
constraint prerequisite(48, 47);
constraint prerequisite(50, 47);




int: n_courses;
int: n_periods;
int: load_per_period_lb;
int: load_per_period_ub;
int: courses_per_period_lb;
int: courses_per_period_ub;
array [1..n_courses] of int: course_load;
int: max_course_load = sum(c in courses)(course_load[c]);

set of int: courses = 1..n_courses;
set of int: periods = 1..n_periods;

% period course is assigned to
array [courses] of var periods: course_period;
% whether period i has course j assigned
array [periods, courses] of var 0..1: x;
% total load for each period
array [periods] of var load_per_period_lb..load_per_period_ub: load;
% optimisation target
var load_per_period_lb..load_per_period_ub: objective;

constraint forall(p in periods) (
    forall(c in courses) (x[p,c] = bool2int(course_period[c] = p)) /\
    sum(i in courses) (x[p,i]) >= courses_per_period_lb /\
    sum(i in courses) (x[p,i]) <= courses_per_period_ub /\
    load[p] = sum(c in courses) (x[p,c] * course_load[c]) /\
    load[p] >= load_per_period_lb /\
    load[p] <= objective
);

% prerequisite(a, b) means "course a has prerequisite course b".

predicate prerequisite(courses: a, courses: b) =
    course_period[b] < course_period[a];

% add some redundant linear constraints

constraint forall(p in 0..n_periods-1) (
    let {
		var 0..max_course_load: l = sum(c in courses) (bool2int(course_period[c] > p) * course_load[c])
	} in 
        l >= (n_periods-p) * load_per_period_lb /\
        l <= (n_periods-p) * objective
    );

solve :: seq_search([
      int_search([x[i,j] | i in periods, j in courses], input_order, indomain_max, complete),
      int_search([objective], input_order, indomain_min, complete)
    ]) minimize objective;

output 
    [show(c) ++ "-" ++ show(course_period[c]) ++ "\t" | c in courses ] ++ ["\n"] ++
    ["objective = ", show(objective)];