logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro