[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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?
Please see:
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.