Contando el número de satisfechos los modelos - dado matemática restricciones

Question

Pregunta

Hay un montón de algoritmos para la solución de la #SAT problema, siendo uno el algoritmo DPLL y se aplica para todos los tipos de lenguajes de programación.Como he visto, todos ellos tienen una fórmula booleana en CNF como entrada y las salidas el número de satisfechos interpretaciones.

Matemática restricciones, por otro lado, es otra forma de definir una instancia de SAT-problema y se utiliza a menudo en discretos de optimización, donde uno trata de optimizar alguna función con respecto a estas restricciones. Hay un programa que tiene en matemática restricciones de entrada y salidas el número de satisfechos interpretaciones?

Ejemplo

Nosotros representamos a la fórmula booleana $P = (a \lor b) \wedge (c \lor d)$ como limitaciones como $$a + b \geq 1 \\ c + d \geq 1$$ o como una matriz $A$ y de soporte vectorial $b$ $$ A= \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix} \\ b = \begin{bmatrix} 1 & 1 \end{bmatrix} $$

donde todas las variables $a,b,c,d \in \{0,1\}$.Sabemos que hay programas de toma $Q$ como entrada y las salidas el número de interpretaciones, pero hay programas que toman $A$ y $b$ como entrada (o de construcción similares) y las salidas el mismo número de interpretaciones?

Answer 1

Sé de dos enfoques razonables.

Enfoque # 1 : cuenta el número de puntos enteros dentro de un politopo convexo.

El conjunto de desigualdades lineales que proporcionó, junto con las desigualdades $ 0 \ le a, b, c, d \ le 1 $ , define un politopo convexo. Ahora, usted quiere Cuente el número de puntos enteros que se encuentran dentro de este poliTope .

Hay algoritmos estándar para hacerlo, lo que podría aplicar directamente. Si busca "Contando puntos enteros en politopo" o "Contando puntos de celosía en politopo", encontrará muchos trabajos de investigación. Ver, por ejemplo, https://cstheory.stackexchange.com/q/22280/5038 , Pasando todas las soluciones a un problema de programación lineal de enteros (ILP) .

Enfoque # 2 : convertir a CNF, luego use un Solver #SAT.

Siempre puede convertir sus restricciones a una fórmula CNF. Cada desigualdad lineal se puede convertir a un conjunto de cláusulas CNF. Una desigualdad lineal de la forma $ x_i + \ dots + x_j \ ge 1 $ corresponde inmediatamente a la cláusula CNF $ (x_i \ lor \ dots \ lor x_j) $ . Para una desigualdad lineal más general de la forma $ x_i + \ dots + x_j \ ge c $ , desea expresar la restricción que al menos $ C $ fuera del $ k $ variables $ x_i, \ dots, x_j $ son verdaderos. Hay muchas formas estándar de codificar que. Consulte https://cstheory.stackexchange.com/q/23771/5038 , , codificación 1 -OUT-OF-N Restricción para solucionadores SAT ,

(un enfoque es convertir un circuito booleano que calcule $ x_i + \ dots + x_j $ y lo compara con $ C $ , luego convierte el circuito booleano a CNF usando el Transformación de Tseitin . Puede crear un circuito tan booleano utilizando los circuitos estándar y los circuitos de comparación. Sin embargo, también hay muchas otras formas.)

Una vez que tenga una fórmula de CNF que sea equivalente al conjunto de restricciones, puede usar cualquier solvente SIFT #sat para contar el número de soluciones a esa fórmula CNF.

---

Es difícil decir cuál de estos dos enfoques funcionará mejor; Es posible que deba probarlos tanto en los tipos de instancias con las que está tratando, para saberlo con seguridad. Espero que si tiene desigualdades lineales de la forma $ x_i + \ dots + x_j \ ge c $ donde $ C $ es grande, entonces el enfoque # 1 puede ser superior; Pero si $ c $ es típicamente pequeño, entonces el enfoque # 2 puede ser superior.

Answer 2

Puede implementar DPLL usando directamente utilizando las restricciones en lugar de cláusulas.Esto requiere modificar la estructura de datos y el algoritmo de propagación, pero funciona de todos modos.

Tan pronto como todas las variables de la restricción se establecen excepto una, puede ocurrir la propagación de la unidad.

Tan pronto como se establecen todas las variables de la restricción, puede ocurrir un conflicto.

El resto del algoritmo sigue siendo el mismo.

Una restricción sobre las variables booleanas es solo una colección de cláusulas CNF ocultas (potencialmente exponencialmente muchas cláusulas dependiendo de la restricción).

Answer 3

La pregunta ha sido respondido en o.stackexchange para software de programación de enteros mixtos, con ejemplos de software y scripts existentes (CPLEX, SCIP, ...).

Esto es más similar al algoritmo de CDCL que a DPLL: cuando se encuentra una nueva solución, se agrega una nueva restricción para prohibirla y la búsqueda se reanuda, hasta que el problema se vuelva a ser inviable.