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 instead of , i.e.,
then we call it a linear relaxation. We sometimes also call itself a relaxation of .
Let two problems
be given. The problem is called relaxation of problem if the following conditions are satisfied:
- for all elements .
Condition says that the set of feasible solutions of the relaxation contains that of , i.e., all elements feasible for the original optimization problem remain feasible for the relaxation. Condition 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 and are equal.
Then is a relaxation of iff is a subset of .
Therefore the notation is also used for sets. A set is called relaxation of set iff the inclusion holds.
Often a relaxation of a given problem is obtained by skipping some of the information that is used to describe the set , e.g, integrality constraints or other restrictions that are difficult to handle.
Consider the following discrete problem :
Considering this problem we have and
To obtain a relaxation we skip the integrality constraints in the set . Then we have a relaxation with and
The feasible set of problem (P) as well as its continuous relaxation are shown in the figure above. In this figure and are described by the points and the red area, respectively. The additional line in the figure shows all point with the function value . The arrow gives the direction of optimization.
The optimum function value of the relaxation is a lower bound for the optimum function value of problem .
Furthermore, if the relaxation has an optimum solution with and , then is an optimum solution for problem , 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 is a unique optimum solution of the relaxation and since and are not integer.