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

Firstly, you need to be specific about your meaning of complexity. Mathmatically complexity is defined by irreducibility. A problem is not more complex because it takes glpk longer to solve it, or the special case interior method described below.

Secondly we need to think about glpk solving things. The simplex algorithm simply rearranges a matrix. At each pivot the matrix contains the same information, is technically the same matrix. There is a particular arrangement which enables a human, or a computer following human instructions to read the information contained easily. A little like a rubic cube has a human pleasing arrangement, but however arranged is the same cube.

Thirdly, I have presented a number of examples which demonstrate the use of a constraint matrix as if it were a computer program. I have argued that it can be expressed as a sequence of Dauphantine Equations and therefore mathmatically is a computer program. It is well known that there is no meaningful description for the complexity of a computer program.

You might like to compare bubble sorts with pivot sorts. For a random input the pivot sort will be quicker. If it isn't you have at least discovered that the data is not random but chosen by your worst enemy. But if the data isn't random it is less complex. Bubble sorts and pivot sorts are computer programs, how would you meaningfully describe either as more complex?

The papers described below have chosen data which when changed can mathmatically be ordered as more or less complex. They have then produced a one to one mapping of simplex computational time to data, and presented this. They do not argue that in the general case you can determine the complexity of the data and determine the length of time it will take the simplex algorithm to finish.

Look at huge.mod in the glpk examples. You may change the size of the test set and map that against time taken by glpk. The larger the data set the longer it takes but however large you make it the complexity is the same. If you use the data presented, very simple. If you replace it with genuinely random numbers very complex. But glpk doesn't know the difference.

Nigel Galloway

address@hidden

On Saturday, October 29, 2011 10:45 PM, "Cenk Toker" <address@hidden> wrote:

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
-------------------------------------------------------------------- 
_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

From:	Nigel Galloway
Subject:	Re: [Help-glpk] Simplex vs. Interior-Point
Date:	Sun, 30 Oct 2011 07:46:13 -0700