Compter le nombre de modèles satisfaits - Compte tenu des contraintes mathématiques

Question

Question

Il y a beaucoup d'algorithmes pour résoudre le #sat problème, avec un être L'algorithme DPLL et est mis en œuvre pour toutes sortes de langages de programmation. Aussi loin que j'ai vu, ils prennent tous une formule booléenne sur le CNF comme entrée et génèrent le nombre d'interprétations satisfaites.

Les contraintes mathématiques , d'autre part, est une autre solution définissant une instance du problème SAT et est souvent utilisé dans une optimisation discrète, où l'on essaie d'optimiser certaines fonctions par rapport à ces contraintes. Y a-t-il un programme qui prend des contraintes mathématiques comme entrée et génère le nombre d'interprétations satisfaites?

Exemple

nous représentons la formule booléenne $ q= (a \ lor b) \ wedge (c \ lor d) $ comme contraintes que $$ A + b \ geq 1 \\ c + d \ geq 1 $$ ou en tant que matrice $ A $ A $ < SPAN CLASS="MATH-CONTENEUR"> $ B $ $$ A= \ commencer {bmatrix} 1100 \\ 0 & 0 & 1 & 1 \ fin {bmatrix} \\ b=begin {bmatrix} 1 & 1 \ fin {bmatrix} $$

où toutes les variables $ a, b, c, d \ in \ {0,1 \} $ . Nous savons qu'il y a des programmes prenant $ q $ comme entrée et génère le nombre d'interprétations, mais y a-t-il des programmes prenant $ A $ a $
/ span> et $ B $ comme entrée (ou construction similaire) et génère le même nombre d'interprétations?

Answer 1

Je connais deux approches raisonnables.

approche n ° 1 : compter le nombre de points entier à l'intérieur d'un polytope convexe.

L'ensemble des inégalités linéaires que vous avez fournies, ainsi que les inégalités 0 \ LE A, B, C, D \ LE 1 $ , définit un polytope convexe. Maintenant, vous voulez Compter le nombre de points entier qui tombent dans ce polyope .

Il y a des algorithmes standard pour ce faire, que vous pourriez appliquer directement. Si vous recherchez sur «Compter des points entier dans Polyope» ou «Compter les points de réseau dans Polytope», vous trouverez de nombreux papiers de recherche. Voir, par exemple, https://cstheory.stackexchange.com/q/22280/5038 , Finding toutes les solutions à un problème de programmation linéaire entier (ILP) .

approche # 2 : convertir en CNF, puis utilisez un solveur #sat.

Vous pouvez toujours convertir vos contraintes en formule CNF. Chaque inégalité linéaire peut être convertie en un ensemble de clauses CNF. Une inégalité linéaire de la forme $ x_i + \ dots + x_j \ ge 1 $ correspond immédiatement à la clause CNF $ (x_i \ lor \ dots \ lor x_j) $ . Pour une inégalité linéaire plus générale de la forme $ x_i + \ dots + x_j \ ge c $ , vous souhaitez exprimer la contrainte au moins $ C $ hors de la $ k $ variables $ x_i, \ dots, x_j $ sont vraies. Il existe de nombreuses façons standard de coder cela. Voir https://cstheory.stackexchange.com/q/23771/5038 , Reduivez le problème suivant à SAT , coding 1 -out -out-de-n contrainte pour les solveurs SAT ,

(une approche consiste à convertir un circuit booléen qui calcule $ x_i + \ dots + x_j $ et la compare à $ C $ , puis convertissez le circuit booléen en CNF à l'aide du TSEITTIN Transform . Vous pouvez créer un tel circuit booléen en utilisant des circuits standard additionneur et comparateur. Cependant, il existe également de nombreuses autres manières.)

Une fois que vous avez une formule CNF équivalente à l'ensemble des contraintes, vous pouvez utiliser n'importe quel solveur #SAT sur étagère pour compter le nombre de solutions à cette formule CNF.

---

Il est difficile de dire laquelle de ces deux approches fonctionnera mieux; Vous devrez peut-être les essayer à la fois sur les types d'instances que vous avez affaire à ce que vous traitez, de savoir à coup sûr. J'attendrais que si vous avez des inégalités linéaires de la forme $ x_i + \ dots + x_j \ ge c $ où $ C $ est grand, puis l'approche n ° 1 peut être supérieure; mais si $ C $ est généralement petit, puis l'approche n ° 2 peut être supérieure.

Answer 2

Vous pouvez mettre en œuvre DPLL en utilisant directement à l'aide des contraintes au lieu des clauses.Cela nécessite de modifier la structure de données et de l'algorithme de propagation, mais cela fonctionne tout de même.

Dès que toutes les variables de la contrainte sont définies à l'exception d'une, la propagation de l'unité peut se produire.

Dès que toutes les variables de la contrainte sont définies, un conflit peut se produire.

Le reste de l'algorithme reste le même.

Une contrainte sur les variables booléennes est juste une collection de clauses CNF cachées (potentiellement de nombreuses clauses de manière exponentielle en fonction de la contrainte).

Answer 3

La question a été répondit sur ou.stackexchange pour logiciel de programmation mixte-integer, avec des exemples de logiciels et de scripts existants (CPLEX, SCIP, ...).

Ceci est plus similaire à l'algorithme CDCL que de DPLL: Lorsqu'une nouvelle solution est trouvée, une nouvelle contrainte est ajoutée pour l'interdire et la recherche reprend jusqu'à ce que le problème devienne infaisable.