Slashdot Mirror
The Secret of the Simplex Algorithm Discovered
prostoalex writes "While the Simplex algorithm is considered to be one of the most widely used algorithms in complex networks, the reason for its efficiency has been so far not too clear. Daniel Spielman and Shanghua Teng discovered the secret of why the Simplex algorithm works so well by introducing imprecision into the worst-case scenario analysis. Their article will be published in Journal of ACM, although MIT Technology Review at the aforementioned link quotes Spielman expressing his doubts whether anyone will be able to make it through 80-page document filled with equations and formal explanations of the method."
The simplex algorithm is an algorithm for finding an optimal solution to a set of inequalities. (i.e. a system of constraints)
I say 'an optimal solution' because there can be more than one.
If viewed in space, the solution set for a simplex problem is a convex, generally closed region of space. In isn't neccessarily closed, but it is necessarily convex if it is closed, and it is never concave.
The simplex algorithm is an algorithm whereby some of the points/vertices of that solution space are visited in a search, until an optimal vertex (i.e. solution) is discovered.
It isn't completely fool-proof, you can get into states where the algorithm bounces between two vertices forever (looping), but for most well-stated linearly constrained problems (in any number of dimensions, really), the simplex is a good way to find an optimal solution.
Sorry, for the rather rambling explanation.
If you're truely interested, do a web search for "simplex method"
I wish I had mod points so I could mod you up. I agree. However, I think the problem is that this was posted to developers.slashdot.org and not to slashdot.org. 90% of the people on slashdot will never see this article.
"Times have not become more violent. They have just become more televised."
-Marilyn Manson
Disclaimer: IANAM (I am not a mathematician)
The simplex method solves a class of problems called "Linear Programming" or simply "LP". Many different kinds of network or graph theory problems can be phrased as an LP.
An LP consists of an objective function, and a number of linear contraints. For any given LP, there are 3 possibilites:
1. there does not exist a feasible solution
2. the LP is unbounded
3. there exist an optimal solution.
The goal is to determine an assignment to the variables in the linears system so that the objective value is maximized (or minimized) while satisfying every linear constraint.
There are other algorithms for solving LP, such as the cutting-plane algorithm. But the simplex algorithm exhibits many useful properties over other algorithms. For example, if the solution of a linear system has already been computed, and if the system changes slightly, one can compute a new solution quickly from the old solution, instead of recomputing from scratch. This is obviously quite useful for continuously updating routing tables on a network.
Some examples of LP are:
- single source shortest path (think routing)
- maximum st-flow
- minimum cost flow
The interesting thing to me is that according to theoretical analysis, the simplex method ought to have exponential complexity in the worst case. (Hence, all the fuss about Karmakar's algorithm, which has provably polynomial complexity.) But for almost all problems, the simplex method actually has polynomial complexity. What the researchers have discovered is why simplex runs as well as it does.
"Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time" by Daniel A. Spielman and Shang-Hua Teng
http://arxiv.org/abs/cs.DS/0111050
Quote (from the intro):
We propose an analysis that we call smoothed analysis which can help explain the success of many algorithms that both worst-case and average case cannot. In smoothed analysis, we measure the performance of an algorithm under slight random perturbations of arbitrary inputs. In particular, we consider Gaussian perturbations of inputs to algorithms that take real inputs, and we measure the running times of algorithms in terms of their input size and the variance of the Gaussian perturbations.
We show that the simplex method has polynomial smoothed complexity. The simplex method is the classic example of an algorithm that is known to perform well in practice but which takes exponential time in the worst case[KM72, Mur80, GS79, Gol83, AC78, Jer73, AZ99]. In the late 1970's and early 1980's the simplex method was shown to converge in expected polynomial time on various distributions of random inputs by researchers including Borgwardt, Smale, Haimovich, Adler, Karp, Shamir, Megiddo, and Todd[Bor80, Bor77, Sma83, Hai83, AKS87, AM85, Tod86]. However, the last 20 years of research in probability, combinatorics and numerical analysis have taught us that the random instances considered in these analyses may have special properties that one might not find in practice.
Oh wow! This takes me waaay back, to when I was an undergraduate.
Simplex, for those who aren't familiar with it, is a method of solving linear inequalities by representing the inequalities as a set of vectors which describe the outer bounds of the valid problem space. All space within those bounds is a "valid" solution to the inequalities.
Simplex assumes that some of the inequalities are contradictory. ie: that improving one variable will worsen one or more others.
The method works by starting off in some corner, and then progressing round the outer bounds until an optimal solution is achieved.
Operational Research is the science of applying the Simplex method to real-world problems. Early uses of OR (and, indeed, where the name originates) were in World War II, where the problem was to commit the fewest possible resources to achieve the greatest possible result with the fewest possible Allied casualties.
(Too few resources, and the enemy would likely be able to inflict more damage. Too many resources would reduce that damage, but would also reduce the number of operations you could perform.)
Modern uses of OR include production of prefabricated components from some material M, such that you get the most components out, and maximise the amount of M that is usable for some other production work, rather than having it as waste, while (at the same time) keeping additional production and processing costs below the savings made from more efficient use of the material.
In this case, the number of components (N) is one inequality. You need to equal or exceed the ordered number.
M is also an inequality - you want to order strictly less than you were ordering before, using the old process, or you've gained nothing.
M' (the usable remainder) is an inequality, equal or greater than 0 and less than M - W.
W (the waste) is the fourth inequality, which is greater than 0 and less than M - M'.
If the cost per unit M is C, and the amount of M needed before applying the Simplex method is I, then your savings are (I - M) * C.
This gives us the final inequality, where P (the increase in cost, due to increase in complexity) must be strictly less than (I - M) * C.
Without OR, these inequalities are horribly complicated, and "good" solutions are very hard to find. So most companies who aren't familiar with OR just don't bother. Such companies are easy to spot - the only way they can cut costs is to cut workforce.
Those companies with a good OR team can often make significant savings by improving the methods used. Such companies don't downsize when the going gets tough. Often, they'll simply revamp their methods and discover they can get more output for less cost, for the same labor force. These companies do brilliantly during recessions, as they can literally rob competitors of the remaining market, by out-producing and under-cutting anything that companies with poorer designs can do.
You can see from that that VERY few companies use OR in their day-to-day practices. The number of layoffs, blamed on "restructuring" but really the result of restructuring the wrong thing, has been horrendous.
OR isn't the perfect solution to all problems, and is only really designed to solve linear inequalities, but it's the best method out there. And it's about time it was understood.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Linear programming has become a necessary part of basic mathematical literacy. Most secondary-level Algebra 2 books include it with some rudimentary graphical methods for solving problems. I'd be surprised if most slashdotters didn't have some knowledge of linear programming.
It's been known for a long time that the simplex method is polynominal most of the time, and exponential in the worst case. It's also known that the exponential cases are metastable - a small perturbation in the inputs and they collapse to a polynominial case. So adding a little noise to the algorithm can kick it out of the bad cases.
But that's been an ad-hoc result. There hasn't been theory on how much noise to add, and when, and how. With sound theory underneath, algorithms that use noise injection to get out of the pathological states may become much more reliable.
Polyhedral collision detection, as used in games, works a lot like the simplex algorithm, and there are some pathological cases. The current best solution, "Enhanced GJK", is adequate but still has trouble in some "pathological cases". There are ways out of those difficulties, but they're inelegant. This new work might lead to a cleaner algorithm in that area.
There are other algorithms with similar properties, where the worst case is far slower than the average case. The simplex algorithm is for linear optimization. Many of the same difficulties appear in nonlinear optimization, where everything is more complicated and the methods all have severe restrictions. This may have applications in physics engines for video games, but it's too early to say.
In practice, simplex is so good that it still wins on many problems. However, all serious modern linear programming libraries also do interior point algorithms, because they are faster in some cases, especially when the problem is large. But speed is not everything -- even when the methods are about equally fast, simplex has some practical advantages, such as the ability to modify the problem slightly and continue efficiently from the solution of the original problem. This is important in integer programming.
This might be considered redundant, but this is the only explanation of the simplex method I can comprehend. IANA Linear Programmmer, so I may be wrong. Bear that in mind.
The simplex algorithm is a way of solving Linear Programming problems. Linear Programming problems require you to find an optimal solution for a series of constraints.
An example might be:
You are a baker, and you have 20 pounds of flour and a dozen eggs. You can make either loaves of bread (requiring four pounds of flour each) or cakes (requiring three pounds of flour and two eggs each). A loaf of bread sells for $1 and a cake for $4. How can you maximise or minimise your profit? (Those last two are the optimal solutions: minimising or maximising.) Let's say we want to maximise profit.
We can illustrate the problem on a 2-D graph, using one axis for the number of loaves and one axis for the number of cakes. We draw inequalities as lines on the graph to demonstrate the boundaries; for example, we can make at most six cakes (which then implies two loaves, making you $26 in total) and at least zero cakes (which then implies five loaves, making you $5 in total). Thus, if cakes = 6, loaves = 2 and if cakes = 0, loaves = 5. We can plot these as two points on the graph (e.g. at co-ordinates (6,2) and (0,5)) and then join the two points to get a line, which is one of our boundaries; on one side of the line are feasible solutions and on the other impossible ones (e.g trying to make more than six cakes).
In addition to this there are two more boundary lines, x=0 and y=0 (since we can't make fewer than zero cakes or fewer than zero loaves). These three boundary lines define a triangle, a polygon with three vertices. Inside the polygon are feasible solutions, on the outside...well, you probably can guess.
The simplex method would work here by taking advantage of the fact that the optimal solution must be at a vertex of this polygon defined by the problem. Here it works very quickly since there's only three vertices to try.
Now say we add another constraint, such as that loaves require 15 minutes to make, cakes require 25, and we only have four hours to bake what we need. This constraint would be represented by another axis on the graph, making it three-dimensional. Once again we would get a closed shape with straight edges; a 3-D shape instead of a 2-D polygon. Again, the optimal solution now lies at one of the vertices of this shape.
The simplex method can be used here. We can continue adding more constraints on resources. This adds more axes to the graphs and each time the number of dimensions is incremented. Some problems may involve shapes in 20 or 30 dimensions, or even more with tens of thousands of vertices (any of which could be an optimal solution). Here the simplex method uses a probabilistic method to make its way to the vertex which gives maximum yied (in this case, profit.)
I'll leave someone else to go into the specifics of how the simplex method traverses it. It's a very nice algorithm though, working in polynomial time.
Note to M1-ers: a curt but otherwise insightful message is not "Flamebait" or "Troll".