Solving many linear programs that differ only in the right-hand side
\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.
- Solving linear programs with multiple right-hand sides: Pricing and ordering schemes
- scientific article; zbMATH DE number 3852786
- scientific article; zbMATH DE number 4131948
- Stochastic linear programming method for right-hand sides random vector
- A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- A piecewise linear upper bound on the network recourse function
- A Separable Piecewise Linear Upper Bound for Stochastic Linear Programs
- Aggregation bounds in stochastic linear programming
- Bounds on the Expectation of a Convex Function of a Multivariate Random Variable
- Computation in Discrete Stochastic Programs with Recourse
- Decomposing the requirement space of a transporation problem into polyhedral cones
- Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse
- scientific article; zbMATH DE number 3878686 (Why is no real title available?)
- scientific article; zbMATH DE number 3965788 (Why is no real title available?)
- scientific article; zbMATH DE number 4085417 (Why is no real title available?)
- scientific article; zbMATH DE number 3673848 (Why is no real title available?)
- Investing in arcs in a network to maximize the expected max flow
- Matrix augmentation and partitioning in the updating of the basis inverse
- Solving stochastic programs with network recourse
- stochastic quasigradient methods and their application to system optimization†
- Accelerating the regularized decomposition method for two stage stochastic linear problems
- Algorithms for the solution of stochastic dynamic minimax problems
- Solving linear programs with multiple right-hand sides: Pricing and ordering schemes
- Scenario tree construction driven by heuristic solutions of the optimization problem
- Finding and identifying optimal inventory levels for systems with common components
- scientific article; zbMATH DE number 4131948 (Why is no real title available?)
- Solving Large Batches of Linear Programs
This page was built for publication: Solving many linear programs that differ only in the right-hand side
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108193)
