Mejorando el rendimiento de los solucionadores SAT basados en CDCL mediante la explotación de espinas dorsales y puertas traseras
Autores: Al-Yahya, Tasniem; Menai, Mohamed El Bachir Abdelkrim; Mathkour, Hassan
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Mejorando el rendimiento de los solucionadores SAT basados en CDCL mediante la explotación de espinas dorsales y puertas traseras
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Boolean
Medidas estructurales
Cdcl
Solucionadores sat
Espinas dorsales
Puertas traseras
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Se introdujeron medidas estructurales booleanas para explicar el alto rendimiento de los solucionadores SAT basados en aprendizaje de cláusulas impulsado por conflictos (CDCL) en instancias SAT industriales. Aquellas consideradas en este estudio incluyen medidas relacionadas con espinas dorsales y puertas traseras: tamaño de la espina dorsal, frecuencia de la espina dorsal y tamaño de la puerta trasera. Un área clave de investigación es mejorar el rendimiento de los solucionadores SAT CDCL mediante la explotación de estas medidas. Con el propósito de guiar al solucionador SAT CDCL para ramificar en variables de espina dorsal y puerta trasera, este estudio propone heurísticas de bajo costo para calcular estas variables. A través de estas heurísticas, se sugiere un conjunto de modificaciones al heurístico de decisión Variable State Independent Decaying Sum (VSIDS) para explotar espinas dorsales y puertas traseras y potencialmente mejorar el rendimiento de los solucionadores SAT CDCL. En total, se desarrollaron quince variantes de dos solucionadores base competitivos, MapleLCMDistChronoBT-DL-v3 y LSTech. Se realizó una evaluación empírica en 32 familias industriales de competencias SAT de 2002 a 2021. Según los resultados, modificar el heurístico VSIDS en los solucionadores base para explotar espinas dorsales y puertas traseras mejora su rendimiento. En particular, nuestro nuevo solucionador SAT CDCL, LSTech_BBsfcr_v1, resolvió más instancias SAT industriales que los solucionadores SAT CDCL ganadores en las competencias SAT de 2020 y 2021.
Descripción
Se introdujeron medidas estructurales booleanas para explicar el alto rendimiento de los solucionadores SAT basados en aprendizaje de cláusulas impulsado por conflictos (CDCL) en instancias SAT industriales. Aquellas consideradas en este estudio incluyen medidas relacionadas con espinas dorsales y puertas traseras: tamaño de la espina dorsal, frecuencia de la espina dorsal y tamaño de la puerta trasera. Un área clave de investigación es mejorar el rendimiento de los solucionadores SAT CDCL mediante la explotación de estas medidas. Con el propósito de guiar al solucionador SAT CDCL para ramificar en variables de espina dorsal y puerta trasera, este estudio propone heurísticas de bajo costo para calcular estas variables. A través de estas heurísticas, se sugiere un conjunto de modificaciones al heurístico de decisión Variable State Independent Decaying Sum (VSIDS) para explotar espinas dorsales y puertas traseras y potencialmente mejorar el rendimiento de los solucionadores SAT CDCL. En total, se desarrollaron quince variantes de dos solucionadores base competitivos, MapleLCMDistChronoBT-DL-v3 y LSTech. Se realizó una evaluación empírica en 32 familias industriales de competencias SAT de 2002 a 2021. Según los resultados, modificar el heurístico VSIDS en los solucionadores base para explotar espinas dorsales y puertas traseras mejora su rendimiento. En particular, nuestro nuevo solucionador SAT CDCL, LSTech_BBsfcr_v1, resolvió más instancias SAT industriales que los solucionadores SAT CDCL ganadores en las competencias SAT de 2020 y 2021.