[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] GLPK complexity and scalability
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] GLPK complexity and scalability |
Date: |
Tue, 12 Feb 2008 09:18:38 -0600 (CST) |
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."