Re: [Help-glpk] Linear Programming Relaxation

[David Bremner]

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