CMP.5:1 - Problem frame

Use this when an optimization problem is difficult to solve directly, but weakening some of its restrictions or costs gives a more accessible problem. Its solution may help construct a candidate for the original problem, or bound how much better the current candidate could become.

The situation occurs in combinatorial selection, scheduling, routing, program synthesis and continuous optimization. A relaxed solution can make an inaccessible search informative, but it may violate the original conditions. For example, fractional choices are useful for reasoning about an indivisible selection even though the fractions cannot be implemented as that selection.

The gain is a useful bound, a recovered admissible candidate, or both, together with a reason they apply to the original question. The reader needs feasible sets, an objective and inequalities. MATH.20 supplies further bound reasoning; a solver for the selected relaxed problem may be obtained as a separate contribution.

Use an available direct method when it already produces the needed result at acceptable cost. Approximation alone does not make a problem a relaxation: this method needs the correspondence and inequality that support its bound. A good heuristic can still be used without that bound, with its result stated accordingly.