RC Loh wrote:
>Just to confirm on question (2). I understand that GLPK also uses >Interior Point method. Isn't the Interior Point method a polynomial >time method? Yes it is, but for linear programming, not for integer or mixed integer programming. >So with the Linear Programming Relaxation, the GLPK still does not >runs in polynomial time? A MIP solver needs to solve a whole search tree where each node is an LP relaxation, and in general the number of LP relaxations solved is not bounded by a polynomial in the input size. There are many books where this is explained; I happen to know "A First Course in Combinatorial Optimization" by Jon Lee, see Chapters 6 and 7. David _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
