3 ms·

AFAIR first step of simplex method is to convert system of inequalities to system of equalities by adding weak variables and making tableau (matrix) of those. A

• eru 6y ago
  Simplex uses solving systems of linear equations as a building block. Most variants of simplex have exponential runtime on worst case input. (But they do well in practice.) Recently, some variants of simplex with polynomial runtime have been found. Solving linear equations was always known to 'only' take polynomial amounts of time at most. But the question is whether that's n^3 or n^2 or something better..
• vitus 6y ago
  (I'd be interested to see an average-case running-time analysis of Simplex that yields O(n^2.332) additions/multiplications, where n is the number of variables. Or even O(n^3). Because that's what's claimed here.) That's mostly correct. You end up with a system of equalities for _a subset_ of your points, which yields a single vertex. Ultimately with a linear program, you're trying to optimize an objective function, max w'x s.t. Ax <= b, x >= 0 (in canonical form). The x >= 0 constraint makes this nontrivial to translate from a linear equation Ax = b. If you magically knew the sign of each component of the solution, you'd be able to perform a simple variable substitution, but you generally don't, at least not without solving the system of equations. (And yes, you need that constraint, or else your LP is unbounded, and your solution ends up with a negative infinity in it.)