> 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. _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
