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.
I've got mod points and would like to mod you off-topic, but I'll just wag my toungue at you instead. Your NZ Jetsteram thingy sounds kinda interesting but you give no details. You should include your submission in your bitch & moan post, or at a minimum, include it in your journal. You have no journal entries - write some!
PS. please don't waste our time trying to make something "on topic" by adding useless filler.
What the hell? I would mod you off topic if I had mod points. Some people _are_ going for a CS PhD...why can't they have stories, too? Besides, this isn't on the front page, and obviously only a few people are reading it, anyway. Cut 'em some slack.
:Wq
Not an editor command: Wq
Waste of time this may be, it is still an interesting waste of time. I find it refreshing that occasionaly there are bits of complex math (and other stuff) that gets posted sometimes. And it makes my course work look easier.
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.
ILP has time of exponential complexity
ILP was researched by millions of persons for >50 years, :P
JCPM (c)
Smale, Blum et al have a really good book called "Complexity and Real Computation" which analyzes the Simplex Method and other algorithms at some length. It tries to build up a theoretical foundation for complexity analysis of numerical algorithms (where the objects being computed are real numbers), just like traditional complexity theory (with Turing machines) analyzes algorithms which compute on discrete sets (e.g. bits).
Just one thing. O(N) is less than O(N log N) so I assume that you meant the worst case of quicksort is O(N^2). I never studied its complexity, so I really don't know.
This could work, I believe, but only if Quicksort exhibits the same sort of lets say "poly time affinity" (for lack of a better description) that the Simplex method does. Not all algorithms have this characteristic.
It is worth looking into, though. If this is (statistically) true, one could try to solve in paralell 3 or 4 "pertubed" quicksorts, and still come out ahead of just a quicksort that exhibits O(N^2) because it is "a worst case". Of course this would only be useful for large values of N.
Yes, worst case for Quicksort is O(n^2). As I recall, this requires that the data is already sorted but in the opposite order you want.
Dyolf Knip
what else can be said. I'm always amazed at all the complexity that is involved in modern computing and the mathematics that make it happen.
âoeTolerance applies only to persons, but never to truth. Intolerance applies only to truth, but never to persons.
how are they ripping people off?
do you have some inside knowledge?
What would Brian Boitano do?
Another factor may be that until you get a ways into advanced problems most of the applications linear programming and the simplex method are pretty much cookbook these days - but most courses in linear programming are a semester long - so its hard to tell a cs major that taking a course in LP is more important than taking a course in Visual Something-or-Other. As a professor type though, I always try to mention some of the techniques and ideas I've seen in other areas - even when not necessarily applicable to the class I'm currently teaching. This includes things like LP - but also things like cryptic crosswords, Intercal and so on. Something seen by some students as a Good Thing, by others (most, probably) as a Waste of Time.
Me, I'm going to take a look at the paper and see what I can get from it. The posted information on what is said looks very interesting indeed.
Yeah, I meant O(N^2), but was posting when tired. :)
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
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.
Say, does anybody know what ever happened with Karmarkar's algorithm? The early press releases when it came out said it was going to revolutionize Operations Research (specifically replacing Simplex). It doesn't appear this has happened. What's the scoop?
There's no time to stop for gas, we're already late.
Never underestimate the power of stupid people in large groups. This is why it's a Good Thing that hardly anything is really democratic; the masses just aren't interested and thus ignorant.
Please correct me if I got my facts wrong.
You won't get it on the fron page cos it's in NZ, not NY or similar. This is /. - deal with it.
Having said that, write your diatribe here and then we'll know what you're on about.
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".
Don't mod it down just because you don't understand what it means, you stupid friggin' crackhead.
And that is why I prefer heap-sort (_always_ O(n log n)).
I suppose it would only be marginally slower to implement; compare the neighbours and shift to the best one.
Note to M1-ers: a curt but otherwise insightful message is not "Flamebait" or "Troll".
Let alone read the article.
Sigs are like bumper stickers.
I catch the idea of what Simplex does but wonder how it compares to other algorithms? For example, a genetic algorithm (say using multi-objective GA) can be used to solve LP's as well without (I think) pathological cases but with an uncertainty on the time to arrive at a solution. Is Simplex preferred because of simplicity, efficiency, or what? TIA
In fact to get O(n^2) it doesn't matter which way the data is sorted. The algorithm works by choosing an element as a "pivot", then dividing the remaining data into two sets, the set of data lower than the "pivot", and the set greater than the "pivot" (and then sorting those two sets recursively). The algorithm is efficient when the two sets are of roughly equal size (as will often be the case when the data is random), but O(n^2) when one is significantly larger than the other.
Since most implementations pick the "pivot" as the first item in the list they're sorting, this gives the empty set as one of the sets, and the rest of the data as the other set, which is of course the worst case...
Applying a random permutation to the input data, or choosing the pivot randomly from the set, can help if you know in advance that the data is likely to be biased in such a way that the two sets will often have different sizes.
Need to type accents and special characters in Windows? Use FrKeys