Ce projet a pour but de vous permettre d'appliquer concrètement les méthodes et outils vus en cours sur les problématiques de recherche (Search), de programmation par contraintes (CSP), et de raisonnement logique avancé (SAT/SMT). Vous serez amenés à résoudre des problèmes réels ou réalistes à l'aide de ces techniques en développant un projet complet, depuis la modélisation jusqu'à la solution opérationnelle.
Chaque groupe devra forker ce dépôt Git et déposer son travail dans un répertoire dédié du dépôt. Ce répertoire contiendra :
- Le code source complet, opérationnel, documenté et maintenable (en Python, C#, C++, ou autre).
- Le matériel complémentaire utilisé pour le projet (datasets, scripts auxiliaires, etc.).
- Les slides utilisés lors de la présentation finale.
- Un notebook explicatif détaillant les étapes du projet, les choix de modélisation, les expérimentations et les résultats obtenus.
Les livraisons se feront via des pull requests, qui devront être régulièrement mises à jour durant toute la durée du projet de sorte que l'enseignant puisse suivre l'avancement et éventuellement apporter des retours et de sorte que tous les élèves aient pu prendre connaissance des travaux des autres groupes avant la soutenance avec évaluation collégiale.
- Présentation orale finale avec support visuel (slides).
- Démonstration de la solution opérationnelle devant la classe.
- Évaluation collégiale : chaque élève évaluera les autres groupes en complément de l’évaluation réalisée par l’enseignant.
- Critères : clarté, originalité, robustesse de la solution, qualité du code, pertinence des choix méthodologiques et organisation.
Pour faciliter la réalisation du projet, vous aurez accès à plusieurs ressources avancées :
- Plateforme Open-WebUI : intégrant des modèles d'intelligence artificielle d'OpenAI et locaux très performants, ainsi que des plugins spécifiques et une base de connaissances complète alimentée par la bibliographie du cours (indexée via ChromaDB, taper # en conversation pour invoquer les KB).
- Clés d'API OpenAI et locales : mise à votre disposition pour exploiter pleinement les capacités des modèles GPT dans vos développements.
- Notebook Agentique : un notebook interactif permettant d'automatiser la création ou la finalisation de vos propres notebooks, facilitant ainsi la structuration et l'amélioration de vos solutions.
Vous avez également la possibilité d'intégrer les Large Language Models (LLMs) directement dans votre projet CSP afin d'en étendre significativement les capacités, via :
- Une utilisation directe des LLM pour assister la conception ou la résolution de CSP complexes.
- Le recours au "function calling" : fournir à un LLM un accès direct à votre CSP, permettant ainsi au modèle de piloter la résolution du problème de manière plus flexible et intuitive. Le notebook agentique fourni constitue un exemple pratique et efficace de cette méthodologie légère mais puissante. La normalisation en cours des MCPs constitue également un excellent exemple d'application de cette approche (vous développez un MCP utilisant la PrCon dans le cadre de votre projet).
Ces exemples couvrent des problématiques variées et réelles, illustrant la diversité des domaines applicatifs potentiels (planification de ressources, optimisation logistique, jeux de logique, gestion des plannings, etc.) en lien direct avec les compétences acquises dans ce cours. Vous pouvez choisir l'un de ces sujets ou proposer le vôtre en prenant soin de le faire valider au préalable.
Ce sujet consiste à résoudre le problème classique de planification du personnel soignant. L’objectif est d’affecter de manière optimale les infirmier·ère·s aux différents shifts (matin, après-midi, nuit) sur une période (hebdomadaire ou mensuelle), tout en respectant un ensemble de contraintes strictes et des préférences :
- Contraintes légales et organisationnelles : Respect des durées maximales de travail, nombre maximal de jours consécutifs, jours de repos obligatoires, etc.
- Contraintes opérationnelles : Chaque poste doit être pourvu à chaque créneau, avec une couverture adéquate en fonction des besoins du service.
- Contraintes de préférences et d’équité : Prise en compte des souhaits individuels et équilibre dans la répartition des shifts.
Ce problème est reconnu comme NP-difficile, ce qui rend l’approche par programmation par contraintes (CSP) particulièrement adaptée pour modéliser et résoudre efficacement l’ensemble des exigences (contraintes dures et souples).
- Modélisation : Définir des variables représentant les infirmier·ère·s, les shifts et les jours, avec des domaines correspondant aux affectations possibles.
- Contraintes : Imposer les règles de couverture (chaque créneau doit être attribué), les règles de repos et les règles spécifiques (par exemple, interdiction de travailler plus de X jours consécutifs) ainsi que les préférences individuelles (souhaits, équité).
- Méthodologie : Utiliser un solveur CSP (ex. OR-Tools CP-SAT, IBM CP Optimizer) ou une approche hybride (CSP + MILP) pour explorer l’espace des solutions.
- Livrables : Code opérationnel, dépôt Git avec des commits réguliers, et un notebook explicatif détaillant la modélisation, les choix méthodologiques et l’analyse des résultats.
- Présentation : Une présentation orale avec support visuel illustrera la modélisation, l’implémentation et l’évaluation de la solution.
- Burke et al., The state of the art of nurse rostering (2004) – Revue de littérature sur les méthodes d’optimisation des plannings infirmiers.
- P. Laborie et al., IBM CP Optimizer for staffing problems (IBM, 2018) – Approche et cas d’utilisation de la programmation par contraintes pour le staffing.
- Solver Max - Nurse rostering in OR-tools CP-SAT solver – Exemple de modèle CSP pour générer un tableau de service satisfaisant.
- Solving the Nurse Rostering Problem using Google OR-Tools – Article détaillé sur la modélisation et la résolution du problème par OR-Tools.
- Constraint programming for nurse scheduling - IEEE Xplore – Étude comparative démontrant l’efficacité de CP pour la planification infirmière.
Appariement optimal de donneurs et receveurs d’organes incompatibles, modélisé comme un graphe orienté où chaque cycle représente un échange de greffes (Optimal kidney exchange - Wikipedia). L’objectif est de maximiser le nombre de transplantations effectuées, sous la contrainte qu’aucun couple ne donne sans recevoir (stabilité individuelle) (Optimal kidney exchange - Wikipedia). Ce problème d’optimisation combinatoire admet de multiples variantes et est NP-difficile dès que les cycles d’échange autorisés dépassent la longueur 2 ou 3 (Optimal kidney exchange - Wikipedia). Des modèles en programmation linéaire en nombres entiers et par contraintes ont été proposés pour le résoudre efficacement (e.g. formulations en graphe de cycles) (GitHub - jamestrimble/kidney_solver: Solve kidney-exchange instances using Python and Gurobi).
Références : Roth et al., Efficient Kidney Exchange (AER 2007) (GitHub - jamestrimble/kidney_solver: Solve kidney-exchange instances using Python and Gurobi); Abraham et al., Clearing Algorithms for Barter Exchange (EC 2007) (GitHub - jamestrimble/kidney_solver: Solve kidney-exchange instances using Python and Gurobi); Wikipedia – Optimal kidney exchange (définitions et contraintes) (Optimal kidney exchange - Wikipedia) (Optimal kidney exchange - Wikipedia).
Ce sujet porte sur le problème classique du Job-Shop Scheduling. Il s'agit de planifier l'exécution d'un ensemble de tâches (jobs) devant être traitées sur plusieurs machines, chacune ayant une capacité limitée (une tâche par machine à la fois). L’objectif principal est de :
- Minimiser le makespan : Réduire la durée totale de production.
- Optimiser l'utilisation des ressources : Assurer que chaque machine travaille de manière efficiente sans chevauchement d'opérations.
Des contraintes supplémentaires peuvent être intégrées, telles que la maintenance programmée des machines, des contraintes de ressources cumulatives (par exemple, consommation énergétique ou disponibilité d'opérateurs) ou encore des objectifs multi-critères (réduction des retards, équilibre de charge).
- Modélisation : Utiliser des variables d'intervalle pour chaque opération, représentant le début et la durée fixe des tâches.
- Contraintes :
- Non-chevauchement : Chaque machine ne peut traiter qu’une seule tâche simultanément.
- Ordonnancement : Respecter l’ordre prédéfini des opérations pour chaque job.
- Méthodologie : Implémenter le modèle en utilisant un langage de programmation adapté et exploiter un solveur CSP (comme IBM CP Optimizer, OR-Tools ou MiniZinc) pour obtenir la solution optimale ou quasi-optimale.
- Livrables : Code source commenté, dépôt Git, notebook explicatif détaillant la modélisation, le processus de résolution et une analyse comparative (si possible, avec différentes instances de test).
- Extensions possibles : Ajouter des contraintes pratiques (maintenance, ressources cumulatives) et explorer des stratégies d’optimisation hybride (CP combiné avec heuristiques).
- Job Shop Scheduling Problem | sysid blog – Introduction et formulation générale du problème.
- Constraint program solvers - IBM CPLEX – Présentation des solveurs CP utilisés pour le job-shop.
- J. Carlier (1982), Proc. of the first job-shop scheduling constraint solver – Référence historique et méthodologique sur la résolution par contraintes du problème.
- Autres études de cas et travaux académiques sur le Job-Shop Scheduling permettant de comprendre l’impact de la propagation des contraintes sur l’optimisation de la production.
Répartition des tâches d’assemblage sur une séquence de postes de travail de manière à minimiser le nombre de postes (ou à respecter un temps de cycle donné) (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly). Chaque tâche a une durée et des précédences, et la somme des durées affectées à un poste ne doit pas dépasser le temps de cycle. Ce problème d’équilibrage est NP-difficile et présente de nombreuses variantes industrielles. Une modélisation classique utilise la programmation par contraintes ou en nombres entiers pour attribuer les tâches à des postes tout en respectant les contraintes d’ordre et de temps (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly). Des études montrent que même des solveurs génériques (CP Optimizer, Gurobi) peuvent traiter efficacement des cas de grande taille, bien qu’il existe aussi des algorithmes spécialisés (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly) (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly).
Références : Hexaly (2024) – Simple Assembly Line Balancing Problem, définition et difficultés (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly); Hexaly – comparatif de solveurs MILP vs CP sur SALBP (instances jusqu’à 1000 tâches) (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly) (Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP) - Hexaly); Scholl & Becker (2006), State-of-the-art in assembly line balancing.
Ce sujet porte sur la planification optimale des tournées d'une flotte de véhicules chargés de livrer des colis ou des marchandises. L’objectif principal est de minimiser la distance parcourue ou le coût total, tout en respectant un ensemble de contraintes telles que :
- Capacités et fenêtres temporelles : Chaque véhicule dispose d’une capacité limitée et les livraisons doivent respecter des horaires imposés par les clients.
- Contraintes de routage classiques : Chaque tournée doit former un circuit fermé, en respectant l’ordre des visites.
- Contraintes environnementales (version « vertes ») : Pour des flottes de véhicules électriques, intégrer les contraintes liées à l’autonomie, la nécessité de passages par des stations de recharge, et la minimisation de l’empreinte carbone.
Ces problématiques, qui se déclinent dans une version classique (VRP) et une version étendue intégrant des contraintes environnementales, présentent une complexité NP-difficile. La programmation par contraintes (CSP) permet de modéliser de façon déclarative l’ensemble de ces contraintes et d’explorer efficacement l’espace des solutions possibles.
- Modélisation :
- Définir des variables pour représenter l’ordre de passage des clients sur chaque tournée.
- Associer des variables pour la charge et la consommation d’énergie (le cas échéant) sur chaque véhicule.
- Contraintes :
- Routing et capacité : Chaque véhicule ne doit pas dépasser sa capacité, et tous les clients doivent être desservis.
- Fenêtres temporelles : Les livraisons doivent être effectuées dans les intervalles horaires définis.
- Contraintes environnementales : Pour les véhicules électriques, intégrer la contrainte d’autonomie et prévoir des passages obligatoires par des stations de recharge si nécessaire.
- Méthodologie : Utiliser un solveur CSP (ex. OR-Tools CP-SAT, MiniZinc) éventuellement combiné avec des heuristiques de recherche locale (comme le Large Neighborhood Search) pour améliorer la qualité des solutions.
- Livrables : Code opérationnel, dépôt Git structuré, notebook explicatif détaillant la modélisation, la stratégie de résolution et une analyse comparative sur des instances de test.
- A brief introduction to VRP - PyVRP documentation
- Solving the Vehicle Routing Problem (Routific, 2024)
- Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM Monographs on Discrete Mathematics and Applications.
- A Constraint Programming Approach to Electric Vehicle Routing with Time Windows (Haddadene et al., 2016)
Décisions stratégiques d’implantation de centres (usines, dépôts) et d’allocations de flux pour satisfaire la demande au moindre coût ((PDF) Supply Chain Network Design Using Constraint Programming). Par exemple, choisir quels entrepôts ouvrir et quels clients y assigner, tout en respectant les capacités et coûts de transport. Traditionnellement modélisé en PLNE, ce problème peut aussi se formuler en CSP : on définit des variables pour les affectations et on impose des contraintes de capacité, de couverture, etc. ((PDF) Supply Chain Network Design Using Constraint Programming). La programmation par contraintes offre une alternative flexible pour intégrer des variantes (contrainte de robustesse, critères multiples) ((PDF) Supply Chain Network Design Using Constraint Programming). Des études ont montré que l’approche CP peut donner de bons résultats, comparables aux modèles entiers, pour concevoir des réseaux optimisés satisfaisant l’ensemble des contraintes de la chaîne logistique ((PDF) Supply Chain Network Design Using Constraint Programming).
Références : Özgür-Polat et al. (2016), Supply Chain Network Design Using CP – modélisation CP vs IP du problème ((PDF) Supply Chain Network Design Using Constraint Programming); Sabharwal (2023), chap.6 Constraint Programming in Optimization Modeling for Supply Chain; C. Dotoli et al. (2005), Logistics Network Design by CP.
Ce sujet consiste à concevoir et résoudre le problème de la planification des emplois du temps dans un établissement universitaire (cours ou examens). L'objectif est d'assigner des cours ou examens à des créneaux horaires et des salles en tenant compte de multiples contraintes :
- Contraintes de ressources : Disponibilité des enseignants, capacité et disponibilité des salles, et répartition équilibrée des cours.
- Contraintes temporelles : Éviter tout conflit horaire pour un même enseignant ou une même salle.
- Contraintes supplémentaires : Intégrer des préférences (éviter les cours en fin de journée, par exemple), des contraintes sur la répartition géographique ou des contraintes liées aux groupes d’étudiants.
Ce problème, souvent NP-combinatoire, bénéficie grandement de l'approche CSP qui permet de modéliser de façon déclarative les contraintes et de bénéficier de techniques de propagation pour éliminer rapidement les affectations impossibles.
- Modélisation : Définir des variables pour représenter les créneaux horaires et les salles affectées à chaque cours ou examen.
- Contraintes :
- Exclusion mutuelle : Aucun enseignant ou salle ne peut être attribué(e) à deux activités simultanément.
- Alignement des ressources : Respecter les capacités des salles et les disponibilités des enseignants.
- Contraintes supplémentaires : Optimiser la répartition pour réduire les conflits et satisfaire au maximum les préférences.
- Méthodologie : Utiliser un solveur CSP (par exemple MiniZinc ou OR-Tools) pour générer automatiquement des emplois du temps valides et, le cas échéant, optimiser un critère (minimiser les conflits ou maximiser la satisfaction des préférences).
- Livrables : Code opérationnel, dépôt Git, notebook explicatif détaillant la modélisation, la gestion des contraintes et l’analyse des solutions générées.
- Extensions possibles : Intégrer des contraintes issues de travaux antérieurs sur la timetabling (ex. règles de répartition géographique, préférences spécifiques des départements) et utiliser des données réelles pour tester la robustesse du modèle.
- Constraint Logic Programming over finite domains for timetabling (Citeseerx) – Document décrivant l'application du CLP aux emplois du temps.
- Constraint-based Timetabling – Thèse ou rapport de recherche détaillant les méthodes CP appliquées à la timetabling.
- Goltz & Matzke (1999), University Timetabling using Constraint Logic Programming – Exemple d’encodage du problème en CLP et analyse des performances.
- Schaus et al. (2014), CBLS for Course Timetabling – Approche basée sur la recherche locale combinée aux contraintes pour l’optimisation des emplois du temps.
- Archives de l’International Timetabling Competition – Ressources et données sur des cas réels de planification universitaire.
Élaboration du calendrier de rencontres d’un championnat (par ex. tournoi toutes rondes en football), en respectant de multiples contraintes: alternance domicile/extérieur, disponibilités de stades, équité entre équipes (pas plus de X déplacements consécutifs, etc.). Ces problèmes, très complexes, ont motivé de nombreux travaux en CP. Par exemple, l’ordonnancement d’un tournoi « round-robin » peut se modéliser par contrainte avec des variables représentant qui rencontre qui à chaque journée, et des global constraints pour éviter les « breaks » (deux matchs Domicile ou Extérieur de suite) (sls.dvi). La CP a permis de prouver des bornes théoriques, comme le nombre minimal de « breaks » (n–2 pour n équipes) en quelques secondes, exploitant la propagation sur des contraintes globales spécifiques (sls.dvi). Plus généralement, la littérature sur le scheduling sportif montre l’intérêt de CP pour gérer les règles complexes imposées par les ligues (sls.dvi).
Références : Régin (CP 2008), Minimizing breaks in sports schedules – modèle CP pour tournoi rondes simples (sls.dvi) (sls.dvi); Schaerf (1999), Sports scheduling – revue d’approches; ITC 2021 Sports Scheduling Track (compétition utilisant CP et métaheuristiques).
Les puzzles Sudoku se prêtent bien à la modélisation CSP : on assigne des chiffres 1–9 à chaque case d’une grille 9×9 en imposant la contrainte all-different sur chaque ligne, colonne et sous-grille (C:/sudoku/report/report.dvi). Il s’agit d’un problème NP-complet dont la structure de contraintes est fixée. La propagation de contraintes (arc-consistency, all-different) permet souvent de résoudre des Sudoku sans recherche exhaustive, en réduisant considérablement le domaine des variables (C:/sudoku/report/report.dvi) (C:/sudoku/report/report.dvi). Un modèle CP classique du Sudoku comporte 81 variables (valeurs des cases) et utilise principalement des contraintes d’inégalité sur les unités. De nombreux solveurs l’illustrent comme exemple didactique, et la génération de grilles Sudoku peut aussi se faire via CP en garantissant l’unicité de solution (C:/sudoku/report/report.dvi) (C:/sudoku/report/report.dvi).
Références : Simonis (CP Workshop 2005), Sudoku as a Constraint Problem – modélisation par contraintes (contrainte alldifferent sur lignes/colonnes) (C:/sudoku/report/report.dvi); Norvig (2006), Solving Every Sudoku Puzzle – algorithme de propagation; H. Simonis, blog (2018) – variantes de modélisation Sudoku.
Wordle est un jeu de mots dans lequel à chaque tentative de mot, on obtient des indications de lettres bien placées, mal placées ou absentes. Ces indices se traduisent par des contraintes sur le mot secret : certaines positions doivent contenir certaines lettres, d’autres non, etc. Un programme peut appliquer ces contraintes à un dictionnaire pour filtrer les mots possibles. Par exemple, une approche par contraintes définit des variables pour chaque lettre du mot secret et impose les retours (vert, jaune, gris) comme contraintes logiques sur ces variables (Beating Wordle: Constraint Programming | by Asim - Medium). Des outils de CP (ou de recherche exhaustive optimisée) permettent de réduire l’espace des solutions à chaque coup et ainsi de résoudre le Wordle. Par ailleurs, on peut intégrer un LLM en function-calling pour qu’il exploite un solveur CSP sous-jacent et propose des coups optimisés (le LLM déduisant les contraintes linguistiques, le CSP garantissant le respect strict des contraintes de lettres).
Références : Asim (2022), Beating Wordle: Constraint Programming – utilisation d’un solver de contraintes sur un dataset de mots (Beating Wordle: Constraint Programming | by Asim - Medium); hakank.org – implémentation d’un solveur Wordle en OR-Tools CP-SAT; OpenAI (2023), Function calling documentation – appel de fonctions pour déléguer des tâches (ex. solveur externe) (Function calling - OpenAI API).
Ce sujet consiste à résoudre automatiquement le jeu du Démineur en modélisant le problème sous forme de satisfaction de contraintes (CSP).
- Principe : Chaque case inconnue de la grille est représentée par une variable booléenne indiquant la présence ou non d’une mine.
- Contraintes : Pour chaque case ouverte, le chiffre affiché impose que le nombre de mines présentes dans son voisinage corresponde exactement à cette valeur.
- Objectif : Utiliser la propagation de contraintes pour déduire systématiquement quelles cases sont sûres et lesquelles contiennent une mine, imitant ainsi le raisonnement humain tout en profitant de l’exhaustivité de la recherche par contraintes.
Ce problème, bien que généralement résolvable par propagation, devient NP-complet dans sa version générale et peut nécessiter une recherche complémentaire (backtracking ou approches probabilistes) pour certaines configurations.
- Modélisation :
- Définir une variable booléenne par case inconnue.
- Pour chaque case ouverte, ajouter une contrainte d’égalité sur la somme des variables de son voisinage.
- Méthodologie : Appliquer un solveur CSP pour explorer l’espace des solutions, en utilisant des techniques de propagation (arc-consistency, all-different pour certains regroupements) et de backtracking intelligent pour les configurations ambiguës.
- Livrables : Code source commenté, dépôt Git, notebook explicatif détaillant la modélisation, la résolution et une évaluation sur différentes grilles (de petite à grande taille).
- A Constraint-Based Approach to Solving Minesweeper (Bayer et Snyder, 2013)
- Minesweeper is NP-complete (Princeton, 2013)
- GitHub - jgesc/Minesweeper_CSP : Solving minesweeper as a Constraint Satisfaction Problem
La génération automatique de grilles de mots-croisés peut se formuler en problème de satisfaction de contraintes. On doit remplir une grille noire/blanche avec des mots qui se croisent de façon cohérente (les lettres qui se croisent doivent être identiques). Une approche consiste à pré-définir la grille (emplacements des cases noires) puis à affecter un mot de dictionnaire à chaque « slot » horizontal ou vertical. Les contraintes lient les slots entre eux via les lettres communes. La programmation par contraintes permet de modéliser cela naturellement et de rechercher une solution où tous les slots sont remplis de mots existants (Generating Crossword Grids Using Constraint Programming). On peut également ajouter des contraintes de thématique, ou maximiser un score. Des modèles CSP ou MILP ont ainsi été utilisés pour compiler automatiquement des grilles de mots-croisés cohérentes (Solver Max - Nurse rostering in OR-tools CP-SAT solver).
Références : Solver Max – exemple de formulation MILP pour composer une grille de mots-croisés (Solver Max - Nurse rostering in OR-tools CP-SAT solver); Philippe O. (2023), Generating Crossword Grids Using CP – modélisation pas à pas d’une grille avec OR-Tools CP-SAT (Generating Crossword Grids Using Constraint Programming); G. Gervet (1995), Crossword puzzle solving via constraint logic programming.
Appariement bipartite entre deux ensembles (par ex. étudiants et postes, ou hommes et femmes dans le problème classique) sur la base de préférences de classement mutuelles. Un « matching » est stable s’il n’existe pas deux agents qui se préfèreraient mutuellement à leurs attributions actuelles (). Gale & Shapley (1962) ont proposé l’algorithme glouton des propositions différées garantissant une solution stable en temps polynomial (). On peut aussi formuler le problème en CSP : rechercher une affectation (bijection) sans paire bloquante. Des modèles par contraintes ont été développés, montrant par exemple que faire l’arc-consistance sur ces CSP équivaut à exécuter l’algorithme de Gale-Shapley (élimination des paires incompatibles) () (). Des variantes incluent les mariages stables hospital–résidents (capacités multiples) utilisées chaque année pour le Matching des internes en médecine ().
Références : Manlove & O’Malley (CP 2008), Modelling Stable Marriage with CP – deux encodages CSP et lien avec Gale-Shapley () (); Gale & Shapley (1962), College Admissions and Stability; Gusfield & Irving (1989), The Stable Marriage Problem: Structure and Algorithms.
Variante du mariage stable où les « femmes » sont des écoles avec des capacités d’accueil et un ordre de priorité (par exemple, points de secteur, fratrie). L’algorithme d’appariement utilisé dans des villes comme New York ou Boston s’appuie sur une adaptation de Gale-Shapley, assurant qu’aucun élève ne reste mécontent si une école qu’il préfère a de la place pour lui en évitant d’évincer un autre élève plus prioritaire (Microsoft PowerPoint - School Matching Systems.ppt). Autrement dit, à l’issue de l’affectation, si un élève n’a pas eu son vœu plus favorable, c’est que toutes les places y sont prises par des élèves ayant priorité sur lui (Microsoft PowerPoint - School Matching Systems.ppt). Ce mécanisme est stable (et stratégique-proof), et peut se formuler en contraintes en modélisant les choix et priorités comme des contraintes d’optimalité sous réserve de priorité. Des approches en CP ou MILP ont été explorées pour introduire de la flexibilité (par ex. pour améliorer l’efficacité en cas d’égalités de priorités (Microsoft PowerPoint - School Matching Systems.ppt)).
Références : Abdulkadiroğlu & Sönmez (2003), School Choice – A Mechanism Design Approach; Roth (2008), Deferred Acceptance in School Choice; Rapport Boston School Committee (2005) – propriété de stabilité/priorité de l’affectation finale (Microsoft PowerPoint - School Matching Systems.ppt).
Attribuer des couleurs à chaque nœud d’un graphe (p. ex. régions d’une carte) de sorte que deux nœuds adjacents n’aient pas la même couleur. On cherche à minimiser le nombre de couleurs utilisées ou à respecter un nombre fixé de couleurs. C’est un problème NP-difficile très connu, utilisé comme exemple classique en CSP. En CP, on crée une variable « couleur » pour chaque nœud avec un domaine de couleurs autorisées, puis on impose pour chaque arête que les deux extrémités aient des valeurs différentes (contrainte binaire) (Color a Map with Constraint Programming — AIMMS How-To). La propagation de ces contraintes (node consistency, arc consistency) facilite grandement la recherche d’une coloration valide. Un cas particulier célèbre est la coloration de carte : on sait que 4 couleurs suffisent pour n’importe quelle carte planaire (Color a Map with Constraint Programming — AIMMS How-To). Les solveurs CP peuvent retrouver une coloration valide d’une carte (France, USA, etc.) facilement et sont un bon outil pédagogique pour ce problème (Color a Map with Constraint Programming — AIMMS How-To).
Références : AIMMS – Color a Map with CP (tutoriel) (Color a Map with Constraint Programming — AIMMS How-To) (Color a Map with Constraint Programming — AIMMS How-To); Map coloring problem in MiniZinc (blog phabe.ch 2019); Applegate & Cook (1989), A Computational Study of Graph Coloring.
Ce sujet porte sur l’utilisation de la programmation par contraintes pour assister la composition musicale. L’idée est de générer ou de compléter automatiquement une pièce musicale en respectant un ensemble de règles harmoniques et de contrepoint, typiques de la musique tonale occidentale (par exemple, en style baroque).
- Principe : Chaque note de chaque voix (soprano, alto, ténor, basse) sur chaque temps est modélisée par une variable dont le domaine est l’ensemble des notes possibles dans la gamme.
- Contraintes musicales :
- Respecter les règles d’harmonie (accords conformes à la tonalité, progression harmonique logique).
- Éviter les erreurs classiques telles que les octaves ou quintes parallèles.
- Intégrer des contraintes de contrepoint (mouvement indépendant des voix, intervalles acceptables).
- Objectif : Offrir un outil interactif qui, tout en laissant une marge de créativité au compositeur, garantit que les règles musicales imposées ne sont jamais violées.
- Modélisation :
- Définir des variables représentant les notes pour chaque voix et chaque temps.
- Spécifier les contraintes correspondant aux règles musicales (règles de voix, interdiction des parallèles, etc.).
- Méthodologie : Utiliser un solveur CSP pour explorer les différentes combinaisons possibles et proposer des solutions compatibles avec l’ensemble des contraintes, éventuellement en mode interactif pour permettre au compositeur de fixer certaines notes.
- Livrables : Code opérationnel (avec une interface possible pour une utilisation interactive), dépôt Git, notebook explicatif détaillant la modélisation, la validation des contraintes musicales et des exemples d’utilisation (harmonisation de chorals par exemple).
- Extensions possibles : Intégrer des contraintes de style ou des préférences de l’utilisateur, explorer différentes modélisations (par exemple, séparer la structure globale de l’harmonisation locale).
- Constraint Programming in Music (Anders Torsten, Wiley, 2012)
- Expressing Musical Ideas with Constraint Programming Using a Model of Tonal Harmony (IJCAI, 2024)
- Pachet, F., & Roy, P. (2014). "Non-Conformant Harmonization: the Real Book in the Style of Take 6." Proceedings of the International Conference on Computational Creativity.
- Constraint Programming in Musical Composition (Truchet, OpenMusic Tutorial, 2016)
Sujet émergent alliant IA de langage (LLM) et solveur de contraintes pour assister un utilisateur dans des tâches comme la planification d’horaires. L’LLM (ex. ChatGPT) comprend les demandes en langage naturel et peut déduire les contraintes implicites, puis appelle une fonction externe (solveur CSP) pour calculer un horaire qui satisfait strictement ces contraintes. La technique du function calling permet ainsi au modèle de déléguer la partie recherche exhaustive au solveur (Function calling - OpenAI API). Par exemple, pour un problème d’emplois du temps de réunions avec disponibilités, le LLM peut convertir les préférences en contraintes formelles et invoquer un CP solveur (via son API) qui renvoie un planning satisfaisant. Cette approche combine la flexibilité du langage naturel et la rigueur de la résolution par contraintes. Elle est prometteuse car les LLM seuls ne sont pas fiables pour respecter des contraintes combinatoires strictes (Why ChatGPT and LLMs Aren't Ideal for Automatically Generating Shift Schedules | Blogs | Soon), alors qu’un CSP garantira la validité de la solution finale.
Références : Soon.works (2023) – Why ChatGPT isn’t ideal for shift scheduling (LLM ≠ OR, besoin de CP pour contraintes rigides) (Why ChatGPT and LLMs Aren't Ideal for Automatically Generating Shift Schedules | Blogs | Soon); OpenAI (2023) – Documentation Function Calling (connecter un LLM à un outil externe) (Function calling - OpenAI API); Xu et al. (2023), Augmenting LLMs with Symbolic Solvers for Planning.
Ce sujet traite de la problématique de la configuration de produits ou de systèmes complexes (ordinateurs, automobiles, etc.) où le client peut personnaliser son produit en choisissant parmi un ensemble d’options. L’objectif est de garantir que les choix effectués sont compatibles entre eux grâce à l’application d’un grand nombre de règles de compatibilité et d’exclusion :
- Exemple concret : Dans la configuration d’un véhicule, le choix d’un moteur électrique peut imposer une compatibilité avec un type spécifique de batterie et de boîte de vitesses.
- Approche par contraintes : Chaque option est représentée par une variable et les interdépendances (ex. « si option A alors option B obligatoire ») sont modélisées par des contraintes logiques.
- Objectif : Fournir un configurateur interactif qui, en temps réel, élimine les options incompatibles à mesure que l’utilisateur fait ses choix, assurant ainsi une configuration finale cohérente et réalisable.
- Modélisation :
- Définir des variables représentant les composants ou options (par exemple, CPU, carte-mère, motorisation, etc.) avec leurs domaines possibles.
- Imposer des contraintes d’exclusion ou d’implication entre les options (ex. contraintes de compatibilité technique ou commerciale).
- Méthodologie : Utiliser un solveur CSP pour propager les contraintes en temps réel et guider l’utilisateur vers des configurations valides.
- Livrables : Code source (avec une interface utilisateur si possible), dépôt Git, et un notebook explicatif détaillant la modélisation, le processus de propagation des contraintes et des cas d’utilisation concrets.
- Extensions possibles : Intégrer des critères d’optimisation (par exemple, minimiser le coût ou maximiser la performance) et des contraintes dynamiques (mise à jour des règles en fonction de l’inventaire).
- GitHub - foohardt/or-tools-product-configurator: Product configuration using Google OR-Tools
- Mittal, S., & Frayman, F. (1989). "Towards a Generic Model of Configuration Tasks." Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI).
- Hotz, L., Felfernig, A., & Stumptner, M. (2014). "Configuration Knowledge Representation and Reasoning." In: Knowledge-Based Configuration, Morgan Kaufmann, Elsevier, pp. 41-72.
- Constraints in product configuration models - Microsoft Dynamics 365 Product Documentation
Sélection d’un ensemble d’investissements (actions, actifs) maximisant le rendement attendu pour un niveau de risque donné, en respectant diverses contraintes (budget maximum, limites par secteur, etc.). Le problème se ramène souvent à une optimisation combinatoire (et continue) où l’on décide quelles fractions du capital allouer à chaque actif. On peut modéliser cela en CP/MILP en introduisant des variables entières (nombre d’unités de chaque actif) ou booléennes (actif sélectionné ou non) avec des contraintes de budget et de diversification, et en maximisant une fonction d’utilité (rendement moins pénalité de risque). Par exemple, un modèle CP-SAT peut utiliser des variables entières pour chaque produit financier (avec bornes min/max d’investissement) et ajouter des contraintes de type knapsack et d’allocation (algorithm - Portfolio optimization problem: improving the O(n!) solution - Stack Overflow), l’objectif étant de maximiser le profit total (algorithm - Portfolio optimization problem: improving the O(n!) solution - Stack Overflow). Grâce aux solveurs modernes, ce type de problème (combinatoire non linéaire approché linéairement) peut être résolu sur des portefeuilles de taille raisonnable, offrant une solution optimale respectant strictement les contraintes de gestion du risque.
Références : Markowitz (1952), Portfolio Selection – modèle moyenne/variance; StackOverflow (2022) – formulation d’un portefeuille en CP-SAT (OR-Tools) (algorithm - Portfolio optimization problem: improving the O(n!) solution - Stack Overflow) (algorithm - Portfolio optimization problem: improving the O(n!) solution - Stack Overflow); Michalewicz & Fogel (2000), How to Solve It: Modern Heuristics – chapitre sur optimisation financière.
Les publications suivantes constituent un ensemble de ressources variées introduisant le problème d'optimisation de portefeuille financier sous contrainte et différentes techniques autour de la programmation par contrainte.
Domaine d’application varié des CSP pour la ville intelligente : par exemple, le placement optimal de centres (écoles, hôpitaux, bornes de recharge) de façon à couvrir la population avec un minimum de sites (problèmes de localisation), ou l’optimisation des temps de feux tricolores pour fluidifier le trafic. Un cas typique est le problème de localisation d’installations : on dispose de candidats et on veut en sélectionner un sous-ensemble tel que chaque zone de demande ait une installation à distance raisonnable. Ce problème NP-dur (proche du set covering / p-médiane) peut se résoudre en CP en posant des variables booléennes par candidat (ouvert/fermé) et en imposant que chaque zone soit couverte par au moins une installation ouverte. Les solveurs CP/CO peuvent traiter ce problème, ou on peut le transformer en contraintes globales de type pack ou cover. D’ailleurs, les bibliothèques de CP fournissent souvent des contraintes spécialisées pour ce type de problèmes combinatoires (p.ex. pack, distribute) utilisées dans les modèles de localisation et de configuration (Constraint program solvers - IBM CPLEX). La planification urbaine intègre aussi des objectifs multiples (coût, équité, temps de trajet) qu’un modèle par contraintes peut équilibrer via l’optimisation multi-critères.
Références : IBM CP Optimizer – exemples d’utilisation de contraintes pack, count pour des problèmes de localisation ou de routage (Constraint program solvers - IBM CPLEX); Chabrier (2006), Vehicule Routing in urban logistics – contraintes de temps/ville; Urban Planning and CP (CACIC 2017) – modèle CSP pour l’aménagement du territoire.
Description : Il s’agit de planifier la tournée d’une flotte de véhicules (par exemple pour livrer des colis) de façon optimale, en prenant en compte des contraintes comme les capacités des véhicules, les fenêtres de temps de livraison chez les clients, et dans un contexte « vert » la consommation ou l’autonomie en énergie. Un cas typique est le Vehicle Routing Problem (VRP) avec véhicules électriques : chaque véhicule a une batterie de capacité limitée, doit éventuellement passer par des stations de recharge, et on cherche à maximiser le nombre de livraisons ou minimiser la distance totale parcourue ((PDF) A Constraint Programming Approach to Electric Vehicle Routing with Time Windows). Ce problème étend le VRP classique en ajoutant des contraintes d’énergie (autonomie, stations de charge) et éventuellement de réduction d’émissions polluantes, ce qui le rend très complexe (NP-difficile).
Intérêt de l’approche CSP : La programmation par contraintes permet de modéliser finement les contraintes multiples de tournées (capacités, horaires, autonomie) dans un cadre unifié. Elle s’adapte bien au VRP car ces problèmes comportent de nombreuses contraintes spécifiques en conditions réelles (). Des travaux récents montrent l’efficacité de modèles CSP pour le VRP avec véhicules électriques (EVRPTW), permettant d’intégrer directement les contraintes de batteries et de stations de charge ((PDF) A Constraint Programming Approach to Electric Vehicle Routing with Time Windows). Les solveurs CSP/CP hybride peuvent trouver des solutions optimales ou quasi-optimales en raisonnant globalement sur les contraintes, là où des approches purement heuristiques doivent ajuster manuellement chaque nouveau type de contrainte. Cela fait de l’approche CSP un choix pertinent pour optimiser des tournées de livraison en intégrant des objectifs environnementaux (minimisation de l’énergie consommée, etc.).
Références : Booth & Beck, CP for Electric VRP with Time Windows ((PDF) A Constraint Programming Approach to Electric Vehicle Routing with Time Windows) – introduit les premières modélisations CP du VRP électrique avec fenêtres temporelles, intégrant autonomie et recharge. Shaw, Using Constraint Programming and LNS for VRP () – explique pourquoi la programmation par contraintes convient au VRP en raison de la multitude de contraintes pratiques (l’étude y démontre l’efficacité d’une approche CP/LNS sur des instances de VRP). Liste d’applications d’OR-Tools – mentionne la routing comme un domaine de succès de CP (1.3. Real examples — or-tools User's Manual).
Description : Ce sujet vise à générer automatiquement des niveaux ou des cartes de jeu vidéo en respectant des contraintes de jouabilité. Par exemple, on peut vouloir peupler un donjon de monstres, objets et obstacles de sorte que le niveau soit solvable (chemin accessible, clés non bloquées derrière la porte qu’elles ouvrent, équilibre entre ennemis et bonus, etc.). Des travaux montrent qu’on peut utiliser un solveur de contraintes pour peupler un niveau tout en garantissant des propriétés de jouabilité : ainsi, Horswill et Foged imposent des path constraints pour s’assurer qu’un joueur ait toujours une chance raisonnable de survivre (par exemple, les bonus de santé sont placés avant des ennemis puissants, les clés toujours avant la porte correspondante) (Fast Procedural Level Population with Playability Constraints). La génération procédurale sous contraintes permet aussi de fixer des règles de design (taille maximale du niveau, thème imposé, etc.) tout en explorant automatiquement de nombreuses configurations possibles.
Intérêt de l’approche CSP : La programmation par contraintes offre une grande expressivité pour encoder les règles de gameplay et les critères de qualité d’un niveau. Il est facile d’ajouter ou modifier une contrainte (ex. « placer au moins 2 monstres et au plus 5 trésors ») et de relancer le solveur pour obtenir un nouveau niveau satisfaisant ces règles. Cette approche garantit que toutes les contraintes ludiques sont strictement respectées, ce qui évite d’obtenir des niveaux injouables (Room Generation using Constraint Satisfaction | pvigier’s blog) (Fast Procedural Level Population with Playability Constraints). De plus, l’approche CSP donne des garanties sur la sortie (par ex. un niveau toujours gagnable), là où des méthodes aléatoires ou apprenantes peuvent échouer sur certains critères. Des systèmes comme Harmony ou Strasheela ont démontré que l’on peut générer des contenus artistiques (musique ou niveaux de jeu) en traduisant les règles de composition en contraintes formelles, avec un contrôle total du concepteur sur le résultat.
Références : Horswill & Foged, Playability Constraints for Level Generation (Fast Procedural Level Population with Playability Constraints) – démontre comment des contraintes (chemins, équilibre ennemis/bonus, clés/portes) assurent qu’un niveau généré est jouable. Vigier, Room Generation using CSP (Room Generation using Constraint Satisfaction | pvigier’s blog) (Room Generation using Constraint Satisfaction | pvigier’s blog) – décrit un générateur de donjons basé sur un CSP (variables = objets à placer, domaines = positions possibles, contraintes = pas de chevauchement, accessibilité, etc.), soulignant la simplicité d’ajouter des règles (« douche près d’un mur », etc.). Smith et al. – travaux sur la génération de puzzles (ex. Sudoku) et de contenus ludiques via des solveurs de contraintes, assurant des propriétés comme l’unicité de solution.
Description : Dans le cloud computing, on reçoit un ensemble de demandes (machines virtuelles à lancer, tâches à exécuter) et on doit les placer sur des serveurs physiques disponibles. Ce problème comporte des contraintes de capacité (chaque serveur a une RAM, CPU limités), de performance (certaines applications nécessitent d’être sur le même rack, ou au contraire réparties), et souvent des objectifs de coût ou d’équilibrage de charge. On peut formuler cela en CSP : variables = instances ou tâches à placer, domaines = choix de serveurs, contraintes = ne pas dépasser les capacités par serveur, respecter les affinités ou anti-affinités, etc. (). Ce problème est complexe car il combine satisfaction de contraintes (trouver un placement valide) et optimisation (minimiser le coût ou l’énergie).
Intérêt de l’approche CSP : La programmation par contraintes offre un cadre souple pour exprimer les diverses politiques d’allocation (contrainte de colocalisation, de redondance, respect des SLA, etc.) et trouver un placement satisfaisant. Des travaux ont montré qu’on peut modéliser l’allocation de machines virtuelles comme un problème de satisfaction de contraintes, puis utiliser un solveur CP pour trouver une solution respectant QoS et coûts () (). L’approche CSP facilite l’ajout de nouvelles contraintes (par exemple, réserver certaines VM sur des serveurs alimentés par énergies renouvelables) sans changer fondamentalement l’algorithme. De plus, grâce aux techniques de filtrage et de propagation, un solveur peut drastiquement réduire l’espace de recherche en éliminant d’office les affectations impossibles (serveur surchargé, combinaison incompatible, etc.). Ceci permet d’aborder des instances plus dynamiques ou complexes que ne pourraient le faire des heuristiques figées, tout en garantissant le respect strict des contraintes critiques (disponibilité, sécurité).
Références : Zhang et al., Virtual Cloud Resource Allocation model (VCRA-CP) () – formalise l’allocation de VMs comme un CSP/optimisation, en montrant son efficacité pour concilier QoS et coûts. Van et al. – travaux cités par Zhang où la sélection de machines virtuelles pour des applications est convertie en problème de satisfaction de contraintes pour obtenir un ordonnancement optimal (). Microsoft Learn – Product configuration constraints – illustre l’utilisation de contraintes (d’expression ou table) pour contrôler les choix de configuration de produits ou ressources dans un configurateur cloud (foohardt/or-tools-product-configurator - GitHub) (analogie avec VM placement).
Description : On considère une flotte de robots mobiles (par ex. des robots de manutention dans un entrepôt) devant accomplir un ensemble de tâches (transporter des objets, préparer des commandes) dans des délais impartis. Le problème consiste à assigner les tâches aux robots et à planifier l’ordonnancement de celles-ci, en gérant les contraintes de disponibilité des robots, d’évitement de collisions (deux robots ne doivent pas se trouver au même endroit en même temps), et d’énergie (retours à la base pour recharger). Ce problème de planification et ordonnancement multi-robots est très complexe, car il combine l’affectation (qui fait quoi) et l’ordonnancement dans le temps, souvent avec des contraintes de chemins. Par exemple, dans un centre de retrait de colis, on doit planifier pour chaque robot une suite d’actions (aller à telle étagère, déposer l’objet à telle station) en s’assurant que les chemins ne se croisent pas dangereusement et que les deadlines sont respectées ((PDF) A Constraint Programming Approach to Multi-Robot Task Allocation and Scheduling in Retirement Homes) ().
Intérêt de l’approche CSP : La programmation par contraintes (souvent couplée à des techniques de planification) a montré de très bons résultats pour ce type de problème, notamment en fournissant des solutions optimisées respectant rigoureusement toutes les contraintes. Par exemple, une approche CP a surpassé les MILP (programmation linéaire) classiques sur un cas de planification de robots d’assistance en maison de retraite, en trouvant des solutions de haute qualité beaucoup plus rapidement (). Un modèle CSP permet d’intégrer naturellement des contraintes temporelles disjointes, des dépendances entre tâches (ne pas commencer la tâche B avant que A soit terminée par un autre robot), et les niveaux de batterie de chaque robot ((PDF) A Constraint Programming Approach to Multi-Robot Task Allocation and Scheduling in Retirement Homes). Grâce à des stratégies de recherche adaptées (ordre de variable, large neighborhood search combiné avec CP…), on peut résoudre des instances réalistes et même obtenir toutes les solutions stables. L’approche CSP apporte également de la flexibilité : si une nouvelle contrainte apparaît (par exemple, un robot ne peut pas aller dans une certaine zone temporairement), on l’ajoute au modèle et le solveur recalculera un planning valide, plutôt que de devoir redévelopper un algorithme dédié.
Références : Booth et al., CP for multi-robot scheduling in retirement homes ((PDF) A Constraint Programming Approach to Multi-Robot Task Allocation and Scheduling in Retirement Homes) () – met en évidence que l’approche CP produit des plannings multi-robots de meilleure qualité et plus rapidement que l’approche MILP, en tenant compte des fenêtres de temps, temps de trajet et énergie des robots. Wang et al., MAPF as CSP (A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results) – adoptent une perspective CSP pour la planification de chemins multi-agents (chaque agent = variable dont le domaine est l’ensemble de ses chemins possibles, contraintes de non-collision), avec à la clé un solveur efficace surpassant plusieurs algorithmes spécialisés. ICAPS’16 DC paper – confirme l’avantage de CP pour intégrer incertitudes réelles et contraintes complexes dans la coordination de flottes de robots.
Description : Ce sujet porte sur la planification de chemin pour un robot (par exemple un bras robotique ou un robot mobile) devant se rendre à un point cible en évitant les obstacles. On peut discrétiser l’espace (par ex. grille pour un mobile ou états angulaires pour un bras) et formuler la recherche de chemin comme un CSP : chaque étape du chemin est une variable, avec des contraintes définissant les mouvements légaux (pas d’obstacle, mouvement contigu, etc.) et éventuellement des contraintes d’optimisation (minimiser la longueur du chemin). Dans le cas multi-robot mentionné plus haut, cela s’étend à la planification de chemins multi-agents (MAPF : Multi-Agent Path Finding) où plusieurs robots doivent se déplacer simultanément sans collision. Par exemple, on peut modéliser un problème MAPF en disant que chaque robot doit avoir un chemin de son départ à son arrivée (variable = chemin du robot, domaine = ensemble des chemins possibles) et ajouter des contraintes inter-robots pour interdire les conflits de position dans le temps (A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results).
Intérêt de l’approche CSP : Utiliser un solveur de contraintes pour la planification de trajectoire offre une approche complète évitant de se restreindre à un algorithme glouton comme A*. Pour un seul robot, on peut intégrer directement des contraintes additionnelles (par ex. « passer par ce point intermédiaire », « éviter telle zone », contraintes d’angle pour un bras robotique) dans le modèle et trouver un chemin satisfaisant tout. Pour plusieurs robots, la modélisation en CSP permet de résoudre le problème globalement en évitant les contentions de ressources (cases du grille, segments de couloir, etc.) plutôt que de planifier séparément puis réparer les collisions. Wang et al. ont ainsi proposé un solveur CSP pour les chemins multi-agents qui égale ou dépasse les performances des meilleurs algorithmes spécialisés, tout en étant plus simple à généraliser (A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results) (A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results). L’approche CSP est surtout utile quand les contraintes de chemin deviennent complexes (temps, synchronisation, carburant, etc.), car on peut les ajouter dans le modèle sans devoir changer l’architecture globale. En somme, traiter la planification de trajectoire comme un CSP permet d’explorer rigoureusement l’espace des chemins possibles et de garantir le respect de toutes les contraintes de mouvement du robot, ce qui est crucial pour la sécurité en robotique.
Références : Wang et al., MAPF as CSP (A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results) (A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results) – formulation d’un problème de chemins multi-robots en CSP, montrant que la résolution par recherche CSP (avec ordre dynamique et redémarrages aléatoires) trouve des solutions optimales et rivalise avec l’état de l’art en planification multi-agents. Lopez & al., Constraint-Based Planning – (ICAPS 2012) discute de l’usage de la planification par contraintes pour des problèmes de cheminement complexes. Équipe MovingAI – exemples de résolution de pathfinding grids via SAT/CP pour obtenir le plus court chemin tout en respectant des contraintes additionnelles (parcours thématiques dans des jeux, etc.).
Description : Les smart contracts (contrats intelligents) sont des programmes s’exécutant sur une blockchain (p. ex. Ethereum), manipulant des fonds selon des règles prédéfinies. Une fois déployés, ils sont immuables, d’où l’importance de vérifier l’absence de bugs critiques (par ex. vulnérabilité de réentrance, dépassement de limites, etc.). Ce sujet consiste à utiliser un solveur de contraintes (souvent un SMT solver tel que Z3) pour analyser toutes les exécutions possibles d’un smart contract à la recherche de violations de propriétés. Par exemple, on peut modéliser les conditions d’exécution d’une fonction de contrat et demander au solveur s’il existe une affectation des entrées (appelant, montant, état global) menant à un état non désiré (vol de fonds, invariant violé). Des outils comme Oyente ou Mythril procèdent ainsi par symbolic execution : ils explorent les chemins du code et accumulent les contraintes booléennes correspondantes, puis utilisent un solveur pour voir si ces contraintes sont satisfaisables (ce qui correspondrait à un scénario d’attaque réel) () (FlawCheck: Detecting Smart Contract Vulnerabilities Based on ...).
Intérêt de l’approche CSP : La vérification formelle par contraintes permet d’explorer automatiquement des scénarios d’exécution extrêmes que les tests manuels pourraient manquer. Un SMT solver peut par exemple trouver la suite d’appels tordue menant à une faille de réentrance, en résolvant les contraintes logiques du code (solvant l’équivalent d’un CSP booléen). L’approche CSP est exhaustive sur l’espace des possibilités, dans les limites de la complexité, et a montré son efficacité : par exemple, le model checker de Solidity convertit les assertions du contrat en contraintes logiques et utilise des solveurs SMT comme Z3 pour prouver que ces assertions sont toujours vraies (ou fournir un contre-exemple d’exécution en cas de bug) (Formally Verifying the World's Most Popular Smart Contract | Zellic). Les avantages sont multiples : on obtient soit une garantie que certaines propriétés de sécurité tiennent, soit un exploit concret (valeurs d’entrées) si elles peuvent être rompues, ce qui est inestimable pour corriger avant déploiement. Cette approche a permis de détecter automatiquement des vulnérabilités majeures (reentrancy de TheDAO, dépassements arithmétiques, etc.) en parcourant systématiquement les chemins d’exécution symboliques des contrats ().
Références : Luu et al., Making Smart Contracts Smarter (Oyente) () – décrit l’outil Oyente qui, via exécution symbolique et résolveur de contraintes, détecte des failles dans les contrats Ethereum (par ex. TheDAO). Solidity SMTChecker – documentation officielle (Formally Verifying the World's Most Popular Smart Contract | Zellic) expliquant que le compilateur Solidity intègre un SMT solver pour prouver les invariants et assertions des contrats. FlawCheck (2020) – utilise aussi la méthode d’Oyente et déclare employer Z3 pour vérifier la satisfaisabilité des chemins suspects dans le contrat (FlawCheck: Detecting Smart Contract Vulnerabilities Based on ...).
Description : Un mineur (ou validateur) de blockchain doit choisir les transactions à inclure dans le prochain bloc, en respectant une contrainte de taille maximale (par exemple 1 Mo pour Bitcoin) ou de gaz maximal (pour Ethereum). Chaque transaction apporte une récompense (frais de transaction) au mineur. Le problème est de sélectionner un sous-ensemble de transactions parmi celles en attente de façon à maximiser la somme des frais, tout en ne dépassant pas la capacité du bloc. C’est en fait exactement le problème du sac à dos (knapsack), où chaque transaction a un poids (sa taille) et une valeur (son fee), et on a une capacité totale fixe (Bitcoin mining is NP-hard - CITP Blog). Le problème est NP-difficile en général (un miner optimal doit résoudre deux NP-difficultés : un knapsack et un problème de conflits éventuels entre transactions (Bitcoin mining is NP-hard - CITP Blog) (Bitcoin mining is NP-hard - CITP Blog)). En pratique, les mineurs utilisent des heuristiques (trier par ratio fee/taille) mais celles-ci ne garantissent pas l’optimalité.
Intérêt de l’approche CSP : Formuler la sélection de transactions comme un CSP/optimisation permet d’utiliser des solveurs pour trouver la combinaison optimale. On peut modéliser chaque transaction par une variable booléenne (incluse ou non), ajouter la contrainte que la somme des tailles des transactions choisies ≤ capacité, et définir comme objectif la maximisation de la somme des frais. Un solveur CP-SAT (comme celui d’OR-Tools) peut résoudre ce type d’instance efficacement pour des blocs de taille modérée, garantissant ainsi au mineur un revenu maximal. De plus, cette approche est extensible : on peut ajouter des contraintes sans effort, par ex. exclure deux transactions conflictuelles (double-dépense) en ajoutant la contrainte « pas les deux à la fois » ou modéliser des préférences de priorité. Des analyses théoriques confirment que l’assemblage optimal d’un bloc est équivalent au problème du sac à dos et donc NP-difficile (Bitcoin mining is NP-hard - CITP Blog), mais un modèle de contraintes peut néanmoins être résolu rapidement sur les cas pratiques grâce aux progrès des SAT/CP solvers. Enfin, cette approche pourrait aider à étudier les cas d’attaque par extraction de valeur maximale (MEV), en intégrant non seulement les frais mais aussi d’autres facteurs (par ex. interdire certaines combinaisons nuisibles) – ce qui devient plus naturel dans un cadre à contraintes qu’avec une heuristique figée.
Références : Bonneau, Bitcoin mining is NP-hard (Bitcoin mining is NP-hard - CITP Blog) (Bitcoin mining is NP-hard - CITP Blog) – explique que le choix des transactions pour maximiser les frais sous contrainte de taille équivaut à un problème de sac à dos, NP-difficile, et discute les deux sous-problèmes (frais vs conflits). Narayanan et al., Bitcoin and Cryptocurrency Technologies – Chapitre sur le minage, mentionnant le tri par fee/byte comme heuristique mais reconnaissant la nature d’optimisation combinatoire du problème. Arxiv 2024 – MEV and Knapsack (Blockchains, MEV and the knapsack problem: a primerThis research is funded by The Ethereum Foundation Academic Grant Program no. FY22-0682. The authors thank Barnabé Monnot for useful discussions and feedback on the content and implementation of this grant project.) – souligne également que la décision du producteur de bloc s’assimile à un problème de sac à dos NP-hard, ce qui ouvre la porte à des approches d’enchères ou de résolution exacte pour améliorer la sélection de transactions.
Description : Les data centers consomment énormément d’énergie ; ce sujet vise à planifier l’exécution des tâches ou la gestion des serveurs pour minimiser la consommation électrique ou l’empreinte carbone, tout en respectant la qualité de service. Par exemple, on peut décider quand exécuter des batchs de calcul intensif en fonction de la disponibilité d’électricité renouvelable ou du tarif horaire, mettre certains serveurs en veille lors des creux de charge, migrer des machines virtuelles pour consolider sur moins de serveurs actifs, etc. On se retrouve avec un problème d’ordonnancement sous contraintes : les tâches ont des fenêtres de temps possibles, des durées, consomment une certaine puissance si sur tel serveur, et on a des contraintes de capacité par serveur (nombre de tâches simultanées) et éventuellement de performance (pas dépasser un seuil de température).
Intérêt de l’approche CSP : La complexité de ces problèmes (multi-objectifs, multi-contraintes temporelles et de ressources) rend l’approche CSP très intéressante. On peut modéliser chaque tâche ou chaque intervalle de temps par des variables, ajouter des contraintes liées à l’énergie (par ex. « la consommation totale à chaque heure ≤ X kW » ou « si groupe électrogène activé alors ne pas lancer de tâches non critiques »), et utiliser un CP-optimisation pour minimiser une fonction de coût énergétique. Par exemple, Mastrolilli et al. ont proposé un modèle CP pour planifier des tâches dans un centre de données en intégrant des contraintes d’énergie verte disponible, et ont pu formuler cela dans un solveur de contraintes pour trouver la planification optimal (Green Energy Aware Scheduling Problem in Virtualized Datacenters)】. L’avantage est de pouvoir facilement tester différents scénarios (ajout d’un panneau solaire, contraintes de température) en modifiant ou ajoutant quelques contraintes. Le solveur va alors chercher une solution qui concilie ces aspects, souvent en éteignant des serveurs inutiles ou en retardant certaines tâches non urgentes en heures creuses. Cette approche permet de réduire significativement les coûts énergétiques tout en garantissant que toutes les tâches finissent dans les délais, ce qui est difficile à obtenir avec des heuristiques gourmandes non contraintes.
Références : Kishore et al., *Green energy-aware scheduling (CP model) (Green Energy Aware Scheduling Problem in Virtualized Datacenters)】 – formalisation d’un problème de scheduling dans un datacenter vert sous forme de CP global (avec contraintes de disponibilité d’énergie renouvelable, temps d’exécution) et proposition d’une méthode de résolution par CP + heuristiques. Google – Carbon Intelligent Computing System – bien que non détaillé publiquement, Google a indiqué utiliser des optimisations sophistiquées (type CP/LP) pour décaler ses charges de travail flexibles en fonction de la disponibilité en énergie bas carbone. OR-StackExchange (Energy Scheduling) – discussion sur la modélisation CP de l’allocation de jobs avec contraintes d’énergie, suggérant des variables d’allocation horaire et des contraintes linéaires pour la consommatio (Job Scheduling with Energy Consumption using Linear Programming)】.
Description : À la fin d’un cursus, on doit souvent assigner des étudiants à des sujets de projet ou des offres de stage, en tenant compte des préférences de chacun, des capacités (chaque projet a un nombre de places, chaque encadrant peut suivre un certain nombre d’étudiants), et d’éventuelles contraintes d’admission (prérequis, éviter que deux étudiants d’une même option se retrouvent sur le même projet, etc.). Ce problème d’affectation avec préférences est un cas particulier de problème de matching en présence de contraintes complexes. Il généralise le problème classique du Stable Marriage (ou du résident-hôpital) en ajoutant des projets et enseignants. L’objectif peut être de trouver une affectation stable (pas de bloquants où un étudiant et un encadrant préféreraient être ensemble plutôt que leurs affectations actuelles), ou simplement de maximiser la satisfaction globale des vœux.
Intérêt de l’approche CSP : La programmation par contraintes offre un moyen unifié d’exprimer les préférences et les règles complexes puis de rechercher soit une solution stable, soit la meilleure solution selon un score. Par exemple, on peut modéliser comme un CSP en posant une variable pour chaque étudiant indiquant le projet auquel il est assigné, avec des domaines restreints à ses choix acceptables, et des contraintes pour respecter les capacités de chaque projet. On peut même inclure les définitions de stabilité comme contraintes : aucune paire (étudiant, encadrant) ne doit se préférer mutuellement à leurs assignation ((PDF) A Constraint Programming Approach to the Stable Marriage Problem)】. Gent et al. ont montré qu’on pouvait encoder le Stable Marriage Problem en contraintes et retrouver directement le matching homme-optimal et femme-optimal via la propagation de l’arc-consistanc ((PDF) A Constraint Programming Approach to the Stable Marriage Problem)】. De la même façon, un solveur CP peut trouver une affectation stable pour Student-Project Allocation, même si le problème est NP-difficile dès qu’on a des capacités >1 (on profite de la puissance de filtrage et de recherche). L’approche CP est aussi très flexible pour ajouter des contraintes secondaires (par exemple, chaque étudiant doit avoir un projet dans son top 5 ou répartir équitablement les étudiants entre encadrants), ce qui serait difficile à intégrer dans l’algorithme spécialisé de Gale-Shapley. En pratique, des outils d’affectation étudiante (pour des projets ou pour l’orientation) ont été réalisés avec des moteurs de contraintes ou de SAT, car cela permet d’obtenir en quelques secondes des solutions optimisées satisfaisant un grand nombre de critères.
Références : Gent et al., *Stable Marriage as CSP ((PDF) A Constraint Programming Approach to the Stable Marriage Problem)】 – deux encodages du problème de mariage stable en CSP, prouvant qu’appliquer l’arc-consistance équivaut à l’algorithme de Gale-Shapley et permettant d’énumérer toutes les solutions stables. SPA-P (Student-Project Allocation) – University of Glasgow – travaux de D. Manlove et al. sur des algorithmes spécialisés, qu’on peut reproduire avec CP pour intégrer des variantes (capacités, projets multiples). Cornell (BOOM 2001) – projet étudiant utilisant le CSP pour résoudre des Cryptoquotes, démontrant l’efficacité de la recherche exhaustive par contraintes pour trouver la solution unique d’un puzzle – par analogie, une affectation étudiants-projets peut se modéliser et se résoudre de façon similaire, en tenant compte de toutes les contraintes pour garantir une solution cohérente.
Description : Pour tester un programme, on cherche souvent des jeux de données d’entrée qui forcent l’exécution de certains chemins ou scénarios (par exemple, couvrir toutes les branches d’un code critique). Le problème peut se formuler ainsi : trouver une entrée (ou une séquence d’appels) telle qu’une condition donnée soit vraie à un point du programme (par ex. atteindre une ligne de code particulière, ou violer une assertion pour détecter un bug). Au lieu de deviner à la main, on peut utiliser une technique de génération de tests par contraintes, connue aussi sous le nom d’exécution symbolique. On exécute le programme en symbolique, c’est-à-dire en accumulant des contraintes logiques sur les variables d’entrée le long des chemins, et on utilise un solveur de contraintes pour obtenir des valeurs concrètes satisfaisant ces contrainte ([PDF] KLEE: Unassisted and Automatic Generation of High-Coverage ...)】. Par exemple, pour tester une fonction triant un tableau, on peut demander un cas où array[0] > array[1] à la fin (erreur potentielle), le moteur symbolique extraira les contraintes reliant les entrées à cet état et le solveur donnera un tableau d’entiers effectif réalisant cela.
Intérêt de l’approche CSP : Cette méthode automatise la génération de tests avec une couverture élevée et ciblée. En effet, le solveur va systématiquement tenter de satisfaire la condition d’intérêt en explorant l’espace d’entrée, et s’il y a une solution il la trouvera (et sinon on a la quasi-certitude qu’aucune entrée ne provoque ce scénario). L’outil KLEE a par exemple montré qu’il pouvait générer automatiquement des tests couvrant la plupart des chemins d’utilitaires Unix complexe (KLEE: Unassisted and Automatic Generation of High-Coverage ...)】. L’utilisation de solveurs de contraintes garantit aussi que les tests générés sont pertinents : pas de faux positifs, on trouve des entrées concrètes qui réalisent précisément le chemin voul ([PDF] KLEE: Unassisted and Automatic Generation of High-Coverage ...)】. Par rapport à des méthodes fuzz aléatoires, on explore de manière plus intelligente : chaque branche du programme engendre une contrainte (ex. si on prend le branche then, on ajoute la contrainte conditionnelle correspondante), puis on résout pour sortir des valeurs. Ainsi on peut couvrir des branches difficiles d’accès nécessitant des combinaisons spécifiques de conditions. De plus, cette approche permet de trouver des bugs subtils et d’explorer les limites (dépassements d’entier, division par zéro, etc.) en formulant ces erreurs comme des contraintes à réaliser. De nombreux frameworks de test modernes (Microsoft SAGE, KLEE, etc.) intègrent de tels solveurs SMT pour améliorer la portée des tests logiciels.
Références : Cadar et al., *KLEE (Automatic High-Coverage Tests) ([PDF] KLEE: Unassisted and Automatic Generation of High-Coverage ...)】 – KLEE utilise un solveur de contraintes pour déterminer un ensemble concret de valeurs d’entrée satisfaisant les contraintes d’exécution d’un chemin, qu’il exporte en tant que cas de test. Patrice Godefroid et al., DART (PLDI’05) – introduit le concept d’exécution dirigée par contraintes pour générer des tests, combinant exécution concrète et symbolique. *Blog « VerificationGlasses » (10. Automated test generation using symbolic execution)】 – tutoriel sur la génération de tests avec KLEE, expliquant comment un path constraint est converti en un input réel via un SMT solver, démontrant la puissance de l’approche pour atteindre des branches spécifiques du code.
Description : Dans l’edge computing, on déploie des services (par ex. des microservices IoT, des instances d’applications) non pas dans un cloud centralisé unique, mais sur une multitude de petits nœuds proches des utilisateurs (antennes 5G, mini-datacenters régionaux) afin de réduire la latence et la charge réseau. Le problème est de décider où déployer chaque composant d’une application pour satisfaire les contraintes de latence entre utilisateurs et services, ainsi qu’entre services eux-mêmes, tout en respectant les capacités limitées de chaque nœud (CPU, mémoire) et éventuellement en minimisant le coût global. Par exemple, une application de réalité augmentée peut nécessiter qu’un composant de traitement d’image soit déployé sur un edge node à moins de 10 ms de l’utilisateur final, tandis que d’autres composants moins critiques peuvent rester dans le cloud. On a donc un problème d’affectation de modules à des serveurs edge/cloud, avec contraintes de latence (distance maximale en sauts ou en temps entre certains modules et/ou l’utilisateur) et de capacité (chaque edge ne peut héberger plus d’un certain nombre de conteneurs).
Intérêt de l’approche CSP : Ce problème combine optimisation (par ex. minimiser la latence moyenne ou l’utilisation de bande passante) et satisfaction de multiples contraintes (capacités, latences maximales garanties, fiabilité, etc.), ce qui le rend naturellement modélisable en CSP à optimiser. Une approche par contraintes permet d’évaluer globalement les compromis : le solveur peut explorer des placements non-intuitifs mais valides que des heuristiques gloutonnes rateraient. Par exemple, on peut introduire une contrainte de type « le service A et la base de données B doivent être déployés dans le même cluster régional » si leur trafic est intense, ou au contraire « pas plus d’un service critique par nœud (pour fiabilité) », et laisser le solveur chercher un arrangement satisfaisant tout. Des travaux comme EdgeON ont formulé le déploiement edge comme un problème fortement contraint (ENPP : Edge Node Placement Problem) et examiné diverses stratégies d’optimisation, ce qui souligne la lourdeur combinatoire du problèm ([PDF] Network-Aware Placement Optimization for Edge Computing ...)】. L’approche CSP/ILP permet de garantir qu’une solution proposée respecte bien tous les SLA de latence, ce qui est crucial pour des applications temps réel. De plus, la flexibilité du modèle permet d’intégrer rapidement de nouvelles contraintes (par ex. contraintes de localisation pour souveraineté des données) sans recoder un algorithme dédié. Enfin, l’exploration complète peut aider à quantifier la qualité des solutions : on peut trouver l’optimal ou s’approcher d’un gap prouvé, donnant confiance dans le déploiement choisi, comparé à une approche heuristique dont on ne sait pas à quel point elle s’éloigne de l’optimal.
Références : Zhang et al., *Edge Node Placement Problem (ENPP) ([PDF] Network-Aware Placement Optimization for Edge Computing ...)】 – présente un cadre d’optimisation de placement réseau-aware très contraint (latence réseau, coûts) pour le edge computing, ce qui indique la nécessité de méthodes avancées de résolution. J. Guyonet, Edge Computing and CP – (séminaire CP 2021) discute des analogies entre placement cloud/edge et contraintes, et comment des solveurs peuvent trouver des solutions innovantes minimisant les coûts de latence. *Microsoft Azure – expression constraints for product config (foohardt/or-tools-product-configurator - GitHub)】 – bien que relatif à la configuration logicielle, ce document montre l’utilisation de contraintes tabulaires pour s’assurer que certaines combinaisons de choix (analogue à emplacement-service) sont valides, concept applicable au placement edge (exclusion mutuelle de services sur un même nœud, etc.).
Description : Les agences spatiales font face au problème d’ordonnancer les prises de vue et communications de leurs satellites. Un satellite d’observation de la Terre, par exemple, a une liste de requêtes d’images à prendre de différentes zones géographiques, mais il ne peut en réaliser qu’un nombre limité par orbite (contraintes de visibilité des cibles, de mémoire embarquée, de disponibilité d’une station pour télécharger les données, etc.). Il faut donc sélectionner quelles observations effectuer et planifier à quel moment, en respectant les contraintes orbitales (fenêtres de visibilité de chaque cible) et de ressource (un satellite ne peut faire qu’une tâche à la fois, il a une capacité mémoire limitée, il doit parfois orienter ses instruments ce qui prend du temps, etc. (DIMACS final version D.PDF) (DIMACS final version D.PDF)】. C’est un problème d’ordonnancement avec ressources multiples et contraintes temporelles, très complexe étant donné les interactions (certaines observations périodiques, priorités, etc.).
Intérêt de l’approche CSP : La programmation par contraintes a été appliquée avec succès à ces problèmes dès les années 90, intégrée dans des systèmes comme SPIKE au CNES ou le framework EUROPA de NASA. Le modèle CSP permet d’unifier la gestion des différentes contraintes : on représente les créneaux possibles pour chaque tâche (prise de vue) comme des variables temporelles, on impose que deux tâches ne peuvent se chevaucher sur le même satellite ou la même station sol, on inclut des contraintes de précédence (par ex. le téléchargement doit se faire après la prise d’image correspondante), etc (DIMACS final version D.PDF)】. Grâce à la propagation de contraintes, de nombreuses combinaisons impossibles sont éliminées d’emblée (ex. deux tâches dont les fenêtres de temps ne se croisent pas ne seront jamais planifiées sur le même passage de satellite). L’approche CSP permet aussi d’optimiser un critère, typiquement maximiser la somme des priorités des tâches réalisées. Des solveurs dédiés (ou des bibliothèques CP générales) ont ainsi permis d’automatiser une grande partie de la planification satellitaire, avec une flexibilité pour intégrer de nouvelles contraintes d’exploitation (ajout d’un nouveau satellite, périodes d’indisponibilité, etc. simplement en mettant à jour les données de contraintes) – alors qu’autrement chaque nouveau cas particulier nécessiterait de recoder des heuristiques. Enfin, la recherche par contraintes peut fournir non seulement une solution, mais aussi des preuves d’optimalité ou des alternatives (pour permettre aux opérateurs de comparer plusieurs plannings valides en fonction de critères secondaires).
Références : Frank et al. (NASA Ames), Constraint-based Scheduling for Space Missions – détaille l’architecture d’EUROPA, qui utilise un noyau CSP pour planifier des missions complexes (rovers martiens, satellites) en gérant des contraintes d’événements, de ressources et de temps. Jussien & Laas (Onera), *Scheduling Satellite modes with CP ([PDF] Scheduling Running Modes of Satellite Instruments Using ... - Onera)】 – montre que les changements d’instruments d’un satellite peuvent être planifiés efficacement via CP malgré l’accroissement de la complexité. *DIMACS’98 Paper – Constraint-Based Satellite Scheduling (DIMACS final version D.PDF) (DIMACS final version D.PDF)】 – introduit formellement le problème comme un CSP (variables = tâches avec start/duration, contraintes de ressources et de visibilité, etc.) et décrit une implémentation qui a réussi à planifier des constellations de satellites en respectant l’ensemble des contraintes opérationnelles.
Description : Pour un touriste visitant une ville pendant un temps limité, on souhaite planifier automatiquement un itinéraire quotidien incluant un sous-ensemble de points d’intérêts (musées, monuments…) qui maximisent son plaisir. C’est le Tourist Trip Design Problem (TTDP), qui est une variante de problème d’orientation (Orienteering Problem) avec des contraintes supplémentaires propres au tourism (Branch-and-Check Approaches for the Tourist Trip Design Problem with Rich Constraints | Request PDF)】. On dispose d’une liste de lieux, chacun avec une durée de visite et un intérêt (score), parfois des horaires d’ouverture, et on doit choisir lesquels visiter et dans quel ordre, de façon à ne pas dépasser la durée totale de la journée (ou la durée de séjour), et en respectant les plages horaires de chaque lieu. D’autres contraintes peuvent s’ajouter : visites obligatoires (le touriste a absolument voulu X), catégories à limiter (pas plus de 2 musées dans la journée), ordre imposé (déjeuner après telle visite), etc (Branch-and-Check Approaches for the Tourist Trip Design Problem with Rich Constraints | Request PDF)】. L’objectif est souvent d’optimiser la somme des intérêts des lieux visités (ou la satisfaction du touriste) sous ces contraintes.
Intérêt de l’approche CSP : Ce problème combine une sélection combinatoire (sous-ensemble de lieux) et un ordonnancement (ordre de visite avec temps de trajet entre lieux). Une approche par contraintes permet d’intégrer aisément tous les types de contraintes mentionnées (faisabilité temporelle, fenêtres d’ouverture, quotas de catégories, obligations) dans un seul modèle. Par exemple, on peut utiliser des variables booléennes pour indiquer si un lieu est visité, des contraintes de temps cumulatif pour s’assurer que le parcours entre 9h et 18h rentre dans la durée disponible, et des contraintes de chemin pour la logique de parcours. Duc Minh Vu et al. ont proposé une approche exacte (branch-and-check) où le problème maître sélectionne les lieux et un problème esclave vérifie la possibilité d’un circuit temporel – c’est une approche hybride CP/PLNE qui utilise des contraintes pour valider les contraintes riches (ordre, types (Branch-and-Check Approaches for the Tourist Trip Design Problem with Rich Constraints | Request PDF)】. L’approche CSP pure pourrait consister à créer une séquence de positions horaires (1er lieu, 2ème lieu, etc.) avec des contraintes de transition (si lieu A en position 1 et B en position 2, alors respecter temps trajet + durée(A) ≤ heure(B)), etc. La force du CSP est de pouvoir pruner l’exploration en éliminant tôt les séquences impossibles (par ex. si ajouter tel lieu rend le total > temps dispo, ce branchement est coupé). De plus, on peut optimiser la somme des scores via une technique de branch and bound sur le CSP. Bien que NP-difficile, des solveurs peuvent trouver des itinéraires optimaux pour un nombre raisonnable de POIs, et fournir des options alternatives en fonction des préférences. Cela dépasse largement ce qu’un simple algorithme glouton ferait, et garantit de ne pas rater une combinaison de lieux peu évidente mais très avantageuse.
Références : Vu et al., *Tourist Trip Design Problem with rich constraints (Branch-and-Check Approaches for the Tourist Trip Design Problem with Rich Constraints | Request PDF)】 – définit formellement le problème (objectifs et multiples contraintes pratiques : budget temps, horaires, catégories, ordre imposé) et propose une méthode exacte combinant sélection de lieux et vérification de chemin faisable. Souffriau et al. – travaux fondateurs sur le TTDP modélisé comme un Orienteering Problem avec contraintes, solution via une combinaison de CP et de VNS (Variable Neighborhood Search). Vansteenwegen, Orienteering Problem survey – discute des nombreuses variantes (Time Windows, Team orienteering, etc.) qui peuvent être toutes vues comme des ajouts de contraintes, ce qui milite pour une approche CSP modulable pour traiter un cas comme l’itinéraire touristique personnalisé.
Description : On considère un texte chiffré par substitution monoalphabétique (chaque lettre de l’alphabet a été remplacée par une autre, permutation secrète). C’est un casse-tête classique (les « cryptoquotes » des journaux). Par exemple, « UJHOP » peut être « BONNE » si le chiffrement substitue U→B, J→O, etc. Résoudre cela à la main implique de tester des correspondances lettres->lettres en s’appuyant sur la fréquence des lettres et la reconnaissance de mots. On peut modéliser le déchiffrement comme un CSP : chaque lettre chiffrée est une variable dont le domaine est les lettres claires possibles, avec comme contraintes que c’est une bijection (une substitution bijective) et que chaque mot déchiffré doit appartenir au dictionnair (Applying Constraint Satisfaction Methods to CryptoQuotes)】. Par exemple, si le texte chiffré contient un mot de 3 lettres « XQZ » et que dans le dictionnaire il n’y a que « THE, ONE, CAT, … » en 3 lettres, alors X→C, Q→A, Z→T sera imposé pour satisfaire au moins un mot (« CAT »). Le but est de trouver l’affectation des 26 variables (ou moins si on ne chiffrait que les lettres A-Z en gardant la ponctuation) qui satisfait toutes les contraintes (chaque mot forme un mot anglais valide).
Intérêt de l’approche CSP : Une telle méthode exploite la puissance des contraintes pour réduire drastiquement l’espace de recherche. Par propagation, dès qu’une lettre est assignée, elle élimine cette possibilité pour les autres (contrainte bijective) et restreint les candidats pour former des mots valides. Une équipe de Cornell a montré que cette approche résolvait systématiquement et rapidement des cryptogrammes de longueur significative, là où des méthodes de recherche locale pouvaient rester coincée (Applying Constraint Satisfaction Methods to CryptoQuotes) (Applying Constraint Satisfaction Methods to CryptoQuotes)】. En effet, les algorithmes gloutons ou génétiques sont parfois piégés par de faux amis (mauvais départ dans l’affectation des lettres) et n’explorent pas assez, alors que le backtracking contraint va explorer toutes les possibilités mais en coupant agressivement celles incompatibles avec le dictionnaire. L’approche CSP garantit de trouver la solution unique si elle existe (ou toutes les solutions possibles s’il y a des ambiguïtés), et on peut l’améliorer en ajoutant des contraintes supplémentaires (par ex. respecter la distribution de fréquence des lettres pour guider le choix initial). C’est ainsi qu’en 2012, Freebase a utilisé une approche par satisfaction de contraintes couplée à un A* pour battre le record de déchiffrement de l’Enigma (plus complexe qu’une simple substitution). Plus modestement, pour des chiffrés classiques journaliers, un programme CSP résout en quelques millisecondes là où un humain mettrait de longues minutes.
Références : Cornell BOOM Project, Cryptoquotes as a CSP (Applying Constraint Satisfaction Methods to CryptoQuotes) (Applying Constraint Satisfaction Methods to CryptoQuotes)】 – détaille la modélisation (variables = lettres chiffrées, contraintes de bijection et de dictionnaire) et conclut que la méthode par contraintes est « extrêmement efficace » et renvoie toujours la solution correcte très rapidement. Constraint satisfaction algorithm for automatic decryption (Lucks 1988) – un des premiers algorithmes CSP appliqués au déchiffrage monoalphabétique, présenté à Crypto’88, qui a posé les bases de cette approche systématique. StackOverflow Q&A « solve substitution cipher » – discute des algorithmes existants et mentionne que la recherche exhaustive intelligente (avec contraintes ou A) garantit le déchiffrement fiable, contrairement aux simples hill-climbing qui peuvent échouer sur des textes courts.
Contexte :
Chaque année, plusieurs compétitions internationales dédiées à la résolution de problèmes de satisfaction de contraintes (CP), problèmes de satisfiabilité booléenne (SAT), et problèmes de satisfiabilité modulo théories (SMT) sont organisées. Ces compétitions visent à évaluer les progrès réalisés par la communauté scientifique sur des méthodes de résolution efficaces, innovantes, et robustes. Les contributions peuvent prendre deux formes principales : le développement de nouveaux algorithmes de résolution, ou bien la création de nouveaux exemples de problèmes (benchmarks) permettant d'évaluer et comparer ces algorithmes.
Objectif du projet :
L'objectif de ce projet est de préparer une contribution concrète à l'une de ces compétitions internationales, à choisir entre les domaines CP, SAT ou SMT. Deux types de contribution sont possibles selon les intérêts et les compétences du groupe :
-
Contribution algorithmique : Développer ou adapter un algorithme original capable de résoudre efficacement une catégorie spécifique de problèmes, en s'inspirant des approches les plus récentes de la littérature scientifique.
-
Contribution aux benchmarks : Concevoir et produire un ensemble original et pertinent de problèmes-tests (benchmarks), permettant de mieux évaluer et différencier les performances des algorithmes actuels, en s'inspirant de problématiques concrètes ou théoriques peu couvertes par les benchmarks existants.
Attentes et livrables :
- Identifier clairement la compétition cible (CP, SAT ou SMT) et les modalités de participation.
- Pour les contributions algorithmiques : Implémentation opérationnelle et évaluation comparative rigoureuse par rapport aux algorithmes existants.
- Pour les contributions aux benchmarks : Description précise de l'origine des nouveaux problèmes, justification de leur intérêt scientifique et expérimental, et génération d'un jeu de données au format standard utilisé par la compétition choisie.
- Rédaction d'un court rapport scientifique documentant la démarche, les résultats obtenus et les perspectives éventuelles.
Ressources utiles :
- International SAT Competition
- SMT-COMP
- MiniZinc Challenge (CP)
- BenchExec (outil standardisé pour l'évaluation des solveurs)
Ce sujet représente une excellente opportunité pour acquérir une visibilité scientifique en contribuant directement aux progrès internationaux dans le domaine de la résolution automatique de problèmes complexes.