User:Kxx/Sandbox/Network simplex method

In mathematical optimization, the network simplex method is an algorithm for solving the minimum-cost flow (MCF) problems. The network simplex method is an adaptation of the simplex method for linear programming (LP). Compared to the matrix-oriented approach of the simplex method, the network simplex method is directly formulated on flow networks. Matrix-based concepts such as bases are replaced by their graph-based equivalents such as spanning trees; the pivot operation is defined in terms of swapping edges in and out of the spanning tree instead of swapping columns in and out of the basis. This graph-oriented approach enables the network simplex method to have a more straightforward implementation and achieve greater efficiency than directly applying the simplex method to the LP formulations of MCF problems. In practice, together with the cost scaling algorithm, the network simplex method is considered to be one of the fastest algorithms for solving MCF problems.