Generating Random Instances of Weighted Model Counting: An Empirical Analysis with Varying Primal Treewidth

Paulius Dilkas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Weighted model counting (WMC) is an extension of propositional model counting with applications to probabilistic inference and other areas of artificial intelligence. In recent experiments, WMC algorithms perform similarly overall but with significant differences on specific subsets of benchmarks. A good understanding of the differences in the performance of algorithms requires identifying key characteristics that favour some algorithms over others. In this paper, we introduce a random model for WMC instances with a parameter that influences primal treewidth—the parameter most commonly used to characterise the difficulty of an instance. We then use this model to experimentally compare the performance of WMC algorithms c2d, Cachet, d4, DPMC, and miniC2D. Using these random instances, we show that the easy-hard-easy pattern is different for algorithms based on dynamic programming and algebraic decision diagrams than for all other solvers. We also show how all WMC algorithms scale exponentially with respect to primal treewidth and how this scalability varies across algorithms and densities. Finally, we combine insights from experiments involving both random and competition instances to determine how the best-performing WMC algorithm varies depending on clause density and primal treewidth.
Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 2023
EditorsAndre A. Cire
PublisherSpringer
Pages395-416
Number of pages22
Volume13884
ISBN (Electronic)9783031332715
ISBN (Print)9783031332708
DOIs
Publication statusPublished - 23 May 2023
EventThe 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2023 - Nice, France
Duration: 29 May 20231 Jun 2023
Conference number: 20
https://sites.google.com/view/cpaior2023/home

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2023
Abbreviated titleCPAIOR 2023
Country/TerritoryFrance
CityNice
Period29/05/231/06/23
Internet address

Keywords / Materials (for Non-textual outputs)

  • Weighted model counting
  • Random model
  • Parameterised complexity

Fingerprint

Dive into the research topics of 'Generating Random Instances of Weighted Model Counting: An Empirical Analysis with Varying Primal Treewidth'. Together they form a unique fingerprint.

Cite this