Higher Order Tree Dual Approximation Methods for the Distribution Problem

This paper develops efficient algorithms for obtaining a dual feasible starting basis for the capacitated distribution problem. The motivation for the development of such a technique is threefold. Firstly, although efficient dual methods for solving such problems have been developed, none of these methods have addressed themselves to the problem of efficiently determining a dual feasible starting basis. Secondly, no counterpart method exists for obtaining a primal feasible starting basis for the capacitated problem; furthermore, the development of such a counterpart procedure is unlikely. Finally, because our approach provides a dual feasible basis that is both legitimate (i.e., nonartificial) and good (in terms of the dual functional), the synthesis of our procedure with one of the dual distribution methods should provide a more efficient computational algorithm for solving capacitated distribution problems than primal counterpart methods.