To jest stara wersja strony!
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.
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:
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
Etap 3:
zastosować globalne ograniczenie
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
cumulative
Podpowiedź - wygodne może być złożenie ograniczeń korzystając z alternatywy \/
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.
-
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 - tablicę można odwrócić używające funkcji reverse
.
% 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)]
Prawdziwy problem: ładowanie węgla na kontenerowce
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.
Sortowanie tablicy na potrzeby definiowania kolejności przeszukiwania zmiennych można zrealizować używając funkcji sort_by.