Symmetry Breaking para Z3: en el contexto de la lógica de UFBV (nueva versión)

Question

(Este es mi segundo intento de obtener ayuda. Si la pregunta/enfoque no tiene sentido o no es claro, hágamelo saber. También me complacería cualquier pequeña pista o referencia, lo que puede ayudarme a comprender el comportamiento de Z3 con mis SBA)

Estoy trabajando en la verificación limitada de la especificación relacional utilizando la lógica UFBV Z3. El problema actual que estoy investigando necesita la falsificación de todos los modelos posibles (debido a un uso negativo de un predicado de accesibilidad), que mata el rendimiento del solucionador en los límites superiores.

Debido a que solo una parte de los posibles modelos es realmente interesante (no isomórficos para los demás), estoy tratando de introducir técnicas de ruptura de simetría (conocidas en el área de SAT).

Sin embargo, el uso de lo que llamo axiomas de ruptura de simetría puede mejorar el rendimiento de Z3 en algunos casos, pero el comportamiento general del solucionador se vuelve inestable.

Uno de mis enfoques (creo que el más prometedor) se basa en romper la simetría en las relaciones con sus dominios. Introduce de cada dominio d de una relación r y cada átomo a en d axioms, que imponen un orden en la representación binaria de r^{m} y r^{m [a+1/a]}, donde m es un modelo para la especificación. Para las relaciones homogéneas, los axiomas están relajados.

Sea r subset axa una relación. Mis axiomas de ruptura de simetría relajada para R se ven así:

;; SBA(R, A)_upToDiag
(assert
 (forall ( (ai A) (aj A) )
  (=>
   (bvult ai aj)
   (=>
    (forall ((x A))
     (=>
       (bvult x aj)
       (= (R ai x) (R (bvadd ai (_ bv1 n)) x)) 
     )
    )
    (=>
     (R ai aj)
     (R (bvadd  ai  (_ bv1 n)) aj)
)))))    

;; SBA(R, A)_diag
(assert
 (forall ( (ai A) )
  (=>
   (forall ((x A))
    (=>
      (bvult x ai)
      (= (R ai x) (R (bvadd ai (_ bv1 n)) x)) 
    )
   )
   (=>
    (R ai ai)
    (R (bvadd  ai  (_ bv1 n)) (bvadd  ai  (_ bv1 n)))
)))) 

Mi problema es que el efecto de usar este SBAS no es estable/consistente. Difiere de un límite a la especificación de forma y forma a otra. También el uso de todos o solo uno de los SBA afecta el rendimiento.

En el contexto SAT, el éxito del llamado bases de aproximación de predicadas de ruptura de simetría (SBP) en la capacidad de retroceso del solucionador SAT, que (de alguna manera) garantía, que si el solucionador atrasó la pista, luego hará el espacio de búsqueda utilizando, Entre otros, los SBP.

• ¿Cuáles son las diferencias (si las hay) en el contexto de Z3?
• ¿Cómo puedo hacer cumplir la resolución para usar estos axiomas para podar el espacio de búsqueda (cuando se retrocede)?
• ¿Ayuda el uso de patrones (cuantificador) para mis SBA?

Saludos,

Aboubakr Achraf el Ghazi

Answer 1

En Z3 3.2, hay dos motores principales para manejar fórmulas cuantificadas: E-Matching y MBQI (instanciación de cuantificador basado en el modelo). La maticación electrónica solo es efectiva en fórmulas insatisfactorias. Z3 no podrá demostrar que una fórmula es satisfactoria usando este motor. MBQI es más caro, pero puede mostrar que varias clases de fórmulas (que contienen cuantificadores) son satisfactorias. los Guía Z3 describe estos dos motores (y otras opciones). Para usar Z3 de manera efectiva en problemas no triviales, es muy útil comprender cómo funcionan estos dos motores.

La ruptura de la simetría suele ser una forma muy efectiva de reducir el espacio de búsqueda. Es difícil identificar exactamente lo que está sucediendo en su problema. Puedo ver las siguientes explicaciones para el comportamiento no estable:

• MBQI está teniendo dificultades para crear un modelo que satisfaga los SBA. Aunque los SBA podan el espacio de búsqueda, si el problema es satisfactorio, Z3 intentará construir una interpretación (modelo) que los satisfaga. Entonces, en este caso, la SBA está justo por encima. Esto es particularmente cierto, si la fórmula de entrada es muy fácil de satisfacer, pero se vuelve difícil cuando agrega los SBA. Puede confirmar esta hipótesis utilizando la opción MBQI_TRACE=true. Z3 mostrará mensajes como: [mbqi] failed k!18. Dónde k![line-number] es la identificación del cuantificador. Puede asignar sus propias identificaciones usando la etiqueta :qid. Aquí hay un ejemplo:

  (afirmar (forall (((x t) (y t)) (! (=> (y (subtipo xy) (subtipo yx)) (= xy)): antisimetría qid))))

Por cierto, puede deshabilitar el módulo MBQI usando MBQI=false.

En futuras versiones de Z3, estamos planeando agregar una opción para deshabilitar MBQI para algunas fórmulas cuantificadas. Esta característica puede ser útil para los SBA.

• Otra explicación es que la maticación electrónica está creando demasiadas instancias de los SBA. Puede confirmar que usando la opción QI_PROFILE=true. Z3 descargará información como:

cuantificador_instances] antisimetría: 12: 1: 2.00

El primer número es el número de instancias generadas. Si esa es la fuente del problema, una solución es asignar patrones restrictivos para los SBA que están generando demasiadas instancias. Por ejemplo, Z3 usará (R ai aj) Como patrón para SBA(R, A)_upToDiag. Este tipo de patrón puede crear un número cuadrático de instancias. Otro experimento consiste en deshabilitar la maticación electrónica. Ejemplo, la opción

AUTO_CONFIG=false EMATCHING=false MBQI=true

También puede intentar deshabilitar la propagación de relevancia en la configuración anterior, opción: RELEVANCY=0.

Finalmente, otra opción es generar las instancias de los SBA que cree que son útiles y eliminar las fórmulas cuantificadas.