[Top][All Lists]

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

Re: [Help-glpk] Linear Programming Relaxation

From: RC Loh
Subject: Re: [Help-glpk] Linear Programming Relaxation
Date: Wed, 25 Nov 2009 13:08:34 +0800 (SGT)

Hi Andrew,
Thank you very much for your reply.
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?
So with the Linear Programming Relaxation, the GLPK still does not runs in polynomial time?


From: Andrew Makhorin <address@hidden>
To: RC Loh <address@hidden>
Cc: address@hidden
Sent: Tuesday, 24 November 2009 11:10:13
Subject: Re: [Help-glpk] Linear Programming Relaxation

> I have an Integer Program and I run the GLPK to solve it. I noticed
> that the GLPK automatically turns ON the Linear Programming Relaxation
> without me specifying it. I have 4 questions:

> 1) Can I turned OFF the Linear Programming Relaxation? Because I want
> to let the GLPK run without the relaxation to see how long does the
> program takes to produce a result.

Solving LP relaxation to optimality is needed to start the MIP

> 2) Can I say that we the Linear Programming Relaxation turns ON, the
> program runs in polynomial time?

No. Neither the simplex method nor the branch-and-bound method is
a polynomial time algorithm.

> 3) I understand that with the Linear Programming Relaxation turns on,
> the programs actually produce an approximate result. But GLPK actually
> corrected the approximated results automatically. Can I turn OFF the
> correction of the approximation? Because I want to see the results
> without the correction.

> 4) How GLPK correct the approximated results?

Optimal solution to LP relaxation is not an approximation to MIP
solution, because it may be integer infeasible; it gives a global
bound to MIP optimum.

New Email names for you!
Get the Email name you've always wanted on the new @ymail and @rocketmail.
Hurry before someone else does!
reply via email to

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