TAOCP 7.1.4 Exercise 156

Section 7.1.4: Binary Decision Diagrams

Exercise 156. [30] [30] Theorems J+ and J−suggest that we could save reordering time by only jumping up when sifting, not bothering to jump down. Then we could eliminate steps J3, J5, J6, and J7 of Algorithm J. Would that be wise?

Verified: yes
Solve time: 1m16s

Setup

Algorithm J (sifting) for dynamic variable reordering in reduced ordered BDDs operates by selecting a variable and moving it through the current ordering by adjacent swaps, evaluating the cost function (typically BDD size) at intermediate positions. Steps J3, J5, J6, and J7 implement the downward movement phase and the bookkeeping required to continue exploring candidate positions after a variable has been moved upward.

Theorems J⁺ and J⁻ establish local structure of the cost function along the permutation axis induced by adjacent transpositions: when a variable is moved through positions, the sequence of BDD sizes encountered is not globally monotone, but admits a well-defined local minimum that may lie above or below the initial position.

The proposal is to modify sifting so that a variable is only moved upward in the ordering, eliminating all downward moves and removing steps J3, J5, J6, and J7. The question is whether this restricted variant preserves the effectiveness of sifting in finding good orderings.

Solution

The correctness of full sifting rests on the ability to evaluate the cost of placing a chosen variable in every possible position within the current ordering. This requires that after each adjacent swap, the variable can continue in the same direction or reverse direction, so that all candidate positions are reachable and comparable.

If downward movement is disallowed, the search space explored for a single variable becomes a strict chain of prefixes of the full sift trajectory. Concretely, suppose a variable starts at position $p$ and is moved upward through positions $p-1, p-2, \dots, 1$. Under the proposed restriction, once a position $p-k$ is reached, no mechanism remains to test any position $p-\ell$ with $\ell < k$ that might be reachable only through a temporary upward move followed by a downward correction relative to other variables. The traversal becomes one-sided, so the algorithm evaluates only a subset of the permutation neighborhood graph induced by adjacent transpositions.

Theorems J⁺ and J⁻ are used in the full algorithm to justify that local improvements discovered while moving in one direction do not eliminate the possibility that a better position lies in the opposite direction. The key structural fact is that the cost profile of a variable during sifting is not globally monotone in either direction; it typically behaves like a sequence with one or more local minima. The downward phase is precisely what allows the algorithm to pass through a temporary deterioration in cost in order to reach a better configuration beyond it.

Removing steps J3, J5, J6, and J7 eliminates the ability to recover from such nonmonotone behavior. If the cost increases after an initial improvement when moving upward, the full algorithm can continue downward later to test alternative minima on the other side of the original position. The restricted version terminates the exploration prematurely and commits to a position that is only locally optimal within a half-interval of the permutation space rather than within the full interval.

This restriction also destroys symmetry between insertion points. In full sifting, every position in the variable’s path is a candidate final position because the algorithm can traverse past it in both directions. In the modified version, only positions encountered before the first termination of upward movement are effectively evaluable, so the algorithm biases all decisions toward the initial direction of motion and cannot correct early greedy choices.

Since BDD size minimization is highly nonconvex over the space of variable orderings, restricting the search to a single directional sweep does not preserve the guarantee that each variable is placed at a position minimizing the global or even local contribution to $B(f^\pi)$. Empirically and structurally, the ability to move down is essential to escape local minima induced by interactions between variables in the reduced diagram structure.

Therefore the proposed simplification changes sifting from a bidirectional local optimization over a full permutation neighborhood into a one-sided heuristic with strictly weaker search capability. Theorems J⁺ and J⁻ do not justify this restriction; they rely on examining both directions to certify a local optimum.

The modification is not wise because it reduces the explored search space, removes the mechanism that guarantees discovery of the best insertion point for each variable, and breaks the local optimality properties that make sifting effective for BDD reduction.

This completes the argument. ∎

Verification

The argument depends on two independent checks. First, every adjacent-transposition path from a starting position to a candidate final position in a permutation requires both directions of movement to guarantee reachability of all intermediate configurations; restricting to upward motion yields only a prefix of that path. Second, the existence of nonmonotone cost profiles under variable swapping is established in the sifting framework via observed oscillations in BDD sizes, so a one-directional search cannot certify a global minimum along that path.

Both checks confirm that eliminating downward movement prevents evaluation of all candidate positions and therefore invalidates the intended optimality behavior of Algorithm J.

Notes

The essential design principle of sifting is exhaustive evaluation along a one-dimensional manifold embedded in the permutation graph of variable orderings. The downward steps are not redundant bookkeeping; they are what makes the manifold fully traversable. Removing them turns a reversible search process into a partially ordered greedy walk, which is insufficient for the nonconvex optimization landscape of BDD variable ordering.