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