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

Acknowledgments

This research is partly supported by National Science Foundation (NSF) Grants CMMI-1363261, CMMI-1538451, CMMI-1635160 and National Science Foundation of China (NSFC) Grants 71520107001. The author thanks Yehua Wei for bringing the reference Chen (2004) to his attention and the anoymous reviewers for their valuable comments.

RIGHTS & PERMISSIONS

2017 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)