3.5 Short Evalution

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. 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.

Constraints Model

Nodes

Solutions

Failure

Depth

runtime [sec]

heap [MB]

Finite Domain Model

5270

44

5227

18

4.980

10.4

Linear Programming Model

490

12

479

26

3.390

3.3

Combined 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).


Tobias Müller
Version 1.0.1 (19990218)