This laboratory will concern practical use of the constraint programming. However, real problems are difficult, classes are short. Therefore it will take more than one meeting to finish the assignments. Students are expected to work at home between the classes and finish work during the second meeting.

First we will deal with a simple problem that is strictly related to the real problem we are interested in. The packing problem is a problem of fitting n-dimensionals solids in the n-dimensional container. We will discuss the simple case — packing squares into a rectangle.

• Definition: having n squires sized accordingly 1×1,2×2,…,nxn, we have to find the rectangle with the smallest area, inside witch we can fit all the sqaures without overlapping..
• Stage 1:
  1. Fill the domains' bounds
  2. Tip — use set comprehension (np. [… |i in SQUARES])
• Stage 2:
  1. Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small n
• Stage 3:
  1. Replace your constraint with the global constraint diffn
  2. Tip — you may have to introduce a new array parameter to the model
• Stage 4:
  1. Add redundant constraints
  2. Tip 1 — how is the packing related to the scheduling, e.g. the cumulative constraint?
  3. Tip 2 — scheduling is a kind of packing where time is one of the dimensions
  4. Tip 3 — this picture satisfies ''cumulative'' constraint, but it doesn't satisfy packing constraint
• Stage 5:
  1. Change the search procedure, so the solver would first try the smallest containers
  2. Change the search procedure, so the solver would first try the biggest squares.
  3. Tip — to force the search order, you have to put the variables in a specific order to the array and then use input_order search annotation.
  4. Tip 2 — you can put the height and width in one array, and squares' coordinates in the second. Then use ''seq_search'' annotation to combine two search procedures
  5. Tip 3 — you can achieve a specific order using array comprehensions, but of course you can also try built-in function like ''reverse'' or ''sort_by''.
• Evaluate the new search procedure with the more difficult instances (bigger n))

% Parameters
%%%%%%%%%%%
int: n;                      % How many squares do we have?
set of int: SQUARES = 1..n;  % Set of the available squares

% Variables
%%%%%%%%%%%
var <min>..<max>: height;    % height of the container
var <min>..<max>: width;     % width of the conainer
var <min>..<max>: area = height * width; % container's area
array[SQUARES] of var <min>..<max>: x; % squares' coordinates in the container
array[SQUARES] of var <min>..<max>: y; % squares' coordinated in the container
  
% Constraints 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

% Constraint 1: Squares should fit inside the container
  
% Constraint 2: Squares should not overlap

% Goal
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
solve minimize area; 
  

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

The real problem we have to deal with is much less abstract — we have to schedule coal loading in the Australian port. The problem is a relaxed version of a real problem, the University of Melbourne had to deal with.

During the first class student is expected to finish the A stage, which is nothing more than packing problem with a plot. During the second class student should finish the model. In case there is no enough time, student is encouraged to work on the problem at home between the classes.

1. Please download and extract |the data.
   1. handout.pdf contains the detailed description of the problem
   2. portschedule.mzp is a MiniZincIDE project. There are numerous helpful comments inside.