A Value Ordering Heuristic for Weighted CSP
Nicolas Levasseur, Patrice Boizumault, Samir Loudni · 2007
In this paper, we propose a new value ordering heuristic for weighted constraint satisfaction problems (WCSP) based on the quality of solutions. The H-quality of an assignment estimates its capacity at occurring in solutions of "good" quality. Experiments using limited discrepancy search on random WCSP instances and CELAR benchmarks show that our value ordering always outperforms MinAC in a significant way.