Multiple pricing and suboptimization in dual linear programming algorithms

Abstract

This paper discusses the successful implementation of multiple pricing and suboptimization in a product-form dual algorithm. Dual pricing is shown to result in a greater improvement in the dual functional per major dual iteration, and dual suboptimization is shown to be effective in reducing both I/O and CPU time when the LP problem resides on auxiliary storage. Several industrial problems, chosen at random, were solved under limited core storage conditions and empirical results indicate that dual multiple pricing and suboptimization reduce both major iterations and the average time per iteration for large problems.