CMP.4:5 - Archetypal Grounding

CMP.4:5.1 - Select a best subset and interpret an interrupted search

Choose a subset of three items within capacity 5. Their (weight,value) pairs are A=(4,7), B=(3,5) and C=(2,3). Values and weights are positive integers. A partial state fixes which items are included or excluded; the next undecided item supplies the two covering extensions.

An initial candidate {A} is admissible with value 7. To bound the root, allow fractions of items. Filling by value per weight takes A and one third of B, giving 7+5/3=26/3. To establish that this is an upper bound, let a, b and c be the selected fractions. For 0≤a,b,c≤1 and 4a+3b+2c≤5,

7a+5b+3c=(5/3)*(4a+3b+2c)+a/3-c/3≤25/3+1/3=26/3.

The displayed fill attains the bound. Every integral subset is included in this relaxed set, so it too has value at most 26/3. Since integral subset values are integers, 8 is also a valid upper bound.

If the run is interrupted here, it has established 7≤optimum≤8, together with candidate {A}. It has not established optimality of A.

In the include-A branch, neither B nor C can also fit, so its best completion is A with value 7. In the exclude-A branch, B and C fit together and give 8. This meets the global upper bound, establishing that {B,C} is optimal. The algorithm obtained both a usable subset and a stopping reason.

Changed output: add an item D=(5,8) and ask for all optimal subsets. Once {B,C} has value 8, pruning a branch with upper bound 8 could lose the distinct answer {D}. Retain equality branches, or use a separate enumeration phase constrained to the established optimum value. The former “one optimum” exclusion answers a different request.

CMP.4:5.2 - Use a conflict, then revise its assumptions

Three tasks A, B and C must occupy slots 0 or 1. Every pair conflicts, so conflicting tasks must use different slots. After choosing A=0, propagation forces B=1 and leaves C with no allowed slot. The branch is infeasible. Choosing A=1 gives the symmetric conflict. Exhausting these two A choices proves that no assignment exists under these constraints.

If a third slot 2 becomes available, the earlier impossibility no longer applies. The construction A=0, B=1, C=2 is feasible. An implementation reusing conflicts learned under the two-slot domain must retain or reconsider that domain assumption. Searching faster with an obsolete conflict would prevent the useful new answer.