====== Lab CSP: Zastosowanie w praktyce =====

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).

===== Rozgrzewka: problem pakowania ======

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. 

{{ :pl:dydaktyka:csp:square_packing.png?300|}}
  * **Definicja problemu**: mając ''n'' kwadratów o rozmiarach kolejno ''1x1,2x2,...,nxn'', należy znaleźć prostokąt a najmniejszym polu, wewnątrz którego zmieszczą się te kwadraty bez nachodzenia na siebie. 
  * **Etap 1:**
    - Proszę uzupełnić poniższy model a brakujące granice dziedzin. 
    - Podpowiedź - należy użyć set comprehension (np. ''[i | in SQUARES]'')
  * **Etap 2:**
    - Należy uzupełnić ograniczenia pod odpowiednimi komentarzami tak, aby problem był rozwiązywalny dla małych ''n''
    - Podpowiedź - wygodne może być złożenie ograniczeń korzystając z alternatywy ''\/'' 
  * **Etap 3:**
    - zastosować globalne ograniczenie [[http://www.minizinc.org/2.0/doc-lib/doc-globals-packing.html|diffn]]
    - Podpowiedź - może być konieczne dodanie kolejnego parametru w postaci tablicy
  * **Etap 4:**
    - Dodać nadmiarowe ograniczenia
    - Podpowiedź - jaka jest relacja między pakowanie a harmonogramowaniem pracy, np. używając ograniczenia {{:pl:dydaktyka:csp:cumulative.png?linkonly|cumulative}}
  * **Etap 5:** 
    - Zmienić procedurę szukania tak, aby najpierw próbowała ustalić rozmiar prostokąta, zaczynając od najmniejszych wartości
    - Zmienić procedurę szukania tak, aby najpierw próbowała ustalić położenie największych kwadratów.
    - Połączyć obie strategie używając ''seq_search'' ([[http://www.minizinc.org/downloads/doc-latest/minizinc-tute.pdf|Tutorial MiniZinca, s. 57]])
    - Porównać obie strategie szukania z domyślną - która strategia wydaje się bardziej opłacalna w trudnych przypadkach?
    - Podpowiedź 1 - 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 zmiennych używając np. ''array comprehension''.
    - Podpowiedź 2 - dla uproszczenia tablicę można odwrócić używające funkcji ''reverse'' --- ale nie jest to konieczne.


<code>
% 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)]
</code>

===== Prawdziwy problem: ładowanie węgla =====

==== Krótki opis ====
Głównym problemem, z którym przyjdzie nam się zmierzyć, będzie problem harmonogramowania pracy portu, który ma załadować węgiel na odpowiednie kontenerowce. Zastosowane poniżej materiały pochodzą z Uniwersytetu w Melbourne, ponieważ problem ten jest realnym wyzwaniem dla prężnie funkcjonującego w Australii eksportu węgla.


==== Plan Zajęć ====

W ramach pierwszego laboratorium należy zapoznać się z problemem i rozwiązać poziom "A". Jest on analogiczny do problemu pakowania, przedstawionego powyżej. W ramach drugiego laboratorium zajmiemy się pozostałymi fazami. 

<WRAP center round tip 60%>
Sortowanie tablicy na potrzeby definiowania kolejności przeszukiwania zmiennych można zrealizować używając funkcji [[http://www.minizinc.org/2.0/doc-lib/doc-builtins-array.html|sort_by]].
</WRAP>

==== Materiały ====

  - Proszę pobrać i rozpakować {{:pl:dydaktyka:csp:portschedule.zip|dane problemu}}.
  - Plik ''handout.pdf'' zawiera szczegółowy opis projektu
  - Plik ''portschedule.mzp'' jest plikiem projektu MiniZinc. Należy go otworzyć w MiniZincIDE. Plik źródłowy jest wzbogacony o liczne komentarze, które powinny ułatwić budowę modelu.