Encodage des contraintes à la plupart des contraintes à la plupart d'un problème max-sat

Question

supposer un ensemble de variable $ V $ = $ \ {v_1, ..., v_m \} $ < / span>.

donné TOTAL N $ N $ AT-One (AMO) Contraintes (à la plupart d'un élément d'un ensemble donné est vrai ) Définissez [du formulaire ci-dessous], sur l'ensemble de la variable $ v $ ,

$$ Amo \, (v_1, v4, \ nge v_6, v_ {10}) \\ ... \\ amo \, (v_2, \ neg v3, v_7 ) $$

Problem: Find an assignment to $V$ that maximize
         the number of satisfiable AMO constraint set. 

Je ne peux pas le représenter en tant que problème max-sat.

essayé jusqu'à présent (tentative 1): Utiliser une contrainte dure pour chacune des contraintes à la plupart d'une contrainte. Cela ne fonctionnera pas comme codage de $ amo (v_i, ..., v_w) $ aura plusieurs clauses pour chaque $ Amo $ et tous ont attribué le même poids (poids supérieur). Une solution à cet ensemble peut ne pas être maximale.

Tentative (2): Pour corriger le problème ci-dessus, j'ai essayé le poids de la clause relative; C'est-à-dire que, pour chaque clause, attribuez du poids proportionnellement à la taille de la clause. Cela préférera attribuer une clause plus courte satisfaisante. Mais cela ne fonctionne pas dans des situations extrêmes comme si toute la clause a la même longueur.

J'ai une expérience avec les solveurs SAT, mais c'est ma première tentative de problème maximum-sat.

Answer 1

Le moyen standard de créer des contraintes douces dans MaxSat est d'utiliser des variables d'étiquettes:

pour chaque $ AMO_J $ contrainte, créez une nouvelle variable $ l_j $ .Ensuite, créez une clause d'unité $ (\ lnot l_j) $ avec poids $ 1 $ et ajoutez le littéral $ l_j $ à chaque clause de la norme $ amo_j $ codage contenant uniquement des clauses durs (poids infini).

maintenant la variable d'étiquette $ l_j $ actes comme interrupteur: réglage $ l_j= true $ "Désactiver" la $ AMO_J $ Contraint dure, mais ne satisfasse pas la clause de l'unité $ (\ lnot l_j) $ .