Overview

• Aims of mac-dbt
• Experimental results
• Conclusion

Most of complete search algorithms over Constraint Satisfaction Problems (CSP) are based on Chronological Backtracking (BT). That algorithm can be improved in two ways:

avoiding future failures eg. using filtering algorithms at each step of the search: the search space is reduced a priori. Such an improvement leads to algorithms such as Forward Checking (FC) and more recently MAC [Sabin and Freuder, 1994] which maintains arc-consistency in each step. avoiding past failures. One of the drawbacks of BT is called thrashing: continuously reexploring parts of the search space because BT could not figure out that it has already explored it (in another context). One solution to overcome this drawback is to try to analyse the past contradictions in order to get back to a relevant choice-point (as done in Conflict-directed backjumping - CBJ [Prosser, 1993]) or in order to repair bad choices (as done in Dynamic Backtracking - DBT [Ginsberg, 1993].

Naturally, the idea came to combine those two improvements in order to get efficient algorithms: FC-CBJ, FC-DBT and even MAC-CBJ. But, nobody tried MAC-DBT. There were two main reasons:

• results of the previous algorithms were not that good. Too much time was spent on analysing failures instead of really improving search.
• maintaining arc-consistency in a algorithm such as Dynamic Backtracking is not really easy and needs the use of a really dynamic constraints system.

Two series of experimentations are presented here. Note that results presented here were computed whith a version of mac-dbt implemented with the PaLM system. The aim of the shown experiments is:

1. To compare mac-dbt with fc-dbt and dbt to illustrate the interest of arc-consistency maintenance.
2. To compare mac-dbt to mac: the best CSP solving algorithm.

Results for a series of 100 <15,10,43%> problems

Zoom on phase transition

mac-dbt is much more quicker than its competitors. The closest the problem to the transition phase, the quicker mac-dbt (see a zoom view on the side).

In order to compare mac-dbt and mac, random problems are not really suitable. Indeed, mac-dbt is only of great interest if a underlying structures exists in the problem because e-constraints programming uses such a structure through explanations. Of course, random problem do not usual present such a hidden structure. Note, that results on random problems only a show a slight disadvantage for mac-dbt which maintains information (the explanations) which are not really used (see [Jussien et al., 2000] for more details).

Structured random problem were generated in order to fairly compare mac-dbt and mac. Only using two distinct random problems is no a good way for that because adequate pre-processing can identify the structure. Following [Bayardo and Schrag, 1996], random problem with an hidden structure were generated.

Two small sub-problems (in the hard zone) are generated and immerged (by renaming variables and adding soft constraints) in a bigger one. The following diagram described the obtained problems. Pour cela, nous générons deux sous-problèmes de petites taille dans la zone dure que nous immergeons (par renommage des variables et ajout de contraintes molles) dans un plus grand problème. Le schéma ci-dessous décrit les problèmes obtenus.

Generating structured problems

Here are results obtained on problems whose total number of variables varies from 20 to 26 with a fixed domain size of 15 and two immerged sub-problem involving each 8 variables with a 57% constraint density and 76% constraint tightness.

Results on structured problems (average cpu time in seconds)

The results presented above show a comparison between mac-dbt and mac with two of the best variable choice heuristics: dom which focuses on small domain variable and dom-deg which takes into account the number of related constraints.

Two interesting remarks can be drawn from the preceding results:

1. mac-dbt remains very stable as the size of the problem increases. As far as mac is concerned, cpu time tends to get higher.
2. Even if for small problems, mac-dbt results are not as good as those of mac, it quickly shows its interest as the size of the problem increases.

After those very promising results, it is time to see what appends when the number of variables dramatrically increases: from 20 to 70. As shown on the folling diagram, mac is clearly and very quickly overwhelmed by mac-dbt.

Results on big structured problems (comparison with Quick as well)

On that diagram, results obtained by the Quick [Debruyne, 1998]. This algorithm maintain stronger consistencies. The remarkable result here is that mac-dbt remains highly competitive compared to Quick. Note that the accidents at the end of the diagram are due to the low number of experiments which gives too much importance to outlayers: some problems still resists mac-dbt !

mac-dbt fills a hole in the constraint solvers menagerie: it is to dbt what mac is to bt. Adding arc-consistency to dbt-based algorithms really pays off. Moreover, mac-dbt shows that e-constraints really provides powerful new search techniques. It has been showed here on structured problems.