Future Work

1. Disruptive conflict analysis

In some cases constraint propagation enters long loops, repeating similar work many times. For example, consider the CSP:

  • C1: (x=0 || a < b)
  • C2: (y=0 || b < a)

When x=y=1 this problem is clearly unsatisfiable and constraint propagation should detect the conflict. Even though the algorithm works correctly, it requires many iterations of the constraint-propagation algorithm. Even though, in theory, the HaifaCSP is able to learn (x=0 || y=0) this does not work well for various reasons. Nevertheless I believe that this can be fixed.

2. Support more constraint combinations during conflict analysis

Currently, HCSP is able to combine only a small set of pairs of constraints. I have seen several pairs of constraints for which it would be a big win to combine during conflict analysis. For example, combine table constraints.

3. Software engineering improvements

  • Be able to use small-domain data structures even when big domains are present in the problem.
  • Store modification-history in a more compact way to avoid memory issues with some of the CSPs