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."
Euler was wrong?? I don't think that argument holds water. While 80 pages is long for a proof it looks like more of a philosophical diatribe than anything else.
But what is the simplex algorithm? Or at least, what problem does it solve? I've never heard of it before, and the linked description is either not describing what the algorithm actually does or is too dense for me to understand.
The idea of an algorithm that is used on all kinds of major networks, but no one knows why it works sounds rather intriguing, but can anyone offer any background?
Thanks in advance.
I used to bulls-eye womp-rats in my pants
Does anyone else here think that it's sad that the number of comments for this story, which represents a significant breakthrough in mathematics and information theory, is less than 5 whereas the once-every-three-days stories about how Microsoft is screwing over their customers or some newfangled thing for Linux has been released always generates 100s of comments?
The simplex method is widely used in Operations Research and many classic 'computing' problems. For example, IIRC the "Shortest Route" problem is managed (solved is too strong a word, for reasons explained in the previous post). For instance, if your business has three warehouses, 20 trucks and 10 major customers, how do you determine the cheapest way to supply all the customers with the goods they need? The 'best result' often seems counterintuitive.
:O)
It's also used by the airlines to figure out how to schedule planes. There are uses in physics, social sciences, etc. I don't know any offhand, but I wouldn't be surprised if at one time it was used to assist in scheduling computing resources. It's also widely used in complex pricing models.
It's also a way to decide, given 10 women and 10 men (or any number), which ones are most likely to get along with each other based on their preferences and characteristics.
It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
"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)
most of us working on a Masters in Mathematics are too busy to comment, sorry.
What a poorly chosen name. Simplex is pretty complex when compared to some of the other things I studied in math class. I always wondered why they called it simplex.
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.