Differences

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

Link to this comparison view

Next revision
Previous revision
en:dydaktyka:csp:lab2 [2017/03/10 19:14]
msl created
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 ​=====
  
-===== Łamanie symetrii ​===== +===== Symmetry Breaking ​===== 
  
-Mówimy, że dany problem ​przejawia symetrięjeśli istnieją dla niego rozwiązania symetryczne,​ tjtakie, które pomimo różnych wartości zmiennych decyzyjnych,​ są sobie równoważne. Przykładem może być problem kolorowania wierzchołków grafu przedstawiony na poprzednim laboratium ​--- w każdym rozwiązaniu tego problemu możemy bez przeszkód zamienić ze sobą dwa kolorywszystkie wierzchołki zielone przemalować na niebieskieniebieskie zaś na zieloneTak powstałe rozwiązania w niczym nie ustępuje oryginalnemu,​ niemniej istnienie symetrii niesie ze sobą jedną zasadniczą wadęmianowicie ogromną przestrzeń rozwiązańw której wiele stanów jest nadmiarowychUsunięcie ich prowadzi do znacznie efektywniejszego przeszukiwania naprawdę interesujących rozwiązań.+The problem ​is said to contain symmetry if there exist classes of equivalent solutions --- solutionswhich are called symmetrical because there exists a simple mechanical procedure to obtain one from anotherGraph Coloring Problem has a very obvious symmetry ​--- in every solution we can freely swap colorse.g. every red node repaint as blueand every blue node repaint as redSolutions of this kind aren't badjust redundantleading to a much bigger search spaceSymmetry breaking prunes the search space by removing symmetries from the problem.
  
-==== Kolorowanie wierzchołków grafu ==== +All files required to solve the assignments are available via [[https://gitlab.com/agh-krr/​2019-2020/​labs/​|the repository]]so clone it first.
-  * Problemmając dany graf, należy pomalować jego wierzchołki w taki sposób, by wierzchołki połączone krawędzią miały różne kolory. +
-  * Należy: +
-    ​Pobrać i rozpakować {{:​pl:​dydaktyka:​csp:​csp_coloring.zip|}}. +
-    - Przyjrzeć się modelowi ''​csp_coloring.mzn''​. ​    +
-    - Korzystając z modelu spróbować rozwiązać problem kolorowania grafu zapisanego w ''​csp_coloring_data.dzn''​. +
-      * W razie posiadania własnego modelu z pierwszego laboratoriummożna go wykorzystać. +
-      * Istnieje szansa, że problem jest zbyt duży, żeby rozwiązać go w rozsądnym czasie. ​  +
-    - Plik ''​csp_coloring_data2.dzn''​ prócz informacji o grafie zawiera informacje o największej klice w grafie: +
-      * ''​minColoursNumber''​ - rozmiar największej kliki +
-      * ''​maxClique''​ - indeksy wierzchołków należących do największej kliki +
-    - Zmienić model tak, aby wykorzystywał informacje z ''​csp_coloring_data2.dzn''​.  +
-    - Spróbować rozwiązać problem opisany w ''​csp_coloring_data2.dzn''​ korzystając z nowego modelu.+
  
-==== Problem wielo-plecakowy ​==== +==== Graph Coloring ​==== 
-  * Problem: ​Problem plecakowy z kilkoma identycznymi plecakami zamiast jednego. +  * Problem: ​Same as [[http://​ai.ia.agh.edu.pl/wiki/en:​dydaktyka:​csp:​lab1#​graph_coloring|before]] 
-  * Należy: +  * Assignment: 
-    - Zastanowić się, gdzie leży symetria w tym problemie. +    - Look at and comprehend ​''​lab3/​graph_coloring/​graph_coloring.mzn'' ​model. ​    
-    - Pobrać i rozpakować {{:pl:​dydaktyka:​csp:​csp_n_knapsack.zip|}}  +    - Try to solve the ''​basic_data.dzn''​ instance
-    - Przyjrzeć się modelowi ​''​csp_n_knapsack.mzn''​. +      * You can use the model created during previous classes 
-      * Uwaga: ten model nie jest zbyt dobry; ma jedynie pokazać prostą technikę łamania niektórych symetrii. +      * There is a chance, that problem would too difficult to be solved in a reasonable time. 
-      * Proszę zwrócić uwagę na zastosowane ograniczenie globalne ​''​at_most''​. +    - File ''​data_with_clique.dzn'' ​includes info about the largest clique in the graph 
-      * Model zawiera zdefiniowany predykat ​''​knapsack''​ -> warto wiedzieć, że coś takiego typu można modelować w MiniZinc. Pozwala to na większą modularyzację kodu. +      * ''​minColorsNumber''​ - size of the largest clique 
-    - Uruchomić model z dołączonym plikiem: +      * ''​maxClique'' ​- indexes of the vertices forming the largest clique 
-      * Problem może być za trudny do rozwiązania. +    - Improve ​model to make use of the info about the largest clique ​ 
-      * Gdyby solver zwracał wynik "​UNSATISFIABLE",​ proszę spróbować użyć solvera "G12 fd" w zakładce "​Configuration"​ +    - Try to solve the problem again.
-    - Dodać do kodu łamanie symetrii korzystająć z ograniczenia globalnego [[http://​www.minizinc.org/​2.0/​doc-lib/​doc-globals-lexicographic.html|''​lex_less''​]]. Pozwala ona na wymuszenie kolejności plecaków. Plecaki muszą być zawsze uporządkowe leksykograficznie ze względu na swoją zawartość. +
-    - Uruchomić nowy model z tymi samymi danymi. +
-    - Czerpać zyski +
  
-===== Ograniczenia nadmiarowe =====+==== Multi-Knapsack Problem ​==== 
 +  * Definition: Knapsack problem with several identical knapsacks instead of one. 
 +  * Assignment:​ 
 +    - Find a symmetry in the problem. 
 +    - Look at and comprehend ''​lab3/​multi_knapsack/​multi_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 use of the ''​at_most''​ global constraint. 
 +      * There is a defined predicate named ''​knapsack''​ -> it's the first example of user-defined predicate 
 +    - Run model with the associated data file: 
 +      * The problem may be too hard for the solver 
 +    - Break symmetry using [[https://​www.minizinc.org/​doc-2.4.2/​en/​lib-globals.html#​lexicographic-constraints|''​lex_less_eq''​ global constraint]]. 
 +    - Run the new model with the same data file
  
-Jedną z podstawowych zasad programowania z ograniczeniami mówi, że ograniczenia są jak pieniądze --- nawet jeżeli jest ich wystarczająco,​ przydałoby się więcej. Załóżmy, że udało nam się opisać wszystkie ograniczenia konieczne do opisu zadanego problemu (tj. spełnione tylko i wyłącznie przez rozwiązania prawidłowe oraz nie eliminujące żadnych rozwiązań prawidłowych);​ nie oznacza to wcale, że powinniśmy na nich zaprzestać. Każde kolejne ograniczenie,​ które dodaje jakąś informację,​ pozwala  +===== Redundant Constraints =====
-na zmniejszenie przestrzeni przeszukiwania --- solver jest dzięki nim w stanie wcześniej "​odciąć"​ gałęzie przeszukiwania niedające nadziei na przyszłość.+
  
-==== Magiczne ciągi ​=====+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,​ a redundant constraint may boost this process). 
 +==== Magic Sequence ​===== 
 +  * Definition: Same as [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​magic_sequence|before]] 
 +  * Assignment:​ 
 +    - Look at and comprehend ''​lab3/​magic_series/​magic_series.mzn''​ 
 +    - Add redundant constraints,​ hints: 
 +      * what should be equal the sum of the magic sequence? 
 +      * what should be equal the sum of sequence elements multiplied by their indexes (if indexing starts from 0)? 
 +    - Compare solving time with and without the redundant constraints. 
 +    - Smile with satisfaction
  
-Jeżeli ktoś nie zrobił tego wcześniej, proszę przed przystąpieniem do ćwiczenia przynajmniej przeczytać opis problemu na stronie poprzedniego laboratorium.+==== Channeling ====
  
-  * Należy: +If you have more than one model of the same problem, you can combine them into a single ​model. ​Why would one do thatMostly because some constraints are easier to express with different variablesOther reason could be that the second model often makes a great example of the redundant constraints.
-    - Ściągnąć i zrozumieć ​model: {{:​pl:​dydaktyka:​csp:​csp_magic_series.zip|}} +
-    - Dodać ​do niego nadmiarowe ograniczenia. Podpowiedzi:​ +
-      * ile powinna wynosić suma magicznego ciągu? +
-      * ile powinna wynosić suma elementów magicznego ciągu, pomnożonych przez numery swoich indeksów (indeksując od 0)? +
-    - Porównać działanie modelu ''​z''​ i ''​bez''​ dodatkowych ograniczeń na dłuższych ciągach. +
-    - Czerpać zyski.+
  
-==== Modele łączone ​- n-hetmans return! ====+  * Problem: [[http://​ai.ia.agh.edu.pl/​wiki/​en:​dydaktyka:​csp:​lab1#​n-queens|N-Queens]] again 
 +  * Assignment:​ 
 +    - Look at and comprehend ''​lab3/​n_queens/​n_queens.mzn''​ 
 +    - Add another model of the problem 
 +      * try to use the boolean array of variables ''​array[1..n, 1..n] of var bool: qb;''​ (queen boolean) 
 +      * add missing constraints so the second model was also independent  
 +    - Channel constraints from the both models: 
 +      * create constraint that connects variables from the model  
 +    - Compare running time of the normal and channeled model 
 +    - 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>​
  
-Jedną z technik dodawania dodatkowych ograniczeń jest wykorzystanie kilku modeli tego samego problemu równocześniePomimo tegoże wszystkie te modele mogą wskazywać na te same rozwiązaniazawarte w nich ograniczenia w innej kolejności zawężają dziedziny zmiennychKombinacja kilku modeli pozwala na ograczenie przestrzeni przeszukiwania z kilku "​perspektyw"​ równocześnie.+<​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>​
  
-  * Problem: ponownie problem n-hetmanów. +===== Reified Constraints ​=====
-  * Należy: +
-    - Odkopać model n-hetmanów z poprzednich zajęć. Ewentualnie pobrać ten: {{:​pl:​dydaktyka:​csp:​csp_n_hetmans.zip|}} +
-    - Dopisać do niego drugą możliwość wyboru zmiennych decyzyjnych i ograniczeń +
-      * Jeżeli ostatnio zmienne były indeksowane kolumnami i wskazywały na numer wiersza, należy dopisać model odwrotny. +
-    - Powiązać ze sobą ograniczeniami oba zestawy zmiennych. +
-      * Pomocne może być globalne ograniczenie [[http://​www.minizinc.org/​2.0/​doc-lib/​doc-globals-channeling.html|''​inverse''​]] +
-    - Porównać działanie modelu pojedynczego i dualnego na problemach wielu hetmanów. +
-    - Czerpać zyski <wrap lo>z nabytej wiedzy, bowiem nowe solvery radzą sobie z n-hetmanami lepiej bez nadmiarowych ograniczeń. Niemniej w innych modelach technika ta może okazać się istotną optymalizacją.</​wrap>​ +
- +
-===== Sterowanie przeszukiwaniem ​===== +
- +
-O ile budowanie modelu w programowaniu z ograniczeniami jest zadaniem czysto deklaratywnym,​ często wiele zależy od sposobu, w jaki przeszukiwana jest przestrzeń rozwiązań. Istnieje wiele możliwych strategii, jednak w podstawowym przypadku można je zdefiniować poprzez dwa parametry:​ +
- +
-  - kolejność wyboru zmiennych - np. w kolejnym kroku solver ustali wartość zmiennej, która ma najmniejszą dziedzinę; ma największą dziedzinę; w kolejności zdefiniowania przez użytkownika,​ etc. +
-  - kolejność wyboru wartości - po wyborze zmiennej, solver musi przypisać jej wartość z dziedziny, np. wartość najmniejszą,​ medianę dziedziny, wartość losową, etc. +
- +
-Aby w MiniZincu wymusić na solverze strategię przeszukiwania,​ należy użyć tzw. adnotacji (ang. //​annotations//​). W ogólnym przypadku można je przypisywać do zmiennych podobnie jak inne parametry, ale najczęściej używa się ich przy specyfikacji celu, np. <​code>​ +
-solve :: int_search(array,​ first_fail, indomain_min,​ complete) satisfy; +
-</​code>​ +
-daje solverovi znać, że tablica zmiennych array zawiera liczby i należy ją przeszukiwać,​ najpierw wybierając zmienne o najmniejszej dziedzinie (''​first_fail''​),​ następnie przypisywać im jak najmniejsze wartości (''​indomain_min''​) i przeszukiwać całą przestrzeń rozwiązań (''​complete''​). ​+
  
-Istnieją bardziej zaawansowane metody określania strategii w poszczególnych solverachale MiniZinc chcąc być językiem niezależnym od solvera nie możsobie na to pozwolićAktualnie konstrukcje pozwalające na pełną kontrolę nad procesem przeszukiwania działają jedynie dla solvera Gecode ​wymagają dodania pewnych patchy ​do standardowej dystrybucji MiniZinc.+[[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 :)
  
-==== n-hetmans again ==== +==== Stable Marriage Problem ===== 
-  +  * 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]]. 
-  * Problem: ​już chyba każdy go zna. +  * Assignment: 
-  * Należy: +    - Look at and comprehend ''​lab3/​stable-marriage/​stable-marriage.mzn''​ 
-    - Spróbować różnych adnotacji do przeszukiwania dla tego problemu, np. <​code>​ +    - Add missing variables, constraints 
-int_search(rows, input_order,​ indomain_mincomplete)+    - Give a high-five to your teacher :)
-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> ​  +
-    - Zerknąć do [[http://www.minizinc.org/downloads/doc-latest/​flatzinc-spec.pdf|dokumentacji flatzinc, rozdział 5.6.1]]. Przeczytać opisy różnych strategii i wypróbować jakąś szaloną+
-    - Porównać prędkość działania solvera n-hetmanów dla różnych strategii+
-    - Wyczerpać zyski z dzisiejszego laboratorium. ​+
  
  
en/dydaktyka/csp/lab2.1489169652.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