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 a 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 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 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
Packing Problem
The packing problem is a problem of fitting n-dimensional 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 squares 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)]