Résolution pratique de
problèmes NP-complets
Actes de conférences organisées par le
CRID, université de Bourgogne
83,85 €
Commander |
 |
1996
304 pages
format 16 x 23 cm
broché
réf. LIF022
I.S.B.N.: 2-87717-055-1 |
|
Présentation
Table des matières
Introduction
Comités |
|
Présentation
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.
Comités
Comité d'organisation :
 |
Jean-Jacques Chabrier, CRID, Université de
Bourgogne |
|
Marie-Catherine Vilarem, LIRMM, Université de Montpellier |
|
Jacqueline Chabrier, CRID, Université de Bourgogne |
|
François Jacquenet, CRID, Université de Bourgogne
Comité de lecture : |
|
J.-J. Chabrier, CRID, Dijon |
|
P. David, EMN, Nantes |
|
D. Diaz, INRIA, Rocquencourt |
|
O. Dubois, LAFORIA, Paris |
|
L. Fribourg, LIENS/CNRS, Paris |
|
R. Genisson, LIM, Marseille |
|
J.-J. Hebrard, LAIAC, Caen |
|
G. Plateau, LIPN, Paris |
|
A. Rauzy, LABRI, Bordeaux |
|
M. Rusinowitch, LORIA, Nancy |
|
P. Siegel, LIM, Marseille |
|
T. Schiex, INRA, Toulouse |
|
M.-C. Vilarem, LIRMM, Montpellier
Rapporteurs supplémentaires : |
|
C. Bessiere |
|
P. Boucher |
|
C. Codognet |
|
P. Codognet |
|
J.-M. Geffroy |
|
I. Gouachi |
|
P. Loisel |
|
P. Lopez |
|
P. Luquet |
|
F. Pekergin |
|
P. Vila |
|
Table des
matières
Session 1 :
problèmes de satisfaction de contraintes 1ère partie
Un système de réécriture appliqué à la recherche de petits ensembles
coupe-cycles, Philippe Jégou :
Abstract
1. Introduction / 2. Définitions préliminaires
/ 3. Les opérations de contraction / 4.
L'algorithme de contraction
5. Classes de graphes résolues / 6. Conclusion
Simplification des contraintes de différence, Pierre Boiron
1. Introduction / 2. Les problèmes de satisfaction de contraintes (CSP)
/ 3. Le problème de la coloriabilité des graphes /
4. Différentes sortes de CSP / 5. Les graphes à 2-décomposition semi-complète
/ 6. Étude des DCSP à domaines larges / 7 Un algorithme de résolution des DCSP à domaines larges
/ 8 Méthodes de simplification / 9 Conclusion
Session 2 :
algorithmes
stochastiques
A Neural Network Method to Exhibit Maximal Set of Solutions for Binary
Constraint Satisfaction Problems, Mahamoudou Ouedraogo, Paul Bourret
1. Mapping a Binary CSP onto Potts Glasses
/ 2. MFT Approximation for Potts Model Mapping /
3. Convergence towards Maximal Set of Solutions /
4. Results and Comments
Sur les algorithmes stochastiques et les problèmes NP-difficiles, Jihad Jaam
1. Les problèmes d'optimisation combinatoire
/ 2. Les méthodes stochastiques / 3. Algorithmes de descente rapide
/ 4. Le recuit simulé / 5. La méthode de recherche Tabou
/ Conclusion
Dénombrement approché des solutions d'instances de problèmes difficiles par
recherche locale stochastique, Olivier Bailleux, Jean-Jacques Chabrier
1. Introduction / 2. Principe
/ 3. Mise en œuvre / 4. Résultats expérimentaux
/ 5. Conclusion
Session 3 :
problèmes SAT
Restriction des données SAT, résolution en moins de o((2k -
1)p/k) étapes, Éric Humbert
1. Introduction / 2. Notation des données SAT
/ 3. Restriction sur le nombre exact d'occurrences par variable
4. Restriction des données 3+-SAT / 5. Restriction des données 3-SAT
/ 6. Élimination de solutions /
7. Élimination d'une clause / 8. Décomposition de type
k
Deux approches pour la résolution du problème SAT, Bertrand Mazure,
Lakhdar SaÏs, Éric Grégoire
1. Introduction / 2. TWSAT : l'algorithme
/ 3. Réglage de TWSAT : résultats expérimentaux
/ 4. GSAT vs TWSAT / 5. Inconsistance locale vs Inconsistance globale
/ 6. Utilisation de TWSAT pour circonscrire l'inconsistance
/ 7. DP+TWSAT une méthode mixte / 8. FFIS vs TWSAT
/ 9. Optimisations naturelles / 10. Conclusion
Session 4 :
problèmes
de satisfaction de contraintes 2ème partie
Une nouvelle approche de résolution systématique sur les domaines finis
entiers, basée sur la recherches locale : SCORE(FD/I),
Isabelle Blot,
Jacqueline Chabrier
1. Introduction / 2. Quelques préliminaires
/ 3. Le langage SCORE(FD/I) / 4. La résolution
/ 5. Conclusion et perspectives
CSP dynamiques et relaxation de contraintes, Narendra Jussien,
Patrice Boizumault
1. Introduction / 2. Contraintes explicites et contraintes implicites
/ 3. Relaxation de contraintes / 4. Maintien de déductions
/ 5. Apports et comparaisons / 6 Conclusion et travaux futurs
Session 5 : Davis et Putnam
Une nouvelle méthode de calcul des impliquants et des impliqués premiers,
Thierry Castell,
Michel Cayrol
Introduction / Le produit unioniste /
Impliquants et impliqués premiers par le produit unioniste global
/ Impliquants et impliqués premiers par un double produit unioniste
/ Calcul du produit unioniste / Caractère "anytime algorithm"
/ Résultats empiriques / Conclusion
Efficient Horn Renaming: yet a Davis and Putnam's procedure, Richard GÉnisson, Antoine Rauzy
1. Introduction / 2. Horn Renaming
/ 3. A Davis and Putnam's like Algorithm for Horn Renaming
/ 4. Experimental Results / 5. Related Problems
/ 6. Conclusion
Session 6 : applications
Application d'un algorithme de recuit simulé pour la résolution d'un problème
complexe de dimensionnement, Éric Nespoulos, Tanguy Le Quenven,
Gregory Stéfanou
1. Introduction / 2. Définition du problème
/ 3. Les méthodes envisagées / 4. Description de l'algorithme de recuit simulé utilisé
/ 5. Les résultats / Conclusion
Applying Tabu Search to Frequency Assignment Problems, Jin-Kao Hao,
Laurent Perrier
1. Introduction / 2. Problem Modeling
/ 3. Tabu_ Fap: a Tailored TS Procedure / 4. Experimentation and Results
/ 5. Conclusion & Future Work
Résolution du problème d'ordonnancement d'ateliers de type job-shop généralisé par
des algorithmes génétiques, Fatima Ghedjati
1. Introduction / 2. Description du problème d'ordonnancement considéré
/ 3. Description de l'approche génétique utilisée /
4. Expérimentations et résultats / 5. Conclusion
Session 7 :
problèmes
de satisfaction de contraintes 3ème partie
Consistance de circuit et résolution de problèmes,
M. S. Affane,
S. Ould Hamiche
1. Introduction / 2. Préliminaires
/ 3. Méthode de résolution / 4. Expérimentations
/ 5. Conclusion
Dealing with Forward Checking Search Method in CSP's, Belaid Benhamou,
Assef Chmeiss
1. Introduction / 2. Improvements of Forward Checking
/ 3. Experiments / 4. Conclusion
Session 8 : Nogoods
Échange de Nogoods pour la résolution coopérative de problèmes de
satisfaction de contraintes, David Martinez, Gérard Verfaillie
1. Recherche parallèle coopérative /
2. Production et mémorisation de Nogoods / 3. Mise ne œuvre d'une recherche parallèle coopérative avec échange de nogoods
/ 4. Expérimentations / 5. Différentes heuristiques d'ordonnancement des variables
/ 6. Différentes heuristiques d'ordonnancement des valeurs
/ 7. Analyse des résultats / 8. Discussion
Distribution de l'arbre de recherche des problèmes de satisfaction de contraintes en
domaines finis, Nicolas Prcovic, Bertrand Neveu, Pierre Berlandier
1. Introduction / 2. Rappels théoriques
/ 3. L'algorithme de distribution de l'arbre de recherche
/ 4. Intégration des techniques d'élagage de l'arbre de recherche
/ 5. Résultats expérimentaux / 6. Conclusion
Session 9 : application
Du codage des automates en vue de la synthèse sur silicum : comparaison
systématique et critique des approches existantes, Ludovic Jacomme,
Frédéric Pétrot
1. Introduction / 2. Présentation du problème
/ 3. Les techniques de codages d'états / 4. Comparaisons
/
5. Conclusion |
|
Introduction
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.
Sur 27 articles soumis, le Comité de lecture en a sélectionné 19 qui offrent un bon
équilibre entre recherche théorique et applications.
Deux conférenciers invités, Toby Walsh
et Jean Goubault-Larrecq, exposeront des résultats et réflexions sur des recherches
concernant GSAT de B. Selman, la logique du
premier ordre et BDD.
Je veux maintenant chaleureusement remercier, pour leur
aide :
· Marie-Catherine Vilarem (LIRMM Montpellier),
vice-présidente de la conférence
· Michel Rusinowitch
(CRIN-LORIA Nancy) et Antoine Rauzy (LaBRI
Bordeaux) pour leur contribution efficace
· les membres du Comité de lecture qui ont fourni un
travail important et très efficace malgré les délais serrés
· les partenaires qui ont apporté leur contribution financière
· et enfin, les membres du Comité d'organisation, mes collègues du CRID (Dijon) :
Dominique Belime,
Jacqueline Chabrier, François Jacquenet qui ont fait preuve de beaucoup
d'abnégation pour que ces journées se déroulent dans les meilleures conditions
possibles.
Jean-Jacques Chabrier, Président de la Conférence
|
|