You are here

Explanation-Based Weighted Degree

Authors: 

Emmanuel Hebrard, Mohamed Siala

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
The weighted degree heuristic is among the state of the art generic variable ordering strategies in constraint programming. However, it was often observed that when using large arity constraints, its efficiency deteriorates significantly since it loses its ability to discriminate variables. A possible answer to this drawback is to weight a conflict set rather than the entire scope of a failed constraint. We implemented this method for three common global constraints (AllDifferent, Linear Inequality and Element) and evaluate it on instances from the MiniZinc Challenge. We observe that even with simple explanations, this method outperforms the standard Weighted Degree heuristic.
Conference Name: 
International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming
Digital Object Identifer (DOI): 
--
Publication Date: 
05/06/2017
Conference Location: 
Italy
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: