TAOCP 7.2.2.2 Exercise 286

Section 7.2.2.2: Satisfiability

Exercise 286. [M24] What choice of signatures-to-keep in Fig. 50 is optimum, in the sense that it maximizes $\sum q_{pq} r_{pq}$ subject to the conditions $\sum_p q_{pq} r_{pq} \le 3114$, $r_{pq} \in {0, 1}$, and $r_{pq} \ge r_{p'q'}$ for $1 \le p \le p' \le 7$, $0 \le q \le q' \le 8$? Here $q_{pq}$ and $b_{pq}$ are the sums of the gray and black clauses that have signature $(p, q)$, as given by the matrices in the text. [This is a special case of the "knapsack problem with a partial ordering."]

Verified: no
Solve time: 6m37s

I cannot produce a correct numerical solution for this exercise from the information provided. The exercise depends on the specific $7\times 9$ matrices of $q_{pq}$ and $b_{pq}$ from Fig. 50, and those entries are not included in the prompt. Without them, the optimal set of signatures, the value of

$$ \sum_{p,q} q_{pq}r_{pq}, $$

and the verification of the budget constraint

$$ \sum_p q_{pq}r_{pq}\le 3114 $$

cannot be determined.

A complete solution must begin by taking the entries of Fig. 50 and solving the resulting downward-closed knapsack problem. The admissible choices are exactly the order ideals of the partial order

$$ (p,q)\preceq (p',q') \quad\Longleftrightarrow\quad p\le p',\ q\le q', $$

because the constraint

$$ r_{pq}\ge r_{p'q'} $$

forces every retained signature to include all signatures northwest of it. The optimum can then be found by dynamic programming over these order ideals, or by exhaustive enumeration of the finite set of possible boundary paths through the $7\times 9$ grid.

The corrected solution requires the actual matrices from Fig. 50. Once those are supplied, the computation can be carried out and the final answer can state:

1. the optimal $r_{pq}$ pattern,
2. the corresponding retained signatures,
3. the attained objective value,
4. the proof that no other order ideal within the $3114$ budget has a larger objective value.