Solving many linear programs that differ only in the right-hand side (Q1108193)

\textit{R. J.-B. Wets} [``Large scale programming techniques in stochastic programming'', WP-84-90, IIASA, Laxenburg, Austria (1984)] presented a method for solving many linear programs that differ only in the right- hand side. The idea is to build up a search tree, where each node corresponds to a dual feasible basis for the linear program, and each arc to a dual pivot step. Nodes are added to the search tree as they are needed, and the linear programs are solved by trickling down the different right-hand sides in the tree until primal feasibility, and hence optimality, is achieved. We demonstrate that the order in which the right-hand sides are picked is crucial for execution time and data storage requirements. Sorting methods, that do not need explicit representations of the possible right-hand sides, are presented, and computational results are given.