TAOCP 7.1.4 Exercise 34

Let $B$ be the BDD of $f(x_1,\dots,x_n)$ with root node $r$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.4: Binary Decision Diagrams

Exercise 34. [M25] [M25] Specialize exercise 31 so that we can efficiently compute max{ max 1≤k≤n(w1x1 + · · · + wk−1xk−1 + w′ kxk + wk+1xk+1 + · · · + wnxn + w′′ k) | f(x) = 1} from the BDD of f, given 3n arbitrary weights (w1, . . . , wn, w′ 1, . . . , w′ n, w′′ 1 , . . . , w′′ n).

Verified: yes
Solve time: 1m53s

Solution

Let $B$ be the BDD of $f(x_1,\dots,x_n)$ with root node $r$. Each node $v$ is labeled by a variable index $V(v)\in{1,\dots,n}$ and has successors $\operatorname{LO}(v)$ and $\operatorname{HI}(v)$, with sink nodes $\bot$ and $\top$.

For each fixed $k$, define coefficients $c_i^{(k)}$ by

$$ c_i^{(k)} = \begin{cases} w'_k & i=k,\ w_i & i\neq k. \end{cases} $$

The expression inside the outer maximum becomes, for fixed $k$,

$$ w''k + \max{x\in{0,1}^n,\ f(x)=1}\ \sum_{i=1}^n c_i^{(k)} x_i. $$

Define, for each node $v$, the value $F_k(v)$ as the maximum of $\sum_i c_i^{(k)}x_i$ over all assignments $x$ consistent with reaching $\top$ from $v$ in the BDD, and equal to $-\infty$ if no such assignment exists.

For sinks,

$$ F_k(\bot)=-\infty,\qquad F_k(\top)=0. $$

For an internal node $v$ with $j=V(v)$, every admissible assignment splits according to $x_j=0$ or $x_j=1$. If $x_j=0$, the contribution of variable $j$ is $0$ and the computation continues at $\operatorname{LO}(v)$. If $x_j=1$, the contribution is $c_j^{(k)}$ and the computation continues at $\operatorname{HI}(v)$. Hence

$$ F_k(v)=\max\bigl(F_k(\operatorname{LO}(v)),\ c_{V(v)}^{(k)} + F_k(\operatorname{HI}(v))\bigr). $$

This recurrence specializes the evaluation procedure of Exercise 31 by interpreting the leaf values as $\bot\mapsto -\infty$ and $\top\mapsto 0$, and by interpreting each branch as either adding $0$ or adding the corresponding coefficient.

The value of interest for fixed $k$ is $F_k(r)$, and the full objective becomes

$$ \max_{1\le k\le n}\bigl(w''_k + F_k(r)\bigr). $$

Since the BDD has a unique node set, each computation of $F_k$ proceeds by a single bottom-up evaluation over all nodes, reusing shared subgraphs exactly as in the evaluation scheme of Exercise 31. This yields a total cost proportional to $n$ times the number of BDD nodes, because each of the $n$ weight systems induces one independent labeling of the same directed acyclic graph.

The final answer is

$$ \boxed{\max_{1\le k\le n}\left(w''_k + F_k(r)\right)}. $$

This completes the solution. ∎