OKlibrary  0.2.1.6
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.

Todo:
constraint_backtracking
  • 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.
Todo:
Heuristics
  • 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 ?!
Todo:
Further propagators

Definition in file ConstraintSatisfaction.hpp.