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

[Cenk Toker]

Thanks for the answer Haroldo.

Does GLPK implement the "textbook" simplex method?
I am not an computational complexity analysis expert (not even an algorithm one).  As far as I know there is no simple way to calculate the complexity of the simplex algorithm. As you wrote there exist some worst case analysis, e.g. the one in Bazaraa MS, Jarvis JJ, Sherali HD. Linear Programming and Network Flows. 4th edn., Wiley Interscience Publication: New York, 2010.

For the special structure of my problem I was able to calculate the complexity of the interior-point algorithm. Since simplex in GLPK is running faster, I am wondering whether I can do the same for the simplex algorithm. If there exist any references (which an electrical (Comms.) engineer can understand) you may recommend, I would be more than happy to hear them.

I ask these questions for the revision of one of my papers. Reviewers sometimes are not very considerate and ask for the computational complexity of algorithms you just use, which can be difficult to calculate :(.

Regards,
Cenk.

On 29.10.2011 17:56, Haroldo Santos wrote:

Hi Cenk,

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

--
=============================================================
Haroldo Gambini Santos
Computing Department - Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: www.decom.ufop.br/haroldo/
 
"Computer science is no more about computers than astronomy
is about telescopes." Edsger Dijkstra
 

-- 
--------------------------------------------------------------------
Cenk Toker, PhD, SMIEEE, MIET, TA2ACT
Associate Professor

Hacettepe University
Department of Electrical and Electronics Engineering
Beytepe, 06800
Ankara, Turkey

Tel: +90-312-2977006
Fax: +90-312-2992125
email: address@hidden
URL: http://www.ee.hacettepe.edu.tr/?lang=e&link=400201&sublink=217
--------------------------------------------------------------------