
| Benchmark                   | time (ms)   | mem. (KByte)   | failures   | propagations   |
|-----------------------------|-------------|----------------|------------|----------------|
| All-Interval (50)           | 183.21      | 148            | 0          | 6685           |
| All-Interval (100)          | 3904.21     | 516            | 0          | 25866          |
| Alpha (naive)               | 100.00      | 23             | 7435       | 136179         |
| BIBD (7-3-60)               | 1762.85     | 4516           | 1306       | 921686         |
| Eq-20                       | 1.52        | 14             | 54         | 3460           |
| Golomb Rulers (Bnd, 10)     | 423.39      | 67             | 8890       | 1181704        |
| Golomb Rulers (Dom, 10)     | 607.86      | 419            | 8890       | 1181770        |
| Graph Coloring              | 324.46      | 3910           | 1100       | 125264         |
| Magic Sequence (Smart, 500) | 251.50      | 4484           | 251        | 84302          |
| Magic Sequence (GCC, 500)   | 305.15      | 330            | 251        | 3908           |
| Partition (32)              | 5928.04     | 265            | 160258     | 12107504       |
| Perfect Square              | 185.54      | 3972           | 150        | 305391         |
| Queens (10)                 | 36.88       | 27             | 4992       | 43448          |
| Queens (Dom, 10)            | 103.38      | 99             | 3940       | 59508          |
| Queens (100)                | 1.54        | 235            | 22         | 455            |
| Queens (Dom, 100)           | 31.83       | 2056           | 8          | 693            |
| Sorting (400)               | 1400.01     | 151413         | 0          | 459501         |
| Social Golfers (8-4-9)      | 193.37      | 10254          | 32         | 181290         |
| Social Golfers (5-3-7)      | 1199.51     | 2117           | 1174       | 852391         |
| Hamming Codes (20-3-32)     | 1140.98     | 24746          | 2296       | 753751         |
| Steiner Triples (9)         | 120.11      | 901            | 1067       | 297501         |
| Sudoku (Set, 1)             | 3.48        | 83             | 0          | 1820           |
| Sudoku (Set, 4)             | 7.30        | 148            | 1          | 3752           |
| Sudoku (Set, 5)             | 55.14       | 514            | 25         | 28038          |

variable (see Section 4.4), this invariant is violated: if, for instance, the current domain is {{1,2},{3}}, and 1 is added to the lower bound, then 3 is removed from the upper bound (in addition to 2 being added to the lower bound). If a propagator reports that it has computed a fixed point based on the assumption that the upper bound cannot have changed, it may actually not be at a fixed point. This potentially results in incorrect propagation, for instance if the propagator could detect failure if it were run again.

## 7 Evaluation

While Section 3 proved that derived propagators are perfect with respect to the mathematical model, this section shows that in most cases one can also obtain perfect implementations of derived propagators, not incurring any performance penalties compared to dedicated, handwritten propagators. Experimental setup. The experiments are based on Gecode 3.1.0, compiled using the GNU C++ compiler gcc 4.3.2, on an Intel Pentium IV at 2.8 GHz running Linux. Runtimes are the average of 25 runs, with a coefficient of deviation less than 2.5% for all benchmarks. All example programs are available in the Gecode distribution. Table 2 shows the figures for the unmodified Gecode 3.1.0 (pure integer models above, models with integer and set variables below the horizontal line), and results will be given relative to these numbers. For example, a runtime of 130% means that the example needs 30% more time, while 50% means that it is twice as fast as in Gecode 3.1.0. The column *time* shows the runtime, *mem.* the peak allocated memory, *failures* the number of failures during search, and *propagations* the number of propagator invocations.