This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:dydaktyka:csp:lab1 [2017/03/03 14:18] msl created |
en:dydaktyka:csp:lab1 [2020/03/22 18:47] (current) msl [Constraint Programming: Basic Problems] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== 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 ===== | ||
| Line 48: | Line 49: | ||
| ==== 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}}): | ||
| Line 94: | Line 95: | ||
| - 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 ==== | ||
