Ist es möglich, dieses Subset-Abdeckungsproblem mit SAT-Solver zu lösen?
-
28-09-2020 - |
Frage
Das Problem ist, $ \ Mathcal {S} $ , eine minimale Sammlung von Teilmengen von $ \ {1 , \ dots, 17 \} $ so, dass die beiden Bedingungen erfüllt sind:
- .
- Wenn $ s \ subseticq \ matcal {s} $ dann $ | S |= 6 $ ;
- 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
Dies erfordert $ \ Binom {17} {6}= 12376 $ Variablen, $ \ Binom {17} { 3}= 680 $ Klauseln der Länge
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
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.
Lösung
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.
Andere Tipps
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
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
Sie können die Sätze auch anders codieren. Lassen Sie $ s_i $ den
Sie könnten auch versuchen, dies als ILP-Instanz anstelle von SAT auszudrücken.