Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

https://hal.inria.fr/inria-00085808
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 3:24:25 PM
Last modification on : Saturday, February 15, 2020 - 1:55:30 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:09:55 AM

File

Identifiers

  • 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. ⟨inria-00085808⟩

Share

Metrics

Record views

165

Files downloads

150