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.
All files required to solve the assignments are available via the repository, so clone it first.
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:
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:
first_fail
)indomain_min
).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.
int_search(rows, input_order, indomain_min, complete); int_search(rows, input_order, indomain_median, complete); int_search(rows, first_fail, indomain_min, complete); int_search(rows, first_fail, indomain_median, complete);
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.
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. [… |i in SQUARES]
)n
input_order
search annotation.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 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)]