Constraint Programming: Search Modeling
This laboratory will concern basic search modeling in the Constraint Programming.
First it will be introduced in the already known NQueens
problem.
Next we will solve a new issue, where search modeling will have a big impact on the solving process.
All files required to solve the assignments are available via the repository, so clone it first.
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 socalled MiniSearch language, which still isn't a part of the MiniZincIDE package.
NQueens Again
Packing Problem
The packing problem is a problem of fitting ndimensional solids in the ndimensional 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[n1], y[n1], …, 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 builtin 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)]