Abstract
A cumulative-capacitated transportation problem is studied. The supply nodes and demand nodes are each chains. Shipments from a supply node to a demand node are possible only if the pair lies in a sublattice, or equivalently, in a staircase disjoint union of rectangles, of the product of the two chains. There are (lattice) superadditive upper bounds on the cumulative flows in all leading subrectangles of each rectangle. It is shown that there is a greatest cumulative flow formed by the natural generalization of the South-West Corner Rule that respects cumulative-flow capacities; it has maximum reward when the rewards are (lattice) superadditive; it is integer if the supplies, demands and capacities are integer; and it can be calculated myopically in linear time. The result is specialized to earlier work of Hoeffding (1940), Fréchet (1951), Lorentz (1953), Hoffman (1963) and Barnes and Hoffman (1985). Applications are given to extreme constrained bivariate distributions, optimal distribution with limited one-way product substitution and, generalizing results of Derman and Klein (1958), optimal sales with age-dependent rewards and capacities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E.R. Barnes and A.J. Hoffman, “On transportation problems with upper bounds on leading rectangles,”SIAM Journal on Algebraic and Discrete Methods 6 (1985) 487–496.
C. Derman and M. Klein, “Inventory depletion management,”Management Science 4 (1958) 450–456.
M. Fréchet, “Sur les tableaux de corrélation dont les marges sont données,”Annales de l'Université de Lyon Section A 14 (1951) 53–77.
W. Hoeffding, “Maßstabinvariante Korrelationstheorie,”Schriften des Mathematischen Instituts und des Instituts für Angewande Mathematik der Universität Berlin 5 (1940) 179–233. [Originally published under the name W. Höffding.]
A.J. Hoffman, “On simple linear programming problems,” in: V. Klee, ed.,Convexity. Proceedings of the Symposium on Pure Mathematics No. 7 (American Mathematical Society Providence, RI, 1963) pp. 317–327.
A.J. Hoffman and A.F. Veinott, Jr., “Staircase transportation problems with superadditive rewards and cumulative capacities,” Research Report RJ 7399 (69201), IBM Research Division (Yorktown Heights and Almaden, April 3, 1990), 13 pp.
G.G. Lorentz, “An inequality for rearrangements,”The American Mathematical Monthly 60 (1953) 176–179.
I. Olkin and S.T. Rachev, “Distributions with given marginals subject to certain constraints,” Technical Report No. 270, Department of Statistics, Stanford University (Stanford, CA, July 1990) 28 pp.
S.T. Rachev, “The Monge—Kantorovich mass transference problem and its stochastic applications,”Theory of Probability and its Applications 29 (1985) 647–676. [Translated from:Teoriya Veroyatnostei i ee Primeneniya (1984).]
D.M. Topkis, “The structure of sublattices of the product ofn lattices,”Pacific Journal of Mathematics 65 (1976) 525–532.
D.M. Topkis and A.F. Veinott, Jr., “Monotone solution of extremal problems on lattices (Abstract),”Abstracts of 8th International Symposium on Mathematical Programming (Stanford University, Stanford, CA, 1973) 131.
D.M. Topkis and A.F. Veinott, Jr., “Meet-representation of subsemilattices and sublattices of product spaces (Abstract),”Abstracts of 8th International Symposium on Mathematical Programming (Stanford University, Stanford, CA, 1973) 136.
A.F. Veinott, Jr., “Representation of general and polyhedral subsemilattices and sublattices of product spaces,”Linear Algebra and its Applications 114/115 (1989) 681–704.
W. Whitt, “Bivariate distributions with given marginals,”Annals of Statistics 4 (1976) 1280–1289.
Author information
Authors and Affiliations
Additional information
To our friend, Philip Wolfe, with admiration and affection, on the occasion of his 65th birthday.
Research was supported respectively by the IBM T.J. Watson and IBM Almaden Research Centers and is a minor revision of the IBM Research Report [6].
Rights and permissions
About this article
Cite this article
Hoffman, A.J., Veinott, A.F. Staircase transportation problems with superadditive rewards and cumulative capacities. Mathematical Programming 62, 199–213 (1993). https://doi.org/10.1007/BF01585166
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585166