Solving many linear programs that differ only in the right-hand side (Q1108193)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving many linear programs that differ only in the right-hand side |
scientific article |
Statements
Solving many linear programs that differ only in the right-hand side (English)
0 references
1988
0 references
\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.
0 references
right-hand side
0 references
search tree
0 references
Sorting methods
0 references
computational results
0 references
0 references
0 references