0
$\begingroup$

What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints

$\endgroup$

1 Answer 1

4
$\begingroup$

It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form $$\min c^T x\,\,\,\,\text{s.t.}\,\,\,\, Ax=b,\, x \geq 0$$ Linear algebra tells us that this only has a solution if the rank of the matrix $A$ is at least the dimension of $b$, which for us is $m$. But $\texttt{rank}(A) \leq \min\{n,m\}$ so in order to have a solution at all, we need $n \geq m$.

The number of pivots that occur during the Simplex algorithm (assuming you implement a pivoting rule that prohibits cycling) is at most the number of different bases you can make with the columns of $A$, which is $\binom{n}{m} < 2^n$ (since $m \leq n$). Thus the number of pivots is $O(2^n)$.

However, if you want to solve a Linear Program that is not in SEF then you need to first put it into SEF. When you do this any "free" variable (one not constrained to be nonnegative or nonpositive) is split into two and we introduce "slack variables for each inequality constraint. If we let $n'$ be the number of variables in this new version of the problem, then we have $n' \leq 2n + m$ and thus the number of pivots is $O(2^{2n+m})$. [If the original problem had nonnegative variables, but all inequality constraints, then $n' = n + m$ which is probably the case in the second variant you found.]

However, both of these don't factor in the running time of each pivot. I have never seen a careful analysis of the running time of each pivot, and it will depend on implementation, but I think a straightforward implementation and analysis would achieve a runtime of $O(n+m^\omega)$, where $\omega$ is the number such that you can invert an $m \times m$ matrix in $O(m^\omega)$ running time. Thus I would say that the running time for solving an arbitrary linear program with the simplex method is $O\left((n+m^\omega)2^{2n+m}\right)$ but I am not confident about the $(n+m^\omega)$ factor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.