[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Differences between LP Relaxation and Lagrange Relaxatio
Re: [Help-glpk] Differences between LP Relaxation and Lagrange Relaxation
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
> 1) What is the differences between linear programming (LP)
> relaxation and Lagrange 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
> 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