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:lab2 [2017/03/13 13:31]
msl [Graph Coloring]
en:dydaktyka:csp:lab2 [2020/03/13 13:48] (current)
msl
Line 1: Line 1:
-====== Constraint Programming:​ Basic Modelling ​Tenchniques ​=====+====== Constraint Programming:​ Basic Modelling ​Techniques ​=====
  
 ===== Symmetry Breaking =====  ===== Symmetry Breaking ===== 
  
-The problem is said to contain symmetry if there are exist classes of equivalent solutions --- solutions, which are called symmetrical because there exist a simple mechanical procedure to obtain one from another. Graph Coloring Problem has a very obvious symmetry --- in every solution we can freely swap colors, e.g. every red node repaint as blue, and every blue node repaint as red. Solutions of this kind aren't bad, just redundant, leading to much bigger search space. Symmetry breaking prunes the search space by removing symmetries from the problem.+The problem is said to contain symmetry if there exist classes of equivalent solutions --- solutions, which are called symmetrical because there exists ​a simple mechanical procedure to obtain one from another. Graph Coloring Problem has a very obvious symmetry --- in every solution we can freely swap colors, e.g. every red node repaint as blue, and every blue node repaint as red. Solutions of this kind aren't bad, just redundant, leading to much bigger search space. Symmetry breaking prunes the search space by removing symmetries from the problem
 + 
 +All files required to solve the assignments are available via [[https://​gitlab.com/​agh-krr/​2019-2020/​labs/​|the repository]],​ so clone it first.
  
 ==== Graph Coloring ==== ==== Graph Coloring ====
   * Problem: Same as [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​graph_coloring|before]]   * Problem: Same as [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​graph_coloring|before]]
   * Assignment:   * Assignment:
-    ​- Download and extract {{:​en:​dydaktyka:​csp:​csp_coloring.zip||archive}}. +    - Look at and comprehend ''​lab3/​graph_coloring/​graph_coloring.mzn''​ model. ​    
-    ​- Look at and comprehend ''​csp_coloring.mzn''​ model. ​    +    - Try to solve the ''​basic_data.dzn''​ instance. 
-    - Try to solve the ''​csp_coloring_data.dzn''​ instance. +      * You can use the model created during previous classes 
-      * You can use model created during previous classes +      * There is a chance, that problem would too difficult to be solved in a reasonable time. 
-      * There is a chance, that problem would to difficult to be solved in a reasonable time. +    - File ''​data_with_clique.dzn''​ includes info about the largest clique in the graph
-    - File ''​csp_coloring_data2.dzn''​ includes info about the largest clique in the graph+
       * ''​minColorsNumber''​ - size of the largest clique       * ''​minColorsNumber''​ - size of the largest clique
       * ''​maxClique''​ - indexes of the vertices forming the largest clique       * ''​maxClique''​ - indexes of the vertices forming the largest clique
Line 23: Line 24:
   * Assignment:   * Assignment:
     - Find a symmetry in the problem.     - Find a symmetry in the problem.
-    ​- Download and extract {{:​pl:​dydaktyka:​csp:​csp_n_knapsack.zip|the archive}}  +    - Look at and comprehend ''​lab3/​multi_knapsack/​multi_knapsack.mzn''​.
-    ​- Look at and comprehend ''​csp_n_knapsack.mzn''​.+
       * Note :!:: this model is not an example of good constraint model; it's just used to show a common technique to break symmetries       * Note :!:: this model is not an example of good constraint model; it's just used to show a common technique to break symmetries
       * Note use of the ''​at_most''​ global constraint.       * Note use of the ''​at_most''​ global constraint.
-      * There is a defined predicate named ''​knapsack''​ -> it's the first example of user defined predicate+      * There is a defined predicate named ''​knapsack''​ -> it's the first example of user-defined predicate
     - Run model with the associated data file:     - Run model with the associated data file:
-      * The problem may be to hard for the solver +      * The problem may be too hard for the solver 
-    - Break symmetry using [[http://​www.minizinc.org/​doc-lib/doc-globals-lexicographic.html#Ipredicate-lex_less-po-array-bo-int-bc-of-var-set-of-int-cl-x-cm-array-bo-int-bc-of-var-set-of-int-cl-y-pc|''​lex_less''​ global constraint]]. +    - Break symmetry using [[https://​www.minizinc.org/​doc-2.4.2/en/lib-globals.html#​lexicographic-constraints|''​lex_less_eq''​ global constraint]]. 
-    - Run new model with the same data file+    - Run the new model with the same data file
  
 ===== Redundant Constraints ===== ===== Redundant Constraints =====
  
-There is a good chance the problem can be defined in more than one way. Also you may find a set of constraints that is sufficient to define the problem. That's cool, however there can exist so called "​redundant constraints";​ redundant because they do not have impact on the number or quality of the solutions. The only reason to include them into the model is that they may contain additional info about the structure of the problem, therefore giving solver an opportunity to prune the search space (most of the solver prune the search space by propagating constraints,​ redundant constraint may boost this process).+There is a good chance the problem can be defined in more than one way. Also you may find a set of constraints that is sufficient to define the problem. That's cool, however there can exist so called "​redundant constraints";​ redundant because they do not have an impact on the number or quality of the solutions. The only reason to include them in the model is that they may contain additional info about the structure of the problem, therefore giving solver an opportunity to prune the search space (most of the solver prune the search space by propagating constraints, ​redundant constraint may boost this process).
 ==== Magic Sequence ===== ==== Magic Sequence =====
   * Definition: Same as [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​magic_sequence|before]]   * Definition: Same as [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​magic_sequence|before]]
   * Assignment:   * Assignment:
-    - Download, extract, ​comprehend ​{{:​pl:​dydaktyka:​csp:​csp_magic_series.zip|model}}+    - Look at and comprehend ​''​lab3/​magic_series/​magic_series.mzn''​
     - Add redundant constraints,​ hints:     - Add redundant constraints,​ hints:
       * what should be equal the sum of the magic sequence?       * what should be equal the sum of the magic sequence?
Line 48: Line 48:
 ==== Channeling ==== ==== Channeling ====
  
-If you have more than one model of the same problem, you can combine them into one model. Why would one do that? Mostly because some constraints are easier to express with different variables. Other reason could be that the second model often makes a great example of the redundant constraints.+If you have more than one model of the same problem, you can combine them into a single ​model. Why would one do that? Mostly because some constraints are easier to express with different variables. Other reason could be that the second model often makes a great example of the redundant constraints.
  
   * Problem: [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​n-queens|N-Queens]] again   * Problem: [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​n-queens|N-Queens]] again
   * Assignment:   * Assignment:
-    - Download, extract ​and comprehend ​{{:​pl:​dydaktyka:​csp:​csp_n_hetmans.zip|}} (or use your own model) +    - Look at and comprehend ​''​lab3/​n_queens/​n_queens.mzn''​ 
-    - Add the other problem definition to the problem +    - Add another model of the problem 
-      * Example: if the queens were assigned ​to the columnsyou may now assign them to the rows+      * try to use the boolean array of variables ''​array[1..n1..n] of var bool: qb;''​ (queen boolean) 
 +      * add missing constraints so the second model was also independent ​
     - Channel constraints from the both models:     - Channel constraints from the both models:
-      * You may use channeling ​constraint ​[[http://​www.minizinc.org/​doc-lib/​doc-globals-channeling.html#​Ifunction-array-bo-int-bc-of-var-int-cl-inverse-po-array-bo-int-bc-of-var-int-cl-f-pc|''​inverse''​]]+      * create ​constraint ​that connects variables from the model 
     - Compare running time of the normal and channeled model     - Compare running time of the normal and channeled model
-    - Give yourself a high five, <wrap lo>however new solvers are good enough to solve n-queens without ​the channeling. This technique is still valid for the more complicated ​problems</​wrap>​+    ​- Add symmetry breaking to the problem by using ''​lex_lesseq''​ constraint on the different permutations of the ''​qb''​ array   
 +      * below the assignments there is a code listing with all permutations calculated in MiniZinc, can you tell what symmetries they represent?​ 
 +    - Compare running time again 
 +    ​- Give yourself a [[https://​youtu.be/​kMUkzWO8viY|self-five]], <wrap lo>in this case, it may not improve the running time, but the technique ​itself ​is very useful in more complex ​problems</​wrap>​
  
-===== Search Modeling ===== +<​code>​ 
- +array[int] of var bool: qb0 array1d(qb);​ 
-So far we haven'​t talked about the way solver looks for the solutionThere are many different techniques to solve to constraint programming problemhowever basic techniques often perform a DFS (backtrackingsearch with two steps at every node: +array[int] of var bool: qb1 [ qb[j,i] | i,j in 1..n ]; 
-  - select variable --- choosewhich variable will receive a value in this step +array[int] of var bool: qb2 [ qb[i,j] | i in reverse(1..n),​ j in 1..n ]; 
-  - select value --- choosewhich value from the variable'​s domain will be chosen +array[int] of var bool: qb3 = [ qb[j,i] | i in 1..nj in reverse(1..n]; 
-You may control this procedure ​in MiniZinc using search annotations just after the solve keyworde.g<​code>​ +array[int] of var bool: qb4 = [ qb[i,j] | i in 1..nj in reverse(1..n) ]; 
-solve :: int_search(array, ​first_failindomain_min,​ completesatisfy;+array[int] of var bool: qb5 = [ qb[j,i] | i in reverse(1..n), j in 1..n ]; 
 +array[int] of var boolqb6 = [ qb[i,j] | i,j in reverse(1..n) ]; 
 +array[int] of var bool: qb7 = [ qb[j,i] | i,j in reverse(1..n];
 </​code>​ </​code>​
-mean that że 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 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.+===== Reified Constraints =====
  
-==== N-Queens Again ==== +[[https://en.wikipedia.org/​wiki/​Reification|Reification]] in Constraint Programming means treating the constraint as a first-order citizeni.e. you can use the constraint as a boolean value in your model. If you've used the ''​bool2int''​ function in the Magic Sequence problem, you could do that only because the constraint ''​=''​ has been reified. Reification allows us to create models ​with "soft constraints"​ or "​conditional constraints",​ i.e. one constraint has to be satisfed only if the second one is satisfied too, otherwise they both can be ignored. To do that, one has only to reify the constraints and connect them with the implication''​constraint1 ​-> constraint2''​. Let's practice this quite useful technique :
-  + 
-  * Definitionsame as always. +==== Stable Marriage Problem ===== 
-  * Assignments:​ +  * Problem: There are two classes of objects ​(men and womenfor examplethat have to be matched according to their preferences. We say that a matching ​(marriageis unstable if both spouses would prefer to be with somebody else. You can read more about this problem on [[https://en.wikipedia.org/wiki/Stable_marriage_problem|wikipedia]]. 
-    ​Run model using Gecode (Gistbundled) solver --- select it in the configuration tab +  * Assignment: 
-      * play with the search ​:)  +    - Look at and comprehend ''​lab3/​stable-marriage/​stable-marriage.mzn''​ 
-    ​Check four different search strategies<​code> +    - Add missing variablesconstraints 
-int_search(rows,​ input_order,​ indomain_min,​ complete); +    - Give a high-five to your teacher :)
-int_search(rows,​ input_order,​ indomain_median,​ complete); +
-int_search(rowsfirst_fail, indomain_min,​ complete)+
-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+
-    - Compare solving time of the problem using different stragies+
-    - Don't worrybe happy.+
  
  
en/dydaktyka/csp/lab2.1489408278.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