
| misclassification penalty [s]   |                |                |              |                |
|---------------------------------|----------------|----------------|--------------|----------------|
| instance set 1                  | instance set 2 |                |              |                |
| classifier                      | all features   | cheap features | all features | cheap features |
| oracle                          | 0              | 0              | 0            | 0              |
| anti-oracle                     | 19993          | 19993          | 47144        | 47144          |
| default decision                | 2304           | 2304           | 223          | 223            |
| random decision                 | 5550           | 5550           | 564          | 564            |
| best classifier on set 1        | 0.998          | 0.994          | 131          | 220.3          |
| worst classifier on set 1       | 2304           | 2304           | 223          | 223            |
| best classifier on set 2        | 0.998          | 61.66          | 131          | 186            |
| worst classifier on set 2       | 1.34           | 1.44           | 621          | 610            |
| meta-classifier                 | 1.16           | 0.996          | 220          | 222.95         |

Table 2. Summary of classifier performance on both sets of benchmarks in terms of total misclassification penalty in seconds. We first evaluated the performance using the full set of features described in Section 4, then using only the cheap features. The oracle classifier always makes the right decision, the anti-oracle always the wrong decision.

The "default decision" classifier always makes the same decision and the "random decision" one chooses one of the possibilities at random. Three-fold cross-validation was used. All numbers are rounded.

the set of instances that each one misclassifies are different for each classifier.

Note also that the classifier which performs best on one set of instances is not necessarily the best performer on the other set of instances. The same observation can be made for the classifier with the worst performance on one of the instance sets. This means that we cannot simply choose "the best" classifier or discard "the worst" for a given set of training instances.

The time required to compute the features was 27 seconds per instance on average, and it took 0.2 seconds per instance on average to run the classifiers and combine their decisions. If we take this time into account, our system is slower than just using the default implementation. This is mostly because of the cost of computing all the features required to make the decision. We do however learn good classifiers in the sense that the decision they make is better than just using the standard implementation.

For the alldifferent constraint, there is little room for improvement to start with. We therefore need to focus on making a decision as quickly as possible. Most of the time required to make the decision is spent computing the features that the classifiers need. We removed the most expensive features - all the properties of the primal graph described in Section 4 apart from edge density.

The results for the reduced set of features are shown in Table 2 as well.

The performance is not significantly worse and even better on the first set of instances, but the time required to compute all the features is only about 3 second per instance. On the first set of benchmarks, we solve each instance on average 8 seconds faster using our system (misclassification penalty of default decision minus that of our system divided by the number of instances in the set). We are therefore left with a performance improvement of an average of 5 seconds per instance. On the second set, we cannot reasonably expect a performance