Reordering the Hidden Tree: Dynamic Variable Orders for Decomposed MDD Constraints

Constraint solvers often represent a complicated constraint as a multi-valued decision diagram (MDD). An MDD is a layered graph in which each layer tests one variable, and every path from top to bottom spells out one allowed assignment. A recent and very fast way to enforce such a constraint is to decompose it. The Binary Constraint Tree encoding turns the MDD into a tree of "hidden" auxiliary variables linked by simple two-variable constraints. Because the resulting network is a tree, ordinary arc consistency on it removes exactly the values that full generalized arc consistency (GAC) on the original constraint would remove. Pruning is not lost. The cost of the decomposition, meaning how many hidden variables there are, how large their domains are, and how much work each propagation pass does, is fixed by the variable order chosen when the MDD is built. That order is chosen once, statically, and never revisited.

We propose to treat the MDD variable order as a runtime parameter of the decomposition. During search, the solver periodically takes the MDD restricted to the current domains, re-sifts its variable order, rebuilds a smaller binary tree for the subtree it is about to explore, and discards that tree on backtrack. The key point is that this reordering cannot change what gets pruned: every order yields GAC. Dynamic reordering here is therefore a pure cost lever. With the same branching heuristic the search tree is identical, so the experiment isolates one question. Does the size of the decomposition under the static order drift far enough from the size under the best order, as search restricts domains, that paying for re-encoding wins?

Core Claim

The overhead of a tree-decomposed MDD constraint depends on the variable order. The best order for the constraint restricted to a search node can differ sharply from the best order at the root. Proof complexity gives the reason to expect this. Reordering Rule Makes OBDD Proof Systems Stronger and On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables show exponential separations between fixed-order and reorderable decision-diagram reasoning. Changing Partitions in Rectangle Decision Lists shows that a single change of variable partition can shrink some representations from exponential to constant size. SPUDD observed the practical version of the same effect: during value iteration, an order that starts out good becomes a bottleneck as the represented functions change.

Our claim is that restricting domains during constraint search produces the same kind of drift. We further claim that re-encoding at a small number of well-chosen search checkpoints recovers this gap on a measurable fraction of table benchmarks, without changing the pruning.

The claim is also bounded by negative results. The same Itsykson et al. paper proves $2^{\Omega(n)}$ lower bounds for pigeonhole and Tseitin-on-expander formulas under any reordering sequence, so some constraints will have no good order at any node. Part of the work is predicting when re-encoding is not worth attempting.

Relation to Prior Work

The mechanism we build on is Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees. That paper introduces the tree binary encoding, four reduction rules that shrink the tree by over 2,000x, and a bitwise propagator. It builds everything from one static MDD order and never revisits that order. We keep its encoding, reductions and propagator unchanged and make the order dynamic.

Compact-MDD compresses tables into semi-MDDs and filters them with reversible sparse bit-sets. It explicitly notes that optimal ordering is NP-hard and uses fixed layer orders. Our work does not try to find optimal orders. It asks whether cheap local re-sifting pays off during search.

Two further papers use ordering heuristics only once, before solving. Compiling Constraint Networks into Multivalued Decomposable Decision Graphs chooses orders with static betweenness centrality for offline compilation. Constraint and Variable Ordering Heuristics for Compiling Configuration Problems supplies our reordering method: Rudell-style sifting that moves clusters of related variables as blocks. That work applies it only during offline BDD compilation, where it cut compilation of the C211_FS automotive instance from 1,432 s to 4.5 s. We move it inside search, on residual constraints.

The broader decomposition-overhead literature shows that decompositions usually trade pruning for speed or portability. The Complexity of Global Constraints shows that polynomial decompositions of NP-hard constraints must lose pruning. The Hall-interval decompositions of Decompositions of All Different, Global Cardinality and Related Constraints and the pyramid decomposition of Decomposition of the NVALUE constraint pay for their stronger pruning with $O(nd^2)$ to $O(nd^3)$ auxiliary variables. MDD constraints are the setting where that trade-off disappears: GAC is polynomial in diagram size, and the tree encoding keeps it. The only remaining overhead is the auxiliary footprint, and that footprint is what the order controls. This is why we chose this setting over the more speculative idea of "re-partitioning" NP-hard decompositions, which would have to contend with the Bessiere et al. penalty directly.

Research Program

The first stage is a measurement study, and it can kill the project. We will instrument a solver running the static tree encoding on the XCSP table repository. At sampled search nodes, we record the size of the restricted MDD under the static order. We also record its size after block sifting, meaning the reduced tree's hidden-variable count and total hidden-domain size. The quantity of interest is the ratio $\rho(v) = S_{\text{static}}(v) / S_{\text{sifted}}(v)$. Here $S$ is the reduced tree size at search node $v$ and $S_{\text{sifted}}$ is the size after sifting the restricted diagram. We compare $\rho$ at depth $d$ with $\rho$ at the root.

If $\rho$ at depth barely exceeds $\rho$ at the root, then offline sifting captures all the benefit, and the dynamic proposal is dropped. The result would be reported as a negative finding.

The second stage builds checkpointed re-encoding. At a checkpoint node, the solver restricts the MDD to the current domains, sifts the restricted diagram with cluster-preserving block moves, and re-applies the four reduction rules. It then swaps in the new tree for the subtree and restores the parent tree on backtrack. Rebuilding off the trail avoids having to make sifting reversible.

The trigger decides when to checkpoint. It fires when the estimated remaining subtree work multiplied by the predicted saving exceeds the rebuild cost. We estimate the saving cheaply by running a bounded number of sifting swaps and measuring how much the diagram shrinks. We estimate subtree work from failure statistics that the branching heuristic already maintains. Wang and Yap report that a full initial tree takes under 0.5 s per instance to generate. That figure is an upper bound on per-checkpoint cost for the root-sized constraint, and restricted diagrams should be smaller. Even so, it makes clear that checkpoints must be rare.

The third stage is analysis. We will characterize which constraint families benefit, using the Itsykson et al. expander-style lower bounds to identify constraints for which no order can help. We will also check whether aligning the new order with the branching order explains most of the gain.

Baselines

The naive reference point is the static tree binary encoding exactly as published, built from the default MDD order. Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees reports that this encoding was fastest on 71% of over 2,500 XCSP table instances, up to 12x faster than Compact Table, and up to 98x faster than the leading MDD propagator. On Pentominoes it reached 246 nodes per second versus 4 for baseline MDD solvers. It is also the strongest existing method on this exact question, because it is the decomposition we modify.

The strongest non-decomposed competitor is Compact Table, the bitwise table propagator. Compact-MDD on semi-MDDs is included as a representative of compressed diagram filtering; it solved 40% of 4,111 XCSP3 instances within a factor of 2 of Compact Table's time (Compact-MDD).

The ablation that isolates the key ingredient is offline sifting. Before search, we apply the same cluster-preserving sifting to the full MDD, build one tree, and never re-encode. A second ablation fixes the MDD order to match the branching heuristic's expected order at the root.

All systems run in the same solver with the same branching heuristic (dom/wdeg), the same restarts, the same timeout and the same hardware. The sifting budget is identical across the offline and dynamic variants. Because every variant enforces GAC, node counts should match. Any mismatch is a correctness bug, not a result.

Beating the baseline means two things. First, on the full XCSP table suite, dynamic re-encoding must solve strictly more instances within the timeout than offline sifting. Second, on commonly solved instances, it must show a statistically significant runtime reduction at equal node counts, with no more than a small slowdown on instances where no checkpoint fires. Winning against the unsifted static encoding alone would not count.

Why not just…?

Why not just sift once before search? This is the real threat. The measurement study exists to settle it. If the root-optimal order stays near-optimal for restricted diagrams, offline sifting wins because it pays the reordering cost once. The proposal only has a case where $\rho$ grows with depth. The SPUDD and rectangle-list results suggest drift is plausible, but no reported result on Lacuna measures it for constraint search. If the offline ablation matches the dynamic variant, we will report that and stop.

Why not just use Compact Table or semi-MDD compression? Wang and Yap's published comparison already favors the static tree encoding over Compact Table on 71% of instances. Semi-MDD relaxation shrinks node counts but still uses a fixed order. We include both as baselines, and we can also apply dynamic reordering on top of semi-MDDs. A gain that appears only relative to the tree encoding, and not relative to Compact Table, would limit the claim to the tree-encoded regime.

Why not just order the MDD to match the branching order? When branching is adaptive, as with dom/wdeg, the branching order is not known in advance. Matching it at the root is our second ablation. If that ablation captures most of the gain, the contribution reduces to "align the order with branching." That would still be a finding, but a smaller one, and our analysis stage will report it that way.

Proposed Experiments

The benchmarks are the XCSP table repository used by Wang and Yap and by Compact-MDD, and the Pentominoes, car sequencing and nurse scheduling models from the tree-encoding paper. Metrics are instances solved within the timeout, total and per-node runtime, the number of checkpoints fired, rebuild time as a fraction of runtime, and the tree-size ratio $\rho$ at checkpoints.

The first decisive check is the drift curve: $\rho$ as a function of depth across the suite, reported before any solver engineering. The second is the equal-node-count runtime comparison against offline sifting. The third is a trigger-quality analysis that compares our cost-model trigger with an oracle that knows each subtree's actual work. The oracle is computed by rerunning the instance, which is possible because the search tree is fixed. This bounds how much of the available gain a better trigger could recover.

Finally, we will build synthetic MDD constraints from pigeonhole and expander-derived families, where Itsykson et al. show no order helps. On these, the trigger should essentially never fire. Firing there would indicate a broken cost model.