Explanation-Based Weighted Degree

Emmanuel Hébrard 1 Mohamed Siala 1
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
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 (AllD-ifferent, 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.
Type de document :
Communication dans un congrès
CPAIOR, Jun 2017, Padoue, Italy. 9p., 2017
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/hal-01670307
Contributeur : Emmanuel Hebrard <>
Soumis le : jeudi 21 décembre 2017 - 11:46:36
Dernière modification le : mercredi 28 février 2018 - 10:23:14

Fichier

cpaior2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01670307, version 1

Citation

Emmanuel Hébrard, Mohamed Siala. Explanation-Based Weighted Degree. CPAIOR, Jun 2017, Padoue, Italy. 9p., 2017. 〈hal-01670307〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

15