[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Theoretical complexity

From: Andrew Makhorin
Subject: Re: [Help-glpk] Theoretical complexity
Date: Fri, 25 Oct 2013 12:44:24 +0400

> 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.

reply via email to

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