Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable. Ils sont notamment au cœur de la programmation par contraintes, un domaine fournissant des langages de modélisation de problèmes et des outils informatiques les résolvant.
Formellement, un problème de satisfaction de contraintes est défini par un triplet , où est un ensemble de variables, est un ensemble de domaines de valeurs tels qu'un de ses éléments soit le domaine d'une variable de , et est un ensemble de contraintes. Chaque contrainte est à son tour une paire , où est un N-uplet de variables et est un ensemble de N-uplets de valeurs ; tous ces N-uplets ayant le même nombre d'éléments ; ainsi définit une relation. Une évaluation des variables est une fonction des variables vers les domaines, . Une telle évaluation satisfait une contrainte si . Une solution est une évaluation qui satisfait toutes les contraintes.
Les CSP sont aussi étudiés en théorie de la complexité des algorithmes et en théorie des modèles finis. Une question importante est de savoir si pour chaque ensemble de relations, l'ensemble de tous les CSP qui peuvent être représentés uniquement par des relations choisies à partir de cet ensemble est soit de classe P soit NP-complet (en présumant P ≠ NP). Si une telle dichotomie est vraie, alors les CSP fournissent l'un des plus larges ensembles connus de NP, évitant les problèmes qui ne sont ni résolubles en un temps polynomial ni NP-complets, dont l'existence fut démontrée par le théorème de Ladner. La dichotomie est connue pour des CSP où le domaine de valeurs est de taille 2 ou 3.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
The student will acquire the basis for the analysis of static structures and deformation of simple structural elements. The focus is given to problem-solving skills in the context of engineering desig
Présentation des méthodes de la mécanique analytique (équations de Lagrange et de Hamilton) et introduction aux notions de modes normaux et de stabilité.
Le but du problème des huit dames est de placer huit dames d'un jeu d'échecs sur un échiquier de 8 × 8 cases sans que les dames puissent se menacer mutuellement, conformément aux règles du jeu d'échecs (la couleur des pièces étant ignorée). Par conséquent, deux dames ne doivent jamais partager la même rangée, colonne, ou diagonale. Ce problème appartient au domaine des problèmes mathématiques et non à celui de la composition échiquéenne. Simple mais non trivial, ce problème sert souvent d'exemple pour illustrer des techniques de programmation.
La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).
En informatique, plus précisément en algorithmique, le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour trouver des solutions à des problèmes algorithmiques, notamment de satisfaction de contraintes. Contrairement à une recherche exhaustive, un algorithme de retour sur trace construit incrémentalement des solutions candidates. Il abandonne la construction lorsqu'il ne peut compléter le candidat courant en solution valide.
Explore l'optimisation avec des contraintes en utilisant les conditions KKT et l'algorithme de point intérieur sur deux exemples de programmation quadratique.
L'art des structures propose une découverte du fonctionnement des structures porteuses, telles que les bâtiments, les toitures ou les ponts. Ce cours présente les principes du dimensionnement et les s
Les structures en treillis, en poutre, en dalles et en cadre sont essentielles pour une grande partie des constructions modernes : immeubles pour l'habitation ou de bureaux, halles et usines, ponts, o
Modern optimization is tasked with handling applications of increasingly large scale, chiefly due to the massive amounts of widely available data and the ever-growing reach of Machine Learning. Consequently, this area of research is under steady pressure t ...
EPFL2024
In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...
This doctoral thesis navigates the complex landscape of motion coordination and formation control within teams of rotary-wing Micro Aerial Vehicles (MAVs). Prompted by the intricate demands of real-world applications such as search and rescue or surveillan ...