Hybridation de La Programmation Par Contraintes

**Hybridation de la programmation par contraintes avec des techniques d'apprentissage automatique // Using machine learning in constraint programs solving**:

- Réf **ABG-125720**
**ADUM-58905**
- Sujet de Thèse- 09/09/2024- Autre financement public- Université de Montpellier- Lieu de travail- Montpellier cedex 5 - France- Intitulé du sujet- Hybridation de la programmation par contraintes avec des techniques d'apprentissage automatique // Using machine learning in constraint programs solving- Champs scientifiques- Indifférent
- Mots clés- Intelligence artificielle, programmation par contraintes, heuristiques, apprentissage en ligne
AI, Constraint Programming, Heuristics, Online learning**Description du sujet**:

- Résumé: La programmation par contraintes permet de résoudre des problèmes combinatoires tels que l'ordonnancement de tâches, la configuration de produits ou les emplois du temps du personnel. L'utilisateur spécifie les contraintes sur les solutions réalisables pour un ensemble de variables de décision et appelle un solveur pour trouver une solution (c'est à dire une valeur pour chacune de ces variables).

Dans cette thèse, l'objectif est d'hybrider la programmation par contraintes avec des techniques d'apprentissage automatique. Un premier objectif sera de comprendre les propriétés des différentes stratégies de résolution existantes (ordonnancement des variables, quantité de propagation) et l'impact des caractéristiques du problème sur leur efficacité. Nous essayerons aussi de comprendre les effets que peuvent avoir ces stratégies les unes sur les autres pendant la résolution. L'objectif final est de proposer un cadre d'apprentissage qui sélectionne des ordonnancements de variables et des niveaux de propagation robustes aux différents types de problèmes.

La validation des résultats se fera dans le cadre des réseaux de contraintes qualitatives, qui sont généralement utilisés pour représenter et raisonner sur des informations spatiales et temporelles d'une manière intuitive et semblable à celle d'un humain. Toutefois nos résultats devront s'appliquer aussi aux contraintes classiques car nous souhaitons obtenir un cadre totalement générique.

It is well known from the SAT/CP community that different strategies for selecting variables during search (i.e., the order in which the variables are assigned) exhibit different performance depending on the class or instance of problem they solve. Numerous such strategies exist in the literature, including static, dynamic and adaptive
ones. Choosing the right strategy depends on problem features, such as the density of the constraint network, the size of the domains of variables, but also from other criteria not easy to
characterize. Choosing the best strategy requires domain expertise, which deprives many users of the best choice for their problem.
In this doctoral project, we aim at investigating the properties of
the existing strategies to understand their effectiveness on given problem features. We aim at understanding the impact of random perturbations on the performance of these strategies. We are also interested in examining their relationship and interaction with other important parameters for CSP solving such as constraint propagation and no-good recording. The ultimate goal is to propose a learning framework that can guide search by efficiently combining branching strategy and propagation. In several of the above steps, an experimental evaluation is required as well as a comparison with the state of the art.

Début de la thèse : 01/10/2025**Nature du financement**:

- Autre financement public**Précisions sur le financement**:

- ANR Financement d'Agences de financement de la recherche**Présentation établissement et labo d'accueil**:

- Université de Montpellier**Etablissement délivrant le doctorat**:

- Université de Montpellier**Ecole doctorale**:

- 166 I2S - Information, Structures, Systèmes- Bonnes compétences en programmation Python ou JAVA - Une expérience en CP et ML sera très appréciée.
- Good programming skills on Python or JAVA - Background on CP and ML is highly appreciated.-
- 20/09/2024