Re: [Help-glpk] Theoretical complexity

[Andrew Makhorin]

> Please, do you have any idea about the time theoretical complexity of
> a linear program and a MILP program. In other words, how to compute
> the worst time complexity for an LP and a MILP based on the number of
> variables and constraints ?
> 

LP can be solved in polynomial time (e.g. with Kahchiyan's ellipsoid
algorithm), though the simplex method may require exponential time in
worst cases [Klee and Minty]. Most MIPs are in NP, and, assuming that
P != NP, any exact method to solve such a MIP requires exponential time
in worst case. The number of variables and constraints do not reflect
the MIP complexity.