[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Linear Programming Relaxation

From: David Bremner
Subject: Re: [Help-glpk] Linear Programming Relaxation
Date: Wed, 25 Nov 2009 08:54:12 -0400
User-agent: EMIKO/1.14.1 (Choanoflagellata) FLIM/1.14.9 (Goj ō) APEL/10.7 EasyPG/1.0.0 Emacs/23.1 (i486-pc-linux-gnu) MULE/6.0 (HANACHIRUSATO)

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.  


reply via email to

[Prev in Thread] Current Thread [Next in Thread]