Abstract
Solving a large number of linear programs with the same coefficient matrix, but different cost coefficients or right hand sides is often an important part of the solution procedures for dynamic and stochastic programs. This usually involves a decomposition of the parameter space, a decomposition which is dictated by the optimality criteria. The subregions correspond to (sub) bases of the coefficient matrix. We suggest an efficient procedure to generate such a decomposition in the following case: the linear programs are transportation problems with different right hand sides. We also report on our computational results.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
M.L. Balinski, “The Hirsch conjecture for dual transportation polyhedra”, Collaborative paper CP-83-9, IIASA, Laxenburg, Austria (1983).
G. Gallo and C. Sodini, “Extreme points and adjacency relationship in the flow polytope”, Calcolo 15 (1978) 277–288.
D.W. Walkup and R.J.-B. Wets, “Lifting projections of convex polyhedra”, Pacific Journal of Mathematics 28 (1969) 465–475.
S. W. Wallace, “A two-stage stochastic facility-location problem with time-dependent supply”, Report no. 832555-10, Chr. Michelsen Institute, Bergen, Norway (1984).
R. J-B. Wets and C. Witzgall, “Algorithms for frames and lineality spaces of cones”, Journal of Research of the National Bureau of Standards 71B (1967) 1–7.
R. J-B. Wets “Stochastic programs with fixed recourse: The equivalent deterministic program”, SIAM Review, 16 (1974) 309–339.
R. J-B. Wets, “Stochastic programming: Solution techniques and approximation schemes”, in: A. Bachem, M. Grötschel and B. Korte, eds., Mathematical programming: The state of the art, Bonn 1982 (Springer-Verlag, Berlin, 1983) pp. 566–603.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 The Mathematical Programming Society, Inc.
About this chapter
Cite this chapter
Wallace, S.W. (1986). Decomposing the requirement space of a transporation problem into polyhedral cones. In: Prékopa, A., Wets, R.J.B. (eds) Stochastic Programming 84 Part II. Mathematical Programming Studies, vol 28. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121124
Download citation
DOI: https://doi.org/10.1007/BFb0121124
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00926-6
Online ISBN: 978-3-642-00927-3
eBook Packages: Springer Book Archive