License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.7
URN: urn:nbn:de:0030-drops-152982
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15298/
Go to the corresponding LIPIcs Volume Portal


Kheireddine, Anissa ; Renault, Etienne ; Baarir, Souheib

Towards Better Heuristics for Solving Bounded Model Checking Problems (Short Paper)

pdf-format:
LIPIcs-CP-2021-7.pdf (0.8 MB)


Abstract

This paper presents a new way to improve the performance of the SAT-based bounded model checking problem by exploiting relevant information identified through the characteristics of the original problem. This led us to design a new way of building interesting heuristics based on the structure of the underlying problem. The proposed methodology is generic and can be applied for any SAT problem. This paper compares the state-of-the-art approach with two new heuristics: Structure-based and Linear Programming heuristics and show promising results.

BibTeX - Entry

@InProceedings{kheireddine_et_al:LIPIcs.CP.2021.7,
  author =	{Kheireddine, Anissa and Renault, Etienne and Baarir, Souheib},
  title =	{{Towards Better Heuristics for Solving Bounded Model Checking Problems}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{7:1--7:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15298},
  URN =		{urn:nbn:de:0030-drops-152982},
  doi =		{10.4230/LIPIcs.CP.2021.7},
  annote =	{Keywords: Bounded model checking, SAT, Structural information, Linear Programming}
}

Keywords: Bounded model checking, SAT, Structural information, Linear Programming
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021
Supplementary Material: Software (Source Code): https://gitlab.lrde.epita.fr/akheireddine/bmctool archived at: https://archive.softwareheritage.org/swh:1:dir:ef063522105b17855a9f7d76382848f5e7f2a150


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI