Minizinc: is this constraint possible?

Question

I'd like to figure out how to write this constraint: I have a list of exams,every exam has a duration; the final output is the display of a real timetable, in the columns there are the available hours, four in the morning and four in the afternoon, with two hours in the middle of lunch which won't be available.So,let me make this perfectly clear,if I have two exams and each exam has an assigned duration, I'd like to show the number of the exam in the timetable linked to their duration,because my variables are the exams.

For example: I have two exams and the first takes one hours,the second three hours

int: Exams;
array[1..Exams] of int: Exams_duration;


int: Slotstime;         % number of slots
int: Rooms;             % number of rooms
array[1..Slotstime,1..Rooms] of var 0..Exams: Timetable_exams;

%Data

Exams=2;
Exam_duration=[1,3];
Slotstime=4;            

I'd like to have this output: [1,2,2,2] and not [0,0,0,4] (in vertical mode) Is it possible to do in Minizinc? The code for the second output is:

constraint forall (p in 1..Rooms)                 
( 
  sum (s in 1..Slotstime) (Timetable_exams[s,p]) 
  = sum (f in 1..Exams)(Exams_duration[f])
);

Thanks in advance

Answer 1

(Hi, this question is easier to answer than your original question since it is much more to the point.)

Here is a version that use two extra arrays of decision variables: "ExamsRoom" to handle the assignment of the room to an exam, and "ExamsStart" for the start time of the exam. Perhaps these are not really necessary, but they makes it easier to state the exam duration constraint; the assignments of the room and time are more also shown more clearly. They might also be useful for adding further constraints.

I also added the parameter "Rooms = 2" since it was missing from your example.

int: Exams;
array[1..Exams] of int: Exams_duration;

int: Slotstime;         % number of slots
int: Rooms;             % number of rooms
array[1..Slotstime,1..Rooms] of var 0..Exams: Timetable_exams;

array[1..Exams] of var 1..Rooms: ExamsRoom; % new
array[1..Exams] of var 1..Slotstime: ExamsStart; % new

solve satisfy;
% solve :: int_search(x, first_fail, indomain_min, complete) satisfy;

constraint

  % hakank's version

  % for each exam
  forall(e in 1..Exams) (
    % find a room
    exists(r in 1..Rooms) (
       % assign the room to the exam
       ExamsRoom[e] = r /\
       % assign the exam to the slot times and room in the timetable
       forall(t in 0..Exams_duration[e]-1) (
          Timetable_exams[t+ExamsStart[e],r] = e
       )
    ) 
  ) 

  /\ % ensure that we have the correct number of exam slots
  sum(Exams_duration) = sum([bool2int(Timetable_exams[t,r]>0) | t in 1..Slotstime, r in 1..Rooms])
 ;

output [
  if r = 1 then "\n" else " " endif ++ 
     show(Timetable_exams[t,r])
  | t in 1..Slotstime, r in 1..Rooms
 ]
 ++
 [
   "\nExamsRoom: ", show(ExamsRoom), "\n",
   "ExamsStart: ", show(ExamsStart), "\n",
 ]
 ;

 %
 % Data
 %
 Exams=2;
 Exams_duration=[1,3];
 Slotstime=4;            

 % was not defined
 Rooms = 2;

This model have 20 different solutions, the first two (using Gecode as a solver) is

2 0
2 0
2 0
1 0
ExamsRoom: [1, 1]
ExamsStart: [4, 1]
----------

2 1
2 0
2 0
0 0
ExamsRoom: [2, 1]
ExamsStart: [1, 1]
----------

The first solution means that exam 1 starts at time 4 in room 1, and exam 2 starts at time 1, also in room 1. The second solution has the same assignment for exam 2, but set exam 1 to room 2 (at time 1).

Hope this helps you to go further with the model.

/hakank