Improved Primal Simplex Algorithms for Shortest Path, Assignment and Minimum Cost Flow Problems : November, 1988 (Classic Reprint)

Excerpt from Improved Primal Simplex Algorithms for Shortest Path, Assignment and Minimum Cost Flow Problems: November, 1988

The network simplex algorithm maintains a feasible basis structure at each iteration and successively modifies the basis structure via pivots until it becomes an optimum basis structure. The special structure of the basis enables the simplex computations to be performed very efficiently. In the following discussion, we give a brief summary of the network simplex algorithm and the data structure required to implement the algorithm.

The basis B of the minimum cost flow problem is a spanning tree. We consider this tree as hanging from node 1. The tree arcs either are upward pointing (towards node 1) or are downward pointing (away from node We associate three indices with each node i in the tree: a predecessor index pred( i), a depth index depth( i), and a thread index, thread( i). Each node i has a unique path connecting it to node 1. The predecessor index stores the first node in that path (other than node i and the depth index stores the number of arcs in the path For node 1, these indices are zero. We say that pred(i) is the predecessor of node i, and i is the successor of node pred( i). The descendants of a node i consist of node i itself, its successors, successors of its successors, and so on. The set of descendants of a node i induce a subtree rooted at node i. We denote the nodes of the subtree by the set D(i). Node i is called an ancestor of nodes in D(i). The thread indices define a traversal of the tree, a sequence of nodes that walks or threads its way through the nodes of the tree, starting at node 1 and visiting nodes in a top to bottom and left to right order, and then finally retuming to node 1. The thread indices can be formed by performing a depth first search of the tree. The thread indices provide a means for visiting (or finding) all descendants of a node i in C(| D(i) I) time. For a detailed description of the tree indices see Kennington and Helgason In the basis there is a unique path connecting any two nodes. We refer to this path as the basis path.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.