Next revision
|
Previous revision
|
en:dydaktyka:csp:lab1 [2017/03/03 14:18] msl created |
en:dydaktyka:csp:lab1 [2020/03/22 18:47] msl [Constraint Programming: Basic Problems] |
====== Lab CSP: Basic Problems ====== | ====== Constraint Programming: Basic Problems ====== |
| |
In this laboratory we will solve some toy problems from the constraint programming literature. The created models will be later improved using some basic constraint programming techniques. | In this laboratory we will solve some toy problems from the constraint programming literature. The created models will be later improved using some basic constraint programming techniques. |
| |
| All files required to solve the assignments are available via [[https://gitlab.com/agh-krr/2019-2020/labs|the repository]], so clone it first and follow the Readme instructions. |
===== Warm Up ===== | ===== Warm Up ===== |
| |
==== Graph Coloring ==== | ==== Graph Coloring ==== |
| |
* Definition: assign colors the vertices in a graph in the way that no adjacent vertices have the same colors. In case of the planar graph you will require only four colors (why? there is a very famous [[http://en.wikipedia.org/wiki/Four_color_theorem|proof of this fact]]). Otherwise you can require even as many colors as there are vertices. More on the [[http://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring|wikipedia page]]. | * Definition: assign colors to the vertices in a graph in the way that no adjacent vertices have the same color. In case of the planar graph you will require only four colors (why? there is a very famous [[http://en.wikipedia.org/wiki/Four_color_theorem|proof of this fact]]). Otherwise you may need even as many colors as there are vertices. More on the [[http://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring|wikipedia page]]. |
* Assign: | * Assign: |
- Fill missing elements in the model shown below ({{:en:dydaktyka:csp:csp_coloring_data.dzn.zip|example data files}}): | - Fill missing elements in the model shown below ({{:en:dydaktyka:csp:csp_coloring_data.dzn.zip|example data files}}): |
- they are implemented using very efficient algorithms, which may take advantage of the problem structure in a better way than the many separate normal constraints. | - they are implemented using very efficient algorithms, which may take advantage of the problem structure in a better way than the many separate normal constraints. |
| |
In order to use a global constraint, first you've to find it in [[http://www.minizinc.org/doc-lib/doc-globals.html | the global constraints' library]]. Then you've to import in in the model, e.g. in order to use ''cumulative'' constraint, you've to add the ''include cumulative.mzn;'' line to the model. | In order to use a global constraint, first you've to find it in [[http://www.minizinc.org/doc-lib/doc-globals.html | the global constraints' library]]. Then you've to import in in the model, e.g. in order to use ''cumulative'' constraint, you've to add the ''include "cumulative.mzn";'' line to the model. |
| |
==== N-Queens + Global Constraints ==== | ==== N-Queens + Global Constraints ==== |