Na tym laboratorium spróbujemy zamodelować w MiniZincu w miarę rzeczywisty problem. Rzeczywiste problemy mają to do siebie, że są trudne - dlatego są doskonałym testem umiejętności. Planowany czas wymagany na zrealizowanie tego laboratorium to dwa zajęcia (2x1h30min) plus czas poświęcony w domu między nimi (w razie potrzeby).

Na rozgrzewkę rozwiążmy prosty problem, który w znaczny sposób ułatwi nam modelowanie problemu końcowego. Zajmijmy się tak zwanym problemem pakowania. Istnieje wiele rodzajów problemów pakowania - to, co je łączy, to konieczność upakowania n-wymiarowych brył w n-wymiarowym pojemniku. My zajmiemy się bardzo prostym przypadkiem pakowania kwadratów w pojemniku o kształcie prostokąta.

• Definicja problemu: mając n kwadratów o rozmiarach kolejno 1×1,2×2,…,nxn, należy znaleźć prostokąt a najmniejszym polu, wewnątrz którego zmieszczą się te kwadraty bez nachodzenia na siebie.
• Etap 1:
  1. Proszę uzupełnić poniższy model a brakujące granice dziedzin.
  2. Podpowiedź - należy użyć set comprehension (np. [i | in SQUARES])
• Etap 2:
  1. Należy uzupełnić ograniczenia pod odpowiednimi komentarzami tak, aby problem był rozwiązywalny dla małych n
  2. Podpowiedź - wygodne może być złożenie ograniczeń korzystając z alternatywy \/
• Etap 2:
  1. Zmienić procedurę szukania tak, aby najpierw próbowała ustalić położenie największych kwadratów
  2. Podpowiedź - kolejność przeszukiwania zmiennych można wymusić przez adnotację input_order - w tym celu należy wcześniej zmienne włożyć w odpowiedniej kolejności do jednej tablicy
• Etap 3:
  1. zastosować globalne ograniczenie diffn
  2. Podpowiedź - może być konieczne dodanie kolejnego parametru w postaci tablicy
• Etap 4:
  1. Dodać nadmiarowe ograniczenia
  2. Podpowiedź - jaka jest relacja między pakowanie a harmonogramowaniem pracy, np. używając ograniczenia cumulative

% Parametry
%%%%%%%%%%%
int: n;                      % liczba kwadratów
set of int: SQUARES = 1..n;  % zbiór dostępnych kwadratów

% Zmienne
%%%%%%%%%%%
var <min>..<max>: height;    % wysokość prostokątnego pojemnika
var <min>..<max>: width;     % szerokość prostokątnego pojemnika
var <min>..<max>: area = height * width; % pole pojemnika
array[SQUARES] of var <min>..<max>: x; % współrzędne kwadratów w pojemniku
array[SQUARES] of var <min>..<max>: y; % współrzędne kwadratów w pojemniku
  
% Ograniczenia 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

% Ograniczenie 1: kwadraty nie powinny wychodzić poza prostokąt
  
% Ograniczenie 2: kwadraty nie powinny nachodzić na siebie

% Cel
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
solve minimize area; 
  

% Nudne wyjście  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
output [ show(i) ++ " > (" ++ show(x[i]) ++ "," ++ show(y[i]) ++ ")\n" | i in 1..n] ++
  ["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)]