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

Introduction

L^{♮}-convexity is a key concept in discrete convex analysis introduced by ^{Murota (1998)} in an attempt to extend powerful convex analysis from continuous spaces to discrete spaces with lattice structures (here L stands for “lattice”). A L^{♮}-convex function on an integer space has several salient properties: it can be extended to a convex function on a continuous space; local optimality guarantees global optimality; elegant duality results similar to what we see in convex programming duality hold. Though L^{♮}-convexity was originally defined on integer spaces, the definition can be naturally extended to continuous spaces and imposes certain combinatorial structures on convex functions. Efficient algorithms have been developed for L^{♮}-convex function minimization. We refer to ^{Murota (2003)} and ^{Murota (2009)} for a comprehensive treatment of discrete convex analysis including L^{♮}-convexity.

The primary purpose of introducing L^{♮}-convexity and some other related discrete convexity concepts is to provide a theoretical framework of tractable combinatorial optimization problems. Interestingly, the close connection of L^{♮}-convexity with lattice programming, which will become clear in the next section, allows us to derive monotone comparative statics in many inventory models. Indeed, it was used by ^{Zipkin (2008)} to derive the optimal structural policy of lost-sales inventory models with positive lead times, which shed new lights on a classical result of ^{Karlin and Scarf (1958)} and ^{Morton (1969)}. Since then, L^{♮}-convexity was found to be powerful to establish the structures of optimal policies in various other operations models: serial inventory systems (^{Huh and Janakiraman, 2010}); inventory-pricing models with positive lead times (^{Pang et al., 2012}); capacitated inventory systems with remanufacturing (Gong and Chao, 2013); perishable inventory models (^{Chen X et al., 2014}); dual-sourcing models with random capacities, assemble-to-order systems with random capacities, and revenue management using booking limits (^{Chen et al., 2017}); a joint inventory and transshipment control model with random capacities (^{Chen et al., 2015}); an instantaneous control model of Brownian motion with positive lead time (^{Xu et al., 2016}); etc.

Instead of providing a comprehensive survey of operations papers which use L^{♮}-convexity, the paper aims to give a brief review of the concepts and properties of L^{♮}-convexity which are useful in deriving structural optimal policies in operations models and illustrate how these properties can be used as a powerful tool to derive monotone comparative statics. A brief overview of lattice programming is also provided due to its close connection with L^{♮}-convexity. We demonstrate the techniques of applying L^{♮}-convexity through detailed analysis of a perishable inventory model and a two-location joint inventory and transshipment control model with random capacities, and hope that through the analysis the readers can get a sense how these applications motivate some of the newly developed properties of L^{♮}-convexity. Though this paper is intended to serve as a survey, it does provide some new results. For example, we show that the notion of m-differential monotonicity is equivalent to L^{♮}-convexity subject to a simple linear transformation.

The organization of this paper is as follows. In Section 2, we briefly review the basic concepts and properties in lattice programming and L^{♮}-convexity. Though many results can be presented in more general terms, we refrain from doing it for the sake of readability. In Section 3, we review two inventory models in which L^{♮}-convexity plays a critical role. Finally, we provide some concluding remarks in Section 4.

For easy reference, we list the main terminologies and notations here. Throughout this paper, we use decreasing, increasing and monotonicity in a weak sense. We use \Reand {\Re }_{+} to denote the real space and the set with nonnegative reals, \mathcal{Z} and \mathcal{Z}₊ to denote the set of integers and the set of nonnegative integers, respectively. For convenience, let \mathcal{F} be \Re either \Re or \mathcal{Z}. Define \overline{\Re }=\Re \cup \left\{+\infty \right\}, e ∈ \mathcal{F}ⁿ a vector whose components are all ones, e_j a unit vector whose jth component is one, and for x, y∈ \mathcal{F}ⁿ, x\le y if and only if x_i\le y_ifor any i=\mathrm{1},...n, x^{+}=\max \left(x,\mathrm{0}\right), x\wedge y=\min \left(x,y\right)and x\vee y=\max \left(x,y\right) (the component-wise minimum and maximum operations). The effective domain of a function f:{\Re }^n\to \overline{\Re }is defined as .The indicator function of any set \mathcal{V}\subseteq \mathcal{F}ⁿ, denoted by {\delta }_{\mathcal{V}}, is defined as {\delta }_{\mathcal{V}}(x) = 0 for x∈\mathcal{V} and +\infty otherwise. We use the superscript T to denote the transpose of a vector or a matrix. We use uppercase letters (e.g., X) to denote random vectors and lowercase letters (e.g., ξ€) for their realizations. Given a random vector \Xi ={({\Xi }_{\mathrm{1}},...,{\Xi }_n)}^T, we use \mathcal{X} = Supp(X) to denote the support of this random vector. In addition, we define {\overline{\xi }}_j = ess sup{ξ_j|ξ_j∈ \mathcal{X}_j}, ξ_j = ess inf{ξ_j|ξ_j∈ \mathcal{X}_j} for j = 1, ..., n, where \mathcal{X}_j is \mathcal{X}’s projection into the j-th coordinate. Let \overline{\xi }={\left({\overline{\xi }}_{\mathrm{1}},...,{\overline{\xi }}_n\right)}^T, ξ = (ξ₁, ..., ξ_n)^T, and almost surely is abbreviated as a.s..

Lattice Programming and L^{♮}-Convexity

In this section, we provide a brief review of lattice programming and L^{♮}-convexity. The materials on lattice programming and L^{♮}-convexity, unless specified, follow ^{Topkis (1998)} and ^{Murota (2003)} respectively. The readers may also refer to ^{Simchi-Levi et al. (2014)}.

Lattice Programming

Since L^{♮}-convexity is the combination of convex analysis with a lattice structure, we first introduce the concepts of lattice and supermodularity. Though the concepts can be defined on general partially ordered sets, for our purpose we focus on the Euclidean space {\Re }^n with the standard partial order≤, i.e., for any x,x^{\prime }\in {\Re }^n, x\le x^{\prime } if and only if x_i\le {x^{\prime }}_i for i=\mathrm{1},\mathrm{2},...,n.

To present the definitions of lattice and supermodularity, we first introduce two operations, join and meet operations, in {\Re }^n. For any two points x=\left(x_{\mathrm{1}},x_{\mathrm{2}},...,x_n\right) and x\text{'}=\left(x{\text{'}}_{\mathrm{1}},x{\text{'}}_{\mathrm{2}},...,x{\text{'}}_n\right) in {\Re }^n, define their join as

x\vee x^{\prime }=\left(\max \left\{x_{\mathrm{1}},{x^{\prime }}_{\mathrm{1}}\right\},\max \left\{x_{\mathrm{2}},{x^{\prime }}_{\mathrm{2}}\right\},\mathrm{...},\max \left\{x_{\mathrm{n}},{x^{\prime }}_{\mathrm{n}}\right\}\right),

and their meet as

x\wedge x^{\prime }=\left(\min \left\{x_{\mathrm{1}},{x^{\prime }}_{\mathrm{1}}\right\},\min \left\{x_{\mathrm{2}},{x^{\prime }}_{\mathrm{2}}\right\},\mathrm{...},\min \left\{x_{\mathrm{n}},{x^{\prime }}_{\mathrm{n}}\right\}\right).

Of course, if x\le x^{\prime }, i.e., x_i\le x_i{}^{\prime } for i=\mathrm{1},\mathrm{2},...,n, then x\vee x\text{'}=x\text{'} and . If none of x\le x\text{'} nor x\ge x\text{'} is true, x and x' are called unordered. A set X\subseteq {\Re }^nis called a lattice if for any x, x\text{'}\in X, x\vee x\text{'}, x\wedge x\text{'}\in X. In some literature, X is called a sublattice of {\Re }^n as it inherits the infimum and supremum from {\Re }^n.

DEFINITION 1. A function f:{\Re }^n\to \overline{\Re }. The function f is supermodular, if for any x,x^{\prime }\in {\Re }^n,

(1)f\left(x\right)+f\left(x\text{'}\right)\le f(x\vee x\text{'})+f(x\wedge x\text{'}).

f is strictly supermodular, if the inequality (1) holds strictly for unordered pairs x, x\text{'}\in dom\left(f\right). A function f is (strictly) submodular if-f is (strictly) supermodular.

For a supermodular function f, its effective domain is a lattice. We say f is supermodular on a set X\subseteq {\Re }^n if X is a lattice and inequality (1) holds for any x,x\text{'}\in X.

One can show that f is supermodular in {\Re }^n if and only if f has increasing difference. That is, for any x\in {\Re }^n, i=\mathrm{1},...,n and any scalar t>\mathrm{0}, f\left(x+t{e}_i\right)-f\left(x\right) is increasing in x_j for any j\ne i. A differentiable function f: ℜⁿ→ℜ is supermodular if and only if for any x\in {\Re }^n and distinct indexes i and j, the partial derivative {\displaystyle \frac{\partial f\left(x\right)}{\partial x_i}} is nondecreasing in x_j. Moreover, a twice differentiable function f is supermodular if and only if for any x\in {\Re }^nand distinct indexes i and j, {\displaystyle \frac{{\partial }^{\mathrm{2}}f\left(x\right)}{\partial x_i\partial x_j}}\ge \mathrm{0}.

Following are some useful results and properties of supermodular functions.

PROPOSITION 1.(a) Any nonnegative linear combination of supermodular functions is supermodular. That is, if f_i:{\Re }^n\to \overline{\Re }(i=\mathrm{1},\mathrm{2},...,m) are supermodular, then for any scalar {\alpha }_i\ge \mathrm{0}, {\displaystyle {\sum }_{i=\mathrm{1}}^m{\alpha }_i{f}_i} is still supermodular.

(b)If f_k is supermodular for k=\mathrm{1},\mathrm{2},... and {\lim }_{k\to \infty }f_k\left(x\right)=f\left(x\right) for any x\in {\Re }^n, then f(x) is supermodular.

(c)A composition of an increasing (decreasing) convex function and an increasing supermodular (submodular) function is still supermodular. That is, if f:\Re \to \Reis convex and nondecreasing (nonincreasing) andg:{\Re }^n\to \Reis increasing and supermodular (submodular), thenf\left(g\left(x\right)\right)is supermodular.

(d)Assume that a function f\left(·,·\right) is defined in the product space {\Re }^n\times {\Re }^m. If f\left(·,\hspace{0.17em}y\right) is supermodular for any given y\in {\Re }^m, then for a random vector ζ in {\Re }^m, E_{\zeta }\left[f\left(x,\zeta \right)\right] is supermodular, provided it is well defined.

The following theorem shows the relationship between convexity and supermodularity for a function, which is quite commonly used in operations models.

THEOREM 1.Let X be a lattice in{\Re }^n, a_i\in \Re (i=\mathrm{1},\mathrm{2},...,n), and Y be a convex subset of\Re. Assume\left\{{\displaystyle {\sum }_{i=\mathrm{1}}^n{a}_i{x}_i}|x\in X\right\}\subseteq Y. For a functionf:Y\to \Re, defineg:X\to \Rewithg\left(x\right):=f\left({\displaystyle {\sum }_{i=\mathrm{1}}^n{a}_i{x}_i}\right)for anyx=(x_{\mathrm{1}},x_{\mathrm{2}},...,x_n)\in X. We have the following.

(a)If a_i\ge \mathrm{0}fori=\mathrm{1},\mathrm{2},...,n, and f is convex on Y, then g is supermodular on X.

(b)If n=\mathrm{2}, a_{\mathrm{1}}>\mathrm{0}and, and f is concave on Y, then g is supermodular on X.

Suppose, in addition, that for any x, x′ with x\le x^{\prime }, x\in Ximpliesx^{\prime }\in X, Y=\left\{{\displaystyle {\sum }_{i=\mathrm{1}}^n{a}_i{x}_i}|x\in X\right\}and f is continuous on the interior of Y.

(c)Ifn\ge \mathrm{2}, a_{\mathrm{1}}>\mathrm{0}anda_{\mathrm{2}}>\mathrm{0}, and g is supermodular on X, then f is convex on Y.

(d)Ifn\ge \mathrm{2}, a_{\mathrm{1}}>\mathrm{0}and, and g is supermodular on X, then f is concave on Y.

(e)Ifn\ge \mathrm{3}, a_{\mathrm{1}}>\mathrm{0}, a_{\mathrm{2}}>\mathrm{0}and, and g is supermodular on X, then f is linear on Y.

Supermodularity plays a critical role in deriving monotonicity of optimal solution sets for a class of parametric optimization problems. To present one of the widely used monotone comparative statics results, we define the induced set ordering ⊑ which defines X⊑X^{\prime } for two nonempty sets X and X′ if x\in X and x\text{'}\in X^{\prime } imply that x\wedge x^{\prime }\in X and x\vee x^{\prime }\in X^{\prime }. Roughly speaking, X⊑X^{\prime } implies that X contains smaller elements and X′ contains larger elements.

Let S(t) be a set function in {\Re }^n parameterized by t\in T\subseteq {\Re }^m, i.e., for a parameter t\in T, S(t) is a subset of {\Re }^n. Throughout this paper, the set function S(t) is called increasing (or increasing set function) in t, if for any t, t^{\prime }\in Twith t\le t^{\prime }, S\left(t\right)⊑S\left(t^{\prime }\right).

Note that the concept of increasing set functions is different from set inclusion. For example, the mapping S\left(t\right)=[t,+\infty )is an increasing set function but S\left(t^{\prime }\right)\subset S\left(t\right)for .

PROPOSITION 2.Let S(t) be an increasing set function in {\Re }^nparameterized byt\in T\subseteq {\Re }^m. We have that S(t) is a lattice of{\Re }^nfor anyt\in T. If in addition S(t) is nonempty and compact for anyt\in T, we can show that S(t) has a largest and a smallest elements, which are increasing in t respectively.

Under some supermodularity assumptions, the sets of optimal solutions for a collection of optimization problems parameterized by a parameter are increasing in the parameter. Meanwhile, for a given parameter, there exist a largest and a smallest optimal solutions, which are increasing in the parameter as well. Consider the parametric optimization problem

(2)f\left(t\right):=\underset{x\in S\left(t\right)}{\sup }g\left(x,t\right).

Define \mathcal{A}:=\left\{\left(x,t\right)|t\in T,x\in S\left(t\right)\right\}\subseteq {\Re }^n\times {\Re }^m be the graph of the parametric constraint set S(·), and S^{*}\left(t\right):=\arg {\max }_{x\in S\left(t\right)}g\left(x,t\right), the set of maximizers of problem (2).

THEMOREM 2.Assume that S(t) is increasing in t\in T, and g(x, t): \mathcal{A}→ℜ is supermodular in x for any fixed t∈ T and has increasing differences in (x, t).

(a)S*(t) is increasing in t on {t∈T|S*(t)≠ ∅}.

(b)Assume, in addition, that S(t) is a nonempty and compact set of €{\Re }^nfor anyt\in T, andg\left(x,t\right)is continuous in x on S(t) for anyt\in T. Then S*(t) is a nonempty and compact lattice and thus there exist\overline{x}\left(t\right), \underline{x}\left(t\right)\in S^{*}\left(t\right) such that for any x\in S*\left(t\right), \underline{x}\left(t\right)\le x\le \overline{x}\left(t\right). Furthermore, \overline{x}\left(t\right) and \underline{x}\left(t\right) are increasing.

Supermodularity can be preserved under the optimization operation (2), which is particularly useful to prove that supermodularity can be carried out in dynamic programming recursions.

THEOREM 3.Consider the optimization problem (2). Assume that the graph of the parametric constraint set, \mathcal{A}, is a lattice in {\Re }^n\times {\Re }^m and g\left(·,·\right):\mathcal{A}\to \Re is supermodular. Let P_t (\mathcal{A}) = {t∈T |S(t)≠Ø} . ThenP_t (\mathcal{A}) is a lattice. In addition, f is supermodular over P_t (\mathcal{A}).

The critical assumption in the above theorem is that the graph of the parametric constraint set is a lattice. Yet in many inventory models this assumption is not valid. The following theorem relaxes the lattice condition yet imposes some other conditions. Consider the parameterized optimization problem by a two dimensional vector t\in T=\{Ax:x\in S\}:

(3)f\left(t\right)=\underset{x}{\sup }\left\{g\left(x\right):Ax=t,x\in S\right\},

where A is a 2 × n matrix, S is a subset of {\Re }^n and g is an n-dimensional function defined on S.

THEOREM 4. (^{Chen et al. 2013}) Given any \mathrm{2}\times nmatrixA\ge \mathrm{0}, if S is a nonempty closed convex sublattice, then so is the set T; moreover, if g is concave and supermodular on S, then so is f on T.

L^{♮}-Convexity

L^{♮}-convexity was first proposed by ^{Murota (1998)} for functions defined on integer spaces. Specifically, a function f: Zⁿ\to \overline{\Re } is (discrete) L^{♮}-convex if for any x, y∈ Zⁿ,

f\left(x\right)+f\left(y\right)\ge f\left(\lceil {\displaystyle \frac{x+y}{\mathrm{2}}}\rceil \right)+f\left(\lfloor {\displaystyle \frac{x+y}{\mathrm{2}}}\rfloor \right),

where \lceil z\rceil is the smallest integer vector no less than z and \lfloor z\rfloor is the largest integer vector no more than z. The above definition is an extension of the midpoint convexity defined in continuous spaces. Interestingly, if the effective domain of f is {\left\{\mathrm{0},\mathrm{1}\right\}}^n, it is straightforward to verify that f is supermodular over {\left\{\mathrm{0},\mathrm{1}\right\}}^n, which illustrates a strong connection between L^{♮}-convexity and supermodularity. In fact, for our purpose, an equivalent but more convenient definition of L^{♮}-convexity on \mathcal{Z}ⁿ is given as follows. In addition, the definition can be extended to functions defined on {\Re }^n. For some applications, we need the extension of L^{♮}-convexity to more general spaces (see for example ^{Chen et al. 2017} and ^{Xu et al. 2016}). For simplicity, we restrict to finite dimensional spaces.

DEFINITION 2( L^{♮}-CONVEXITY). A function f: \mathcal{F}ⁿ→ \overline{\Re } is L^{♮}-convex if for any x, x'∈ \mathcal{F}ⁿ, a∈ \mathcal{F}₊,

(4)f\left(x\right)+f\left(x^{\prime }\right)\ge f\left(\left(x+\alpha e\right)\wedge x^{\prime }\right)+f\left(x\vee \left(x^{\prime }-\alpha e\right)\right),

where e is the n-dimensional all-ones vector. A function f is L^{♮}-concave if-f is L^{♮}-convex. A set \mathcal{V} is L^{♮}-convex if its indicator function, {\delta }_{\mathcal{V}}: \mathcal{F}ⁿ\to \overline{\Re }, defined as {\delta }_{\mathcal{V}}(x) = 0 if x∈ \mathcal{V}and +\inftyotherwise, is L^{♮}-convex.

We sometimes say a function f is L^{♮}-convex on a set \mathcal{V}⊆ \mathcal{F}ⁿ with the understanding that \mathcal{V} is an L^{♮}-convex and the extension of f to the whole space \mathcal{F}ⁿ by defining f\left(x\right)=+\infty for x ∉ \mathcal{V} is L^{♮}-convex.

Next, we give another definition for L^{♮}-convexity.

PROPOSITION 3.A function f: \mathcal{F}ⁿ\to \overline{\Re } is L^{♮}-convex if and only if g\left(x,\xi \right):=f\left(x-\xi e\right) is submodular on \left(x,\xi \right)∈ \mathcal{F}ⁿ × \mathcal{S}, where \mathcal{S} is the intersection of \mathcal{F} and any unbounded interval in \Re.

We can show that if f:{\Re }^n\to \overline{\Re } is L^{♮}-convex and continuous, then f is convex and submodular.

In the following we present some examples of L^{♮}-convex functions and L^{♮}-convex sets.

PROPOSITION 4.(a) Given any univariate convex (or discrete convex if \mathcal{F} = \mathcal{Z}) functions g_i: \mathcal{F}\to \overline{\Re }\left(i=\mathrm{1},...,n\right) and h_{ij}:\Re \to \overline{\Re }\left(i\ne j\right), the function f: \mathcal{F}ⁿ\to \overline{\Re } defined by

f\left(x\right):={\displaystyle \sum _{i=\mathrm{1}}^n{g}_i}\left(x_i\right)+{\displaystyle \sum _{i\ne j}{h}_i{}_j\left(x_i-x_j\right)}

is L^{♮}-convex. As a special case, any linear function is L^{♮}-convex.

(b)A quadratic function f:{\Re }^n\to \Re defined by f\left(x\right)={\displaystyle {\sum }_{i,j=\mathrm{1}}^n{a}_{ij}{x}_i{x}_j} with a_{ij}=a_{ji}\in \Re is L^{♮}-convex if and only if the matrix A with its ij-th component being a_ij is a diagonally dominant M-matrix, i.e.,

a_{ij}\le \mathrm{0},\forall i\ne j,a_{ij}\ge \mathrm{0},and{\displaystyle \sum _{j=\mathrm{1}}^n{a}_{ij}\ge \mathrm{0},\forall i}.

(c)A twice continuously differentiable function f:{\Re }^n\to \Re is L^{♮}-convex if and only if its Hessian is a diagonally dominant M-matrix.

(d)For a given vector a\in {\Re }^n and a nondecreasing univariate function f:\Re \to \Re, the function g:{\Re }^n\to \Re defined by g\left(x\right)=f\left({\max }_{i=\mathrm{1}:n}\left\{a_i+x_i\right\}\right) is L^{♮}-convex.

(e)A set with a representation {x∈ \mathcal{F}ⁿ:l\le x\le u, x_i-x_j\le v_{ij}, \forall i\ne j} is L^{♮}-convex in the space \mathcal{F}ⁿ, where l, u∈\mathcal{F}ⁿ and v_ij∈\mathcal{F}(i\ne j). In fact, any closed L^{♮}-convex set in the space \mathcal{F}ⁿ can have such a representation.

Following are some useful preservation properties for L^{♮}-convex functions. Some of these properties are similar to Proposition 1, but more restrictive than the properties in Proposition 1.

PROPOSITION 5.(a) Any nonnegative linear combination of L^{♮}-convex functions is L^{♮}-convex. That is, if f_i: \mathcal{F}ⁿ\left(i=\mathrm{1},\mathrm{2},...,m\right)\to \overline{\Re } are L^{♮}-convex, then for any scalar {\alpha }_i\ge \mathrm{0},{\displaystyle {\sum }_{i=\mathrm{1}}^m{\alpha }_i{f}_i}is also L^{♮}-convex.

(b)If f_k is L^{♮}-convex for k=\mathrm{1},\mathrm{2},... and {\lim }_{k\to \infty }{f}_k\left(x\right)=f\left(x\right) for any x∈ \mathcal{F}ⁿ, then f\left(x\right) is L^{♮}-convex.

(c)Assume that a function f\left(·,·\right) is defined on the product space \mathcal{F}ⁿ × \mathcal{F}^m. If f\left(·,\hspace{0.17em}y\right) is L^{♮}-convex for any given y∈\mathcal{F}^m, then for a random vector z in \mathcal{F}^m, E_{\zeta }\left[f\right(x,\zeta \left)\right] is L^{♮}-convex, provided it is well defined.

(d)If f: \mathcal{F}ⁿ\to \overline{\Re } is an L^{♮}-convex function, then g: \mathcal{F}ⁿ × \mathcal{F}\to \overline{\Re } defined by g\left(x,\xi \right)=f\left(x-\xi e\right) is also L^{♮}-convex.

L^{♮}-convexity is closely related to a notion called m-differential monotone, introduced by ^{Chen (2004)} to analyze the optimality of hedging point policies for a stochastic two-product flexible manufacturing systems.

DEFINITION 3.Given a given positive vector \mu \in {\Re }^{\mathrm{2}}, a convex function f:{\Re }^{\mathrm{2}}\to \Re is said to be m-differential monotone if for any t>\mathrm{0},

(1) f\left(x_{\mathrm{1}}+t,\hspace{0.17em}{x}_{\mathrm{2}}\right)-f\left(x_{\mathrm{1}},\hspace{0.17em}{x}_{\mathrm{2}}\right) is increasing in x₁ and x₂;

(2) f\left(x_{\mathrm{1}},\hspace{0.17em}{x}_{\mathrm{2}}+t\right)-f\left(x_{\mathrm{1}},\hspace{0.17em}{x}_{\mathrm{2}}\right) is increasing in x₁ and x₂;

(3) f(x_{\mathrm{1}}+{\mu }_{\mathrm{1}}t,\hspace{0.17em}{x}_{\mathrm{2}})-f(x_{\mathrm{1}},\hspace{0.17em}{x}_{\mathrm{2}}+{\mu }_{\mathrm{2}}t) is increasing in x₁ and decreasing in x₂.

REMARK 1.^{Chen (2004)} introduces the definition of m-differential monotone based on directional derivatives, but shows that it is equivalent to the above one in function difference forms.

THEOREM 5.Given a positive vector \mu \in {\Re }^{\mathrm{2}}, if f:{\Re }^{\mathrm{2}}\to \Reis convex, then f isμ-differential monotone if and only iff_{\mu }:{\Re }^{\mathrm{2}}\to \Redefined byf_{\mu }\left(x\right)=f({\mu }_{\mathrm{1}}{x}_{\mathrm{1}},-{\mu }_{\mathrm{2}}{x}_{\mathrm{2}})isL^{♮}-convex.

Proof.We first assume f is twice continuously differentiable. From Proposition 4 part (c), we have that f_μ is L^{♮}-convex if and only if its Hessian is a diagonally dominant M-matrix. That is, for any x\in {\Re }^{\mathrm{2}},

{\displaystyle \frac{{\partial }^{\mathrm{2}}{f}_{\mu }\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}}\le \mathrm{0},{\displaystyle \frac{{\partial }^{\mathrm{2}}{f}_{\mu }\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}{}^{\mathrm{2}}}}\ge -{\displaystyle \frac{{\partial }^{\mathrm{2}}{f}_{\mu }\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}},

{\displaystyle \frac{{\partial }^{\mathrm{2}}{f}_{\mu }\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{2}}{}^{\mathrm{2}}}}\ge -{\displaystyle \frac{{\partial }^{\mathrm{2}}{f}_{\mu }\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}}.

Since for i,j=\mathrm{1},\mathrm{2},

{\displaystyle \frac{{\partial }^{\mathrm{2}}{f}_{\mu }\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_i\partial x_j}}=-{\mu }_i{\mu }_j{\displaystyle \frac{{\partial }^{\mathrm{2}}f\left({\mu }_{\mathrm{1}}{x}_{\mathrm{1}},-{\mu }_{\mathrm{2}}{x}_{\mathrm{2}}\right)}{\partial x_i\partial x_j}}

the above inequalities are equivalent to the following ones respectively: for any x\in {\Re }^{\mathrm{2}},

{\displaystyle \frac{{\partial }^{\mathrm{2}}f\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}}\ge \mathrm{0}\hspace{0.17em},{\mu }_{\mathrm{1}}{\displaystyle \frac{{\partial }^{\mathrm{2}}f\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}{}^{\mathrm{2}}}}\ge {\mu }_{\mathrm{2}}{\displaystyle \frac{{\partial }^{\mathrm{2}}f\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}},

(5){\mu }_{\mathrm{2}}{\displaystyle \frac{{\partial }^{\mathrm{2}}f\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{2}}{}^{\mathrm{2}}}}\ge {\mu }_{\mathrm{1}}{\displaystyle \frac{{\partial }^{\mathrm{2}}f\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}}.

On the other hand, the conditions in the definition of m-differential monotone is equivalent to the inequalities (5) as well. Thus, our proposition holds for twice continuously differentiable functions.

If f is not twice continuously differentiable, we can smoothen f by f^{�}\left(x\right)=E[\hspace{0.17em}f(x-�\tilde{z}\left)\right], where \tilde{z}=\left({\tilde{z}}_{\mathrm{1}},{\tilde{z}}_{\mathrm{2}}\right), and {\tilde{z}}_{\mathrm{1}} and {\tilde{z}}_{\mathrm{2}} are independent and follow the standard normal distribution. It is easy to see that if f is m-differential monotone, then so does f^{�} for any �>\mathrm{0}, which implies that f_{\mu }^{�} is L^{♮}-convex. Letting �\to \mathrm{0}, from Proposition 5 part (b), we have f_{\mu } is L^{♮}-convex. Conversely, if f_{\mu } is L^{♮}-convex, then so does f_{\mu }^{�} by Proposition 5 part (c), which implies that f^{�} is m-differential monotone. Letting �\to \mathrm{0}, we have that f is m-differential monotone.ƒƒƒƒQ.E.D.

L^{♮}-convexity is also closely related to the notion of multimodularity in discrete-event control (^{Hajek, 1985}). A function f:\mathcal{F}ⁿ\to \overline{\Re } with dom (f€)≠∅ is said to be multimodular if the function \tilde{f}:\mathcal{F}^{n+ 1}\to \overline{\Re } defined by

\tilde{f}(x_{\mathrm{0}},x)=f(x_{\mathrm{1}}-x_{\mathrm{0}},x_{\mathrm{2}}-x_{\mathrm{1}},\mathrm{....},x_n-x_{n-\mathrm{1}})

is submodular in n + 1 variables. ^{Murota (2005)} establishes the following relationship.

PROPOSITION 6. A function f:\mathcal{F}ⁿ\to \overline{\Re } is multimodular if and only if it can be represented as

f\left(x\right)=g(x_{\mathrm{1}},x_{\mathrm{1}}+x_{\mathrm{2}},x_{\mathrm{1}}+x_{\mathrm{2}}+x_{\mathrm{3}},\mathrm{....},x_{\mathrm{1}}+\mathrm{...},+x_n)

for someL^{♮}-convex function g. Conversely, a function g: \mathcal{F}ⁿ\to \overline{\Re }isL^{♮}-convex if and only if it can be represented as

g\left(p\right)=f(p_{\mathrm{1}},p_{\mathrm{2}}-p_{\mathrm{1}},p_{\mathrm{3}}-p_{\mathrm{2}},\mathrm{...},p_n-p_{n-\mathrm{1}})

for some multimodular function f.

REMARK2. ^{Murota (2005)} proves the above result for  \mathcal{F}= \mathcal{Z}. It is straightforward to show that it is still true if \mathcal{F} = \Re.

Let

{\mathcal{V}}_{n,k}=\{\left(s_{\mathrm{1}},\mathrm{...},s_n\right)\in {\mathcal{F}}^n:s_{\mathrm{1}}\le \mathrm{...}\le s_k\}

and



{\mathcal{V}}_{n,k}^{+}=\{\left(s_{\mathrm{1}},\mathrm{...},s_n\right)\in {\mathcal{F}}^n:\mathrm{0}\le s_{\mathrm{1}}\le \mathrm{...}\le s_k\}\mathrm{.}

Note that both sets are L^{♮}-convex.

The following result is developed in ^{Chen X et al. (2014)} to analyze perishable inventory models.

PROPOSITION 7. (^{Chen X et al. 2014}) Assume that f: \mathcal{F}ⁿ\to \overline{\Re } is an L^{♮}-convex function. If f is nondecreasing in its first k(\mathrm{1}\le k\le n)variables for s∈ {\mathcal{V}}_{n,k}^{+}, then the function

\widehat{f}(s_{\mathrm{1}},\mathrm{...}{s}_n,s_{n+\mathrm{1}}):=f({\left(s_{\mathrm{1}}-s_{n+\mathrm{1}}\right)}^{+},\mathrm{...},{\left(s_k-s_{n+\mathrm{1}}\right)}^{+},

s_{k+\mathrm{1}}-s_{n+\mathrm{1}},\mathrm{...},s_n-s_{n+\mathrm{1}})

is L^{♮}-convex for (s₁, ..., s_n, s_n+1)∈\mathcal{V}_{n+ 1, k} . If f\left(s\right) is nondecreasing in all variables for s ∈ \mathcal{V}{}_{n,n}^{+}, then the function

g(s_{\mathrm{1}},\mathrm{...},s_n,s_{n+\mathrm{1}}):=f({(s_{\mathrm{1}}-s_{n+\mathrm{1}})}^{+},\mathrm{...},{(s_k-s_{n+\mathrm{1}})}^{+},

s_{k+\mathrm{1}}-s_k\wedge s_{n+\mathrm{1}},\mathrm{...},s_n-s_k\wedge s_{n+\mathrm{1}})

is L^{♮}-convex on the L^{♮}-convex set \mathcal{V}_{n+1, n}.

We now come back to the parametric optimization problem (2) and impose L^{♮}-convexity. Similar to Theorem 2, we can show that the optimal solution set S*(t) is increasing in t. In addition, it has a bounded sensitivity.

THEOREM 6.In the parametric optimization problem (2), assume that the graph of the parametric constraint set, \mathcal{A}, is an L^{♮}-convex set of \mathcal{F}ⁿ × \mathcal{F}^m and g\left(·,·\right): \mathcal{F}ⁿ × \mathcal{F}^m\to \overline{\Re }is anL^{♮}-convex function. Then the optimal solution set S*(t) is increasing in t∈T. In addition, for any t∈T and a scaler \omega \ge \mathrm{0} with t+\omega e\in T,

S^{*}(t+\omega e)⊑\omega \tilde{e}+S^{*}\left(t\right),

where T= {t∈\mathcal{F}^m| S*(t)≠ Ø}, and e and \tilde{e}are the all-ones vectors with dimensions consistent with t and x respectively.

REMARK 3.The above result first appears in ^{Chen et al. (2017)} and is a slight generalization of a corresponding one in ^{Zipkin (2008)} which deals with m=\mathrm{1}.

We also have the following preservation property of L^{♮}-convexity, which again is very useful in dynamic programming recursions.

THEOREM 7.In the parametric optimization problem (2), assume that the graph of the parametric constraint set, \mathcal{A}, is an L^{♮}-convex set of \mathcal{F}ⁿ × \mathcal{F}^m and g\left(·,·\right): \mathcal{F}ⁿ × \mathcal{F}^m\to \overline{\Re }is anL^{♮}-convex function. Then f is L^{♮}-convex over \mathcal{F}^m if f\left(t\right)\ne -\inftyfor any t∈ \mathcal{F}^m.

Similar to Theorem 4, we can relax the L^{♮}-convexity assumption on the graph of the parametric constraint set when the parameters are restricted to a two-dimensional space.

THEOREM 8.(^{Chen et al. 2013}) Consider the parametric optimization problem

f\left(t\right)=\underset{x}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{{\displaystyle \sum _{i=\mathrm{1}}^n{g}_i\left(x_i\right)}:{\displaystyle \sum _{i=\mathrm{1}}^n{x}_i}=t,x_i\in S_i\hspace{0.17em}\forall i=\mathrm{1},\mathrm{...},n\right\},

wheret, x_i∈ \mathcal{F}²and S_i⊆ \mathcal{F}²,

i=\mathrm{1},\mathrm{2},...,n

. If all g_i: \mathcal{F}²\to \overline{\Re }areL^{♮}-convex functions and allS_iareL^{♮}-convex sets, thenf is L^{♮}-convex on T=\{{\displaystyle {\sum }_{i=\mathrm{1}}^n{x}_i}:x_i\in S_i\forall i=\mathrm{1},...,n\}.

REMARK 4.^{Chen et al. (2013)} presents the above theorem for \mathcal{F} = ℜ. It can be extend to \mathcal{F} = \mathcal{Z} easily.

In an attempt to deal with inventory models with random capacity or revenue management problems using booking limit control in which decisions are truncated by random variables, ^{Chen et al. (2017)} derive useful properties of convexity, submodularity and L^{♮}-convexity for the following problem.

(6)f(x,z)=\underset{u:(x,z,u)\in \mathcal{A}}{\inf }{E}_{\Xi }[g(x,u{\diamond }_k(z+\Xi ))],

where g\left(·,·\right): \mathcal{F}^m × \mathcal{F}ⁿ\to \overline{\Re }, x∈ \mathcal{F}^m, z∈ \mathcal{F}ⁿ, the set \mathcal{A}⊆ \mathcal{F}^m × \mathcal{F}ⁿ × \mathcal{F}ⁿ is non-empty, and {\diamond }_k is defined as u{\diamond }_k\xi \triangleq \left(u_{\mathrm{1}}\wedge {\xi }_{\mathrm{1}},...,u_k\wedge {\xi }_k,u_{k+\mathrm{1}}\vee {\xi }_{k+\mathrm{1}},...,u_n\vee {\xi }_n\right).

ASSUMPTION 1.For any given x, (a) g\left(x,·\right)is lower semi-continuous with g\left(x,u\right)\to +\infty for {\Vert u\Vert }_{\mathrm{2}}\to \infty; (b) g\left(x,·\right)is component-wise convex (component-wise discrete convex if\mathcal{F} = \mathcal{Z}).

ASSUMPTION 2.The random vector Xhas independent components. Its support is denoted by\mathcal{X}Xand the support of the j-th component is denoted by\mathcal{X}_j.

ASSUMPTION 3.The set

\mathcal{A}=\left\{\left(x,z,u\right)\right|Au\le b,u_{\mathrm{1}}\ge {\underline{u}}_{\mathrm{1}},

, where b, {\underline{u}}_{\mathrm{1}},\mathrm{...},{\underline{u}}_k, {\overline{u}}_{k+\mathrm{1}},...,{\overline{u}}_nare parameters that may depend on x and z, A=\left(a_{ij}\right)with entriesa_{ij}>\mathrm{0}for any i andj=\mathrm{1},\mathrm{...},k, anda_{ij}\le \mathrm{0}for any i andj=k+\mathrm{1},\mathrm{...},n. In addition, {\mathcal{X}}_jis contained in[{\underline{u}}_j-z_j,+\infty )forj=\mathrm{1},\mathrm{...},k, and{\mathcal{X}}_jis contained in\left(-\infty ,{\overline{u}}_j-z_j\right]forj=k+\mathrm{1},\mathrm{...},n.

THEOREM 9.(^{Chen et al. 2017}) Consider the optimization problem (6). Under Assumptions 1-3, problem (6) and the following optimization problem have the same optimal objective value.

\begin{array}{l}\inf \hspace{0.17em}E\left[\hspace{0.17em}g\left(x,v_{\mathrm{1}}\left({\Xi }_{\mathrm{1}}\right),\mathrm{...},v_n\left({\Xi }_n\right)\right)\right]\hfill \\ \mathrm{s}\mathrm{.t}.v_j\left({\xi }_j\right)\le z_j+{\xi }_j\hspace{0.17em}\hspace{0.17em}\forall {\xi }_j\in {\mathcal{X}}_j,\hspace{0.17em}\forall j=\mathrm{1},\mathrm{...},k\hfill \end{array}

(7)\begin{array}{l}{v}_j\left({\xi }_j\right)\ge z_j+{\xi }_j\hspace{0.17em}\hspace{0.17em}\forall {\xi }_j\in {\mathcal{X}}_j,\hspace{0.17em}\forall j=k+\mathrm{1},\mathrm{...},n\hfill \\ \left(x,z,v_{\mathrm{1}}\left({\xi }_{\mathrm{1}}\right),\mathrm{...},v_n\left({\xi }_n\right)\right)\in {\mathcal{A}}^{\Xi }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall \xi \in \mathcal{X},\hfill \end{array}

where {\mathcal{A}}^{\mathrm{\Xi }}^X = {(x, z, w)| w= u⋄_k(z+ ξ), (x, z, u)∈ A, ξ∈ \mathcal{X}}. Furthermore,

(a) If g and{\mathcal{A}}^{\mathrm{\Xi }}are convex, then f is also convex.

(b) If g is submodular and{\mathcal{A}}^{\mathrm{\Xi }}is a lattice, then f is also submodular.

(c) If g and {\mathcal{A}}^{\mathrm{\Xi }} are L^{♮}-convex, then f is also L^{♮}-convex.

We refer to ^{Gao (2017)} for several generalizations of the above theorem: models with dependent random variables; models with a cost term c(u); models taking risk preference into account.

The following theorem characterizes the monotonicity properties of the solution set to the optimization problem (6). Let {\mathcal{U}}^{*}\left(x,z\right) denote the optimal solution set of (6).

THEOREM 10. (^{Chen et al. 2017}) Consider the optimization problem (6). Under Assumptions 1-3, if {\mathcal{A}}^{\mathrm{\Xi }} is closed, andu_j\le z_j+{\overline{\xi }}_j,j=\mathrm{1},...,k,u_j\ge z_j+{\underline{\xi }}_j, j=k+\mathrm{1},\mathrm{...},n,then we have the following results:

(a) If g is a submodular function, and \mathcal{A}, {\mathcal{A}}^{\mathrm{\Xi }} are lattices, then \mathcal{U}^*(x, z) is increasingin\left(x,z\right). There exist a greatest element and a least element in\mathcal{U}*(x, z), which are increasingin\left(x,z\right).

(b) If g is an L^{♮}-convex function, and \mathcal{A}, {\mathcal{A}}^{\mathrm{\Xi }} are L^{♮}-convex sets, then \mathcal{U}^*(x, z) is increasing in\left(x,z\right)and\mathcal{U}*((x, z) + ωe) ⊑ \mathcal{U}*(x, z) + ωx for any\omega >\mathrm{0}. Within\mathcal{U}*(x, z), there exist a greatest element and a least element, which have the above monotonicity properties with limited sensitivity.

Inventory applications

In this section, we illustrate how to apply L^{♮}-convexity to a perishable inventory model and a joint inventory and transshipment control model.

Perishable inventory models

Dynamic inventory control for perishable products with fixed-lifetime was studied by ^{Nahmias and Pierskalla (1973)} in a two-period lifetime setting with zero lead time and demand uncertainty. ^{Nahmias (1975)} and ^{Fries (1975)} analyze the case with multi-period lifetime and zero lead time. Yet, their analysis is lengthy and difficult to be generalized. To highlight the complexity, note that “The main theorem requires 17 steps and is proven via a complex induction argument” (^{Nahmias, 2011}, page 10) and for models with discrete demand, a separate argument of using a sequence of continuous demand distributions to approximate the discrete demand distribution is needed (^{Nahmias and Schmidt, 1986}).

Employing L^{♮}-convexity, ^{Chen X et al. (2014)} give a significantly simpler proof of the structural result in ^{Nahmias (1975)} and ^{Fries (1975)}. In addition, they provide a unified approach to deal with both backlogging and lost sales models, and their approach allows for both continuous and discrete demand and many other extensions. Our presentation follows ^{Chen X et al. (2014)} but focuses on a simplified version with lost sales and zero lead time.

Consider a periodic-review single-product inventory system over a finite horizon of T periods. The product is perishable and has a finite lifetime of exactly l periods. The replenishment lead time is assumed to be zero. In each period, a single price is charged for inventories of different ages, which are equally useful to fill consumer's price-sensitive demand. Demand is always met to the maximum extent with the on-hand inventory and unmet demand is lost. We assume that the retailer has the power or mechanism to determine how inventory is issued, and can also decide how much inventory to be carried over to the next period and how much inventory in addition to that at the end of its lifetime to be intentionally disposed of. The objective is to dynamically determine ordering, disposal and pricing decisions in all periods so as to maximize the total expected discounted profit over the planning horizon.

For convenience, we assume that the age of the inventory is counted from the period when the replenishment order is placed. If l=\mathrm{1}, then the model reduces to a newsvendor model in the lost-sales case. If l=\infty, then it becomes a standard non-perishable inventory model. We assume that the costs and demand distributions are stationary.

The demand takes an additive form as is commonly used in the literature (see, e.g., ^{Petruzzi and Dada, 1999}; ^{Chen and Simchi-Levi, 2004a,b}). That is, the demand in period t is given as follows:

(8)d_t:=D\left(p\right)+{�}_t,

where D(p) is the expected demand in period t and is strictly decreasing in the selling price p in this period, and є_t is a random variable with zero mean. We assume that \{{�}_t,t\ge \mathrm{1}\} are independently and identically distributed over time with a bounded support \left[A,B\right], (A\le \mathrm{0}\le B). Let F(·)be the probability distribution function of {�}_t. The selling price p is restricted to an interval [\underline{p},\overline{p}].To ensure non-negativity, we assume that D\left(\overline{p}\right)+A\ge \mathrm{0}.

Note that the monotonicity of the expected demand function implies a one-to-one correspondence between the selling price p and the expected demand d\in \mathcal{D}\equiv \left[\underline{d},\overline{d}\right], where \underline{d}=D\left(\overline{p}\right) and \overline{d}=D\left(\underline{p}\right). For convenience, we use the expected demand instead of the price as the decision variable in our analysis.

Let R\left(d,y\right)=P\left(d\right)E\left[min\left(d+{�}_t,y\right)\right] be the expected revenue for any given expected demand level d and on-hand inventory level y. Here P(d) is the inverse function of D(p).

ASSUMPTION 4. R(d, y) is continuous and L^{♮}-concave in \left(d,y\right)\in \mathcal{D}\times {\Re }_{+}.

This assumption implies that the marginal value of the expected revenue is decreasing not only in the demand level but also in the on-hand inventory level. In addition, the higher the inventory level, the higher the marginal revenue of increasing demand level. In other words, the demand and on-hand inventory are complementary to each other. In general, the concavity of the unconstrained revenue P(d)d cannot guarantee the joint concavity of the inventory-truncated revenue R(d,y). We refer to ^{Chen X et al. (2014)} for conditions under which Assumption 4 holds.

The sequence of events in period t is as follows.

1.At the beginning of the period, the inventory levels of different residual useful lifetimes are observed.

2.Based on the inventory levels of different residual useful lifetimes, an order is placed and will be delivered immediately. At the same time, the selling price p_t of period t is determined.

3.During period t, demand d_t arrives, which is stochastic and depends on the selling price p_t, and is satisfied by on-hand inventory.

4.Unsatisfied demand is lost and the remaining inventory with zero useful lifetime has to be discarded. Meanwhile, unused inventory with positive useful lifetimes can be either intentionally discarded or carried over to the next period. In the latter case, their lifetimes decrease by one.

Each order incurs a variable cost c. Inventory carried over from one period to the next incurs a holding cost of h⁺ per unit, and demand that is not satisfied from on-hand inventory incurs a cost of h^- per unit which represents the backlogging cost or the lost-sales penalty cost. Inventory that is disposed of incurs a disposal cost of q per unit. Let g∈ [0,1] be the discount factor.

The system state after receiving the order placed k periods ago but before placing an order can be represented by an (l - 1)-dimensional vector . Here, s_i is the total amount of inventory with residual lifetimes no more than i periods, i=\mathrm{1},...,l-\mathrm{1}. In particular, is the system inventory position and s_{l-k} is the net on-hand inventory level. The state variables satisfy the condition that \mathrm{0}\le s_{\mathrm{1}}\le s_{\mathrm{2}}\le ...\le s_{l-\mathrm{1}} and the set of feasible states is given by

{{\displaystyle \mathcal{F}}}_l={\mathcal{V}}_{l-\mathrm{1},l-\mathrm{1}}^{+}.

In the literature, it is common to denote the system state by an (l-1)-dimensional vector where x_i is the amount of inventory on hand of age l-i. Clearly,

Let s_l be the order-up-to level and a be the amount of on-hand inventory to be depleted or the realized demand of period t, whichever is greater. We have that

s_{\mathrm{1}}\vee d_t\le a\le s_{l-k}\vee d_t.

When demand is greater than the total on-hand inventory level , the above inequalities imply that a=d_t. Otherwise, they imply that s_{\mathrm{1}}\vee d_t\le a\le s_{l-k}, which in turn implies that (1) the firm satisfies the demand to the maximum extent, and (2) in addition to the inventory at the end of life, the firm could also intentionally dispose of some more inventory that will expire in later periods. We also note that since on-hand inventory can be intentionally disposed of, it is not difficult to show that it is optimal to deplete on-hand inventory sequentially with increasing useful lifetimes, i.e., FIFO depletion policy is optimal.

The system state at the beginning of the next period before ordering, denoted by \tilde{\mathit{s}}, evolves as follows:

(9)\tilde{\mathit{s}}=[{(s_{\mathrm{2}}-a)}^{+},\mathrm{...},{(s_l-a)}^{+}].

We are now ready to present the model formulation. Let {\widehat{f}}_t\left(\mathit{s}\right) be the profit-to-go function when the system state is specified by s∈ \mathcal{F}_l at the beginning of period t before ordering. We can write the optimality equation as follows:

{\widehat{f}}_t\left(\mathit{s}\right)=\underset{s_l\ge s_{l-\mathrm{1}},d\in \mathcal{D}}{\max }\left\{R(d,s_l\mathrm{)+}\mathcal{E}\left[{\widehat{g}}_t\left(s,s_l,d|{�}_t\right)\right]\right\},

where

{\widehat{g}}_t\left(\mathit{s},s_l,d|{�}_t\right)=\underset{s_{\mathrm{1}}\vee d_t\le a\le s_l\vee d_t}{\max }\{-c(s_l-s_{l-\mathrm{1}})-\theta (a-d_t)

-h^{+}{\left(s_l-a\right)}^{+}-h^{-}{\left(a-s_l\right)}^{+}+\gamma {\widehat{f}}_{t+\mathrm{1}}\left(\tilde{s}\right)\}.

Here the four terms in the maximization problem defining {\widehat{g}}_t represent the ordering cost, disposal cost, inventory holding cost, and lost-sales penalty cost, respectively. Also recall that d_t=d+{�}_t. For simplicity, we assume that {\widehat{f}}_{T+\mathrm{1}}\left(\mathit{s}\right)=c{s}_{l-\mathrm{1}}, i.e., inventory (or unfilled orders) at the end of the planning horizon is salvaged (or filled) with a unit price (or cost) equal to the unit ordering cost.

It is more convenient to work with a slightly modified profit-to-go function. Define for s∉ \mathcal{F}_l, f_t\left(\mathit{s}\right)=+\infty and for s∈ \mathcal{F}_l, f_t\left(\mathit{s}\right)={\widehat{f}}_t\left(\mathit{s}\right)-c{s}_{l-\mathrm{1}} for all t. Then for s∈ \mathcal{F}_l, f_T{}_{+\mathrm{1}}\left(s\right)=\mathrm{0} and the optimality equation can be rewritten as follows:

(10)f_t\left(\mathit{s}\right)=\underset{s_l\ge s_{l-\mathrm{1}},d\in {\mathcal{D}}_t}{\max }{G}_t(\mathit{s},s_l,d)

with

{{\displaystyle G}}_t\left(\mathit{s},{{\displaystyle s}}_l,d\right)=R\left(d,{{\displaystyle s}}_l\right)+\mathcal{E}\left[{{\displaystyle g}}_t\left(\mathit{s},{{\displaystyle s}}_l,d|{{\displaystyle �}}_t\right)\right],

where

(11)g_t\left(\mathit{s},s_l,d|{�}_t\right)=\underset{s_{\mathrm{1}}\vee d_t\le a\le s_l\vee d_t}{\max }\left\{{\varphi }_t\left(\mathit{s},s_l,d,a|{�}_t\right)\right\},

{\varphi }_t\left(\mathit{s},s_l,d,a|{�}_t\right)=-c{s}_l+h{}^{-}(s_l-a)-\left(h{}^{+}+h{}^{-}-\gamma c\right){(s_l-a)}^{+}

(12)-\theta (a-d_t)+\gamma f_{t+\mathrm{1}}\left(\tilde{s}\right).

Denote by s_{lt}\left(\mathit{s}\right), d_t\left(\mathit{s}\right) the optimal order-up-to inventory position and demand level decisions and a_t\left(\mathit{s},s_l,d\right) the optimal inventory depletion solution for any given \left(\mathit{s},s_l,d\right).

We assume that h^{+}+h^{-}\ge \gamma c which implies that the cost of carrying a unit of inventory to the next period while facing lost sales is larger than the potential salvage value of the inventory.

We have the following monotonicity property of the value-to-go functions, which allows us to use the preservation property of L^{♮}-convexity in Proposition 7.

LEMMA 1.Fort=\mathrm{1},\mathrm{...},T+\mathrm{1} and any s∈ \mathcal{F}_l, f_t\left(s\right) is nonincreasing in , respectively.

We are ready to present our main result in this subsection.

THEOREM 11(MONOTONICITY PROPERTIES OF LOST-SALES MODEL). Under Assumption 4, for t=\mathrm{1},\mathrm{...},T, the functionsf_t\left(\mathit{s}\right),g_t\left(s,s_l,d\right) and {\varphi }_t\left(\mathit{s},s_l,d,a|{�}_t\right)areL^{♮}-concave ins, \left(\mathit{s},s_l,d\right)and\left(\mathit{s},s_l,d,a\right), respectively. Thus, the optimal order-up-to levels_{lt}\left(s\right)and the optimal demand leveld_t\left(\mathit{s}\right)are nondecreasing ins (i.e., the optimal pricep_t\left(\mathit{s}\right)is nonincreasing ins), and for any\omega \ge \mathrm{0}

(13)s_{lt}(\mathit{s}+\omega e)\le s_{lt}\left(\mathit{s}\right)+\omega ,and{d}_t(\mathit{s}+\omega e)\le d_t\left(\mathit{s}\right)+\omega

Given the realized demand d_t, the optimal depletion decisiona_t\left(\mathit{s},s_l,d|{�}_t\right) is nondecreasing in \left(\mathit{s},s_l,d\right) and for any \omega \ge \mathrm{0}

(14){\alpha }_t(\mathit{s}+\omega e,s_l+\omega ,d+\omega |{�}_t)\le a_t(\mathit{s},s_l,d\left|{�}_t\right)+\omega .

Proof. First, applying Lemma 1, we know that f_t\left(\mathit{s}\right) is nonincreasing in s for all t. Then, by Proposition 7, the L^{♮}-concavity of implies that f_{t+\mathrm{1}}\left(\tilde{s}\right)is L^{♮}-concave in \left(\mathit{s},s_l,d,a\right)\in {\mathcal{V}}_{l+\mathrm{1.}l}^{+}. The other terms in {\varphi }_t\left(\mathit{s},s_l,d,a|{�}_t\right)are all L^{♮}-concave in their variables. Thus, {\varphi }_t\left(\mathit{s},s_l,d,a|{�}_t\right)is L^{♮}-concave for \left(\mathit{s},s_l,d,a\right)\in {\mathcal{V}}_{l+\mathrm{2},l}^{+}.

We next show that g_t\left(\mathit{s},s_l,d|{�}_t\right) is L^{♮}-concave in \left(\mathit{s},s_l,d\right)\in {\mathcal{V}}_{l+\mathrm{1},l}. The idea is to use Theorem 7 to show that L^{♮}-concavity can be preserved under the optimization problem (11). Unfortunately, the constraint in (11), s_{\mathrm{1}}\vee d_t\le a\le s_{l-k}\vee d_t, is not L^{♮}-convex. Interestingly, we can prove that this constraint a\le s_l\vee d_t can be removed, i.e., g_t\left(\mathit{s},s_l,d|{�}_t\right)={\tilde{g}}_t\left(\mathit{s},s_l,d|{�}_t\right), where

{\tilde{g}}_t(\mathit{s},s_l,d|{�}_t)=\underset{a\ge s_{\mathrm{1}}\vee d_t}{\max }\left\{{\varphi }_t\left(\mathit{s},s_l,a,d|{�}_t\right)\right\}.

Although a>s_l\vee d_t does not have any physical meaning, it is well defined mathematically. It suffices to show {\varphi }_t\left(\mathit{s},s_l,a,d\right) is decreasing in a for a\ge s_l\vee d_t, which is quite straightforward to verify from (12).

It is easy to check that the set \left\{\left(s_{\mathrm{1}},d,a\right):a\ge s_{\mathrm{1}}\vee d_t\right\}=\left\{\left(s_{\mathrm{1}},d,a\right):a\ge s_{\mathrm{1}},a\ge d_t\right\} is L^{♮}-convex. From Theorem 7, we have {\tilde{g}}_t\left(\mathit{s},s_l,d|{�}_t\right)and hence g_t\left(\mathit{s},s_l,d|{�}_t\right) are L^{♮}-concave in \left(\mathit{s},s_l,d\right). Since L^{♮}-concavity is preserved under expectation and R(d,s_l) is L^{♮}-concave by Assumption 4, the objective function in the optimization problem (10) is L^{♮}-concave. This, together with L^{♮}-convexity of the set associated with the constraints in the optimization problem (10) and Theorem 7, implies that f_t\left(\mathit{s}\right) is L^{♮}-concave in s.

By Theorem 6, we know that the optimal order-up-to level s_{lt}\left(\mathit{s}\right) and the optimal demand level d_t\left(\mathit{s}\right) are nondecreasing in s and the inequalities in (13) hold (the existence of optimal solutions is straightforward to check and is thus omitted). The monotonicity of P(d) implies that the optimal price p_t(s) is nonincreasing in s. The desired results hold. Q.E.D.

The inequalities in (13) imply that the optimal pricing and ordering decisions have bounded sensitivity. That is, a unit increase in some or all of the state variables will increase the order-up-to inventory position level s_{lt}\left(\mathit{s}\right) and the optimal demand level d_t\left(\mathit{s}\right) by at most one unit. The rates of the increase in decision variables are slower than that of the increase in state variables. These inequalities also provide insight into how the freshness of the inventory affects the inventory and pricing decisions. Comparing the states s and \mathit{s}+e_i, the latter has one more unit of inventory with residual lifetime of i periods but one less unit of inventory with residual lifetime of i + 1 periods, i=\mathrm{1},...,l-\mathrm{2}. These monotonicity properties imply that the fresher the inventory in the system, the less inventory to order and the higher price to charge.

The inequalities of (14) imply that the optimal depletion decisions also have bounded sensitivity. Furthermore, since s_{lt}\left(\mathit{s}\right) and d_t\left(\mathit{s}\right) are increasing in s, the optimal depletion decision under the optimal policy, a_t\left(\mathit{s},s_{lt}\left(\mathit{s}\right),d_t\left(\mathit{s}\right)|{�}_t\right), is increasing in s and satisfies a_t(\mathit{s}+\omega e,s_{lt}(\mathit{s}+\omega e), d_t(\mathit{s}+\omega e)\left|{�}_t\right)\le a_t(\mathit{s},s_{lt}(\mathit{s}+\omega e), d_t(\mathit{s}+\omega e)\left|{�}_t\right)+\omega for any {�}_t and \omega >\mathrm{0}. That is, the higher the total on-hand inventory level or the more aged the inventory in the system, the more inventory to deplete and to dispose of.

We now translate the structural properties of the optimal decisions with respect to s back to that with respect to x. Let {\widehat{x}}_{lt}\left(\mathit{x}\right) and {\widehat{d}}_t\left(\mathit{x}\right) be the optimal order quantity and demand level with respect to x, respectively.

COROLLARY 1 (MONOTONE SENSITIVITY). For t=\mathrm{1},\mathrm{...},T+\mathrm{1}and for any\omega \ge \mathrm{0}, the following inequalities hold:

(15)-\omega \le {\widehat{x}}_{lt}(\mathit{x}+\omega e_{l-\mathrm{1}})-{\widehat{x}}_{lt}\left(\mathit{x}\right)\le \mathrm{...}\le {\widehat{x}}_{lt}(\mathit{x}+\omega e_{\mathrm{1}})-{\widehat{x}}_{lt}\left(\mathit{x}\right)\le \mathrm{0},

(16)0\le {\widehat{d}}_{lt}(\mathit{x}+\omega e_{l-\mathrm{1}})-{\widehat{d}}_{lt}\left(\mathit{x}\right)\le \mathrm{...}\le {\widehat{d}}_{lt}(\mathit{x}+\omega e_{\mathrm{1}})-{\widehat{d}}_{lt}\left(\mathit{x}\right)\le \omega .

Corollary 1 illustrates that the optimal order quantity and demand level have bounded and monotone sensitivity. In particular, the inequalities in (15) reveal that the optimal order quantity decreases in the inventory level of each age and the sensitivity decreases in age, i.e., it is more sensitive to the younger inventory or outstanding order and least sensitive to the oldest order. The inequalities in (16) show that the optimal demand level increases in the level of inventory of each age and the sensitivity increases in age as well. In particular, it is most sensitive to the inventory close to expiration, i.e., the more inventory to expire the more discount the seller should offer to induce more sales and avoid the disposals.

A Joint Inventory and Transshipment Control Model with Random Capacities

The joint inventory and transshipment control model is introduced in ^{Hu et al. (2008)} with a very lengthy and complicated analysis. Here we follow ^{Chen et al. (2015)}, which, based on L^{♮}-convexity, provide a significantly simplified proof of the main technical result in ^{Hu et al. (2008)}.

Consider a firm has two manufacturing facilities in two separate markets with multiple time periods. Each facility has random capacities which are independent in time. However, the random capacities at the same time period could be correlated across the two facilities. In each period, the firm's decisions can be divided into two stages. The first stage is the production stage to decide the production volume for each facility. The capacities and demands are realized after the production stage. The firm's actual production quantity, the minimum of the planned production quantity and the realized capacity, incurs a unit production cost. The firm then enters the transshipment stage where the firms decide the inventory quantities to be transshipped from one facility to another. Finally, the demands are fulfilled from on-hand inventories at their corresponding facilities and unsatisfied demands are lost. The firm receives linear revenue on satisfied demands and pays linear holding and transshipment costs. Then, the problem is to seek the optimal production and transshipment quantities in each period to maximize the total discounted profit over the planning horizon.

^{Hu et al. (2008)} give the dynamic programming formulation for the inventory problem in as follows. The basic idea is as follows. In their setting, there are k periods left in the planning horizon. Define G_{*}^k\left(x_{\mathrm{1}}^k,x_{\mathrm{2}}^k\right) as the profit-to-go function where x_{\mathrm{1}}^k and x_{\mathrm{2}}^k represent the current inventory levels at the two facilities respectively.

Production Stage:

\begin{array}{l}{G}_{*}^k(x_{\mathrm{1}}^k,x_{\mathrm{2}}^k)=\underset{y_{\mathrm{1}}^k\ge x_{\mathrm{1}}^k,y_{\mathrm{2}}^k\ge x_{\mathrm{2}}^k}{\mathrm{m}\mathrm{a}\mathrm{x}}{E}_{T_{\mathrm{1}}^k,T_{\mathrm{2}}^k,D_{\mathrm{1}}^k,D_{\mathrm{2}}^k}\{-c_{\mathrm{1}}(y_{\mathrm{1}}^k\wedge (x_{\mathrm{1}}^k+T_{\mathrm{1}}^k)-x_{\mathrm{1}}^k)\hfill \end{array}

(17)\begin{array}{l}-c_{\mathrm{2}}(y_{\mathrm{2}}^k\wedge (x_{\mathrm{2}}^k+T_{\mathrm{2}}^k)-x_{\mathrm{2}}^k)+r_{\mathrm{1}}{D}_{\mathrm{1}}^k+r_{\mathrm{2}}{D}_{\mathrm{2}}^k\hfill \\ +J_{*}^k(y_{\mathrm{1}}^k\wedge (x_{\mathrm{1}}^k+T_{\mathrm{1}}^k)-D_{\mathrm{1}}^k,y_{\mathrm{2}}^k\wedge (x_{\mathrm{2}}^k+T_{\mathrm{2}}^k)-D_{\mathrm{2}}^k)\}\hfill \end{array}

Transshipment Stage:

J_{*}^k(z_{\mathrm{1}}^k,z_{\mathrm{2}}^k)=\underset{{\widehat{z}}_{\mathrm{1}}^k+{\widehat{z}}_{\mathrm{2}}^k=z_{\mathrm{1}}^k+z_{\mathrm{2}}^k}{\max }

(18)J^k(z_{\mathrm{1}}^k,z_{\mathrm{2}}^k,{\widehat{z}}_{\mathrm{1}}^k,{\widehat{z}}_{\mathrm{2}}^k),

where

J^k(z_1^k,z_2^k,{\widehat{z}}_1^k,{\widehat{z}}_2^k)=-r_1{(-{\widehat{z}}_1^k)}^{+}-r_2{(-{\widehat{z}}_2^k)}^{+}-h_1{\left({\widehat{z}}_1^k\right)}^{+}

(19)$$\begin{gathered} -h_2{(-{\widehat{z}}_2^k)}^{+}-s_1{(z_1^k-{\widehat{z}}_1^k)}^{+}-s_2{(z_2^k-{\widehat{z}}_2^k)}^{+} \\ +\alpha G_{*}^{k-1}({\left({\widehat{z}}_1^k\right)}^{+},{\left({\widehat{z}}_2^k\right)}^{+}), \\ and{G}_{*}^0(x_1^0,x_2^0)\equiv 0. \end{gathered}$$

In the production stage, in period k, one will decide the target inventory levels at the two facilities y_{\mathrm{1}}^k and y_{\mathrm{2}}^k. The variables y_{\mathrm{1}}^k and y_{\mathrm{2}}^k need to be no less than the current inventory levels at the two facilities x_{\mathrm{1}}^k and x_{\mathrm{2}}^k, respectively. The first and second terms on the right hand side of (17) are the production costs with c₁, c₂. T_{\mathrm{1}}^k, T_{\mathrm{2}}^k are the marginal production costs and random capacities of the two facilities respectively. The last two terms are the full revenue collected over the realized demands, where r₁, r₂ and D_{\mathrm{1}}^k, D_{\mathrm{2}}^k are marginal revenue and random demand respectively. The collected yet unrealized revenue due to the lost sales will be deducted in the transshipment stage.

In the transshipment stage, we determine the transshipment quantities or equivalently, the inventory levels after transshipment {\widehat{z}}_{\mathrm{1}}^k and {\widehat{z}}_{\mathrm{2}}^k, whose sum is constrained to be equal to the inventory levels before transshipment (but after demands realization) z_{\mathrm{1}}^kand z_{\mathrm{2}}^k. The first two terms on the right hand side of (19) represent the deducted revenue for the lost sales. The next two terms are the holding costs with h₁ and h₂ being the unit holding costs at the two facilities respectively. The two terms following are transshipment costs with s₁(s₂) being the unit transshipment cost from facility 1 (2) to 2 (1). We assume that the marginal profit is always higher when the demand at a facility is satisfied by inventory at this particular facility than using transshipped inventory from the other facility. Note that, though the constraints in (18) seem to allow the transshipped quantity from a facility to exceed its available inventory, this assumption implies that it is never optimal to do so. Finally, a in (19) is the discount factor.

Under the assumption that demands and capacities are continuous, ^{Hu et al. (2008)} prove the following properties on the profit-to-go function G_{*}^k\left(x_{\mathrm{1}},x_{\mathrm{2}}\right).

{\mathcal{A}}_1: G_{*}^{k-\mathrm{1}}\left(x_{\mathrm{1}},x_{\mathrm{2}}\right) is jointly concave in x₁ and x₂, and

{\displaystyle \frac{{\partial }^{\mathrm{2}}}{\partial x_{\mathrm{1}}^{\mathrm{2}}}}{G}_{*}^{k-\mathrm{1}}(x_{\mathrm{1}},x_{\mathrm{2}})\le {\displaystyle \frac{{\partial }^{\mathrm{2}}}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}}{G}_{*}^{k-\mathrm{1}}(x_{\mathrm{1}},x_{\mathrm{2}}),

{\displaystyle \frac{{\partial }^{\mathrm{2}}}{\partial x_{\mathrm{2}}^{\mathrm{2}}}}{G}_{*}^{k-\mathrm{1}}(x_{\mathrm{1}},x_{\mathrm{2}})\le {\displaystyle \frac{{\partial }^{\mathrm{2}}}{\partial x_{\mathrm{2}}\partial x_{\mathrm{1}}}}{G}_{*}^{k-\mathrm{1}}(x_{\mathrm{1}},x_{\mathrm{2}})\mathrm{;}

{\mathcal{A}}_2: G_{*}^{k-\mathrm{1}}\left(x_{\mathrm{1}},x_{\mathrm{2}}\right) is submodular and

{\displaystyle \frac{{\partial }^{\mathrm{2}}}{\partial x_{\mathrm{1}}\partial x_{\mathrm{2}}}}{G}_{*}^{k-\mathrm{1}}(x_{\mathrm{1}},x_{\mathrm{2}})={\displaystyle \frac{{\partial }^{\mathrm{2}}}{\partial x_{\mathrm{2}}\partial x_{\mathrm{1}}}}{G}_{*}^{k-\mathrm{1}}(x_{\mathrm{1}},x_{\mathrm{2}}).

The above properties are essential for ^{Hu et al. (2008)} to derive the optimal transshipment and production policies. Their proof of these properties involves lengthy and delicate analysis of the second order derivatives of the value functions based on a full characterization of the optimal policy. In the following, we illustrate how the concept and properties of L^{♮}-convexity in Section 2 can be used to significantly simplify their proof. Interestingly, our approach does not rely on the characterization of the optimal policy and it applies to discrete demands as well as capacities without any further efforts.

Denote d_i^k as the realization of demand for facility i in period k, and define q_i^k=z_i^k+d_i^k, w_i^k={\widehat{z}}_i^k+d_i^k, i.e., q_i^kand w_i^k are the before and after transshipment inventory levels at facility i respectively after production is done but before demand is fulfilled. Clearly, q_i^k,w_i^k\ge \mathrm{0}. To employ L^{♮}-convexity, we change variables by letting {\tilde{y}}_{\mathrm{2}}^k=-y_{\mathrm{2}}^k, {\tilde{x}}_{\mathrm{2}}^k=-x_{\mathrm{2}}^k, {\tilde{T}}_{\mathrm{2}}^k=-T_{\mathrm{2}}^k, {\tilde{q}}_{\mathrm{2}}^k=-q_{\mathrm{2}}^k, {\tilde{w}}_{\mathrm{2}}^k=-w_{\mathrm{2}}^k. Our original problem can be equivalently reformulated as

\begin{array}{l}{\tilde{G}}_{*}^k(x_{\mathrm{1}}^k,{\tilde{x}}_{\mathrm{2}}^k)=\underset{y_{\mathrm{1}}^k\ge x_{\mathrm{1}}^k,{\tilde{y}}_{\mathrm{2}}^k\le {\tilde{x}}_{\mathrm{2}}^k}{\max }{E}_{T_{\mathrm{1}}^k,{\tilde{T}}_{\mathrm{2}}^k,D_{\mathrm{1}}^k,D_{\mathrm{2}}^k}\{-c_{\mathrm{1}}(y_{\mathrm{1}}^k\wedge (x_{\mathrm{1}}^k+T_{\mathrm{1}}^k)-x_{\mathrm{1}}^k)\hfill \end{array}

\begin{array}{l}+c_{\mathrm{2}}({\tilde{y}}_{\mathrm{2}}^k\vee ({\tilde{x}}_{\mathrm{2}}^k+{\tilde{T}}_{\mathrm{2}}^k)-{\tilde{x}}_{\mathrm{2}}^k)+{\tilde{J}}_{*}^k(y_{\mathrm{1}}^k\wedge (x_{\mathrm{1}}^k+T_{\mathrm{1}}^k),\hfill \end{array}

(20)\begin{array}{l}{\tilde{y}}_{\mathrm{2}}^k\vee ({\tilde{x}}_{\mathrm{2}}^k+{\tilde{T}}_{\mathrm{2}}^k)|D_{\mathrm{1}}^k,D_{\mathrm{2}}^k)\},\hfill \end{array}

where {\tilde{G}}_{*}^k\left(x_{\mathrm{1}}^k,{\tilde{x}}_{\mathrm{2}}^k\right)=G_{*}^k\left(x_{\mathrm{1}}^k-{\tilde{x}}_{\mathrm{2}}^k\right)and by introducing a new variable v

(21)\begin{array}{l}{\tilde{J}}_{*}^k(q_{\mathrm{1}}^k,{\tilde{q}}_{\mathrm{2}}^k|d_{\mathrm{1}}^k,d_{\mathrm{2}}^k)=\underset{w_{\mathrm{1}}^k,{\tilde{w}}_{\mathrm{2}}^k,v}{\max }\tilde{J}(w_{\mathrm{1}}^k,{\tilde{w}}_{\mathrm{2}}^k,v|d_{\mathrm{1}}^k,d_{\mathrm{2}}^k)\hfill \\ s.t.w_{\mathrm{1}}^k+v=q_{\mathrm{1}}^k\hfill \\ {\tilde{w}}_{\mathrm{2}}^k+v={\tilde{q}}_{\mathrm{2}}^k\hfill \\ w_{\mathrm{1}}^k\ge \mathrm{0},{\tilde{w}}_{\mathrm{2}}^k\le \mathrm{0},\hfill \end{array}

where

\begin{array}{l}\tilde{J}(w_{\mathrm{1}}^k,{\tilde{w}}_{\mathrm{2}}^k,v|d_{\mathrm{1}}^k,d_{\mathrm{2}}^k)\hfill \end{array}

\begin{array}{l}=r_1(w_{\mathrm{1}}^k\wedge d_{\mathrm{1}}^k)+r_2\left(\right(-{\tilde{w}}_2^k)\wedge d_2^k)-h_1{(w_{\mathrm{1}}^k\wedge d_{\mathrm{1}}^k)}^{+}\hfill \end{array}

\begin{array}{l}-h_2{(-{\tilde{w}}_2^k-d_2^k)}^{+}-s_1{v}^{+}-s_2{(-v)}^{+}\hfill \end{array}

(22)+\alpha {\tilde{G}}_{*}^{k-1}({(w_1^k-d_1^k)}^{+},-{(-{\tilde{w}}_2^k-d_2^k)}^{+}).

Note that in (21), we impose w_{\mathrm{1}}^k\ge \mathrm{0} and {\tilde{w}}_{\mathrm{2}}^k\le \mathrm{0}, which guarantee that the transshipped quantities won't exceed the inventory levels at the facilities. These constraints can be safely removed as done in ^{Chen et al. (2015)} under the assumption on the marginal profit made earlier.

Now we are ready to state and prove our main result, which offers a new approach that proves the key properties \mathcal{A}₁ and \mathcal{A}₂ with continuous demands and capacities.

THEOREM 12. Suppose that {\tilde{G}}_{*}^{k-\mathrm{1}}\left(·,·\right) is L^{♮}-concave, then {\tilde{G}}_{*}^k\left(·,·\right)is alsoL^{♮}-concave.

Proof. For notational brevity, we omit the superscript k in the proof when there is no ambiguity. Define u₁, u₂ as the inventory level after the sales assuming that the firm can hold inventory with some demand unsatisfied. Then the realized sales are given by w₁-u₁ and w₂-u₂ at the two facilities respectively. By letting {\tilde{u}}_{\mathrm{2}}=-u_{\mathrm{2}}, we claim that \tilde{J}\left(w_{\mathrm{1}},{\tilde{w}}_{\mathrm{2}},v|d_{\mathrm{1}},d_{\mathrm{2}}\right) equals the optimal objective value of the following problem:

\underset{u_{\mathrm{1}},{\tilde{u}}_{\mathrm{2}}}{\max }{r}_{\mathrm{1}}(w_{\mathrm{1}}-u_{\mathrm{1}})-r_{\mathrm{2}}({\tilde{w}}_{\mathrm{2}}-{\tilde{u}}_{\mathrm{2}})-h_{\mathrm{1}}{u}_{\mathrm{1}}+h_{\mathrm{2}}{\tilde{u}}_{\mathrm{2}}

-s_{\mathrm{1}}{v}^{+}-s_{\mathrm{2}}{(-v)}^{+}+\alpha {\tilde{G}}_{*}^{k-\mathrm{1}}(u_{\mathrm{1}},{\tilde{u}}_{\mathrm{2}})

s.t.\mathrm{0}\le u_{\mathrm{1}},u_{\mathrm{1}}-w_{\mathrm{1}}\le \mathrm{0},

{\tilde{w}}_{\mathrm{2}}-{\tilde{u}}_{\mathrm{2}}\le \mathrm{0},{\tilde{u}}_{\mathrm{2}}\le \mathrm{0},

(23)w_{\mathrm{1}}-u_{\mathrm{1}}\le d_{\mathrm{1}},u_{\mathrm{2}}-{\tilde{w}}_{\mathrm{2}}\le d_{\mathrm{2}}.

For the stationary system, the firm should never hold inventory and reject any demand at the same time since meeting the current demand always makes more profit than holding the inventory to fulfill future demands. Hence, u_{\mathrm{1}}={\left(w_{\mathrm{1}}-d_{\mathrm{1}}\right)}^{+}, u_{\mathrm{2}}=-{\left(-{\tilde{w}}_{\mathrm{2}}-d_{\mathrm{2}}\right)}^{+} is the optimal solution and our claim is correct.

We further claim that the objective function of the problem (23) is L^{♮}-concave in \left(w_{\mathrm{1}},{\tilde{w}}_{\mathrm{2}},v,u_{\mathrm{1}},{\tilde{u}}_{\mathrm{2}}\right). In fact, by the hypothesis in the induction part, {\tilde{G}}_{*}^{k-\mathrm{1}}\left(u_{\mathrm{1}},{\tilde{u}}_{\mathrm{2}}\right) is L^{♮}-concave. The L^{♮}-concavity of the rest of terms in the objective function is straightforward to verify. The L^{♮}-convexity of the constraint set follows Proposition 4 part (e). Then \tilde{J}\left(w_{\mathrm{1}},{\tilde{w}}_{\mathrm{2}},v|d_{\mathrm{1}},d_{\mathrm{2}}\right) is L^{♮}-concave which follows from Theorem 7.

Note that the objective function in (21) is separable in variables \left(w_{\mathrm{1}},{\tilde{w}}_{\mathrm{2}}\right) and \left(v,v\right). Thus, the L^{♮}-concavity of {\tilde{J}}_{*}^k\left(q_{\mathrm{1}},{\tilde{q}}_{\mathrm{2}}|d_{\mathrm{1}},d_{\mathrm{2}}\right) follows from Theorem 8.

By defining

\tilde{G}\left(y_{\mathrm{1}},y_{\mathrm{2}}\right)=E_{D_{\mathrm{1}},D_{\mathrm{2}}}\{-c_{\mathrm{1}}{y}_{\mathrm{1}}+c_{\mathrm{2}}{y}_{\mathrm{2}}+{\tilde{J}}_{*}^k(y_{\mathrm{1}},

y_{\mathrm{2}}|D_{\mathrm{1}},D_{\mathrm{2}})\}

, (20) can be expressed as

{\tilde{G}}_{*}(x_{\mathrm{1}},{\tilde{x}}_{\mathrm{2}})=\underset{y_{\mathrm{1}}\ge x_{\mathrm{1}},{\tilde{y}}_{\mathrm{2}}\le {\tilde{x}}_{\mathrm{2}}}{\max }{E}_{T_{\mathrm{1}},{\tilde{T}}_{\mathrm{2}}}\{\tilde{G}(y_{\mathrm{1}}\wedge (x_{\mathrm{1}}+T_{\mathrm{1}}),

{\tilde{y}}_{\mathrm{2}}\vee ({\tilde{x}}_{\mathrm{2}}+{\tilde{T}}_{\mathrm{2}}))\}+c_{\mathrm{1}}{x}_{\mathrm{1}}-c_{\mathrm{2}}{\tilde{x}}_{\mathrm{2}}

Clearly \tilde{G}\left(y_{\mathrm{1}},y_{\mathrm{2}}\right) is L^{♮}-concave in \left(y_{\mathrm{1}},y_{\mathrm{2}}\right). Moreover,

y_{\mathrm{1}}\wedge \left(x_{\mathrm{1}}+T_{\mathrm{1}}\right)=\left(y_{\mathrm{1}}-x_{\mathrm{1}}\right)\wedge T_{\mathrm{1}}+x_{\mathrm{1}}

and

{\tilde{y}}_{\mathrm{2}}\vee \left({\tilde{x}}_{\mathrm{2}}+{\tilde{T}}_{\mathrm{2}}\right)=

\left({\tilde{y}}_{\mathrm{2}}-{\tilde{x}}_{\mathrm{2}}\right)\vee {\tilde{T}}_{\mathrm{2}}+{\tilde{x}}_{\mathrm{2}}

. It is easy to see that by transforming the variables {\widehat{y}}_{\mathrm{1}}=y_{\mathrm{1}}-x_{\mathrm{1}} and {\widehat{y}}_{\mathrm{2}}={\tilde{y}}_{\mathrm{2}}-{\tilde{x}}_{\mathrm{2}}, the above problem can be expressed in the form of (6).Then Theorem 9 implies that the profit-to-go function {\tilde{G}}_{*}\left(x_{\mathrm{1}},{\tilde{x}}_{\mathrm{2}}\right) is L^{♮}-concave. Q.E.D.

By Proposition 4 part (b), it is easy to verify that Theorem 12 implies the properties \mathcal{A}₁ and \mathcal{A}₂ for continuous demands and capacities, which can then be used to derive the structure of the optimal policies. In fact, L^{♮}-concavity of the profit-to-go functions is sufficient for us to establish the optimal policy structure. Since L^{♮}-convexity is defined for both continuous space and discrete space, the structure of the optimal policies established in ^{Hu et al. (2008)} for continuous demands and capacities can be extended to settings with discrete demands and capacities with some minor modifications of their analysis.

Conclusions

In this paper, we provide a brief survey of the properties of L^{♮}-convexity and closely related results in lattice programming. These properties are then used to analyze a perishable inventory model and a joint inventory and transshipment control model with random capacities. When applying L^{♮}-convexity to derive monotone comparative statics of optimal policies, one has to choose the representations of states appropriately. Once this is done, the analysis is more or less standard and the structures of optimal policies have similar flavors. Our choice of the perishable inventory model and the joint inventory and transshipment control model highlights how operations applications can motivate the development of some new properties of L^{♮}-convexity.

L^{♮}-convexity has important computational implications. Indeed, when minimizing a L^{♮}-convex function, local optimality leads to global optimality and the steepest descent algorithm can be applied to find an optimal solution efficiently with proven computational complexity bounds polynomial in the number of variables (see ^{Murota 2003} for L^{♮}-convexity function minimization in integer spaces). Based on discrete L^{♮}-convexity, ^{Lu and Song (2005)} show that in an order-based multiproduct assemble-to-order system, the optimal base-stock levels can be obtained in a greedy fashion.

For stochastic dynamic programs with cost-to-go functions being discrete L^{♮}-convexity, ^{Chen W et al. (2014)} propose a pseudo-polynomial time approximation scheme and demonstrate its effectiveness on a stochastic inventory model with lost sales and a positive lead time. ^{Sun et al. (2014)} develop quadratic approximation of cost-to-go functions for the lost sales and perishable inventory control problems. Finally, we refer to ^{Begen and Queyranne (2011)} and ^{Ge et al. (2014)} for applications of L^{♮}-convexity to appointment scheduling for a given sequence of jobs on a single processor with random durations.

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)