A machine learning approach to model counting

Simple item page
dc.contributor.authorDalla, Marcoen
dc.contributor.authorVisentin, Andreaen
dc.contributor.authorO'Sullivan, Barryen
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2025-01-22T14:41:52Z
dc.date.available2025-01-22T14:41:52Z
dc.date.issued2024en
dc.description.abstractModel counting (#SAT) is the problem of computing the number of satisfying assignments for a given Boolean formula. It has a significant theoretical and practical interest. Tackling it can be challenging since the number of potential solution grows exponentially with the number of variables. Due to the inherent complexity of the problem, approaches to approximate model counting have been developed as a practical alternative. These methods extract the number of solutions within user-specified tolerance and confidence levels and in a fraction of the time required by exact model counters. However, even these methods require extensive computations, restricting their applicability to relatively small instances. In this paper, we propose a new approximate machine learning model counter that overcome this limitation. Predicting the number of solutions can be seen as a regression problem. We deploy an array of machine learning techniques trained to infer the approximate number of solutions based on statistical features extracted from a SAT propositional formula. Extensive numerical experiments performed on synthetic crafted and benchmark datasets show that learning approaches can provide a good approximation of the number of solutions with a much lower computational time and resource cost than the state-of-the-art approximate and exact model counters. Making it possible to approximate the model count of instances previously out of reach. We then investigated the structural factors that lead to a high model count using AI explainability approaches.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationDalla, M., Visentin, A., and O'Sullivan, B. (2024) 'A Machine Learning Approach to Model Counting' , IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Herndon, Virginia, USA, October 28–30, October 2024.en
dc.identifier.endpage9en
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/16877
dc.language.isoenen
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE)en
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Maternity/Adoptive Leave Allowance/12/RC/2289-P2s/IE/INSIGHT Phase 2/en
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Centres for Research Training Programme::Data and ICT Skills for the Future/18/CRT/6223/IE/SFI Centre for Research Training in Artificial Intelligence/en
dc.rights© 2024, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.en
dc.subjectModel countingen
dc.subjectMachine learningen
dc.subjectSAT problemen
dc.subjectFeature analysisen
dc.titleA machine learning approach to model countingen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Marco___ICTAI24___Model_Counting (2) (1).pdf
Size:
654.42 KB
Format:
Adobe Portable Document Format
Description:
Accepted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items