Rechercher

[ROU01] Résolution de MAX 2SAT par programmation semidéfinie

Conférence Internationale avec comité de lecture : Francoro III, Québec, January 2001,

Auteurs: F. Roupin

motcle:
Résumé: La programmation semidéfinie (SDP) a démontré son efficacité pour obtenir des bornes théoriques d'excellente qualité pour le problème MAX 2SAT. En particulier, Goemans et Williamson [1] puis Feige et Goemans [2] ont proposé des algorithmes approchés de ratios de performance au pire cas égaux respectivement à 0,878 et 0,931 pour ce problème. Bien que la résolution d'un programme semidéfini reste coûteuse en temps, nous proposons un algorithme de séparation/évaluation (Branch&Bound) très performant pour la résolution exacte de MAX 2SAT utilisant la SDP pour l'évaluation. Nous montrons comment utiliser les différentes techniques de primalisation proposées par Feige, Goemans et Williamson afin d'obtenir très tôt la solution optimale (souvent à la racine de l'arbre de recherche) et ainsi d'évaluer un nombre de sommets très faible. La résolution des SDPs est effectuée à l'aide de la bibliothèque CSDP [3] mise au point par Brian Borchers qui utilise l'algorithme primal-dual de Helmberg et al. [4]. Cette approche permet d'élaguer des solutions sans avoir à résoudre complètement les SDP puisque la valeur du dual fournit à chaque itération une borne du problème. En fait, la qualité de la relaxation est telle qu'en moyenne 5 ou 6 itérations suffisent alors que la résolution complète du SDP en requiert au moins 20. Les résultats de notre algorithme sont comparés à ceux obtenus par Joy et al.[5] qui proposent un Branch&Cut utilisant GSAT comme heuristique pour le primal. Comme ces auteurs le remarquent dans [5]l'approche par SDP n'est pas compétitive pour des instances comportant peu de clauses. En revanche, pour des instances de moyenne ou forte densité, notre Branch-and-Bound se révèle être très performant. Par exemple, nous résolvons les instances de 50 variables et 2500 clauses en moins de 30 secondes alors qu'une demi-heure est nécessaire au Branch&Cut de Joy et al. Bibliographie [1] M. X. Goemans et D. P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM, 42, pp. 1115-1145, 1995. [2] U. Feige and M. X. Goemans. "Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT", Proceedings of the Third Israel Symposium on Theory of Computing and Systems, Tel Aviv, Israel, 182--189, 1995. [3] Brian Borchers, CSDP, a C library for semidefinite programming. Technical report, Mathematics Department, New Mexico Tech, Socorro, NM87801, March 1997. [4] C. Helmberg, F. Rendl, B. Vanderbei and H. Wolkowicz. "An Interior-Point Method for Semidefinite Programming", SIAM J. Optim., Vol. 6, No.2,pp. 342-361, May 1996. [5] S. Joy, J.E. Mitchell, B. Borchers, Solving MAX-SAT and Weighted MAX-SAT Problems Using Branch-and-Cut, Februray 1998. Rapport de recherche disponible sur http://www.rpi.edu/~mitchj/papers.html.

Commentaires: note

Collaboration: LIPN

BibTeX

@inproceedings {
ROU01,
title="{Résolution de MAX 2SAT par programmation semidéfinie}",
author=" F. Roupin ",
booktitle="{Francoro III, Québec}",
year=2001,
month="January",
note="{note}",
}