A Probabilistic Model to Count Solutions on the alldifferent Constraint

Giovanni Lo Bianco; Charlotte Truchet; Xavier Lorca; Vlady Ravelomanana

A Probabilistic Model to Count Solutions on the alldifferent Constraint

Giovanni Lo Bianco ^{1, 2} Charlotte Truchet ¹ Xavier Lorca ³ Vlady Ravelomanana ⁴

1 TASC - Théorie, Algorithmes et Systèmes en Contraintes

LS2N - Laboratoire des Sciences du Numérique de Nantes

2 DAPI - Département Automatique, productique et informatique

3 CGI - Centre Génie Industriel

4 Université de Paris VII

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.

Type de document :

Communication dans un congrès

CP 2018 - The 24th International Conference on Principles and Practice of Constraints Programming, Aug 2018, Lille, France. 9 p., 2018, Doctoral Program Proceedings. 〈http://cp2018.a4cp.org/dp-proceedings.pdf#page=43〉

Domaine :

Sciences de l'ingénieur [physics]

Liste complète des métadonnées

https://hal-mines-albi.archives-ouvertes.fr/hal-01923767
Contributeur : Imt Mines Albi Ecole Nationale Supérieure Des Mines d'Albi-Carmaux <>
Soumis le : jeudi 15 novembre 2018 - 14:17:46
Dernière modification le : vendredi 14 décembre 2018 - 10:28:18

A Probabilistic Model to Count Solutions on the alldifferent Constraint

Identifiants

Collections

Citation

Exporter

Métriques

59

Contact

A Probabilistic Model to Count Solutions on the alldifferent Constraint

Identifiants

Collections

Citation

Exporter

Partager

Métriques

59

Contact