/*
Timetable problem in Picat.
From alma-0 program timetable.a0
"""
The problem is from
@Conference{Scha97,
author = "Andrea Schaerf",
title = "Combining Local Search and Look-Ahead for Scheduling
and Constraint Satisfaction Problems",
booktitle = "Proc.\ of the 15th International Joint Conf.\ on
Artificial Intelligence (IJCAI-96)",
address = "Nagoya, Japan",
year = "1997",
pages = "1254--1259",
publisher = "Morgan Kaufmann",
}
There are q courses, and each course i consists of
k_i lectures, and p periods 1,...,p. For all i = 1,...,q, all lectures
l = 1,...,k_i must be assigned to a period j in such a way that the
following constraints are satisfied:
1. Conflicts: There is a conflict matrix M such that M[i,j] = 1 if
courses i and j have common students. Lectures of courses i and j must
be all scheduled at different times
2. Availabilities: There is an availability binary matrix A such that
A[i,j] = 1 then lectures of course i cannot be scheduled at period j.
3. Rooms: There are r rooms available. At most r lectures can be
scheduled at period k, for each k = 1,...,p.
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% import util.
import cp.
main => go.
go =>
courses(Courses),
periods(Periods),
rooms(Rooms),
available(Available),
conflict(Conflict),
requirement(Requirement),
% decision variables
Timetable = new_array(Courses,Periods),
Timetable :: 0..1,
% 1. Conflicts: There is a conflict matrix M such that M[i,j] = 1 if
% courses i and j have common students. Lectures of courses i and j must
% be all scheduled at different times
foreach(C1 in 1..Courses, C2 in 1..Courses, C1 < C2)
if Conflict[C1,C2] = 1 then
foreach(P in 1..Periods)
Timetable[C1,P] + Timetable[C2,P] #=< 1
end
end
end,
%
% 2. Availabilities: There is an availability binary matrix A such that
% A[i,j]= 1 then lectures of course i cannot be scheduled at period j.
% [Note: It must be that if A[i,j] = 0 then the lectures cannot be
% scheduled at period j.]
foreach(C in 1..Courses, P in 1..Periods)
if Available[C,P] #= 0 then
Timetable[C,P] #= 0
end
end,
% 3. Rooms: There are r rooms available. At most r lectures can be
% scheduled at period k, for each k = 1,...,p.
foreach(P in 1..Periods)
sum([Timetable[C,P] : C in 1..Courses]) #=< Rooms
end,
% The number of lectures per course
foreach(C in 1..Courses)
sum([Timetable[C,P] : P in 1..Periods]) #= Requirement[C]
end,
solve([ff,updown],Timetable),
foreach(C in 1..Courses)
foreach(P in 1..Periods)
print(Timetable[C,P]),print(" ")
end,
printf("\n")
end,
nl.
%
% data (from the Alma-0 program timetable.a0)
%
index(-)
courses(5).
index(-)
periods(20).
index(-)
rooms(2).
index(-)
available(
[
% 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
[0,0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1],
[1,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1],
[1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
]).
index(-)
conflict(
[
[0,1,0,0,1],
[1,0,0,1,0],
[0,0,0,0,1],
[0,1,0,0,1],
[1,0,1,1,0]
]).
index(-)
requirement([6,10,14,6,4]).