Title :
A Value Ordering Heuristic for Weighted CSP
Author :
Levasseur, Nicolas ; Boizumault, Patrice ; Loudni, Samir
Author_Institution :
Univ. de Caen, Caen
Abstract :
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.
Keywords :
constraint theory; estimation theory; optimisation; search problems; CELAR benchmarks; assignment estimation; limited discrepancy search; value ordering heuristic; weighted constraint satisfaction problems; Artificial intelligence; Constraint optimization; Cost accounting; Counting circuits; Filtering algorithms; Search methods; Tellurium;
Conference_Titel :
Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on
Conference_Location :
Patras
Print_ISBN :
978-0-7695-3015-4
DOI :
10.1109/ICTAI.2007.45
