Both sides previous revision
Previous revision
Next revision
|
Previous revision
Next revision
Both sides next revision
|
en:dydaktyka:csp:lab3 [2018/03/17 18:22] msl [Constraint Programming: Practical Use Case] |
en:dydaktyka:csp:lab3 [2019/03/21 14:30] msl |
int_search(rows, first_fail, indomain_min, complete); | int_search(rows, first_fail, indomain_min, complete); |
int_search(rows, first_fail, indomain_median, complete);</code> | int_search(rows, first_fail, indomain_median, complete);</code> |
- Read about the [[http://www.minizinc.org/doc-lib/doc-annotations-search.html|different strategies]]. Select one according to your taste. | - Read about the [[https://www.minizinc.org/doc-2.2.0/en/lib-annotations.html?highlight=annotation#search-annotations|different strategies]]. Select one according to your taste. |
- Compare solving time of the problem using different stragies. | - Compare solving time of the problem using different stragies. |
- Don't worry, be happy. | - Don't worry, be happy. |
===== Warming Up: Packing Problem ====== | |
| |
First we will deal with a simple problem that is strictly related to the real problem we are interested in. The packing problem is a problem of fitting n-dimensionals solids in the n-dimensional container. We will discuss the simple case --- packing squares into a rectangle. | ===== Packing Problem ====== |
| |
| The packing problem is a problem of fitting n-dimensional solids in the n-dimensional container. We will discuss the simple case --- packing squares into a rectangle. |
| |
{{ :en:dydaktyka:csp:square_packing.png?nolink&300|}} | {{ :en:dydaktyka:csp:square_packing.png?nolink&300|}} |
- Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small ''n'' | - Fill the missing constraints (don't use global constraints, just simple arithmetic), so the model can be solved for small ''n'' |
* **Stage 3:** | * **Stage 3:** |
- Replace your constraint with [[http://www.minizinc.org/doc-lib/doc-globals-packing.html#Ipredicate-diffn-po-array-bo-int-bc-of-var-int-cl-x-cm-array-bo-int-bc-of-var-int-cl-y-cm-array-bo-int-bc-of-var-int-cl-dx-cm-array-bo-int-bc-of-var-int-cl-dy-pc|the global constraint diffn]] | - Replace your constraint with [[https://www.minizinc.org/doc-2.2.0/en/lib-globals.html?highlight=diffn|the global constraint diffn]] |
- Tip --- you may have to introduce a new array parameter to the model | - Tip --- you may have to introduce a new array parameter to the model |
* **Stage 4:** | * **Stage 4:** |
- Add redundant constraints | - Add redundant constraints |
- Tip 1 --- how is the packing related to the scheduling, e.g. [[http://www.minizinc.org/doc-lib/doc-globals-scheduling.html#Ipredicate-cumulative-po-array-bo-int-bc-of-var-opt-int-cl-s-cm-array-bo-int-bc-of-var-int-cl-d-cm-array-bo-int-bc-of-var-int-cl-r-cm-var-int-cl-b-pc|the cumulative constraint]]? | - Tip 1 --- how is the packing related to the scheduling, e.g. [[https://www.minizinc.org/doc-2.2.0/en/predicates.html?highlight=cumulative|the cumulative constraint]]? |
- Tip 2 --- scheduling is a kind of packing where time is one of the dimensions | - Tip 2 --- scheduling is a kind of packing where time is one of the dimensions |
- Tip 3 --- {{:en:dydaktyka:csp:cumulative.png?linkonly|this picture satisfies ''cumulative'' constraint, but it doesn't satisfy packing constraint}} | - Tip 3 --- {{:en:dydaktyka:csp:cumulative.png?linkonly|this picture satisfies ''cumulative'' constraint, but it doesn't satisfy packing constraint}} |
- Tip --- to force the search order, you have to put the variables in a specific order to the array and then use ''input_order'' search annotation. | - Tip --- to force the search order, you have to put the variables in a specific order to the array and then use ''input_order'' search annotation. |
- Tip 2 --- you can put the ''height'' and ''width'' in one array (e.g. ''[height, width]''), and squares' coordinates in the second (e.g. ''[x[n], y[n], x[n-1], y[n-1], ..., x[1], y[1]''). Then use [[http://www.minizinc.org/doc-lib/doc-annotations-search.html#Iannotation-seq_search-po-array-bo-int-bc-of-ann-cl-s-pc|''seq_search'' annotation]] to combine two search procedures | - Tip 2 --- you can put the ''height'' and ''width'' in one array (e.g. ''[height, width]''), and squares' coordinates in the second (e.g. ''[x[n], y[n], x[n-1], y[n-1], ..., x[1], y[1]''). Then use [[http://www.minizinc.org/doc-lib/doc-annotations-search.html#Iannotation-seq_search-po-array-bo-int-bc-of-ann-cl-s-pc|''seq_search'' annotation]] to combine two search procedures |
- Tip 3 --- you can achieve a specific order using array comprehensions, but of course you can also try built-in function like [[http://www.minizinc.org/doc-lib/doc-builtins-array.html#Ifunction-array-bo-dd-dd-E-bc-of-var-dd-T-cl-reverse-po-array-bo-dd-dd-E-bc-of-var-dd-T-cl-x-pc|''reverse'']] or [[http://www.minizinc.org/doc-lib/doc-builtins-sort.html#Ifunction-array-bo-dd-dd-E-bc-of-var-dd-T-cl-sort_by-po-array-bo-dd-dd-E-bc-of-var-dd-T-cl-x-cm-array-bo-dd-dd-E-bc-of-float-cl-y-pc|''sort_by'']]. | - Tip 3 --- you can achieve a specific order using array comprehensions, but of course you can also try built-in function like [[https://www.minizinc.org/doc-2.2.0/en/lib-builtins.html?highlight=reverse|''reverse'']] or [[https://www.minizinc.org/doc-2.2.0/en/mzn_search.html?highlight=seq_search|''sort_by'']]. |
* Evaluate the new search procedure with the more difficult instances (bigger ''n'')) | * Evaluate the new search procedure with the more difficult instances (bigger ''n'')) |
| |
["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] | ["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] |
</code> | </code> |
| |
<wrap lo>{{:en:dydaktyka:csp:csp_packing.zip|Here}} is a complete model for <del>lazy</del> overworked people. </wrap> | |
| |
===== Real Problem: Port Scheduling ===== | |
| |
==== Short Description ==== | |
The real problem we have to deal with is much less abstract --- we have to schedule coal loading in the Australian port. The problem is a relaxed version of a real problem, the University of Melbourne had to deal with. | |
| |
==== Schedule ==== | |
| |
During the first class student is expected to finish the ''A'' stage, which is nothing more than packing problem with a plot. During the second class student should finish the model. In case there is no enough time, student is encouraged to work on the problem at home between the classes. | |
| |
==== Materials ==== | |
| |
- Please download and extract {{:en:dydaktyka:csp:portschedule.zip|the data}}. | |
- ''handout.pdf'' contains the detailed description of the problem | |
- ''portschedule.mzp'' is a MiniZincIDE project. There are numerous helpful comments inside. | |
| |
| |