Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
en:dydaktyka:csp:lab3 [2017/03/20 16:39]
msl [Materials]
en:dydaktyka:csp:lab3 [2020/11/30 12:50] (current)
msl [N-Queens Again]
Line 1: Line 1:
-====== Constraint Programming: ​Practical Use Case =====+====== Constraint Programming: ​Search Modeling ​=====
  
-This laboratory will concern ​practical use of the constraint programmingHowever, real problems are difficult, classes are short. Therefore ​it will take more than one meeting to finish ​the assignmentsStudents 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 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 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|}} {{ :​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}}
Line 27: 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''​)) ​
  
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. ​ 
- 
  
en/dydaktyka/csp/lab3.1490024355.txt.gz · Last modified: 2019/06/27 16:00 (external edit)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0