CMP.4:4.2 - Derive an exclusion that applies to the entire branch
Select a reason for omitting s according to the result required:
| Reason | Required argument | What it allows |
|---|---|---|
| Infeasibility | No completion of s can satisfy the original conditions. | Discard s when looking for admissible answers. |
| Bound | Every completion has a value no better than a bound compared with an already admissible answer. | Discard s for the corresponding optimization conclusion. |
| Dominance | Another retained choice supplies an admissible answer at least as good for every continuation that matters. | Omit dominated work while retaining the stated result. |
| Equivalent completions | A retained representative accounts for the answers required from s. | Share or omit duplicate work with the appropriate treatment of identity and multiplicity. |
Construct these arguments from the constraints and the partial state. Propagating a choice can shrink the permitted values of other variables; an empty remaining domain then excludes that branch. A bound may come from relaxing the remaining problem through CMP.5. Dominance must include future possibilities, not merely compare the current partial scores.
For a maximization problem, let L be the value of the best admissible candidate already obtained, often called the incumbent. Let U(s) be at least as large as the value of every admissible completion of s. If one optimum is required, U(s)≤L permits exclusion. If every attaining candidate is required, equality can still contain needed answers; use U(s)<L for this bound-based exclusion and preserve the attaining alternatives.
For minimization, reverse the bound directions: a lower bound on every completion is compared with the cost of a known feasible candidate. A candidate score and a bound on all completions have different roles even when their numerical values coincide.