Name: Linear network optimization
ISBN: 9780262023344

What Hacker News says

ten_fingersAug 2012

The specific problem is a special case of the 'assignment' problem. First cut, it looks like 0-1 integer linear programming and, thus, maybe in NP-complete.

Looked again, the problem is least cost network flows. That is a linear programming problem. In that problem, if the arc capacities are integers, and in this practical problem they are, then the simplex algorithm can easily start with a basic, feasible, integer solution, and the simplex iterations will automatically maintain an integer solution and, then, find an optimal integer solution which provides the optimal assignments.

When we apply the simplex algorithm to least cost network flows, we get to take advantage of the fact that the problem is not fully general linear programming, and the advantage we can take is huge. E.g., the arcs of a basic, feasible solution form just a spanning tree in the network; the 'entering variable' in the simplex algorithm just adds an arc to the spanning tree and, thus, yields a circuit; we run flow around the circuit in the direction that makes money until the flow on some arc is zero and that arc determines the 'leaving variable'. Using the 'strongly feasible' basis ideas of W. Cunningham, long at Waterloo, we can avoid cycling.

But, the simplex algorithm for least cost network flows, as far as I know, is not guaranteed, worst case polynomial.

However, read:

Dimitri P. Bertsekas, 'Linear Network Optimization: Algorithms and Codes', ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.

and in there, or elsewhere in Bertsekas's work, is an algorithm for least cost network flows and that is worst case polynomial.

Done.

And I covered nothing classified!

And for this thread, we have a "how to" with high precision from some applied math.

thread

graycatOct 2019

In grad school, I was lucky enough to have some especially well qualified professors of optimization including linear programming. I've applied it in business and taught it, both graduate and ugrad, in a business school. So, here I add a little to the original post:

There is no need to explain the meaning of simplex or mention that polytope. The simplex algorithm just works with a polytope and never makes any use of the fact that there can be simplex polotypes.

Or, to be more clear, "simplex algorithm" is the name of the algorithm, but there is no need to mention simplex again.

He mentioned that the feasible region might go off the paper and seemed to suggest that that could cause a difficulty. Actually, no. Instead, a linear programming problem is feasible or not. If it is feasible, then the objective function is bounded or unbounded. The simplex algorithm handles all three cases. That the feasible region is unbounded does not mean that the objective function is, and, again, even if the objective function is unbounded the simplex algorithm handles that, i.e., routinely discovers that fact and reports it.

He hints at cycling; can solve that nicely with the R. Bland anti-cycling rule. That rule is easy to program and can be used in practice but is also an especially elegant way to prove that the simplex algorithm can always work, that is, ends with the problem is feasible or infeasible and if feasible with an objective function bounded or unbounded and if bounded finds an optimal solution. That this situation is true means that we have just one baby step to showing the core saddlepoint theorem of two-person game theory, e.g., the game paper, scissors, rock.

Some of the most interesting linear programming problems are to find the least cost way to move flow through a network where each arc has a maximum flow capacity. Here the simplex algorithm specializes in an astoundingly nice way (end up working with spanning trees). But cycling is still possible. There is an elegant, easy to program anti-cycling rule in (my TeX markup for D. Knuth's TeX)

William H.\ Cunningham and John G.\ Klincewicz, ``On Cycling in the Network Simplex Algorithm'', {\it Mathematical Programming,\/} Volume 26, pages 182-189, North Holland, 1983.\ \

Disclosure: Cunningham was one of my professors.

Why so "interesting"? Now a huge question is how to attack linear programming problems where we ask that some or all of the variable values be integers. Some well informed people regard this problem as the most important in pure and applied math and computer science. Integer linear programming was one of the examples for the importance of the computational complexity question P versus NP; to be more clear, in principle integer linear programming is in NP-complete. There are more details on this question at Clay Mathematics where P versus NP is one of their million dollar prize problems.

Well, for that network flow problem (i) if the arc flow capacities are all integers, (ii) if the problem is feasible with a bounded objective function, (iii) if we start with a feasible integer solution, then the simplex algorithm, including modified for network flows (with the spanning trees), and with an anti-cycling rule will in the simplex algorithm iterations automatically maintain a feasible integer solution and end with an optimal integer solution. In practice, this fact about integers makes a nice dent in the struggle of integer linear programming; that is, surprisingly often in practice integer linear programming problems (in principle in NP-complete) are merely just such network flow problems. Once I had that situation for a marketing resource allocation problem and another time for a NASA signal allocation problem.

The simplex algorithm can be explained nicely as just a slight tweak of standard Gauss elimination for systems of linear equations.

Indeed, the algorithm is so simple that when it ends, terminates, it is easy just to read off a lot of additional, possibly valuable, information about the problem. E.g., if are mixing feed for chickens, then can learn what one more pound of corn would be worth; here we can have what some economists call shadow prices. For one more, it can be easy to change some of the original data, add some constraints, etc. and for surprisingly little additional work solve the problem again. Such work after the algorithm terminates is called post-optimality.

He didn't give any real examples; the usual first example is the diet problem for mixing feed, e.g., chicken feed, to give the chickens the nutrition they need at least total cost. I happened to have written up that problem earlier this week and posted it at

https://themusingsofthebigredcar.com/the-technology-we-dont-...

He gave no references. Here are some old but good references, just from my personal library with my markup for D. Knuth's TeX:

Va\v sek Chv\'atal, {\it Linear Programming,\/} ISBN 0-7167-1587-2, W.\ H.\ Freeman, New York, 1983.\ \

Mokhtar S.\ Bazaraa and John J.\ Jarvis, {\it Linear Programming and Network Flows,\/} ISBN 0-471-06015-1, John Wiley and Sons, New York, 1977.\ \

G.\ Hadley, {\it Linear Programming,\/} Addison-Wesley, Reading, MA, 1962.\ \

Dimitri P.\ Bertsekas, {\it Linear Network Optimization: Algorithms and Codes,\/} ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.\ \

Saul I.\ Gass, {\it Linear Programming: Methods and Applications, Third Edition,\/} McGraw-Hill, New York, 1969.\ \

In practice the simplex algorithm is astoundingly fast. An explanation for just why was by Karl-Heinz Borgwardt with more details and the reference at

https://en.wikipedia.org/wiki/Simplex_algorithm

But there are carefully constructed pathological problems where the simplex algorithm is very slow. The first paper on this was likely from Klee and Minty with more details at

https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube

Disclosure: Minty was one of my professors.

Since I have mentioned integer linear programming, I should include a reference, e.g. (with my TeX markup)

George L.\ Nemhauser and Laurence A.\ Wolsey, {\it Integer and Combinatorial Optimization,\/} ISBN 0-471-35943-2, John Wiley \& Sons, Inc., New York, 1999.\ \

Disclosure: At one time Nemhauser gave me three words of advice, and that was the main direction for my Ph.D. dissertation.

Yes, my references are, like the field, old.

What the future in practice is of linear programming and related applied math I don't know.

thread

NY_EntrepreneurJul 2011

"Get it": No, I am saying that in asking about linear programming and dynamic programming as in Skiena, Google is not "prepared" and, really, is dealing in nonsense. If want someone to know some optimization and have a good reason for this, then fine. Then, cover some good material on optimization. But evaluating people on trivia about optimization as in Skiena is silly and arrogant, uninformed, dysfunctional, destructive, etc. It's something from the Queen in Alice in Wonderland:

"They didn't review Skiena? They don't know dynamic programming? Then, off with their heads!".

At the level of Skiena, f'get about optimization.

Again, Google is showing that they are far too centered on 'computer science' where they accept low quality material just because it was hijacked from its real origins in various fields of applied mathematics into a book on 'computer science' and poorly presented there.

For the network simplex algorithm, about the most elementary case is the transportation problem where find a least cost way to ship widgets from several factories to several warehouses. Then generalize to a network. Then, a simplex algorithm linear programming basis is just a spanning tree in the network. To add a variable to the basis, add an arc from the network. Then the spanning tree will be converted to a network with a circuit. Then run flow around that circuit in the direction that reduces cost until the flow on some arc hits zero. Remove that arc from the basis and again have a spanning tree. Cunningham's work guarantees to avoid cycles and tends to be faster.

See, say, pages 311-317 of

Va\v sek Chv\'atal, {\it Linear Programming,\/} ISBN 0-7167-1587-2, W. H. Freeman, New York, 1983.\ \

(in TeX to get the accents right!),

W. H. Cunningham, "A Network Simplex Method," 'Mathematical Programming', volume 11, pages 105-116, 1976.

W. H. Cunningham, "Theoretical Properties of the Network Simplex Method," 'Mathematics of Operations Research', volume 4, pages 196-208, 1979.

William H. Cunningham and John G. Klincewicz, "On Cycling in the Network Simplex Algorithm", 'Mathematical Programming', Volume 26, pages 182-189, North Holland, 1983.

Cunningham has long been at the Waterloo department of Combinatorics and Optimization.

Then, too, there is the guaranteed polynomial algorithm of D. Bertsekas. See:

Dimitri P. Bertsekas, 'Linear Network Optimization: Algorithms and Codes', ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.

But, if Google calls you, don't mention such things if you want a job! Instead, just mumble on about how great C++ is!

"Oh, I have Stroustrup under my pillow!"

Also mention some other buzz words.

Google has become arrogant, inwardly directed, and process-oriented. The history of companies that do that is not good.

thread