Research map / Learning theory and algorithms / Combinatorial and search optimization
Approximate Integer Solution Counts over Linear Arithmetic Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ApproxLatCount (ALC), a randomized approximate lattice-point counter for polytopes that combines hit-and-run sampling with rejection, a multiphase polytope chain, and a variance-based dynamic stopping criterion giving an (epsilon, delta) bound.
Problem
Counting integer solutions of linear constraints (lattice points in a polytope) is #P-hard and existing exact counters such as Barvinok become too slow beyond about 10 variables.
Approach
Adapts multiphase Monte-Carlo volume estimation to lattice counting: samples lattice points by hit-and-run on a shifted, enlarged polytope with rounding and rejection, builds a chain of polytopes each roughly halving the lattice count, and stops adaptively using an estimated variance of the product estimator.
Key results
- ALC solves random polytopes up to 80 dimensions (1 case solved at n=80), while Barvinok solves none beyond n=8 and Cachet/Ganak/ApproxMC4 none beyond n=15.
- At n=10 ALC solves 33 of 33 random cases versus 0 for Barvinok and 6 for Cachet, Ganak and ApproxMC4.
- Counts from ALC with epsilon=0.2, delta=0.1 fall within the stated bound on the tested cases with exact counts, as claimed by the authors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ALC instead of Barvinok | Random polytopes · Random polytopes, n=10 | #solved: 0 -> 33 | Helped |
| Use ALC instead of ApproxMC4 | Random polytopes · Random polytopes, n=10 | #solved: 10 -> 33 | Helped |
| Use ALC instead of Cachet | Random polytopes · Random polytopes, n=10 | #solved: 6 -> 33 | Helped |
| Use ALC instead of Ganak | Random polytopes · Random polytopes, n=10 | #solved: 5 -> 33 | Helped |
| Use ALC instead of Barvinok | Random polytopes · Random polytopes, n=15 | #solved: 0 -> 28 | Helped |
| Use ALC instead of ApproxMC4 | Random polytopes · Random polytopes, n=15 | #solved: 3 -> 28 | Helped |
| Use ALC instead of Barvinok | Random polytopes · Random polytopes, n=80 | #solved: 0 -> 1 | Helped |
| Set the approximation parameters to epsilon=0.2 and delta=0.1 | ALC · Cases with exact counts | relative error bound: [0.8, 1.2] with probability at least 90% | Helped |
| Use ALC instead of ApproxMC4, Cachet, or Ganak | Rotated thin rectangles · Rotated thin rectangles | cases solved within timeout | Helped |
Surprising findings
- Propositional model counters ApproxMC4, Cachet and Ganak solve more cases than Barvinok at small dimension, attributed to benchmarks with small bounds that favor them.
Limitations
- Hit-and-run is only a nearly uniform sampler, so the output distribution is only approximately uniform.
- Factorization preprocessing is less effective with approximate counting because epsilon and delta must be tightened for each factor.
- Rejection can be costly when the lattice count is much smaller than the enlarged polytope volume.
Experimental setup
Datasets: random polytopes (726 generated) rotated thin rectangles (180 generated) application instances from program analysis and simple temporal planning (4131)
Benchmarks: random polytopes rotated thin rectangles application instances (program analysis, STN)
Metrics: number of solved cases average running time relative error average polytope chain length
Baselines: Barvinok ApproxMC4 Cachet Ganak
Builds on: Multiphase Monte-Carlo algorithm Hit-and-run random walk Barvinok algorithm Shallow-beta-cut ellipsoid method
Closest papers by meaning
- Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo (AAAI 2018 · similarity 0.83)
- Towards Real-Time Approximate Counting (AAAI 2025 · similarity 0.83)
- Auditable Algorithms for Approximate Model Counting (AAAI 2024 · similarity 0.82)
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.82)
- The Ramanujan Library - Automated Discovery on the Hypergraph of Integer Relations (ICLR 2025 · similarity 0.80)
- Towards Projected and Incremental Pseudo-Boolean Model Counting (AAAI 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.