> 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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
