Network simplex method

The network simplex method is an optimization method for solving min-cost-flow problems by using methods of the simplex method . In principle one could formulate this problem as a general linear optimization problem and solve it with the generic simplex method. In the case of this special type of network flow problem, however, each base can be interpreted in the simplex method as a tree in a graph. The transition from one base to the next corresponds to the transition from one tree to another. This allows the solution process to be accelerated significantly by replacing the simplex steps with such combinatorial operations. Starting from an admissible tree vector, one can improve with the help of the associated dual problem in each iteration step until one obtains the optimal tree vector.

swell

• Hamacher, Klamroth: "Linear and Network Optimization - Linear and Network Optimization. A bilingual textbook - A bilingual textbook", ISBN 3528031557
• Krumke, Noltemeier: "Graph Theoretical Concepts and Algorithms", ISBN 3-519-00526-3