The Augmented Predecessor Index Method for Locating Stepping-Stone Paths and Assigning Dual Prices in Distribution Problems

Abstract

The augmented predecessor indexing method provides an efficient way to update the basis and cost evaluators in adjacent extreme point solution methods for transportation problems. The method extends the predecessor indexing method, which was designed to exploit an ancestry relation in the basis tree, by showing how to exploit a more elaborate “family relation,” commonly known as a binary tree representation in computer list processing. This representation, sometimes called the “triple-label method,” was first suggested for application to network optimization problems by Ellis Johnson, who examined its use in the context of maximal flow problems. The augmented predecessor indexing method shows how to take special advantage of this representation in the context of the transportation problem, elaborating Johnson's work by providing an efficient method for characterizing successive basis trees with minimal relabeling. Moreover, we show how this procedure can be applied to update the transportation cost evaluators simultaneously without calculating current node potentials (as ordinarily required in the “stepping-stone” and related basis exchange algorithms), thus greatly speeding the arithmetic calculations.