This is an old revision of the document!
Constraint Programming: Search Modeling
This laboratory will concern basic search modeling in the Constraint Programming.
First it will be introduced in the already known N-Queens
problem.
Next we will solve a new issue, where search modeling will have a big impact on the solving process.
Search Modeling
So far we haven't talked about the way solver looks for the solution. There are many different techniques to solve to constraint programming problem, however basic techniques often perform a DFS (backtracking) search with two steps at every node:
select variable — choose, which variable will receive a value in this step
select value — choose, which value from the variable's domain will be chosen
You may control this procedure in MiniZinc using search annotations just after the solve keyword. e.g.
solve :: int_search(array, first_fail, indomain_min, complete) satisfy;
mean that że integer (int
) variables from the array
should be search exhaustively (complete
) according to the simple strategy:
In order to define more interesting search strategies one has to use so called MiniSearch language, which still isn't a part of the MiniZincIDE package.
N-Queens Again
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
squares 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 place the biggest squares first.
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 (e.g.
[height, width]
), and squares' coordinates in the second (e.g.
[x[n], y[n], x[n-1], y[n-1], …, x[1], y[1]
). 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)]
Here is a complete model for lazy overworked people.
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.