This is an old revision of the document!
Constraint Programming: Basic Modelling Tenchniques
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.
Graph Coloring
-
Assignment:
-
Look at and comprehend csp_coloring.mzn
model.
Try to solve the csp_coloring_data.dzn
instance.
You can use model created during previous classes
There is a chance, that problem would to difficult to be solved in a reasonable time.
File csp_coloring_data2.dzn
includes info about the largest clique in the graph
Improve model to make use of the info about the largest clique
Try to solve the problem again.
Multi-Knapsack Problem
Redundant Constraints
There is a good chance the problem can be defined in more than a 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).
Magiczne ciągi
Jeżeli ktoś nie zrobił tego wcześniej, proszę przed przystąpieniem do ćwiczenia przynajmniej przeczytać opis problemu na stronie poprzedniego laboratorium.
Należy:
-
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!
Jedną z technik dodawania dodatkowych ograniczeń jest wykorzystanie kilku modeli tego samego problemu równocześnie. Pomimo tego, że wszystkie te modele mogą wskazywać na te same rozwiązania, zawarte w nich ograniczenia w innej kolejności zawężają dziedziny zmiennych. Kombinacja kilku modeli pozwala na ograczenie przestrzeni przeszukiwania z kilku “perspektyw” równocześnie.
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.
solve :: int_search(array, first_fail, indomain_min, complete) satisfy;
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 solverach, ale MiniZinc chcąc być językiem niezależnym od solvera nie może sobie na to pozwolić. Aktualnie konstrukcje pozwalające na pełną kontrolę nad procesem przeszukiwania działają jedynie dla solvera Gecode i wymagają dodania pewnych patchy do standardowej dystrybucji MiniZinc.
n-hetmans again