Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Dead-end elimination for weighted CSP

Abstract : Soft neighborhood substitutability (SNS) is a powerful technique to automatically detect and prune dominated solutions in combinatorial optimization. Recently, it has been shown in [26] that enforcing partial SNS (PSNSr) during search can be worthwhile in the context of Weighted Constraint Satisfaction Problems (WCSP). However, for some problems, especially with large domains, PSNSr is still too costly to enforce due to its worst-case time complexity in O(ned4) for binary WCSP. We present a simplified dominance breaking constraint, called restricted dead-end elimination (DEEr), the worst-case time complexity of which is in O(ned2). Dead-end elimination was introduced in the context of computational biology as a preprocessing technique to reduce the search space [13, 14, 16, 17, 28, 30]. Our restriction involves testing only one pair of values per variable instead of all the pairs, with the possibility to prune several values at the same time. We further improve the original dead-end elimination criterion, keeping the same time and space complexity as DEEr. Our results show that maintaining DEEr during a depth-first branch and bound (DFBB) search is often faster than maintaining PSNSr and always faster than or similar to DFBB alone.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

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

https://hal.inrae.fr/hal-02746292
Déposant : Migration Prodinra <>
Soumis le : mercredi 3 juin 2020 - 09:53:32
Dernière modification le : mercredi 14 octobre 2020 - 03:56:35

Fichier

Givry13a_1.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Simon de Givry, Steve Prestwich, Barry O'Sullivan. Dead-end elimination for weighted CSP. 19th International Conference, Constraint Programming 2013, Sep 2013, Uppsala, Sweden. 10 p., ⟨10.1007/978-3-642-40627-0_22⟩. ⟨hal-02746292⟩

Partager

Métriques

Consultations de la notice

14

Téléchargements de fichiers

38