Explanation-Based Weighted Degree - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Explanation-Based Weighted Degree

Résumé

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.
Fichier principal
Vignette du fichier
cpaior2017.pdf (466.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01670307 , version 1 (21-12-2017)

Identifiants

  • HAL Id : hal-01670307 , version 1

Citer

Emmanuel Hébrard, Mohamed Siala. Explanation-Based Weighted Degree. CPAIOR, Jun 2017, Padoue, Italy. 9p. ⟨hal-01670307⟩
51 Consultations
23 Téléchargements

Partager

Gmail Facebook X LinkedIn More