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.

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.

• 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);

  3. Read about the different strategies. Select one according to your taste.
  4. 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).
  5. Don't worry, be happy.

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:
  1. Add redundant constraints
  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
  4. Tip 3 — this picture satisfies ''cumulative'' constraint, but it doesn't satisfy packing constraint
• 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[1], y[1]). 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)]