[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
> (, 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."

reply via email to

[Prev in Thread] Current Thread [Next in Thread]