Relaxation¶

Definition¶

A relaxation retains a problem's objective and removes or weakens constraints to obtain an easier problem. If $F$ and $F_R$ are the original and relaxed feasible sets, then $F\subseteq F_R$ $F_{R}$ .

Interpretation¶

A relaxation keeps the objective but allows more decisions. The relaxed problem is usually easier to solve, and its optimal value is a benchmark that the original problem cannot beat.

The feasible pentagon inside a larger shaded region obtained by dropping the constraint x s at most 40; the optimum moves from (40, 20) with value 180 to (50, 0) with value 200.

Dropping $x_s\le40$ from the Giapetto region adds the small red triangle $F_R\setminus F$ to the blue region $F$ . With the objective $4x_s+x_t$ the original optimum is $(40,20)$ with value $180$ ; in the larger region the best point is $(50,0)$ with value $200$ . That point violates $x_s\le40$ $40$ , so it is not a solution of the original problem, but it shows that no original solution can exceed $200$ .

The reason is $F\subseteq F_R$ $F_{R}$ : every original solution is also a relaxed one, so the best over $F_R$ is at least as good as the best over $F$ . The objective must stay the same, otherwise the two optimal values cannot be compared.

A relaxation does not always change the answer. With Giapetto's own objective $3x_s+2x_t$ $2 x_{t}$ , the same relaxation still has its optimum at $(20,60)$ with value $180$ , because $(50,0)$ gives only $150$ ; this relaxed optimum is feasible, and therefore optimal for the original problem.

Relaxations supply the second side of the optimization bounds, opposite to a heuristic; removing the 100-mile limit in the vehicle routing problem is an example. Later, integer programs are relaxed by dropping the requirement that the variables be whole numbers.

Key Results¶

For minimization, the relaxed optimum is no greater than the original optimum; for maximization, it is no smaller.
A relaxed optimum that is also feasible for the original problem is optimal for the original problem.
An infeasible relaxed optimizer need not have a strictly better value; equality can occur.

Examples¶

For the illustrated objective $4x_s+x_t$ $x_{t}$ , dropping $x_s\le40$ changes the optimum from $(40,20)$ with value 180 to $(50,0)$ with relaxed value 200.

Ignore the 100-mile refuelling limit in the routing example.
Remove integrality restrictions from an integer program while keeping its other constraints.

Prerequisites¶

Sources¶

OR Modelling · Week 1

Aliases: relaxed problem Symbols: subset

Last updated: 20 October 2026 03:02