Re: [Help-glpk] Simplex vs. Interior-Point

On Sat, Oct 29, 2011 at 7:36 AM, Cenk Toker <address@hidden> wrote:

Dear All,

I have recently used GLPK to solve a sparse LP problem (a resource allocation problem for OFDMA) and found that the simplex solver is much faster than the interior-point solver.
The problem has a special structure where all vertices are integer. Therefore, although the original underlying problem is an IP one, even if we relax it to an LP we still get the optimum IP solution.

I performed a computational complexity analysis on an interior-point algorithm I developed for the LP problem and found that it is O(K N^2). Since simplex solver runs faster than the interior-point one, I assume that the computational complexity of the simplex solver being used in GLPK is lower than the other one.

Please note that worst case complexity analysis not necessarily express well how algorithms behave in practice.

The simplex algorithm is well know for having a horrible wort case complexity but performs quite well in practice.

http://en.wikipedia.org/wiki/Simplex_algorithm
http://en.wikipedia.org/wiki/Interior_point_method

[]'s

Haroldo

Which simplex algorithm is being used in GLPK and how can I find/calculate its computational complexity?

Thank you.
Regards,
Cenk.

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

From:	Haroldo Santos
Subject:	Re: [Help-glpk] Simplex vs. Interior-Point
Date:	Sat, 29 Oct 2011 12:56:46 -0200