B.5.TU:5.3 - Keep a useful bound when the optimizer cannot be enacted

A planner learning optimization must select whole jobs for four available hours. At most one A-job is available, taking three hours for stipulated value 5; at most two B-jobs are available, each taking two hours for value 3. Durations and values add in this constructed problem.

A linear relaxation permits real counts 0 <= x <= 1, 0 <= y <= 2 with 3*x+2*y <= 4. It returns x=1, y=0.5, value 6.5. Recover the argument: the time condition gives y <= (4-3*x)/2, so 5*x+3*y <= 6+0.5*x <= 6.5; the returned pair attains that limit.

For the actual whole-job choice, enumerate the alternatives. With A selected, no B fits and value is 5. Without A, two B-jobs fit and value is 6. Select two B-jobs. The fractional optimizer has still supplied a useful bound: no whole-job arrangement can attain value 7 because every such arrangement is also admitted by the relaxation.

The use of the theory changes with the question. Selecting work needs an attainable arrangement; excluding a target can use a bound. The practitioner needs to recover that relation before deciding whether a further optimization step is useful. B.5:5.4 also works the changed five-hour case.