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

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 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
• Etap 5:
  1. Zmienić procedurę szukania tak, aby najpierw próbowała ustalić rozmiar prostokąta, zaczynając od najmniejszych wartości
  2. Zmienić procedurę szukania tak, aby najpierw próbowała ustalić położenie największych kwadratów.
  3. Połączyć obie strategie używając seq_search (Tutorial MiniZinca, s. 57)
  4. Porównać obie strategie szukania z domyślną - która strategia wydaje się bardziej opłacalna w trudnych przypadkach?
  5. 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.
  6. Podpowiedź 2 - dla uproszczenia tablicę można odwrócić używające funkcji reverse — ale nie jest to konieczne.

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

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.

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.

1. Proszę pobrać i rozpakować dane problemu.
2. Plik handout.pdf zawiera szczegółowy opis projektu
3. 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.