Close
A relaxation of an optimization problem
is obtained by dropping some of the original constraints. As a
consequence, it has a larger feasible region and an extended
objective function.
Relaxations are typically much easier to solve than the original
problem (there is not much point in relaxing if the complexity
remains the same)
Relaxations allow us to obtain quick (partial) solutions that can be used to compute bounds on the original problem's objective function. Often however, they provide additional useful information that can be used to guide the search towards the optimal solution of the original problem.
Relaxations allow us to obtain quick (partial) solutions that can be used to compute bounds on the original problem's objective function. Often however, they provide additional useful information that can be used to guide the search towards the optimal solution of the original problem.