| << Prev | - Up - |
The following table shows impressively the benefits of combining propagation-based and linear programming solvers for this kind of problem. We used LP_SOLVE 2.0 as LP solver. Note using a different LP solver may produce different results. By combining both constraint models the number of nodes in the search tree could be reduced by two resp. one to orders of magnitudes. This results in a speed-up of one order of magnitude and memory saving by the same amount.
Model | Nodes | Sols | Failures | Depth | runtime | heap |
|---|---|---|---|---|---|---|
[sec] | [MB] | |||||
FD Model | 5270 | 44 | 5227 | 18 | 4.980 | 10.4 |
LP Model | 490 | 12 | 479 | 26 | 3.390 | 3.3 |
FD+LP Model | 52 | 8 | 45 | 12 | 0.390 | 0.6 |
The times were taken on a Pentium Pro 200MHz with 192 MB memory.
The described technique has been used to tackle set partitioning problems. In contrast to [Mül98] all problem could be solve in acceptable time (detailed benchmarks are included as they are available).
| << Prev | - Up - |