Explanation-based weighted degree

Hebrard, Emmanuel; Siala, Mohamed

Explanation-based weighted degree

Files

4580.pdf(466.25 KB)

Accepted version

Date

2017-05-31

Authors

Hebrard, Emmanuel

Siala, Mohamed

Publisher

Springer International Publishing

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.

Keywords

Constraint programming , Weighted degree heuristic , Global constraints , Computer programming , Constraint theory , Heuristic programming , Operations research , Global constraints , ITS efficiencies , Linear inequalities , State of the art , Variable order , Weighted degree , Weighted degree heuristic , Heuristic methods

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