Ist es möglich, dieses Subset-Abdeckungsproblem mit SAT-Solver zu lösen?

Question

Das Problem ist, $ \ Mathcal {S} $ , eine minimale Sammlung von Teilmengen von $ \ {1 , \ dots, 17 \} $ so, dass die beiden Bedingungen erfüllt sind:

.
1. Wenn $ s \ subseticq \ matcal {s} $ dann $ | S |= 6 $ ;
2. für jeden $ a \ subseteq \ {1, \ dots, 17 \} $ mit $ | a |= 3 $ , gibt es einen $ s \ in \ matcal {s} $ mit $ a \ Subset s $ .

siehe hier für ein verwandtes kombinatorisches Problem ..

Ich denke, das kann als MIN-SAT-Problem formuliert werden.

für jeden $ s \ subseteq \ {1, \ dots, 17 \} $ mit $ | s |= 6 $ , Wir führen eine Variable $ x_s $ ein. Und für jeden $ A \ Subseteq \ {1, \ dots, 17 \} $ mit $ | A |= 3 $ , führen wir eine Klausel ein $$ \ Vee_ {S: A \ Subseteq S, | S |= 6} x_ {S} $$ Dann können wir im Principal einen Sat-Solver verwenden, um die minimale Anzahl der $ XS $ zu finden, die treu ist, um alle Klauseln zu erfüllen.

Dies erfordert $ \ Binom {17} {6}= 12376 $ Variablen, $ \ Binom {17} { 3}= 680 $ Klauseln der Länge $ \ Binom {17-3} {3}= 364 $ .

Ich habe sehr wenig Erfahrung in der tatsächlichen Verwendung von Sat-Löser. So lohnt sich das wirklich, meinen Laptop zu versuchen, oder es gibt überhaupt keine Hoffnung?

---

update

sich herausstellen Es gibt viele Erforschung der Set-Abdeckung. Es scheint, dass ich über ehrgeizig war, um das Problem für die Parameter (17, 6, 3) zu lösen.

Es ist bereits ein offenes Problem für (12, 5, 3).

siehe hier für weitere Details.

---

update 2

versuchte, alles in reine Sat zu schreiben, und es ist ein bisschen schneller mit Cadical als Z3.

Es ist auch wesentlich schneller, eine Lösung zu finden, als keine Lösungen zu zeigen.

Ich habe versucht, die Symmetrie durchzuführen, indem Sie die Einschränkungen hinzufügen, dass die erste und die letzte Teilmenge in Lexikonauftrag ausgewählt werden müssen.

Answer 1

Die Optimierung mit SAT wird in der Regel als MAXSAT anstelle von min Sat bezeichnet.Insbesondere schlage ich vor, nach Löser für "gewichtete partielle MAXSAT", beispielsweise MAXHS und RC2, aufzutragen.

Die Problemgröße, die Sie haben, ist in einem Zusammenhang mit modernen MAXSAT-LÖSHERS ziemlich klein, so dass es sich lohnt, es zu versuchen.Es gibt keine Garantien, dass der Solver effizient funktioniert, und es ist sehr schwer vorherzusagen, wenn es effizient funktioniert, so dass das Beste, was Sie tun sollten, um es zu versuchen.

Answer 2

Mit SAT, kann es schwierig sein, vorherzusagen, was realisierbar ist und was nicht ist. Es ist ein Versuch wert.

Ich würde vorschlagen, dass Sie anstelle von Minsat zum ersten Mal mit binärer Suche auf $ n= | \ mathcal {s} | $ , die Anzahl der Sätze brauchen. Sie können einen Mire-No-SPAN-Klasse="Math-Container"> $ N $ -out-of-12376-Einschränkungen auf Ihrem $ x_s $ Variablen. Es gibt mehrere Techniken für codiert, die in SAT, obwohl in der Praxis ich zuerst versuchen würde, Plble mit dem Z3-Solver.

Ihr Problem hat viel Symmetrie. Sat-Löser können manchmal Schwierigkeiten mit der Symmetrie haben. Sie könnten versuchen, so viel zu tun, wie Sie können, um die Symmetrie zu brechen. Zum Beispiel können wir ohne Verlust der Allgemeinheit davon ausgehen, dass $ \ {1,2,3,4,5,6} $ eines der Sets ist (andernfalls permutieren Alle Zahlen, also ist es), so dass Sie diese Tatsache in Ihrer SAT-Instanz harten können. Je mehr Lemmas Sie beweisen können, desto besser kann der Sat-Solver funktionieren.

Sie können die Sätze auch anders codieren. Lassen Sie $ s_i $ den $ i $ th-Set bezeichnen, der von $ \ mathcal {s} $ . Variabless $ X_ {i, j} $ einführen, um anzuzeigen, dass $ J \ in S_I $ und Variablen < Span-Klasse="Math-Container"> $ y_ {i, a} $ , um anzuzeigen, dass der $ a \ Subset S_I $ für jede $ A \ Subseteq \ {1, \ Dots, 17 \} $ mit $ | A |= 3 $ und Jeder $ i \ in \ {1, \ dots, n \} $ und jeder $ j \ in \ {1, \ dots, 17 \} $ . Hinzufügen einer Klausel $ \ BigVee_I y_ {i, a} $ für jeden $ A $ , um das jeweils sicherzustellen $ A $ ist von mindestens einem Satz abgedeckt. Fügen Sie für jeden $ i $ hinzu, um genau 6 der $ X_ {i , j} $ ist wahr. Fügen Sie schließlich Beschränkungen hinzu, um die Konsistenz zwischen dem $ x $ "s und $ y $ s Insbesondere für jeden $ A={A_1, A_2, A_3 \} $ , Hinzufügen von Klauseln $ \ neg x_ { i, a_1} \ lor \ neg x_ {i, a_2} \ lor \ neg x_ {i, a_3} \ lor y_ {i, a} $ und $ \ neg y_ {i, a} \ lor x_ {i, a_1} $ und $ \ neg y_ {i, a} \ lor x_ {i, a_2} $ < / span> und $ \ neg y_ {i, a} \ lor x_ {i, a_3} $ . Dies erfordert über $ (17 + 680) N $ Variablen und $ 4 \ CDOT 680 N $ Clauses ( nicht zählen der $ n $ 6-out-of-17-Einschränkungen); Da ich erwarte, $ n \ ca. 35 $ , dauert es etwa 24-k-Variablen und 100k-Klauseln. Das ist mehr Klauseln als Ihre Kodierung, und es hat noch mehr Symmetrie, daher könnte es noch schlimmer werden - obwohl sie kürzere Klauseln sind, und es ist schwer vorherzusagen, welche Kodierungen am besten mit Sat arbeiten werden, so oft ein paar Experimente erforderlich ist. .

Sie könnten auch versuchen, dies als ILP-Instanz anstelle von SAT auszudrücken.