Beaucoup de problèmes industriels sont combinatoires. Dès que l’on veut agencer des tâches tout en respectant la capacité des machines ou l’ordre entre certaines tâches, on résout un problème combinatoire. La généralisation de l’utilisation de l’intelligence artificielle pour résoudre de tels problèmes date du milieu des années 1990. Les deux principaux paradigmes d’intelligence artificielle utilisés sont la programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More* et SATvoir Problème SAT **.
Parmi les premiers succès, on peut citer l’utilisation de la programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More pour optimiser les chaînes de montage de voitures en fonction des voitures commandées et du temps de montage des options sur une voiture. Plusieurs constructeurs ont utilisé ces techniques dès les années 1990, augmentant grandement l’efficacité de production (jusqu’à 40 % de gain observé). À la même époque, une des applications qui a rendu célèbre la programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More a été l’utilisation d’ILOG Solverprogramme résolvant des problèmes d’optimisation combinatoire, en utilisant la programmation par contraintes*, développé par la compagnie ILOG (startup issue de l’INRIA créée en 1987, et rachetée en 2008 par IBM), et permettant de résoudre des problèmes de production, de logistique, etc. Son intérêt est de... More* pour optimiser le parcours des excavatrices à charbon
dans une grande mine aux États-Unis. Le rendement de cinq excavatrices a été égalé avec seulement quatre, simplement en optimisant leur parcours dans la mine.
Dans le domaine hospitalier, les emplois du temps des infirmières sont calculés par un programme à contraintesune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More dans plusieurs grands hôpitaux. Un des avantages de cette approche par rapport à la programmation linéaireméthode mathématique qui a pour but d’optimiser (maximiser ou minimiser) une fonction linéaire de plusieurs variables x1, ..., xn qui sont liées entre elles par des contraintes également linéaires (c’est-à-dire de la forme a1·x1 + ... + an·xn = 0, où a1, a2,..., an sont... More* est la facilité avec laquelle on modifie un modèle à contraintesune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More pour exprimer les variations de réglementation du travail selon les années ou le pays. Depuis peu, on utilise également des programmes à contraintesune contrainte exprime des restrictions que l’on souhaite imposer sur des éléments d’un problème. Par exemple, il est possible d’imposer pour un logement que la surface d’une chambre soit d’au moins 12 m2 (qui se traduira ici par une inégalité mathématique largeur x longueur ≥... More pour gérer/minimiser les files d’attente de patients en soins ambulatoires.
Dans le domaine du transport, la programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More a été utilisée pour l’affectation des membres d’équipage à leurs trajets, l’affectation d’avions aux portes d’embarquement ou l’affectation de trains aux quais.
Dans un cadre plus général que l’affectation de tâches / ressources, un problème de planification consiste à atteindre un but en exécutant une séquence d’actions (nous détaillerons cette thématique à la section suivante). Jusqu’aux années 1990, ce problème était trop difficile pour les techniques existantes. Mais un seuil a été franchi quand on a découvert qu’en bornant le nombre d’actions à réaliser (quitte à l’augmenter plus tard) on pouvait coder ce problème en une formule de la logiquela logique, qui apparaît dans la Grèce Antique avec l’étude des syllogismes, s’intéresse à la formalisation du raisonnement. La lo- gique moderne, qui se développe à partir du XIXe siècle, a conduit à la formalisation d’un véritable calcul déductif à partir de formules logiques formées... More* des propositions et le résoudre avec un solveur SATalgorithme dédié à la résolution efficace des instances (cas) du problème SAT*. La complexité* théorique du problème SAT fait que l’on sait que pour un certain nombre d’instances on ne pourra pas trouver de solution en un temps raisonnable. Le but des solveurs SAT est... More* permettant ainsi de venir à bout de très gros problèmes de planification. C’est avec des techniques d’intelligence artificielle que l’on planifie les actions des robots envoyés dans l’espace, qui, vu la distance, doivent décider par eux-mêmes les actions à faire pour atteindre le but fixé.
La technique consistant à borner le nombre d’actions pour pouvoir utiliser un modèle SATvoir Problème SAT * a aussi prouvé son efficacité dans la vérification de programmes ou de microprocesseurs. On borne le nombre d’étapes de l’automate représentant le fonctionnement du composant à vérifier pour pouvoir le coder par une formule de la logiquela logique, qui apparaît dans la Grèce Antique avec l’étude des syllogismes, s’intéresse à la formalisation du raisonnement. La lo- gique moderne, qui se développe à partir du XIXe siècle, a conduit à la formalisation d’un véritable calcul déductif à partir de formules logiques formées... More propositionnelle dont les solutions correspondent à la détection d’une erreur.
De plus en plus de problèmes rencontrés par les biologistes sont combinatoires. Dans les années 2000 la programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More a résolu des problèmes comme l’ordonnancement de marqueurs génétiques, la prédiction de structures d’ARN ou la conception de protéines.
Les années 2010 ont vu la programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More utilisée pour des problèmes soulevés par le développement durable. La programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More permet d’organiser les tâches d’un “data center” de sorte à éviter les gros besoins d’électricité lors des pics de consommation, où l’on doit avoir recours à une centrale thermique, alors qu’à un autre moment on peut utiliser l’énergie éolienne, par exemple. La programmation par contraintesdomaine de l’intelligence artificielle qui s’intéresse à la résolution de problèmes combinatoires. L’utilisateur modélise sa problématique dans un langage simple en identifiant les inconnues et les contraintes* qu’il souhaite imposer. Un algorithme (appelé solveur), basé sur des principes de résolution génériques, lui fournit alors une... More permet aussi d’organiser les pâturages de moutons en Irlande ou les couloirs sanitaires pour les ours dans les Rocheuses.
Enfin, la preuve de théorèmes mathématiques et la simplification de preuves sont deux exemples récents et prometteurs d’utilisation de SATvoir Problème SAT * (voir la section « IA et Mathématiques » pour un exemple).