Browse Prior Art Database

Dynamically Restricted Pricing In The Simplex Method For Linear Programming

IP.com Disclosure Number: IPCOM000068386D
Original Publication Date: 1979-Dec-01
Included in the Prior Art Database: 2005-Feb-20

Publishing Venue

IBM

Related People

Authors:
Crowder, HP Herman, RJ Wolfe, PS [+details]

Abstract

A modification of the conventional simplex method has been developed for use on linear programming problems with large numbers of columns. The basic concept underlying the method is the trade-off between the cost of calculating many reduced costs and the increase in number of iterations resulting from calculating very few. Under suitable assumptions a cost function can be constructed. The optimal choice of the number of reduced costs can then be computed by means of Dynamic Programming. Several approximated solutions are developed which are computationally simpler. Experiments on a number of problems indicate that the method may offer a promising technique for large-scale problems. STATEMENT OF THE PROBLEM