Weight-Based Variable Ordering in the Context of High-Level
  Consistencies
  Dom/wdeg is one of the best performing heuristics for dynamic variable
ordering in backtrack search [Boussemart et al., 2004]. As originally defined,
this heuristic increments the weight of the constraint that causes a domain
wipeout (i.e., a dead-end) when enforcing arc consistency during search. "The
process of weighting constraints with dom/wdeg is not defined when more than
one constraint lead to a domain wipeout [Vion et al., 2011]." In this paper, we
investigate how weights should be updated in the context of two high-level
consistencies, namely, singleton (POAC) and relational consistencies (RNIC). We
propose, analyze, and empirically evaluate several strategies for updating the
weights. We statistically compare the proposed strategies and conclude with our
recommendations.
