Re: [Help-glpk] GLPK complexity and scalability

[Michael Hennebry]

On Tue, 12 Feb 2008, Sam wrote:

> Secondly, does anyone know of any literature that details the complexity
> and scalability of GLPK?
> I am most interested in mixed integer programming.  According to Jurcik
> and Hanzalek
> (http://dce.felk.cvut.cz/hanzalek/publications/Hanzalek05b.pdf), GLPK
> can handle 100,000 constraints and 300 integer variables.  Is there any
> way of confirming this, and does there exist a big-oh complexity
> notation for GLPK ie. O(n), in terms of constraints and variables?

MILP is NP-complete.
Most with an opinion believe NP-complete problems to be superpolynomial.
LP is polynomial, but so far as I know,
no known simplex algorithm is polynomial.

My recollection is that there are 300-variable MILPs
that are challenging even for noteworthy commercial solvers.

With a broad enough definition of handle,
GLPK might be able to handle those prooblems.

-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."