Minizinc: возможно ли это ограничение?

Question

Я хотел бы выяснить, как написать это ограничение: у меня есть список экзаменов, каждый экзамен имеет продолжительность; конечный результат - отображение реального расписания, в столбцах - доступные часы, четыре часа утра и четыре дня, с двумя часами в середине обеда, которые не будут доступны. Так что позвольте мне сделать это совершенно ясно, если у меня есть два экзамена, и каждый экзамен имеет назначенную продолжительность, я бы хотел показать номер экзамена в расписании, связанный с их продолжительностью, потому что мои переменные являются экзаменами.

Например: У меня есть два экзамена и первый занимает один час, вторые три часа

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;    

Я хотел бы иметь этот выход: [1,2,2,2], а не [ 0,0,0,4] (в вертикальном режиме) Можно ли сделать это в Minizinc? Код для второго выхода является:

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

Заранее спасибо

Answer 1

(Привет, этот вопрос легче ответить, чем ваш первоначальный вопрос, так как он гораздо больше точки.)

Вот версия, которая использует два дополнительных массива переменных решения: «ExamsRoom», чтобы обрабатывать назначение комнаты на экзамен, и «ExamsStart» для начала экзамена. Возможно, они не нужны, но облегчают формулировку ограничения продолжительности экзамена; назначение комнаты и времени также более четко показано. Они также могут быть полезны для добавления дополнительных ограничений.

Я также добавил параметр «Комнаты = 2», так как он отсутствовал в вашем примере.

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; 

Эта модель имеет 20 различных решений, первые два (с использованием Gecode в качестве решателя) является

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] 
---------- 

Первое решение означает, что экзамен 1 начинается в момент времени 4 в комнате 1 и экзамен 2 начинается в момент 1, также в комнате 1. Второе решение имеет то же назначение для экзамена 2, но устанавливает экзамен 1 в комнату 2 (в момент 1).

Надеюсь, это поможет вам продолжить работу с моделью.

/hakank