# 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.

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:

1. select variable — choose, which variable will receive value in this step
2. 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:

• select variable which has the lowest amount of available values (`first_fail`)
• select the smallest available value (`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.

### N-Queens Again

• Definition: same as always.
• Assignments:
1. Run model using Gecode (Gist, bundled) solver — select it in the configuration tab
• play with the search :)
2. Check four different search strategies
```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);```
4. Compare solving time of the problem using different stragies.
5. Don't worry, be happy.

## 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:
1. Fill the domains' bounds
2. Tip — use set comprehension (np. `[… |i in SQUARES]`)
• Stage 2:
1. Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small `n`
• Stage 3:
1. Replace your constraint with the global constraint diffn
2. Tip — you may have to introduce a new array parameter to the model
• Stage 4:
2. Tip 1 — how is the packing related to the scheduling, e.g. the cumulative constraint?
3. Tip 2 — scheduling is a kind of packing where time is one of the dimensions
• Stage 5:
1. Change the search procedure, so the solver would first try the smallest containers
2. Change the search procedure, so the solver would place the biggest squares first.
3. 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.
4. 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, y`). Then use ''seq_search'' annotation to combine two search procedures
5. 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)]``` 