Re: [Help-glpk] Linear Programming Relaxation

[Andrew Makhorin]

> 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.