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

Exploiting problem structure for solution counting

Abstract : This paper deals with the challenging problem of counting the number of solutions of a CSP, denoted #CSP. Recent progress have been made using search methods, such as BTD [15], which exploit the constraint graph structure in order to solve CSPs. We propose to adapt BTD for solving the #CSP problem. The resulting exact counting method has a worst-case time complexity exponential in a specific graph parameter, called tree-width. For problems with sparse constraint graphs but large tree-width, we propose an iterative method which approximates the number of solutions by solving a partition of the set of constraints into a collection of partial chordal subgraphs. Its time complexity is exponential in the maximum clique size - the clique number - of the original problem, which can be much smaller than its tree-width. Experiments on CSP and SAT benchmarks shows the practical efficiency of our proposed approaches.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.inrae.fr/hal-02754934
Déposant : Migration Prodinra <>
Soumis le : mercredi 3 juin 2020 - 21:16:19
Dernière modification le : samedi 3 octobre 2020 - 03:29:01

Lien texte intégral

Identifiants

Collections

Citation

Aurélie Favier, Simon de Givry, Philippe Jégou. Exploiting problem structure for solution counting. 15th International Conference on Principles and Practice of Constraint Programming, Sep 2009, Lisbonne, Portugal. 841p., ⟨10.1007/978-3-642-04244-7_27⟩. ⟨hal-02754934⟩

Partager

Métriques

Consultations de la notice

21