3 ms·
When I hear linear programming I always remember this method https://en.wikipedia.org/wiki/Ellipsoid_method https://en.wikipedia.org/wiki/Ellipsoid_method. It i
by oselhn 10y ago
When I hear linear programming I always remember this method https://en.wikipedia.org/wiki/Ellipsoid_method https://en.wikipedia.org/wiki/Ellipsoid_method. It is nice example of algorithm which is not useful for programming only for mathematicians (I believe it was used as proof that linear programming is in P). I think that most of the programmers will have really hard time to implement it and also it is on average slower than simplex method despite a fact that simplex is not in P and this algorithm is.
- mschulze 10y agoIt's been a while since I studied mathematics (and I wrote my thesis in optimization), but at the time it was not clear if simplex is in P or not. I think no one has found a selection function for variables that is always polynomial.
- oselhn 10y agoSee this https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency. But simplex is still widely used because real problems are usually solved in polynomial time. You have to design your problem to not finish in polynomial time. But I am not a matematician this opinion it just how I understand it.
- Pamar 10y agoI vaguely recall that Soviet planners used something based on n-dimensional ellipsoids (instead of Simplex) to optimize resources allocations of Aereoflot flights but I cannot remember anything more specific, alas. (I read this on the magazine of my country's equivalent of ACM in '80s and it somehow stuck with me all these years)