ConstraintSatisfaction.hpp File Reference

Plans on (classical) backtracking techniques for constraint solving. More...

Go to the source code of this file.

Detailed Description

Plans on (classical) backtracking techniques for constraint solving.

  • Likely the constraint-related backtracking should go into its own module?
  • Also output the corresponding splitting trees; perhaps they contain the enforced assignments.
  • Given such splitting trees, again one can represent all solutions, and/or count all solutions.
  • The simple code for "constraint_backtracking_counting" shows the big problem of the notion of "propagators": Only total solutions are recognised! The generalised SAT approach should overcome this.
  • For the purpose of comparisons implement also the 3 other heuristics from [Beek, 2006, Backtracking Search Algorithms] (which use only the the domain sizes from the look-ahead).
    1. Brown and Purdom: Minimise the remaining domain size + the minimum over all other variables of the sum of their domain sizes in the branches.
    2. Geelen: Minimise for a variable the sum over its values of the product of the remaining domain sizes over all other variables. (This is closest to our, but it replaces the tau-rule by the sum, which should be a bad approximation.)
    3. Freeman: As Geelen, but instead of taking the product again the sum is chosen.
    To me (OK) this all looks like guessing around, where the true rule is the tau-rule of variable_heuristics_tau.
  • The heuristics should be optimal, given that only the domain sizes for the potential branches are available ?!
Further propagators

Definition in file ConstraintSatisfaction.hpp.