CMP.5:4 - Solution

State the original problem → construct the easier comparison → obtain its informative result → recover an admissible answer → bound the loss → choose the next use.

CMP.5:4.1 - State what the original candidate must satisfy

Name the original feasible set F, objective f, and whether it is minimized or maximized. Include the conditions that make a candidate usable in the receiving activity. An abstract numerical optimum can leave implementation, uncertainty or other subject conditions outside this particular problem; keep that boundary visible through C.29 and MMP.10.

State what would change the present decision: a better candidate, an infeasibility conclusion, a bound on possible improvement, or an answer within a given tolerance. This selects how much work to spend on the relaxation and recovery.

If several criteria matter, use the existing characterization and Pareto methods to preserve their trade-offs. The scalar constructions below apply to the chosen optimization question. They do not replace that broader comparison with a model-specific score.

CMP.5:4.2 - Construct the relaxation and derive the bound direction

For minimization, give a relaxed feasible set R, objective g, and a way of representing each x in F by i(x) in R, such that g(i(x))≤f(x). Where minima exist, this yields min_R g≤min_F f. For maximization, use the reversed objective inequality so that the relaxed optimum is an upper bound on the original optimum.

Common constructions include:

For the last construction, consider minimization with constraint h(x)≤0. For λ≥0, f(x)+λ*h(x)≤f(x) on original feasible points. Minimizing this expression over a larger, simpler set therefore supplies a lower bound if that minimum is obtained or bounded from below. The returned point can violate h(x)≤0; its usefulness as a bound does not make it an admissible answer.

Choose a relaxation by both its solving cost and its receiving use. A tighter mathematical description can be computationally worse, or make recovery harder. Existing portfolio and improvement methods can compare several candidate relaxations.

CMP.5:4.3 - Obtain a result with the strength its next use requires

Select an obtaining procedure for the relaxed problem. It may return an optimum, a candidate with a bound, a dual bound, or a heuristic estimate. Retain that distinction when using the result.

For minimization, a feasible relaxed point with value P gives an upper bound on the relaxed minimum. It does not by itself give a lower bound on the original minimum. To support such a lower bound, obtain the relaxed optimum or another justified lower bound L, for example from a feasible dual construction. MATH.20 supplies the bound argument; the relevant solver or proof supplies its computed value.

With an original feasible candidate of value C, the useful comparison is L≤original optimum≤C. A relaxed candidate’s value P may lie on either side of the original optimum. Keep it separately when it guides recovery.

Check the computational bound direction when rounding, stopping tolerances or incomplete solving can change an exclusion or conclusion. A conservative weaker bound can be preferable to an expensive stronger one. C.11.DUA selects extra computation or assurance according to its possible effect.

CMP.5:4.4 - Construct an admissible original candidate

Give an effective recovery operation when a candidate is needed. Rounding, selecting a subset, scheduling fractional allocations, repairing violated conditions or searching near the relaxed answer can serve this role. Test the original conditions after recovery and explain why the operation preserves or restores them.

A generic instruction to “round the result” is insufficient. Rounding upward can violate a capacity limit, while rounding downward can leave coverage incomplete. Derive the direction and any subsequent repair from the constraints.

Track objective change through recovery. If every recovered candidate has cost at most α times an attained minimizing relaxation value R*, then C≤α*R*≤α*original optimum for nonnegative costs and the stated approximation factor. If the relaxed solver returns only a feasible value P, the first inequality may still hold with P, but the comparison to the original optimum needs a separate bound on P or a direct comparison of C with a justified lower bound.

Recovery can fail or produce no better candidate. Retain an already admissible better candidate. A useful bound alone can still guide search or show that further improvement is too small to matter.

CMP.5:4.5 - Return to the original problem and choose the next move

Return the recovered candidate under its original conditions and the bound that applies to the original objective. For minimization, an additive gap C-L bounds how much the candidate can still improve. A ratio uses additional conditions, such as a positive denominator; a zero or negative lower bound does not support a generic ratio claim.

Use the result to adopt the candidate, stop at an adequate gap, guide a branch of CMP.4, tighten the relaxation, revise recovery or choose a different algorithm. The stronger relaxation is worthwhile only if its expected contribution warrants the extra work.

When the question or allowed operations change, recheck the representation i, bound direction and recovery. A bound from a more restrictive former problem may cease to constrain the new one. A bound that remains valid may also become too weak to be useful.