Abstract
This paper discusses the use of different pricing and ordering schemes when solving many linear programs that differ only in the right-hand sides. This is done in a setting of what has become known as bunching or trickling down. The idea is to collect (bunch) all right-hand sides that have the same optimal basis, and to organize the search for these bases efficiently. We demonstrate that the choice of pricing rule is indeed very important, but we were not able to make conclusions regarding ordering schemes. Numerical results are given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N.J. Berland, Stochastic optimization and parallel processing, Ph.D. Thesis, Department of Informatics, University of Bergen, February 1993.
D.P. Bertsekas and J.M. Tsitsiklis,Parallel and Distributed Computation, Prentice-Hall, Englewood Cliffs, New Jersey, 1989.
J.R. Birge, Decomposition and partitioning methods for multistage stochastic linear programs, Operations Research 33, 1985, 989–1007.
J. Bisschop and A. Meeraus, Matrix augmentation and partitioning in the updating of the basis inverse, Mathematical Programming 13, 1977, 241–254.
V. Chvátal,Linear Programming, W.H. Freeman, New York, 1980.
B. Dodin, Bounding the project completion time in PERT networks, Operations Research 33, 1985, 862–881.
J.J. Dongarra and E. Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM 30, 1987, 403–407.
H.I. Gassmann, MSLiP: A computer code for the multistage stochastic linear programming problem, Mathematical Programming 47, 1990, 407–423.
D. Goldfarb and J.K. Reid, A practicable steepest-edge simplex algorithm, Mathematical Programming 12, 1977, 361–371.
P.M.J. Harris, Pivot selection methods of the devex LP code, Mathematical Programming 5, 1973, 1–28.
D. Haugland and S.W. Wallace, Solving many linear programs that differ only in the right-hand side, European Journal of Operational Research 37, 1988, 318–324.
J.L. Higle and S. Sen, Stochastic decomposition: An algorithm for two-stage linear programs with recourse, Mathematics of Operations Research 16, 1991, 650–669.
J. Kamburowski, Bounds in temporal analysis of stochastic networks, Foundation of Control Engineering 10, 1985, 177–185.
G.B. Kleindorfer, Bounding distributions for a stochastic acyclic network, Operations Research 19, 1971, 1586–1601.
F. Louveaux and Y. Smeers, Optimal investments for electricity generation: A stochastic model and a test problem, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B Wets, eds., Springer, 1988, pp. 445–454.
J.M. Mulvey and A. Ruszczyński, A new scenario decomposition method for large-scale stochastic optimization, Technical Report, Department of Civil Engineering and Operations Research, Princeton University, May 1992.
J.M. Mulvey and H. Vladimirou, Stochastic network optimization models for investment planning, Annals of Operations Research 20, 1989, 187–217.
B.A. Murtagh,Advanced Linear Programming: Computation and Practice, McGraw-Hill, New York, 1981.
S. Sen, R.D. Doverspike and S. Cosares, Network planning with random demand, Technical Report, SIE Department, University of Arizona, Tucson, AZ, December 1992.
A.W. Dhogan, Bounding distributions for a stochastic PERT network, Networks 7, 1977, 359–381.
R.J-B Wets, Stochastic programming: Solution techniques and approximation schemes, inMathematical Programming: The State of the Art, A. Bachem, M. Grötschel and B. Korte, eds., Springer, Berlin, 1983, pp. 566–603.
R.J-B Wets, Large scale linear programming techniques, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B Wets, eds., Springer, Berlin, 1988, pp. 65–94.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gassmann, H.I., Wallace, S.W. Solving linear programs with multiple right-hand sides: Pricing and ordering schemes. Ann Oper Res 64, 237–259 (1996). https://doi.org/10.1007/BF02187648
Issue Date:
DOI: https://doi.org/10.1007/BF02187648