====== 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:
  - 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. <code>
solve :: int_search(array, first_fail, indomain_min, complete) satisfy;
</code>
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:
    - Run model using Gecode (Gist, bundled) solver --- select it in the configuration tab
      * play with the search :) 
    - Check four different search strategies<code>
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);</code>  
    - Read about the [[https://www.minizinc.org/doc-2.5.2/en/fzn-spec.html#annotations|different strategies]]. Select one according to your taste.
    - Compare solving time of the problem using different strategies (try at least three different problem sizes, you may just fill csv file in the repository).
    - 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.

{{ :en:dydaktyka:csp:square_packing.png?nolink&300|}}
  * **Definition**: having ''n'' squares sized accordingly ''1x1,2x2,...,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:**
    - Replace your constraint with [[https://www.minizinc.org/doc-2.2.0/en/lib-globals.html?highlight=diffn|the global constraint diffn]]
    - Tip --- you may have to introduce a new array parameter to the model
  * **Stage 4:**
    - Add redundant constraints
    - Tip 1 --- how is the packing related to the scheduling, e.g. [[https://www.minizinc.org/doc-2.2.0/en/predicates.html?highlight=cumulative|the cumulative constraint]]?
    - Tip 2 --- scheduling is a kind of packing where time is one of the dimensions
    - Tip 3 --- {{:en:dydaktyka:csp:cumulative.png?linkonly|this picture satisfies ''cumulative'' constraint, but it doesn't satisfy packing constraint}}
  * **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 [[http://www.minizinc.org/doc-lib/doc-annotations-search.html#Iannotation-seq_search-po-array-bo-int-bc-of-ann-cl-s-pc|''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 [[https://www.minizinc.org/doc-2.2.0/en/lib-builtins.html?highlight=reverse|''reverse'']] or [[https://www.minizinc.org/doc-2.2.0/en/mzn_search.html?highlight=seq_search|''sort_by'']].
  * Evaluate the new search procedure with the more difficult instances (bigger ''n'')) 


<code>
% 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)]
</code>