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?
Rdgs,
Paul
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
search.
> 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.