APPROCHE ANALYTIQUE D’UN PROBLÈME DIFFICILE D’OPTIMISATION : MAX-2-XORSAT

APPROCHE ANALYTIQUE D’UN PROBLÈME
DIFFICILE D’OPTIMISATION : MAX-2-XORSAT

Le contexte 2-XORSAT 

Pour les problèmes de satisfaction, deux questions principales peuvent se poser : existet-il une affectation de valeur aux variables réalisant toutes les contraintes, ou comment faire pour satisfaire un nombre maximum de contraintes ? Ces deux questions classent respectivement les problèmes de satisfaction en problème de décision et en problème d’opimisation. Le problème 2-XORSAT consistant à répondre oui s’il existe une solution à la formule donnée et non dans le cas contraire est donc un problème décisionnel. Il peut être formulé de la manière suivante. Nous avons une collection de n variables booléennes x1, x2, . . . , xn et une conjonction de m clauses de la forme xi ⊕ xj =  où  ∈ {0, 1} avec xi ⊕xj = 1 si et seulement si (xi = 0 et xj = 1) OU (xi = 1 et xj = 0), et xi ⊕xj = 0 si et seulement si xi = xj . Notons par P(n, m) la classe de ces formules. Une clause xi⊕xj =  de l’instance ainsi formée est dite satisfaisable s’il existe une affectation (de vrai=1 ou faux=0) aux variables rendant l’équation vraie. Par la suite, une formule sur n variables et à m clauses de P(n, m) est dite satisfaisable si et seulement si toutes les clauses sont satisfaisables. Exemple, soit le probème Π1 ∈ P(4, 4) suivant Π1 =    x1 ⊕ x2 = 1 x2 ⊕ x3 = 0 x3 ⊕ x4 = 1 x4 ⊕ x2 = 1 Π1 est satisfaisable car une solution serait {x1 = 0, x2 = 1, x3 = 1, x4 = 0}. La figure 1.1 représente le graphe correspondant. Comme beaucoup de problèmes de satisfaction, 2-XORSAT se modélise en utilisant la théorie des graphes. Les formules peuvent être traduites sous forme de graphes où les sommets sont étiquetés par les variables xi et les arêtes sont pondérées par 0 ou 1 représentant les relations entre deux sommets. Il est établi qu’une formule est satisaisable si et seulement si il n’existe pas de cycles de poids impairs dans le graphe correspondant problème est facile algorithmiquement car il se résout en temps polynomial. Par contre, s’il n’existe pas une solution au problème donné, MAX-2-XORSAT consiste alors à maximiser le nombre de clauses satisfaisables et ce problème est un problème difficile d’optimisation. Voyons de suite un exemple de formule non satisfaisable, Π2 ∈ P(4, 4) Π2 =    x1 ⊕ x2 = 1 x2 ⊕ x3 = 0 x3 ⊕ x4 = 1 x4 ⊕ x2 = 0 Π2 ne possède pas de solutions. Dans cet exemple, le nombre maximum de clauses satisfaisables est 3. La figure 1.2 représente le graphe correspondant à Π2. 

Le Problème MAX-2-XORSAT 

Nous avons un modèle aléatoire d’un problème de satisfaction de contraintes booléennes. Reprenons l’instance que nous venons de formuler précédemment. Le nombre de clauses est m et le nombre de variables est n. Une clause xi⊕xj =  est tirée uniformement au hasard parmis toutes les clauses possibles. Comme le tirage est sans remise, chaque formule comportant m clauses apparaît avec une probabilité poids impair, que peut on dire à propos du nombre maximum de clauses satisfaisables ? Le problème MAX-2-XORSAT consiste à maximiser le nombre de clauses satisfaisables dans une formule. En d’autres termes, sur les 2 n affectations possibles des variables xi , il s’agit de trouver celle(s) qui vont satisfaire le maximum de clauses dans une formule donnée. Rappelons quelques principales motivations. D’abord, l’une des principales motivations de ce domaine est la relation importante entre les phénomènes observés expérimentalement en physique statistique et les problèmes d’optimisation combinatoire que nous avons mentionnés au début. Le problème sert donc à valider certaines méthodes non encore rigoureuses en physique théorique notamment la méthode des “verres de spin”. Ensuite les problèmes de type satisfaction intéressent beaucoup de chercheurs. A ce propos, nous renvoyons à l’article de Talagrand qui est une introduction au séminaire Bourbaki à l’intention des mathématiques pures de ces objets décrits par des méthodes et des langages motivés par la physique théorique .Ces problèmes sont célèbres non seulement par les difficultés intrinsèques qu’elles engendrent mais aussi par leur rôle central en théorie de complexité computationnelle. Enfin les caractéristiques de 2-XORSAT nous conduisent naturellement à la version OPTIMISATION du problème : étant donné un système de m clauses sur n variables et un nombre positif R, on cherche s’il existe une affectation de valeurs aux variables qui rend R équations vraies. Il est démontré que pour R = m et m = cn, une formule aléatoire de cn clauses sur n variables est satisfaisable avec une probabilité p(n, cn) .