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