TAOCP 7.2.2.2 Exercise 153

Exercise 153. [17] [17] What's a good way to weed out unwanted candidates in step X3, if $C > C_{\max}$?

Verified: no
Solve time: 2m21s

Solution

In step X3, after the initial selection of the $C$ participant variables, each candidate variable $x$ receives the rating

$$ r(x)=h(x)h(\bar{x}). $$

The purpose of the pruning phase is to reduce the number of candidates before the more expensive lookahead work in later steps. If $C>C_{\max}$, the candidates with the least useful ratings should be removed until the number of candidates is small enough.

A natural criterion is to compare each rating with the mean rating

$$ \bar r=\frac{1}{C}\sum_{x\in\mathit{CAND}}r(x). $$

While

$$ C>2C_{\max}, $$

delete every candidate $x$ whose rating satisfies

$$ r(x)>\bar r . $$

The remaining candidates have ratings no larger than the average of the previous candidate set. The deletion step removes variables that are relatively unlikely to be good branching choices, while retaining variables whose two polarities have a strong combined heuristic score.

The use of the factor $2C_{\max}$ leaves room for the possibility that the deletion process removes too many candidates in one pass. After one pass, either

$$ C\le 2C_{\max}, $$

or the candidate set has become smaller because every removed variable had a rating above the current mean. Recomputing the mean on the reduced set and repeating the process continues to lower $C$ until the required cutoff is reached or until all remaining candidates have survived the test.

This procedure preserves the main purpose of step X3: the candidate set contains variables that are most promising according to the heuristic scores, while the expensive later lookahead phase never needs to examine an unnecessarily large set.

∎