2025/09/17 by Mingwei Zhang, Zhang, Mingwei, Zhenhao Gu +10
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2509.13880
openalex publication_date 2025/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Linear constraints are one of the most fundamental constraints in fields such as computer science, operations research and optimization. Many applications reduce to the task of model counting over integer linear constraints (MCILC). In this paper, we design an exact approach to MCILC based on an exhaustive DPLL architecture. To improve the efficiency, we integrate several effective simplification techniques from mixed integer programming into the architecture. We compare our approach to state-of-the-art MCILC counters and propositional model counters on 2840 random and 4131 application benchmarks. Experimental results show that our approach significantly outperforms all exact methods in random benchmarks solving 1718 instances while the state-of-the-art approach only computes 1470 instances. In addition, our approach is the only approach to solve all 4131 application instances.