Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Last revision Both sides next revision
en:dydaktyka:csp:lab2 [2018/03/24 18:44]
msl
en:dydaktyka:csp:lab2 [2019/03/12 17:42]
msl [Channeling]
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 {{:​en:​dydaktyka:​csp:​csp_n_queens.zip|the model}} (or use your own)     - Download, extract and comprehend {{:​en:​dydaktyka:​csp:​csp_n_queens.zip|the model}} (or use your own)
-    - 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 [[https://​youtu.be/​kMUkzWO8viY|self-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 all permutations are calculated in MiniZinc, can you tell what symmetries they represent?​ 
 +<​code>​ 
 +array[int] of var bool: qb0 = array1d(qb);​ 
 +array[int] of var bool: qb1 = [ qb[j,i] | i,j in 1..n ]; 
 +array[int] of var bool: qb2 = [ qb[i,j] | i in reverse(1..n),​ j in 1..n ]; 
 +array[int] of var bool: qb3 = [ qb[j,i] | i in 1..n, j in reverse(1..n) ]; 
 +array[int] of var bool: qb4 = [ qb[i,j] | i in 1..n, j in reverse(1..n) ]; 
 +array[int] of var bool: qb5 = [ qb[j,i] | i in reverse(1..n),​ j in 1..n ]; 
 +array[int] of var bool: qb6 = [ 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>​ 
 +    - 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>​
  
 ===== Reified Constraints ===== ===== Reified Constraints =====
en/dydaktyka/csp/lab2.txt · Last modified: 2019/03/12 17:43 by msl
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