Paru le 15/06/1996 | Broché 302 pages
Professionnels
Les problèmes NP-complets recouvrent un très large spectre de domaines de recherche : SAT (satisfaction d'expressions booléennes), CSP (problèmes de satisfaction de contraintes), Programmation Linéaire, Recherche Opérationnelle, Théorie des Graphes, Combinatoire, Programmation par Contraintes, etc.
Théoriquement intraitables, du moins tant que la conjecture P=NP n'a pas reçu de réponse positive, ces problèmes sont au cœur de la théorie de la complexité. En pratique cependant, des progrès constants et encourageants ont été accomplis ces dernières années pour résoudre ces problèmes fondamentaux et stratégiques pour nombre d'applications industrielles. Plusieurs méthodes proposées récemment s'avèrent particulièrement prometteuses : les méthodes de simplification, la réparation locale, la recherche tabou, les heuristiques, le recuit simulé, l'évolution artificielle, les réseaux neuronaux, etc.
Pour comprendre "pourquoi" et "quand" certaines de ces méthodes marchent "mieux" ou "moins bien", d'autres travaux se sont intéressés d'une part à l'identification d'instances difficiles dans l'espace des problèmes et d'autre part à la proposition de bancs d'essais sur des instances de problèmes NP-complets générés aléatoirement.
Cette conférence annuelle, organisée par le CRID et le groupe de recherche "Aspects Algorithmiques de la Résolution de Problèmes exprimés à l'aide de Contraintes" du PRC-IA est destinée à faire le point sur l'état actuel des connaissances. Elle se veut un lieu de rencontre et d'échange entre les chercheurs travaillant sur cette problématique.
Le présent volume réunit les actes des communications présentées lors des trois journées de la conférence. Les thèmes des différentes sessions sont les suivants :
