In general a relaxation of a problem aims at making a problem (computationally) easier by weakening the constraints to the set of solutions. Therefore the number of solutions for a relaxation increases. In optimization this is often used to compute a bound on the optimum value if it is hard to compute (cf. branch-and-bound, branch-and-cut).
If we optimize over Q instead of P, i.e.,
then we call it a linear relaxation. We sometimes also call Q itself a relaxation of P.
Let two problems
be given. The problem (Q) is called relaxation of problem (P) if the following conditions are satisfied:
- for all elements x ∈ S.
Condition (a) says that the set of feasible solutions of the relaxation contains that of S, i.e., all elements feasible for the original optimization problem remain feasible for the relaxation. Condition (b) makes sure that the optimum of the relaxation is a lower bound for the original optimization problem.
Often one finds in applications that the functions f and g are equal.
Then (Q) is a relaxation of (P) iff S is a subset of R.
Therefore the notation is also used for sets. A set R is called relaxation of set S iff the inclusion S ⊆ R holds.
Often a relaxation of a given problem (P) is obtained by skipping some of the information that is used to describe the set S, e.g, integrality constraints or other restrictions that are difficult to handle.
Consider the following discrete problem (P):
Considering this problem we have and
To obtain a relaxation we skip the integrality constraints in the set S. Then we have a relaxation (Q) with g = f and
The feasible set S of problem (P) as well as its continuous relaxation R are shown in the figure above. In this figure S and R are described by the points and the red area, respectively. The additional line in the figure shows all point (x1,x2) with the function value f(x1,x2) = − 23. The arrow gives the direction of optimization.
The optimum function value of the relaxation (Q) is a lower bound for the optimum function value of problem (P).
Furthermore, if the relaxation (Q) has an optimum solution with and , then is an optimum solution for problem (P), too.
We check the statements of the theorem for the example.
Thus, the first statement is true. We can not apply the second statement since xR = (1.4,2.4) is a unique optimum solution of the relaxation (R) and xR ∉ S since 1.4 and 2.4 are not integer.