What is the average time complexity of the simplex method for solving linear programming? Is it polynomial or logarithmic?
I believe it is polynomial in the number of variables and constraints. You may want to read the Wikipedia page: https://en.wikipedia.org/wiki/Linear_programming
I believe the complexity of the simplex method is still an open research question; correct me if I'm wrong.
For most pivot rules (i.e., the rule to decide which variables enter and leave the basic solution), there exist counter examples of linear programs with exponential computation time. The question is whether a pivot rule exists that solves all linear programs in polynomial time.
The exponential time counter examples are often rather extreme. Small perturbations of the model parameters typically lead to problems that can be solved in polynomial time, hence it is quite rare to encounter an exponential time problem in practice.
I would have a look at this lecture/paper: http://theory.stanford.edu/~tim/f14/l/l15.pdf
Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time
https://doi.org/10.1145/990308.990310
The Polynomiality of the Expected Number of Steps, see in The Simplex Method A Probabilistic Analysis
https://doi.org/10.1007/978-3-642-61578-8
Let's step by step...
Some Linear Programming problems are solved in polynomial time complexity, as in the case of the Inner Point Methods (also referred to as barrier methods).
The Karmarkar algorithm, for exemple, works in polynomial time and provides solutions to linear programming problems that are beyond the capabilities of this method we are analyzing (the Simplex Method). However, as far as I remember, the Simplex is a method that works in exponential time (seen the case of the traveling salesman problem(or the problem of the Caxeiro Viajante as we would say in Portuguese)).
An algorithm with polynomial complexity is one that has its function of complexity, f (N), plus a function g (N) of polynomial order (eg g (N) = N ³).
Algorithms with polynomial complexity are computationally treatable, requiring a runtime limited by a polynomial function.
Since exponentials are typical of solutions related to brute force, which is very characteristic of the Simplex Method, just remember the tableau scheme that Simplex uses to extrapolate the results in an interactive way in order to find a basic solution that can meet the required requirements.
A good reference source is the paper M. Todd, The many facets of linear programming, Math. Progr., 91:417-436, 2002.
see
https://global.oup.com/academic/product/operations-research-9780198096184?cc=us&lang=en&
One problem is that there are several different variants of the simplex method (primal, dual and criss-cross) and several pivot selection rules (steepest edge, DEVEX, random, etc.) So it doesn't make much sense to talk about "the" simplex method.
This paper may however be of interest:
http://dl.acm.org/citation.cfm?id=1132524
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics