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
<[email protected]
<mailto:[email protected]>> 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
[email protected] <mailto:[email protected]>
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 <http://iceb.ufop.br>
home/research page: www.decom.ufop.br/haroldo/
<http://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: [email protected]
URL: http://www.ee.hacettepe.edu.tr/?lang=e&link=400201&sublink=217
--------------------------------------------------------------------
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
