SOLVING MANY LINEAR-PROGRAMS THAT DIFFER ONLY IN THE RIGHT-HAND SIDE

In many cases of mathematical programming, particularly when decomposition methods are employed, there is a need for solving many almost equal optimization problems. In this paper, we consider an aspect of the problem of solving many linear programming (LP) problems that only differ in the righthand side. Our motivation is to find good solution procedures for twostage stochastic programming (TSP) problems. 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 righthand sides in the tree until primal feasibility, and hence optimality, is achieved. We demonstrate that the order in which the righthand sides are picked is crucial for execution time and data storage requirements. Sorting methods, that do not need explicit representations of the possible righthand sides are presented, and computational results are given.