This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:dydaktyka:csp:lab3 [2018/03/17 18:23] msl |
en:dydaktyka:csp:lab3 [2020/11/30 12:50] (current) msl [N-Queens Again] |
||
|---|---|---|---|
| Line 5: | Line 5: | ||
| Next we will solve a new issue, where search modeling will have a big impact on the solving process. | 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 ===== | ===== Search Modeling ===== | ||
| - | So far we haven't talked about the way solver looks for the solution. There are many different techniques to solve to constraint programming problem, however basic techniques often perform a DFS (backtracking) search with two steps at every node: | + | 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 a value in this step | + | - select variable --- choose, which variable will receive value in this step |
| - select value --- choose, which value from the variable's domain will be chosen | - 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> | 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; | solve :: int_search(array, first_fail, indomain_min, complete) satisfy; | ||
| </code> | </code> | ||
| - | mean that że integer (''int'') variables from the ''array'' should be search exhaustively (''complete'') according to the simple strategy: | + | mean that integer (''int'') variables from the ''array'' should be search exhaustively (''complete'') according to the simple strategy: |
| - | * select variable which has to lowest amount of available values (''first_fail'') | + | * select variable which has the lowest amount of available values (''first_fail'') |
| * select the smallest available value (''indomain_min''). | * 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. | + | 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 ==== | ==== N-Queens Again ==== | ||
| Line 30: | Line 31: | ||
| int_search(rows, first_fail, indomain_min, complete); | int_search(rows, first_fail, indomain_min, complete); | ||
| int_search(rows, first_fail, indomain_median, complete);</code> | int_search(rows, first_fail, indomain_median, complete);</code> | ||
| - | - Read about the [[http://www.minizinc.org/doc-lib/doc-annotations-search.html|different strategies]]. Select one according to your taste. | + | - 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 stragies. | + | - 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. | - Don't worry, be happy. | ||
| Line 39: | Line 40: | ||
| {{ :en:dydaktyka:csp:square_packing.png?nolink&300|}} | {{ :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 sqaures without overlapping.. | + | * **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:** | * **Stage 1:** | ||
| - Fill the domains' bounds | - Fill the domains' bounds | ||
| Line 46: | Line 47: | ||
| - Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small ''n'' | - Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small ''n'' | ||
| * **Stage 3:** | * **Stage 3:** | ||
| - | - Replace your constraint with [[http://www.minizinc.org/doc-lib/doc-globals-packing.html#Ipredicate-diffn-po-array-bo-int-bc-of-var-int-cl-x-cm-array-bo-int-bc-of-var-int-cl-y-cm-array-bo-int-bc-of-var-int-cl-dx-cm-array-bo-int-bc-of-var-int-cl-dy-pc|the global constraint diffn]] | + | - 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 | - Tip --- you may have to introduce a new array parameter to the model | ||
| * **Stage 4:** | * **Stage 4:** | ||
| - Add redundant constraints | - Add redundant constraints | ||
| - | - Tip 1 --- how is the packing related to the scheduling, e.g. [[http://www.minizinc.org/doc-lib/doc-globals-scheduling.html#Ipredicate-cumulative-po-array-bo-int-bc-of-var-opt-int-cl-s-cm-array-bo-int-bc-of-var-int-cl-d-cm-array-bo-int-bc-of-var-int-cl-r-cm-var-int-cl-b-pc|the cumulative constraint]]? | + | - 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 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}} | - Tip 3 --- {{:en:dydaktyka:csp:cumulative.png?linkonly|this picture satisfies ''cumulative'' constraint, but it doesn't satisfy packing constraint}} | ||
| Line 58: | Line 59: | ||
| - 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 --- 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 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 [[http://www.minizinc.org/doc-lib/doc-builtins-array.html#Ifunction-array-bo-dd-dd-E-bc-of-var-dd-T-cl-reverse-po-array-bo-dd-dd-E-bc-of-var-dd-T-cl-x-pc|''reverse'']] or [[http://www.minizinc.org/doc-lib/doc-builtins-sort.html#Ifunction-array-bo-dd-dd-E-bc-of-var-dd-T-cl-sort_by-po-array-bo-dd-dd-E-bc-of-var-dd-T-cl-x-cm-array-bo-dd-dd-E-bc-of-float-cl-y-pc|''sort_by'']]. | + | - 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'')) | * Evaluate the new search procedure with the more difficult instances (bigger ''n'')) | ||
