help-glpk
[Top][All Lists]

## Re: [Help-glpk] Differences between LP Relaxation and Lagrange Relaxatio

 From: Andrew Makhorin Subject: Re: [Help-glpk] Differences between LP Relaxation and Lagrange Relaxation Date: Mon, 21 Jul 2008 20:38:33 +0400

```> This question is not directly related to the usage of glpk but it
> is related to linear programming in general. I could not find the
> answer to this question in the Internet so I hope I can find an answer
> here.

> 1) What is the differences between linear programming (LP)
> relaxation and Lagrange relaxation?

http://en.wikipedia.org/wiki/Linear_programming_relaxation
http://en.wikipedia.org/wiki/Lagrangian_relaxation

> 2) Can LP Relaxation and Lagrange Relaxation be used together to solve
> a problem?

In principle, yes.

> 3) By using LP Relaxation, can the problem be solved in polynomial
> time?

> 4) By using Lagrange relaxation, can the problem be solved in
> polynomail time?

It depends on the method used. For example, the simplex method is
not a polynomial algorithm, though it is known that LP is in the P
complexity class.

```