Inférence de cliques pour la résolution de Max-CSPReport as inadecuate




Inférence de cliques pour la résolution de Max-CSP - Download this document for free, or read online. Document in PDF available to download.

1 LIPN - Laboratoire d-Informatique de Paris-Nord

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 DAC13, RDAC8 et WAC1 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.





Author: Mohand Ou Idir Khemmoudj - Hachemi Bennaceur -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents