三年竞赛盘点:推动模型计数技术发展,涵盖四大变体问题
The Model Counting Competitions 2021-2023
- 设立四个赛道,分别针对标准、加权、投影及混合模型计数问题
- 每年吸引7至9个不同技术路线的求解器参与,成果丰富
- 适合关注逻辑推理与概率计算的算法研究者和开发者
现代社会中大量计算挑战依赖于概率推理、统计与组合数学。有趣的是,许多问题可通过将它们编码为命题公式,并计算其模型数量来表述。随着对模型计数实际应用的兴趣增长,社区自2019年秋季发起模型计数(MC)竞赛,首届于2020年举行。该竞赛旨在推动应用发展、识别挑战性基准、促进新求解器研发并改进现有求解器。本文全面回顾2021–2023年三届竞赛的执行过程与成果。竞赛设四个赛道:第一轨为标准模型计数(MC),第二轨为加权模型计数(WMC),第三轨为投影模型计数(PMC),第四轨则结合了投影与加权模型计数(PWMC)。竞赛持续高参与度,每年有7至9个不同版本的求解器提交,采用多种技术路径。
原文摘要 · Abstract (English)
Modern society is full of computational challenges that rely on probabilistic reasoning, statistics, and combinatorics. Interestingly, many of these questions can be formulated by encoding them into propositional formulas and then asking for its number of models. With a growing interest in practical problem-solving for tasks that involve model counting, the community established the Model Counting (MC) Competition in fall of 2019 with its first iteration in 2020. The competition aims at advancing applications, identifying challenging benchmarks, fostering new solver development, and enhancing existing solvers for model counting problems and their variants. The first iteration, brought together various researchers, identified challenges, and inspired numerous new applications. In this paper, we present a comprehensive overview of the 2021-2023 iterations of the Model Counting Competition. We detail its execution and outcomes. The competition comprised four tracks, each focusing on a different variant of the model counting problem. The first track centered on the model counting problem (MC), which seeks the count of models for a given propositional formula. The second track challenged developers to submit programs capable of solving the weighted model counting problem (WMC). The third track was dedicated to projected model counting (PMC). Finally, we initiated a track that combined projected and weighted model counting (PWMC). The competition continued with a high level of participation, with seven to nine solvers submitted in various different version and based on quite diverging techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。