In
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, the network simplex algorithm is a
graph theoretic specialization of the
simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are ...
. The algorithm is usually formulated in terms of a
minimum-cost flow problem
The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery ro ...
. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.
History
For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995
Orlin provided the first polynomial algorithm with runtime of
where
is maximum cost of any edges. Later
Tarjan improved this to
using
dynamic trees in 1997. Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.
Overview
The network simplex method is an adaptation of the bounded variable primal simplex algorithm. The basis is represented as a rooted spanning tree of the underlying network, in which variables are represented by arcs, and the simplex multipliers by node potentials. At each iteration, an entering variable is selected by some pricing strategy, based on the dual multipliers (node potentials), and forms a cycle with the arcs of the tree. The leaving variable is the arc of the cycle with the least augmenting flow. The substitution of entering for leaving arc, and the reconstruction of the tree is called a pivot. When no non-basic arc remains eligible to enter, the optimal solution has been reached.
Applications
The network simplex algorithm can be used to solve many practical problems including,
*
Transshipment problem
*
Hitchcock transportation problem
*
Assignment problem
The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:
:The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any t ...
* Chains and antichains in
partially ordered set
In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
s
*
System of distinct representatives
* Covers and matching in
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
s
* Caterer problem
References
{{Reflist
External links
Solving Network ProblemsSection 14, p B-113 shows an example execution
Optimization algorithms and methods
Linear programming
Network flow problem
Mathematical problems
Network theory
Polynomial-time problems
Graph algorithms
Computational problems in graph theory