Originally posted by: beckywang

I'm just wondering what is LP running time, say, the problem has n variables and L constraints.

O(n^? L)

This depends on a number of things, including the algorithm you are using, whether you are interested in worst-case time or "average" time, and (if you want "average" time) over what class of problems you average. The simplex method is known to have a worst-case performance that is exponential in the problem dimensions, whereas the barrier (interior point) method is I believe known to be polynomial. On the other hand, I saw results years ago saying that "average" simplex performance was polynomial (but I don't recall how "average" was defined).

I think it is reasonable to say that run time tends to be more adversely affected by adding constraints than by adding variables, subject to the inevitable exceptions. (For instance, if you add a constraint that collapses the feasible region down to a single point, you likely will come out ahead.) I'd hesitate to generalize much beyond that, but it's possible the IBM folks, who have a library of test problems, have done some regression analysis on run times on those problems. I will say, though, that the impact of number of constraints on run time is almost surely worse than linear.

Paul

Originally posted by: beckywang

I'm hoping a more solid answer. Is the algorithm used in cplex LP solver  standard enough so your computer scientist could have an expression something like O(n^i  * L^j), where n = #variables, L=#constraints. I'd interested in knowing i and j.

It is more complicated than that. The complexity of the algorithm (among other things) depends on the pivoting rule and for each pivoting rule there is a (different) family of polyhedra that make the simplex algorithm run in exponential time. You can search the internet for "simplex algorithm complexity" and will immediately find lots of articles that talk about that. One starting point may be this paper and references therein.