Inférence de cliques pour la résolution de Max-CSP

Résumé : Peu de travaux sur les problèmes CSP, Max-CSP et CSP valués ont été réalisés dans le domaine de l'Optimisation Combinatoire alors que ce domaine ren- ferme de nombreux outils algorithmiques qui peuvent servir à la résolution de ces problèmes. Dans ce papier, nous décrivons une technique d'inférence d'ensembles de cliques à partir du Max-CSP que nous exploitons pour dénir une nouvelle modélisation en Programma- tion Linéaire (PL) du Max-CSP. Nous montrons que les estimations classiques du nombre minimum de con- traintes violées (bornes inférieures) basées sur la consis- tance d'arc telles que DAC[13], RDAC[8] et WAC[1] peu- vent être traduites par des relaxations duales Lagrangien- nes du PL. Nous tirons aussi prot de cette modélisation pour développer de nouvelles bornes inférieures. Dans un premier temps, an d'avoir une idée sur la qualité des bornes inférieures obtenues à partir du PL, nous avons évalué la valeur de la relaxation continue du PL à l'aide du solveur CPLEX, puis nous avons développé une méth- ode du type Branch and Bound intégrant une relaxation Lagrangienne du PL. Les résultats obtenus sont très en- courageants et ouvrent de nouvelles perspectives à ex- ploiter au mieux les outils de la programmation linéaire pour contribuer à la résolution de ces problèmes.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00085808
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 15:24:25
Dernière modification le : jeudi 11 janvier 2018 - 06:17:31
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:55

Fichier

Identifiants

  • HAL Id : inria-00085808, version 1

Collections

Citation

Mohand Ou Idir Khemmoudj, Hachemi Bennaceur. Inférence de cliques pour la résolution de Max-CSP. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085808〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

44