# Relaxation

## Contents |

### Introduction

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).

### Definitions

Let a polytope *P* of a graph *G* be contained in some polytope *Q*. Assume we need to optimize a linear function over *P*, i.e., need to solve the optimization problem

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.

### Example

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 (*x*_{1},*x*_{2})
with the function value *f*(*x*_{1},*x*_{2}) = − 23.
The arrow gives the direction of optimization.

### Theorem

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.

It holds

- .

Thus, the first statement is true. We can not apply the second statement since *x*^{R} = (1.4,2.4) is a unique optimum solution of the relaxation (*R*) and *x*^{R} ∉ *S* since 1.4 and 2.4 are not integer.