Weight-Based Variable Ordering in the Context of High-Level Consistencies
This work addresses an incremental improvement in constraint satisfaction problem solving for researchers and practitioners in AI and optimization.
The paper tackles the problem of updating constraint weights in the dom/wdeg heuristic when multiple constraints cause domain wipeouts under high-level consistencies like singleton and relational consistencies, proposing and evaluating several strategies with statistical comparisons to provide recommendations.
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.