This is an old revision of the document!
Constraint Programming: Practical Use Case
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.
Warming Up: Packing Problem
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:
Fill the domains' bounds
Tip — use set comprehension (np. [… |i in SQUARES]
)
Stage 2:
Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small n
Stage 3:
-
Tip — you may have to introduce a new array parameter to the model
Stage 4:
Add redundant constraints
-
Tip 2 — scheduling is a kind of packing where time is one of the dimensions
-
Stage 5:
Change the search procedure, so the solver would first try the smallest containers
Change the search procedure, so the solver would first try the biggest squares.
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.
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
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)]
Real Problem: Port Scheduling
Short Description
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.
Schedule
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.
Materials
-
handout.pdf
contains the detailed description of the problem
portschedule.mzp
is a MiniZincIDE project. There are numerous helpful comments inside.