Description

Il est bien connu au sein de la communauté SAT/CP que différentes
stratégies pour sélectionner les variables pendant la recherche
(c’est-à-dire l’ordre dans lequel les variables sont assignées)
présentent des performances différentes selon les classe ou instance
de problème résolues. De nombreuses stratégies existent dans la
littérature, statiques, dynamiques ou adaptatives. Le choix de la
bonne stratégie dépend des caractéristiques du problème, telles que la
densité du réseau de contraintes, la taille des domaines des
variables, mais aussi d’autres critères difficiles à
caractériser. Choisir la meilleure stratégie nécessite une expertise
du domaine, ce qui prive de nombreux utilisateurs du meilleur choix
pour leur problème.

Dans ce projet de doctorat, nous visons à étudier les propriétés des
stratégies existantes pour comprendre leur efficacité selon les
caractéristiques du problème. Nous visons à comprendre l’impact des
perturbations aléatoires sur les performances de ces stratégies. Nous
voulons également examiner leurs relations et leurs interactions avec
d’autres paramètres de la résolution de problèmes à contraintes tels
que la propagation de contraintes et le no-good learning. Le but
ultime est de proposer un cadre d’apprentissage qui puisse guider la
recherche en combinant efficacement la stratégie de branchement et la
propagation. Dans plusieurs des étapes ci-dessus, une évaluation
expérimentale sera nécessaire ainsi qu’une comparaison avec l’état du
art.

Compétences requises

– Bonnes compétences en programmation Python ou JAVA – Une expérience en CP et ML sera très appréciée.

Bibliographie

References

1. Gomes, C., Selman, B., Crato, N., Kautz, H.: Heavy-tailed phenomena
in satisfiability and constraint satisfaction problems. Journal of
Automated Reasoning 24(1), 67–100 (2000).

2. Gomes, C.P., Selman, B., Kautz, H.: Boosting combinatorial search
through randomization. In: Proceedings of AAAI ’98. pp. 431–437
(1998).

3. Christian Bessiere :”Constraint Propagation”. Chapter 3 of the Handbook of Constraint Programming (2006)
https://ics.uci.edu/~dechter/courses/constraint-propagation-bessiere.pdf

4. Hugues Wattez, Christophe Lecoutre, Anastasia Paparrizou, Sébastien Tabary:
Refining Constraint Weighting. ICTAI 2019: 71-77

5. Frédéric Koriche, Christophe Lecoutre, Anastasia Paparrizou, Hugues
Wattez: Best Heuristic Identification for Constraint Satisfaction. IJCAI 2022: 1859-1865

6. Anastasia Paparrizou, Hugues Wattez: Perturbing Branching
Heuristics in Constraint Solving. CP 2020: 496-513

7. Hugues Wattez, Frédéric Koriche, Christophe Lecoutre, Anastasia
Paparrizou, Sébastien Tabary: Learning Variable Ordering Heuristics
with Multi-Armed Bandits and Restarts. ECAI 2020: 371-378

8. Amine Balafrej, Christian Bessiere, Anastasia Paparrizou:
Multi-Armed Bandits for Adaptive Constraint Propagation. IJCAI 2015: 290-296

Mots clés

Intelligence artificielle, programmation par contraintes, heuristiques, apprentissage en ligne