Many planning and scheduling systems can tell you whether a feasible schedule exists. Few can tell you how many there are, or how that number changes as a deadline moves. That number is useful: it measures how much slack a plan has and how fragile it is, and it is the denominator of any uniform-sampling or probabilistic analysis. Counting the integer points of a polytope (the region cut out by linear inequalities $Ax \le b$) has an exact analytic route. The count's generating function is a ratio of simple products, and complex-analysis residues (the coefficients that remain when a function is integrated around its poles) turn it back into a closed-form count. The method works, but the number of residue terms blows up with the size of the whole constraint matrix. Planning research learned long ago to avoid exactly this kind of global explosion by reasoning inside "scopes": small groups of variables tied together by the constraints relevant to one function, such as one floor of a building or one flight mission.
This note proposes running the residue computation scope by scope. Each scope gets its own generating function, with the variables it shares with other scopes left as symbolic parameters. The local pieces are then glued with a residue integral taken only over those shared variables. The claim is that the cost then depends on the subdeterminants (minors) of each small regional block and on the width of the interfaces between blocks, not on the global matrix. For temporal networks built from difference constraints, those regional blocks are totally unimodular, so their counts are plain polynomials in the deadlines. The result is an exact count that is a formula in the deadlines, and its cost does not grow with the time horizon.
Core Claim
Split the integer variables into regional blocks $x_i$ and interface variables $u$ shared between blocks, so the constraints read $A_i x_i + B_i u \le b_i$. The number of integer solutions then factorizes as
$$N(b) = \sum_{u} \prod_i N_i(b_i - B_i u),$$
where $N_i$ counts the solutions of block $i$ for a fixed interface value. In the transform domain, each $N_i$ is a rational generating function whose poles are set by the minors of the block $[A_i\ B_i]$. The sum over $u$ is a convolution, which a contour integral performs over the interface variables alone.
The proposal makes two claims, one theoretical and one empirical. First, when every block has subdeterminants bounded by $\Delta$ and the interface graph is a tree of width $k$, the number of residue terms is bounded by a function of $\Delta$, $k$ and the block sizes. The bound is a sum over scopes, multiplied only across interfaces, rather than the global quantity that makes the monolithic method's complexity unanalyzable. Second, on real scoped scheduling domains, this symbolic gluing beats both monolithic residue counting and the obvious alternative of tabulating interface values, and the advantage widens as the time horizon grows.
The prior work plays three different roles here. On Counting Integral Points in a Convex Rational Polytope supplies the method. It inverts a multidimensional Z-transform (the discrete analogue of a Laplace transform) by iterated one-dimensional residue integrals and gets Ehrhart polynomials, the polynomial formulas for counts as a polytope is scaled up, as a byproduct. It also motivates the gap: the authors could not bound its complexity because poles multiply at each integration step, and the method treats $A$ as one block. Explicit Formula for Counting Lattice Points of Polyhedra simplifies the Brion–Vergne residue formula into sums over fixed cones determined by $A$. It shows directly that the number of terms tracks submatrix determinants, which is why we expect regional minors to govern regional cost. Its formula is global, and ours is not. Enumerating Integer Points in Polytopes with Bounded Subdeterminants and Solving Totally Unimodular LPs with the Shadow Vertex Algorithm show that bounded minors control facet widths and pivot paths. The first also acts as a constraint. Its polynomial-time enumeration requires every $n \times n$ minor to be nonzero, which sparse, block-structured scheduling matrices violate badly. Scoping is how we sidestep that requirement: each block can be made full rank even when the global matrix is degenerate. From planning, Scope and Abstraction: Two Criteria for Localized Planning supplies the partitioning principle and an automatic partitioner (LOC). Temporal Milestones in HTNs supplies the idea of resolving cross-region interactions only through a small set of exposed events. Our interface variables play the role of its milestones. Neither work counts anything; they check consistency or search for a single plan.
Research Program
The work has three parts.
The first part is theoretical, and we deliberately start narrow. Take scheduling blocks made of difference constraints $t_j - t_i \le c_{ij}$, which are totally unimodular. Add a sparse set of coupling constraints, such as shared-resource caps or synchronization events. For this class we will prove that every regional transform has its poles only at $z=1$, so each $N_i$ is piecewise polynomial in its right-hand side. We will then bound the number of polynomial pieces, the "chambers" of the vector partition function, by the regional block structure. For TU blocks the bottleneck is the number of chambers, not roots of unity, and scoping should shrink exactly that number. We will then extend the bound to blocks with $|\text{minor}| \le \Delta$, where poles at $\Delta$-th roots of unity appear and counts become quasi-polynomials.
The second part is an implementation. It builds scopes in one of two ways: from the functional relevance of constraints, following LOC, or from a graph partition of the constraint hypergraph. For each scope it computes a parametric count in the style of Brion–Vergne, with the interface variables as parameters. It then eliminates the interface variables one at a time by residue integration along the tree of interfaces. This is the same elimination order a tree-decomposition algorithm uses, but the messages passed between scopes are rational functions rather than tables.
The third part is a measurement study of where the method breaks: how cost depends on interface width, on the regional minor bound $\Delta$, and on how dense the coupling constraints are.
Baselines
The naive reference point is brute-force enumeration of integer schedules with constraint propagation. It is used only on small instances, to certify that every other method returns the correct count.
The first strong baseline is monolithic residue counting: the Z-transform inversion of On Counting Integral Points in a Convex Rational Polytope and the explicit cone formula of Explicit Formula for Counting Lattice Points of Polyhedra, both applied to the global matrix. It is the most direct competitor because it produces the same parametric output. It runs on identical instances, with the same exact-arithmetic library and the same time and memory limits. We beat it if the number of residue terms and the wall time grow polynomially in the number of scopes, rather than explosively. No reported result was found on Lacuna for its runtime on any benchmark; the paper gives only an illustrative three-constraint example.
The second strong baseline, and the most dangerous one, is dynamic programming over the same scope tree with tabulated interface values. Each scope's count is computed numerically for every interface value, and the tables are multiplied and summed. It uses identical scopes, so the only difference from our method is symbolic versus tabulated gluing. That makes it the ablation that isolates the key ingredient. We beat it if our cost stays flat as the horizon $T$ grows, while tabulation grows roughly like $T^k$ for interface width $k$. We concede to it wherever it wins.
The third baseline is a SAT-based count. Constraints are encoded with the equi-propagation encoder of Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems and handed to a model counter. On its home ground that encoder was reported "38 times faster" with "20 times fewer clauses on average" on quasigroup completion. It gets the same time limits.
As a continuous reference, we use the random-walk volume estimator of Practical Polytope Volume Approximation. It reports "within 2% error in approximately 17 minutes" for the Birkhoff polytope $B_{10}$. We compare its volume against the exact count to show where volume misleads.
A second ablation replaces functional scopes with random scopes of matched size. This tests whether the scope criterion matters or just any partition does.
Why not just…?
Why not just do dynamic programming over a tree decomposition with tables? This is the real threat. When interfaces are narrow and horizons short, it may simply be faster, because tabulating a few hundred interface values is cheap. Symbolic gluing should pay off only when interface variables range over large domains, such as minute-resolution schedules over a week, or when the user wants the count as a formula in the deadlines. The DP ablation is designed to locate the crossover. If tabulation wins across the realistic horizons in our benchmarks, we will report that the contribution is the theory and the parametric output, not raw speed.
Why not just estimate volume with random walks? Volume is not a count. The bounded-subdeterminant analysis in Enumerating Integer Points in Polytopes with Bounded Subdeterminants highlights that thin polytopes can have positive volume and no integer points. Tightly constrained schedules are exactly such thin slabs. Our experiments will report the ratio of estimated volume to exact count across slack levels, to show where approximation is adequate and where it fails.
Why not just use a SAT or constraint encoder plus a model counter? The encoder in Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems relies on unary order encoding, which its authors note becomes memory-prohibitive for wide integer domains. Counting is also harder than satisfiability. We expect it to win on small-domain puzzles from its own suite and to lose as temporal domains widen. Running both families settles which happens.
Why not just use the Nullstellensatz partial-fraction route and skip complex analysis? Its originators restrict it to small constraint counts $m$. It is, however, a perfectly good local solver inside a small scope, so we include it as an alternative per-scope engine rather than a competitor.
Proposed Experiments
The scaling benchmarks are the office-building construction domain from Scope and Abstraction: Two Criteria for Localized Planning, regenerated from its description, and an Air Tasking Order-style generator matching Temporal Milestones in HTNs: up to 100 missions, about 58 tasks each, and decomposition depth 12. Neither paper reports exact numerical tables. The first reports flatter runtime curves for scoped planning; the second reports a "quadratic speedup" over naive path consistency. We therefore treat them as scaling regimes rather than leaderboards. We will plot exact count time, residue-term count and memory against the number of floors or missions.
For realistic constraint structure, the 600 instances of TCP: a Benchmark for Temporal Constraint-Based Planning are converted to integer difference constraints at minute resolution. Its "short" (one day) and "long" (one week) splits give a natural horizon sweep for the decisive comparison against tabulated DP. The accuracy figures reported there, such as o4-mini at 87.17%, concern schedule construction by language models and are not comparable to counting. However, our exact counts can additionally report how constrained each TCP instance is.
As a deliberate negative control we use dilated Birkhoff polytopes $tB_n$. Their matrix is totally unimodular but densely coupled, so there is no narrow scope structure. Scoping should give little or no gain there, and seeing a gain would suggest we are measuring an implementation artifact.
The decisive checks are threefold. First, exact agreement with brute force on all small instances. Second, residue-term counts that track our regional bound rather than the global minor structure as missions are added. Third, a measured crossover in horizon length beyond which symbolic gluing beats tabulated DP at equal interface width. If that crossover does not appear within week-long horizons, the practical case for symbolic gluing fails, and we will say so.
References
- On Counting Integral Points in a Convex Rational Polytope
- Explicit Formula for Counting Lattice Points of Polyhedra
- Enumerating Integer Points in Polytopes with Bounded Subdeterminants
- Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
- Scope and Abstraction: Two Criteria for Localized Planning
- Temporal Milestones in HTNs
- Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
- Practical Polytope Volume Approximation
- TCP: a Benchmark for Temporal Constraint-Based Planning