Explanation-based weighted degree

Files in this item

Icon
Name: 4580.pdf
Size: 466.2Kb
Format: PDF
Description: Accepted version
View/Open

Explanation-based weighted degree

Hebrard, Emmanuel; Siala, Mohamed
Date: 2017-05-31
Copyright: © Springer International Publishing AG 2017. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-59776-8_13
Full text restriction information: Access to this article is restricted until 12 months after publication by request of the publisher.
Restriction lift date: 2018-05-31
Citation: Hebrard, E. and Siala, M. (2017) 'Explanation-Based Weighted Degree', in Salvagnin, D. and Lombardi, M. (eds.) Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Lecture Notes in Computer Science, LCNS vol. 10335, Cham: Springer International Publishing, pp. 167-175. doi:10.1007/978-3-319-59776-8_13
Published Version: 10.1007/978-3-319-59776-8_13

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.

Show full item record

This item appears in the following Collection(s)

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement