This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
en:dydaktyka:csp:lab3 [2017/03/20 15:44] msl |
en:dydaktyka:csp:lab3 [2020/03/22 18:45] msl [Constraint Programming: Search Modeling] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Constraint Programming: Practical Use Case ===== | + | ====== Constraint Programming: Search Modeling ===== |
| - | This laboratory will concern practical use of the constraint programming. However, real problems are difficult, classes are short. Therefore it will take more than one meeting to finish the assignments. Students are expected to work at home between the classes and finish work during the second meeting. | + | 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. | ||
| - | ===== Warming Up: Packing Problem ====== | + | All files required to solve the assignments are available via the repository, so clone it first. |
| + | ===== Search Modeling ===== | ||
| - | First we will deal with a simple problem that is strictly related to the real problem we are interested in. The packing problem is a problem of fitting n-dimensionals solids in the n-dimensional container. We will discuss the simple case --- packing squares into a rectangle. | + | 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.2.0/en/lib-annotations.html?highlight=annotation#search-annotations|different strategies]]. Select one according to your taste. | ||
| + | - Compare solving time of the problem using different stragies. | ||
| + | - 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|}} | {{ :en:dydaktyka:csp:square_packing.png?nolink&300|}} | ||
| - | * **Definition**: having ''n'' squires 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 15: | 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}} | ||
| * **Stage 5:** | * **Stage 5:** | ||
| - Change the search procedure, so the solver would first try the smallest containers | - Change the search procedure, so the solver would first try the smallest containers | ||
| - | - Change the search procedure, so the solver would first try the biggest squares. | + | - 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 --- 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, and squares' coordinates in the second. 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'')) | ||
| Line 62: | Line 94: | ||
| ["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] | ["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] | ||
| </code> | </code> | ||
| - | |||
| - | ===== Real Problem: Port Scheduling ===== | ||
| - | |||
| - | ==== Short Description ==== | ||
| - | The real problem we have to deal with is much less abstract --- we have to schedule coal loading in the Australian port. The problem is a relaxed version of a real problem, the University of Melbourne had to deal with. | ||
| - | |||
| - | ==== Schedule ==== | ||
| - | |||
| - | During the first class student is expected to finish the ''A'' stage, which is nothing more than packing problem with a plot. During the second class student should finish the model. In case there is no enough time, student is encouraged to work on the problem at home between the classes. | ||
| - | |||
| - | ==== Materials ==== | ||
| - | |||
| - | - Please download and extract {{:en:dydaktyka:csp:portschedule.zip|the data}}. | ||
| - | - ''handout.pdf'' contains the detailed description of the problem | ||
| - | - ''portschedule.mzp'' is a MiniZincIDE project. There are numerous helpful comments inside. | ||
| - | |||
