¿Es factible resolver este problema de cobertura de subconjunto con SAT SOLVER?

Question

El problema es encontrar $ \ mathcal {s} $ , una recolección mínima de subconjuntos de $ \ {1 , \ puntos, 17 \} $ de modo que las dos condiciones están satisfechas:

1. si $ s \ subesteq \ mathcal {s} $ luego $ |= 6 $ ;
2. para cualquier $ a \ subesteq \ {1, \ dots, 17 \} $ con $ | a |= 3 $ , existe un $ s \ in \ mathcal {s} $ con $ a \ subset s $ .

ver aquí para un problema combinatorio relacionado.

Creo que esto se puede formular como un problema de SAT MIN.

para cada $ s \ subesteq \ {1, \ dots, 17 \} $ con $ | s |= 6 $ , introducimos una variable $ x_s $ . Y para cada $ A \ subesteq \ {1, \ dots, 17 \ \ \ \ \ span> con $ | a |= 3 $ , introducimos una cláusula $$ \ vee_ {s: a \ subesteceq s, | s |= 6} x_ {s} $$ Luego, en el principio, podemos usar un SAT Solver para encontrar el número mínimo de $ x_s $ que debe ser fiel para satisfacer todas las cláusulas.

Esto necesita $ \ binom {17} {6}= 12376 $ variables, $ \ binom {17} { 3}= 680 $ cláusulas de longitud $ \ binom {17-3} {3}= 364 $ .

Tengo muy poca experiencia en el uso de solucionadores SAT. Entonces, ¿vale la pena intentarlo en mi computadora portátil o no hay esperanza en absoluto?

---

Actualización

Resulta que hay muchas investigaciones en la cubierta establecida. Parece que estaba demasiado ambicioso para tratar de resolver el problema para los parámetros (17, 6, 3).

Ya es un problema abierto para (12, 5, 3).

Consulte aquí para más detalles.

---

Actualización 2

Intenté escribir todo en puro SAT y es bastante más rápido usando cadical que Z3.

Además, es significativamente más rápido encontrar una solución que mostrar que no existan soluciones.

Intenté romper la simetría agregando las restricciones que se debe seleccionar el primer y el último subconjunto en orden de léxico.

Answer 1

La optimización con SAT generalmente se refiere como MaxSat en lugar de Min SAT.En particular, sugiero buscar solucionadores para "ponderados parciales maxsat", por ejemplo, maxhs y rc2.

El tamaño del problema que tiene es bastante pequeño en el contexto de los solversadores modernos de MaxSat, por lo que sí vale la pena intentarlo.No hay garantías de que el solver funcione de manera eficiente, y es muy difícil predecir si funcionará de manera eficiente, por lo que lo mejor que debe hacer es probar.

Answer 2

Con SAT, puede ser un desafío predecir lo que será factible y qué no. Vale la pena intentarlo.

Le sugeriría que, en lugar de MINSAT, primero intenta usar la búsqueda binaria en $ n= | \ mathcal {s} | $ , el número de le establece necesitar. Puede usar una restricción de $ n $ $ n $ -out-of-12376 en su $ x_s $ Variables. Hay varios Técnicas para codificando que en SAT, aunque en la práctica primero intentaría usar pble con el solver Z3.

Tu problema tiene mucha simetría. Los solucionadores SAT a veces pueden tener dificultades con la simetría. Puede intentar hacer todo lo que pueda para romper la simetría. Por ejemplo, sin pérdida de generalidad podemos asumir que $ \ {1,23,4,5,6 \} $ es uno de los conjuntos (de lo contrario permuta Todos los números, por lo que es), por lo que puede cedir este hecho en su caso SAT. Cuantos más lemmas puedan probar, mejor podría realizar el solucionador SAT.

También podría codificar los conjuntos de manera diferente. Deje que $ s_i $ denota el $ i $ conjunto que se elige por $ \ mathcal {s} $ . Introduzca variables $ x_ {i, j} $ para indicar que $ j \ in s_i $ y variables < span class="math-contenedor"> $ y_ {i, a} $ para indicar que el $ a \ subset s_i $ , para cada $ A \ subesteq \ {1, \ puntos, 17 \ \} $ con $ | a |= 3 $ y Cada $ i \ in \ {1, \ dots, n \ \ \ \ span> y cada $ j \ in \ {1, \ Dots, 17 \} $ . Agregar una cláusula $ \ bigvee_i y_ {i, a} $ para cada $ a $ para asegurar que cada uno $ A $ está cubierto por al menos un conjunto. Agregue una restricción de 6-OUT-17 para cada $ i $ para indicar que exactamente 6 de la $ x_ {i , J} $ 's es cierto. Finalmente, agregue restricciones para hacer cumplir la consistencia entre el $ x $ 's y $ y $ ' s. En particular, para cada $ a={A_1, A_2, A_3 \} $ , agregue cláusulas $ \ neg x_ { i, a_1} \ lor \ neg x_ {i, a_2} \ lor \ neg x_ {i, a_3} \ lor y_ {i, a} $ y $ \ neg y_ {i, a} \ lor x_ {i, A_1} $ y $ \ net y_ {i, a} \ lor x_ {i, a_2} $ < / span> y $ \ net y_ {i, a} \ lor x_ {i, a_3} $ . Esto requerirá aproximadamente $ (17 + 680) n $ variables y $ 4 \ CDOT 680 N $ cláusulas ( sin contar el $ n $ 6-OUT-17 restricciones); Dado que espero $ n \ aprox. 35 $ , esto es aproximadamente 24k variables y cláusulas de 100k. Son más cláusulas que su codificación, y tiene aún más simetría, por lo que podría funcionar peor, aunque son cláusulas más cortas, y es difícil predecir qué codificaciones funcionarán mejor con SAT, a menudo se necesita alguna experimentación.

También podría intentar expresar esto como una instancia de ILP en lugar de SAT.