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:
| Construction | Why the comparison can hold | Main design risk |
|---|---|---|
| Drop a constraint or allow fractions instead of integral choices | Every original feasible point remains available with the same objective. | The relaxed optimum may be far from any original feasible candidate. |
| Make transitions or costs more permissive | Every original path remains represented at no greater cost in a minimizing problem. | The relaxed route may use operations forbidden in the original problem. |
| Replace a coupling constraint by a multiplier term | The signed term gives a bound on the objective for original feasible points, while the relaxed computation may separate into smaller problems. | A wrong sign or an unsupported minimizing step reverses or loses the bound. |
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.