LP-Based Weighted Model Integration over Non-Linear Real Arithmetic

S. Akshay, Supratik Chakraborty, Soroush Farokhnia, Amir Kafshdar Goharshady, Harshit Jitendra Motwani, Dorde ZikelicIJCAI 2025 · DOI

Abstract

Weighted Model Integration (WMI) is a powerful framework for probabilistic inference in hybrid domains, yet it faces a significant "expressivity gap" when dealing with non-linear constraints and complex weight functions. We introduce WMI-LP, a novel algorithm that reduces non-linear integration into a series of linear programming (LP) instances using real algebraic geometry. By leveraging Handelman’s Theorem for set containment checks, WMI-LP provides deterministic, $\epsilon$-tight error guarantees for rational and radical weight functions. Our evaluation on 120 challenging benchmarks demonstrates that WMI-LP is more robust and provides tighter bounds than existing symbolic and approximate solvers.

Introduction

Probabilistic inference in hybrid domains—mixing discrete and continuous variables—often requires calculating the "weight" of a model. This involves integrating a weight function over a region defined by logical constraints. While WMI is a robust framework, most existing tools are optimized for linear or polynomial functions. However, real-world applications in physics, finance, and robotics frequently involve rational functions (fractions of polynomials) or radical functions (roots of polynomials).

Exact WMI is #P-hard, and current approximate methods either lack formal error guarantees (like Monte Carlo sampling) or cannot handle the non-linear arithmetic required for these complex functions. WMI-LP addresses this by providing a scalable approach with formal, user-defined precision.

Methodology: From Integration to Linear Programming

WMI-LP transforms the integration of a weight function $w(x)$ over a set $S$ into a volume calculation of a higher-dimensional set $S'$ in $\mathbb{R}^{n+1}$. The algorithm follows a three-step pipeline:

  1. Reduction to Volume: The problem is reframed as finding the volume of a region bounded by the original constraints and the weight function.
  2. Bounding: Binary search and LP solvers determine the interval bounds for the newly introduced dimension.
  3. Recursive Subdivision (Gridding): The algorithm covers the target region with hyper-rectangles. For each rectangle, it must decide if it is entirely "Inside," "Outside," or "Intersecting" the target set.

To handle non-linear constraints without expensive symbolic math, WMI-LP uses Farkas’ Lemma and Handelman’s Theorem. These tools from real algebraic geometry translate the non-linear containment check into a standard Linear Programming (LP) problem. This innovation allows the algorithm to use high-performance solvers like Gurobi to process thousands of checks in milliseconds. Furthermore, the process is perfectly parallelizable, allowing it to scale with modern multi-core processors.

Experimental Evaluation

The authors evaluated WMI-LP using two benchmark families designed to push the limits of current solvers:

  • Family (A) - Random Rational Functions: 60 instances featuring fractions of polynomials of degree two or three.
  • Family (B) - Random Radical Functions: 60 instances involving square roots of polynomials.
Performance of WMI-LP across Family A (rational) and Family B (radical) benchmarks, showing consistent interval bounds across 120 instances.

Key Results and Discussion

WMI-LP demonstrated a clear leap in applicability and precision:

  • Robustness: WMI-LP successfully solved all 120 benchmarks. In contrast, the symbolic tool LattE solved none, and the sampling-based VolEsti failed on all radical function benchmarks (Family B).
  • Tightness: Unlike statistical methods, WMI-LP is $\epsilon$-tight, providing a hard interval $[Lower, Upper]$ where the true value is guaranteed to reside. As shown in the comparative data, WMI-LP consistently provided much tighter error bounds than GuBPI, whose errors were often orders of magnitude larger than the requested precision.
  • Reliability: While Mathematica is powerful, it often returned symbolic expressions too complex for use or encountered execution errors on radical functions. WMI-LP provided reliable numerical approximations where symbolic integrators struggled.
Comparative analysis of WMI-LP against state-of-the-art solvers. WMI-LP provides tight numerical bounds where others fail (ER), time out (TO), or produce complex results (CX).

Conclusion and Future Work

WMI-LP bridges the expressivity gap in hybrid probabilistic inference by providing a scalable, deterministic approximation for non-linear real arithmetic. While the recursive subdivision approach currently faces the "curse of dimensionality" in very high-dimensional spaces, the use of LP as a proxy for integration offers a significant advancement. Future work will focus on optimizing subdivision strategies, such as using non-rectangular shapes or heuristic-driven splitting, to further enhance scalability.

Summary updated

BibTeX
@inproceedings{akshay2025lp,
  author = {S. Akshay and Supratik Chakraborty and Soroush Farokhnia and Amir Kafshdar Goharshady and Harshit Jitendra Motwani and Dorde Zikelic},
  title = {{LP-Based Weighted Model Integration over Non-Linear Real Arithmetic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/1005},
}
Figure