Est-il possible de résoudre ce problème de couverture de sous-ensemble avec le solveur SAT?

Question

Le problème est de trouver $ \ mathcal {s} $ , une collecte minimale de sous-ensembles de $ \ {1 , \ points, 17 \} $ de telle sorte que les deux conditions sont satisfaites:

1. si $ s \ sous -éréeq \ mathcal {s} $ alors $ | s |= 6 $ ;
2. pour tout $ a \ sous -éréq \ {1, \ points, 17 \ \ dots \ avec $ | a |= 3 $ , il existe une $ s \ in \ mathcal {s} $ avec $ A \ sous-ensemble s $ .

voir ici pour un problème combinatoire associé.

Je pense que cela peut être formulé comme un problème de sat min.

pour chaque $ s \ sous -éréq \ {1, \ points, 17 \} $ avec $ | S |= 6 $ , nous introduisons une variable $ x_s $ . Et pour chaque $ a \ sous -éréq \ {1, \ points, 17 \ \ dotes \ avec $ |= 3 $ , nous introduisons une clause $$ \ vee_ {s: A \ Subreteq S, | S |= 6} x_ {s} $$ Ensuite, en principe, nous pouvons utiliser un solveur SAT pour trouver le nombre minimal de $ x_s $ qui doit être vrai pour satisfaire toutes les clauses.

Ceci nécessite $ \ binom {17} {6}= 12376 $ variables, $ \ binom {17} { 3}= 680 $ clauses de longueur $ \ binom {17-3} {3}= 364 $

.
.

J'ai très peu d'expérience en réellement en utilisant des solveurs SAT. Cela vaut donc la peine d'essayer d'essayer sur mon ordinateur portable ou qu'il n'y a pas d'espoir du tout?

---

mise à jour

Éteindre Il y a beaucoup de recherches sur le couvercle de la définition. Il semble que j'étais trop ambitieux pour essayer de résoudre le problème des paramètres (17, 6, 3).

C'est déjà un problème ouvert pour (12, 5, 3).

voir ici pour plus de détails.

---

mise à jour 2

essayé d'écrire tout en pur satellite et c'est un peu plus rapide à l'aide de CADICAL que Z3.

En outre, il est nettement plus rapide de trouver une solution que de montrer aucune solution existent.

J'ai essayé de casser la symétrie en ajoutant les contraintes que le premier et le dernier sous-ensemble dans l'ordre du lexique doit être sélectionné.

Answer 1

L'optimisation avec SAT est généralement appelée maxat au lieu de MIN SAT.En particulier, je suggère de chercher des solveurs pour "maxat partiel pondéré", par exemple MAXHS et RC2.

La taille du problème que vous avez est relativement petite dans le contexte des solveurs MAXSAT modernes, donc oui, cela vaut la peine d'essayer.Il n'existe aucune garantie que le solutionneur fonctionnera efficacement et il est très difficile de prédire si cela fonctionnera efficacement, de sorte que la meilleure chose à faire est d'essayer.

Answer 2

Avec SAT, il peut être difficile de prédire ce qui sera réalisable et ce qui ne sera pas. Ça vaut la peine d'essayer.

Je suggérerais que, au lieu de Minsat, vous essayez d'abord d'utiliser une recherche binaire sur $ n= | \ mathcal {s} | $ , le nombre de sets que vous avez besoin. Vous pouvez utiliser une contrainte sur votre $ X_S $ Variables. Il y a plusieurs Techniques pour codant sur celui en samedi, bien que dans la pratique, je vais d'abord essayer d'utiliser Pble avec le solveur Z3.

Votre problème a beaucoup de symétrie. Les solveurs SAT peuvent parfois avoir des difficultés avec la symétrie. Vous pourriez essayer de faire autant que vous pouvez pour casser la symétrie. Par exemple, sans perte de généralité, nous pouvons supposer que $ \ {1,2,3,4,5,6 \} $ est l'un des ensembles (autrement permit Tous les chiffres, donc c'est), afin que vous puissiez calculer ce fait à votre instance SAT. Plus ces lemmas vous pouvez prouver, mieux le solveur SAT pourrait fonctionner.

Vous pouvez également encoder les ensembles différemment. Laissez $ s_i $ désigne la $ i $ th ensemble choisis par $ \ mathcal {s} $ . Introduire Variable $ X_ {I, J} $ Pour indiquer que $ J \ in S_I $ ET VARIABLES < span class="math-conteneur"> $ y_ {i, a} $ pour indiquer que le $ a \ sous-ensemble s_i $ , pour chaque $ a \ sous -éréeq \ {1, \ points, 17 \ \ dots \ avec $ |= 3 $ et chaque $ i \ \ \ \ \ \ \ \ \ \ \ dots, n \} $ et chaque $ j \ \ \ {1, \ points, 17 \} $ . Ajoutez une clause $ \ bigvee_i y_ {i, a} $ pour chaque $ a $ pour assurer que chacun $ a $ est couvert par au moins un ensemble. Ajoutez une contrainte de 6 sorti de 17 pour chaque $ i $ pour indiquer exactement 6 de la $ x_ {i , j} $ est vrai. Enfin, ajoutez des contraintes à appliquer la cohérence entre la $ X $ 'S et $ Y $ En particulier, pour chaque $ a={a_1, a_2, a_3 \} $ , ajoutez des clauses $ \ ng x_ { i, a_1} \ lor \ neion x_ {i, a_2} \ lor \ negn x_ {i, a_3} \ lor y_ {i, a} $ et $ \ Neg y_ {i, a} \ lor x_ {i, a_1} $ et $ \ neg y_ {i, a} \ lor x_ {i, a_2} $ < / span> et $ \ neg y_ {i, a} \ lor x_ {i, a_3} $ . Cela nécessitera environ $ (17 + 680) N $ variables et $ 4 \ CDOT 680 N $ clauses ( ne pas compter la N $ N $ 6-SUR 17 Contraintes); Puisque je m'attends à $ n \ environ 35 $ , il s'agit d'environ 24k variables et de clauses de 100k. C'est plus de clauses que votre codage, et il a encore plus de symétrie, cela pourrait effrair pire - bien qu'ils soient des clauses plus courtes, et il est difficile de prédire quels codings travailleront le mieux avec SAT, si souvent certaines expérimentations sont nécessaires.

Vous pouvez également essayer d'exprimer cela comme une instance ILP au lieu de SAT.