Hi Cenk, On Sat, Oct 29, 2011 at 7:36 AM, Cenk Toker <[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] > https://lists.gnu.org/mailman/**listinfo/help-glpk<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
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
