A Probabilistic Model to Count Solutions on the alldifferent Constraint

Giovanni Lo Bianco 1, 2 Charlotte Truchet 1 Xavier Lorca 3 Vlady Ravelomanana 4
1 TASC - Théorie, Algorithmes et Systèmes en Contraintes
LS2N - Laboratoire des Sciences du Numérique de Nantes
2 IMT Atlantique - DAPI - Département Automatique, Productique et Informatique
3 CGI - Centre Génie Industriel
4 UPD7 - Université Paris Diderot - Paris 7
Abstract : This article presents two probabilistic models for the alldifferent constraint. We are interested in studying the combinatorial structure of the alldifferent constraint. More specifically, we are interested in the existence of solutions for an instance of alldifferent and to count them. Such informations can be used in search heuristics. From this probabilistic approach, we show how to compute some estimators of the number of solutions and we use them in a search heuristics inspired by Counting-Based Search heuristics.
Document type :
Conference papers
Complete list of metadatas
https://hal-mines-albi.archives-ouvertes.fr/hal-01923767
Contributor : Imt Mines Albi Ecole Nationale Supérieure Des Mines d'Albi-Carmaux <>
Submitted on : Thursday, November 15, 2018 - 2:17:46 PM
Last modification on : Saturday, January 18, 2020 - 1:44:00 AM

Identifiers

  • HAL Id : hal-01923767, version 1

Collections

MINES-ALBI | CGI | CNRS | EC-NANTES | UNAM | LS2N | UNIV-NANTES | IMT-ATLANTIQUE | LS2N-TASC | UNIV-PARIS7 | USPC

Citation

Giovanni Lo Bianco, Charlotte Truchet, Xavier Lorca, Vlady Ravelomanana. A Probabilistic Model to Count Solutions on the alldifferent Constraint. CP 2018 - The 24th International Conference on Principles and Practice of Constraints Programming, Aug 2018, Lille, France. 9 p. ⟨hal-01923767⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

144

Contact

Informations

CCSD