2026-07-24T05:47:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20695 2024-11-27T23:17:44Z ddc:004 open_access

Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference Dubray, Alexandre Schaus, Pierre Nijssen, Siegfried Projected Weighted Model Counting Limited Discrepancy Search Approximate Method Probabilistic Inference Weighted model counting (WMC) plays a central role in probabilistic reasoning. Given that this problem is #P-hard, harder instances can generally only be addressed using approximate techniques based on sampling, which provide statistical convergence guarantees: the longer a sampling process runs, the more accurate the WMC is likely to be. In this work, we propose a deterministic search-based approach that can also be stopped at any time and provides hard lower- and upper-bound guarantees on the true WMC. This approach uses a value heuristic that guides exploration first towards models with a high weight and leverages Limited Discrepancy Search to make the bounds converge faster. The validity, scalability, and convergence of our approach are tested and compared with state-of-the-art baseline methods on the problem of computing marginal probabilities in Bayesian networks and reliability estimation in probabilistic graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandre Dubray and Pierre Schaus and Siegfried Nijssen 2024 Is Part Of LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2024.10 urn:nbn:de:0030-drops-206956 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode