L♮-convexity and its applications in operations

Abstract

L^♮-convexity, one of the central concepts in discrete convex analysis, receives significant attentions in the operations literature in recent years as it provides a powerful tool to derive structures of optimal policies and allows for efficient computational procedures. In this paper, we present a survey of key properties of L^♮-convexity and some closely related results in lattice programming, several of which were developed recently and motivated by operations applications. As a new contribution to the literature, we establish the relationship between a notion called m-differential monotonicity and L^♮-convexity. We then illustrate the techniques of applying L^♮-convexity through a detailed analysis of a perishable inventory model and a joint inventory and transshipment control model with random capacities.

Keywords

L^♮-convexity / lattice programming / perishable inventory models / random capacity

References

[1] Begen M, Queyranne M (2011). Appointment scheduling with discrete random durations. Mathematics of Operations Research, 36(2): 240–257

[2] Chen S (2004). The optimality of hedging point policies for stochastic two-product flexible manufacturing systems. Operations Research, 52(2): 312–322

[3] Chen W, Dawande M, Janakiraman G (2014). Fixed-dimensional stochastic dynamic programs: An approximation scheme and an inventory application. Operations Research, 62(1): 81–103

[4] Chen X, Gao X, Hu Z (2015). A new approach to two-location joint inventory and transshipment control via L♮-convexity. Operations Research Letters, 43(1): 65–68

[5] Chen X, Gao X, Pang Z (2017). Preservation of structural properties in optimization with decisions truncated by random variables and its applications. Operations Research (just accepted)

[6] Chen X, Hu P, He S (2013). Technical Note-Preservation of supermodularity in parametric optimization problems with nonlattice structures. Operations Research, 61(5): 1166–1173

[7] Chen X, Pang Z, Pan L (2014). Coordinating inventory control and pricing strategies for perishable products. Operations Research, 62(2): 284–300

[8] Chen X, Simchi-Levi D (2004a). Coordinating inventory control and pricing strategies with random demand and fixed ordering cost: The finite horizon case. Operations Research, 52(6): 887–896

[9] Chen X, Simchi-Levi D (2004b). Coordinating inventory control and pricing strategies with random demand and fixed ordering cost: The infinite horizon case. Mathematics of Operations Research, 29(3): 698–723

[10] Fries B (1975). Optimal ordering policy for a perishable commodity with fixed lifetime. Operations Research, 23(1): 46–61

[11] Gao X (2017). Stochastic optimization with decisions truncated by random variables and its applications in operations. Dissertation for the Doctoral Degree. America: University of Illinois at Urbana-Champaign

[12] Ge D, Wan G, Wang Z, Zhang J (2014). A note on appointment scheduling with piecewise linear cost functions. Mathematics of Operations Research, 39(4): 1244–1251

[13] Gong X, Chao X (2013). Optimal Control Policy for Capacitated Inventory Systems with Remanufacturing. Operations Research, 61(3): 603–611

[14] Hajek B (1985). Extremal splittings of point processes. Mathematics of Operations Research, 10(4): 543–556

[15] Hu X, Duenyas I, Kapuscinski R (2008). Optimal joint inventory and transshipment control under uncertaincapacity. Operations Research, 56(4): 881–897

[16] Huh W, Janakiraman G (2010). On the optimal policy structure in serial inventory systems with lost sales. Operations Research, 58(2): 486–491

[17] Karlin S, Scarf H (1958). Inventory models of the Arrow-Harris-Marschak type with time lag. In: Arrow K, Scarf H, eds. Studies in the Mathematical Theory of Inventory and Production Chapter 10. Stanford: Stanford University Press, CA

[18] Lu Y, Song J (2005). Order-based cost optimization in assemble-to-order systems. Operations Research, 53(1): 151–169

[19] Morton T (1969). Bounds on the solution of the lagged optimal inventory equation with no demand backlogging and proportional costs. SIAM Review, 11(4): 572–596

[20] Murota K (1998). Discrete convex analysis. Mathematical Programming, 83(1-3): 313–371

[21] Murota K (2003). Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA

[22] Murota K (2005). Note on multimodularity and L-convexity. Mathematics of Operations Research, 30(3): 658–661

[23] Murota K (2009). Recent developments in discrete convex analysis. In: Cook W, Lovasz L, Vygen J, eds. Research Trends in Combinatorial Optimization, Bonn 2008, Springer-Verlag, Berlin, Chapter 11, 219–260

[24] Nahmias S (1975). Optimal ordering policies for perishable inventory-II. Operations Research, 23(4): 735–749

[25] Nahmias S (2011). Perishable inventory systems. International Series in Operations Research & Management Science, 160, Springer

[26] Nahmias S, Pierskalla W P (1973). Optimal ordering policies for a product that perishes in two periods subject to stochastic demand. Naval Research Logistics Quarterly, 20(2): 207–229

[27] Nahmias S, Schmidt C P (1986). An application of the theory of weak convergence to the dynamic perishable inventory problem with discrete demand. Mathematics of Operations Research, 11(1): 62–69

[28] Pang Z, Chen F, Feng Y (2012). A note on the structure of joint inventory-pricing control with leadtimes. Operations Research, 60(3): 581–587

[29] Petruzzi N C, Dada M (1999). Pricing and the newsvendor model: A review with extensions. Operations Research, 30(4): 680–708

[30] Simchi-Levi D, Chen X, Bramel J (2014). The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, 3rd. New York: Springer-Verlag

[31] Sun P, Wang K, Zipkin P (2014). Quadratic approximation of cost functions in lost sales and perishable inventory control problems. Working paper. America: Duke University

[32] Topkis D M (1998). Supermodularity and Complementarity. Princeton, NJ: Princeton University Press

[33] Xu Z, Zhang J, Zhang R (2016). Instantaneous control of brownian motion with a positive lead time. Working paper. Hong Kong: The Hong Kong University of Science and Technology

[34] Zipkin P (2008). On the structure of lost-sales inventory models. Operations Research, 56(4): 937–944

RIGHTS & PERMISSIONS

The Author(s) 2017. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)