Inventory models with minimal service level constraints

This paper investigates inventory models in which the stockout cost is replaced by a minimal service level constraint (SLC) that requires a certain level of service to be met in every period. The minimal service level approach has the virtue of simplifying the computation of an optimal ordering policy, because the optimal reorder level is solely determined by the minimal SLC and demand distributions. It is found that above a certain “critical” service level, the optimal (s,S) policy “collapses” to a simple base-stock or order-up-to level policy, which is independent on the cost parameters. This shows the minimal SLC models to be qualitatively different from their shortage cost counterparts. We also demonstrate that the “imputed shortage cost” transforming a minimal SLC model to a shortage cost model does not generally exist. The minimal SLC approach is extended to models with negligible set-up costs. The optimality of myopic base-stock policies is established under mild conditions.     

Computation of viability kernels: a case study of by-catch fisheries

Traditional means of studying environmental economics and management problems consist of optimal control and dynamic game models that are solved for optimal or equilibrium strategies. Notwithstanding the possibility of multiple equilibria, the models’ users—managers or planners—will usually be provided with a single optimal or equilibrium strategy no matter how reliable, or unreliable, the underlying models and their parameters are. In this paper we follow an alternative approach to policy making that is based on viability theory. It establishes “satisficing” (in the sense of Simon), or viable, policies that keep the dynamic system in a constraint set and are, generically, multiple and amenable to each manager’s own prioritisation. Moreover, they can depend on fewer parameters than the optimal or equilibrium strategies and hence be more robust. For the determination of these (viable) policies, computation of “viability kernels” is crucial. We introduce a MATLAB application, under the name of VIKAASA, which allows us to compute approximations to viability kernels. We discuss two algorithms implemented in VIKAASA. One approximates the viability kernel by the locus of state space positions for which solutions to an auxiliary cost-minimising optimal control problem can be found. The lack of any solution implies the infinite value function and indicates an evolution which leaves the constraint set in finite time, therefore defining the point from which the evolution originates as belonging to the kernel’s complement. The other algorithm accepts a point as viable if the system’s dynamics can be stabilised from this point. We comment on the pros and cons of each algorithm. We apply viability theory and the VIKAASA software to a problem of by-catch fisheries exploited by one or two fleets and provide rules concerning the proportion of fish biomass and the fishing effort that a sustainable fishery’s exploitation should follow.     

An Optimal Chance Constraint Multivariate Stratified Sampling Design Using Auxiliary Information

When we are dealing with multivariate problem then we need an allocation which is optimal for all the characteristics in some sense because the individual optimum allocations usually differ widely unless the characteristics are highly correlated. So an allocation called “Compromise allocation” is to be worked out suggested by Cochran. When auxiliary information is also available, it is customary to use it to increase the precision of the estimates. Moreover, for practical implementation of an allocation, we need integer values of the sample sizes. In the present paper the problem is to determine the integer optimum compromise allocation when the population means of various characteristics are of interest and auxiliary information is available for the separate and combined ratio and regression estimates. This paper considers the optimum compromise allocation in multivariate stratified sampling with non-linear objective function and probabilistic non-linear cost constraint. The probabilistic non-linear cost constraint is converted into equivalent deterministic one by using Chance Constrained programming. The formulated multi-objective nonlinear programming problem is solved by Fuzzy Goal programming approach and Chebyshev approximation. Numerical illustration is also given to show the practical utility of the approaches.     

Strong duality and sensitivity analysis in semi-infinite linear programming

Finite-dimensional linear programs satisfy strong duality (SD) and have the “dual pricing” (DP) property. The DP property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correctly “prices” the perturbation by computing the exact change in the optimal objective function value. These properties may fail in semi-infinite linear programming where the constraint vector space is infinite dimensional. Unlike the finite-dimensional case, in semi-infinite linear programs the constraint vector space is a modeling choice. We show that, for a sufficiently restricted vector space, both SD and DP always hold, at the cost of restricting the perturbations to that space. The main goal of the paper is to extend this restricted space to the largest possible constraint space where SD and DP hold. Once SD or DP fail for a given constraint space, then these conditions fail for all larger constraint spaces. We give sufficient conditions for when SD and DP hold in an extended constraint space. Our results require the use of linear functionals that are singular or purely finitely additive and thus not representable as finite support vectors. We use the extension of the Fourier–Motzkin elimination procedure to semi-infinite linear systems to understand these linear functionals.     

Sensitivity analysis and optimal ultimately stationary deterministic policies in some constrained discounted cost models

We consider a discrete time Markov Decision Process (MDP) under the discounted payoff criterion in the presence of additional discounted cost constraints. We study the sensitivity of optimal Stationary Randomized (SR) policies in this setting with respect to the upper bound on the discounted cost constraint functionals. We show that such sensitivity analysis leads to an improved version of the Feinberg–Shwartz algorithm (Math Oper Res 21(4):922–945, 1996) for finding optimal policies that are ultimately stationary and deterministic.     

Estimating demand by using sales information: inaccuracies encountered

Demand data is integral to a company’s overall information requirement. This is particularly true for manufacturers and retailers with regard to capacity, production, and inventory planning. Notwithstanding the implicit inaccuracies encountered, companies are predisposed to employ sales data as a primary source of information for estimating future demand.In this paper, by adopting a two-product setting, we measure inventory cost inaccuracies that arise from using sales data in estimating demand. By analyzing these costs, we also explore the conditions under which the resulting inaccuracies are either “lessened” or become “acute.” In this context, the determining rule of an induced substitution structure between the two products during stockout occasions is explicitly analyzed.We use a newsboy framework, in a two product environment, wherein one product may be taken as a direct substitute for the other. We provide necessary and sufficient optimality conditions and an extensive computational study to illustrate and support our findings and to provide additional insights on the conditions characterizing optimal stocking policies.     

A note on estimates for the growth order of sequences of multiple rectangular Fourier sums

We develop an optimal growth model of an open economy that uses both an old (“dirty” or “polluting”) technology and a new (“clean”) technology simultaneously. A planner of the economy expects the occurrence of a random shock that increases sharply abatement costs in the dirty sector. Assuming that the probability of an exogenous environmental shock is distributed according to the exponential law, we use Pontryagin’s maximum principle to find the optimal investment and consumption policies for the economy.     

Admission control strategies for tandem Markovian loss systems

Motivated by communication networks, we study an admission control problem for a Markovian loss system comprised of two finite capacity service stations in tandem. Customers arrive to station 1 according to a Poisson process, and a gatekeeper, who has complete knowledge of the number of customers at both stations, decides whether to accept or reject each arriving customer. If a customer is rejected, a rejection cost is incurred. If an admitted customer finds that station 2 is full at the time of his service completion at station 1, he leaves the system and a loss cost is incurred. The goal is to find easy-to-implement policies that minimize long-run average cost per unit time. We formulate two intuitive, extremal policies and provide analytical results on their performances. We also present necessary and/or sufficient conditions under which each of these policies is optimal. Next, we show that for some states of the system it is always optimal to admit new arrivals. We also fully characterize the optimal policy when the capacity of each station is two and discuss some characteristics of optimal policies in general. Finally, we design heuristic admission control policies using these insights. Numerical experiments indicate that these heuristic policies yield near-optimal long-run average cost performance.     

A Bridge Between Bilevel Programs and Nash Games

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our “uneven” horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our “uneven” horizontal model, in some sense, lies between the vertical bilevel model and a “pure” horizontal game.     

How big is too big? Trading off the economies of scale of larger telecommunications network elements against the risk of larger outages

This paper builds a probabilistic model to analyze the risk–reward tradeoffs that larger telecommunications network elements present. Larger machines offer rewards in the form of cost savings due to economies of scale. But large machines are riskier because they affect more customers when they fail. Our model translates the risk of outages into dollar costs, which are random variables. This step enables us to combine the deployment cost and outage cost into a total cost. Once we express the decision makers’ preferences via a utility function, we can find the machine size that minimizes the total cost’s expected utility, thereby achieving an optimal tradeoff between reward and risk. The expected utility answers the question “how big is too big?”.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

Directed graphs,Hamiltonicity and doubly stochastic matrices

We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)‐entry of the fundamental matrices of the Markov chains induced by the same policies. In particular, we focus on the subset of these policies that induce doubly stochastic probability transition matrices, which we refer to as the “doubly stochastic policies.” We show that when the perturbation parameter ? is sufficiently small the minimum of this functional over the space of the doubly stochastic policies is attained very close to a Hamiltonian cycle, provided that the graph is Hamiltonian. We also derive precise analytical expressions for the elements of the fundamental matrix that lend themselves to probabilistic interpretation as well as asymptotic expressions for the first diagonal element, for a variety of deterministic policies that are of special interest, including those that correspond to Hamiltonian cycles. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

A queuing approach for inventory planning with batch ordering in multi-echelon supply chains

This paper presents stylized models for conducting performance analysis of the manufacturing supply chain network (SCN) in a stochastic setting for batch ordering. We use queueing models to capture the behavior of SCN. The analysis is clubbed with an inventory optimization model, which can be used for designing inventory policies . In the first case, we model one manufacturer with one warehouse, which supplies to various retailers. We determine the optimal inventory level at the warehouse that minimizes total expected cost of carrying inventory, back order cost associated with serving orders in the backlog queue, and ordering cost. In the second model we impose service level constraint in terms of fill rate (probability an order is filled from stock at warehouse), assuming that customers do not balk from the system. We present several numerical examples to illustrate the model and to illustrate its various features. In the third case, we extend the model to a three-echelon inventory model which explicitly considers the logistics process.     

Minimizing the ruin probability allowing investments in two assets: a two-dimensional problem

We consider in this paper that the reserve of an insurance company follows the classical model, in which the aggregate claim amount follows a compound Poisson process. Our goal is to minimize the ruin probability of the company assuming that the management can invest dynamically part of the reserve in an asset that has a positive fixed return. However, due to transaction costs, the sale price of the asset at the time when the company needs cash to cover claims is lower than the original price. This is a singular two-dimensional stochastic control problem which cannot be reduced to a one-dimensional problem. The associated Hamilton–Jacobi–Bellman (HJB) equation is a variational inequality involving a first order integro-differential operator and a gradient constraint. We characterize the optimal value function as the unique viscosity solution of the associated HJB equation. For exponential claim distributions, we show that the optimal value function is induced by a two-region stationary strategy (“action” and “inaction” regions) and we find an implicit formula for the free boundary between these two regions. We also study the optimal strategy for small and large initial capital and show some numerical examples.     

Décomposition de domaine pour le contrôle de systèmes gouvernés par des équations d'évolution

We present a non overlapping iterative domain decomposition method with “coupled” Robin transmission conditions. We prove its convergence on an optimal control problem for the wave equation. The linear part of the “feed-back” law associated to the local optimal control problems set on subdomains is independent of the iterative process. The method can be applied, at least formally, to the optimal control of systems governed by evolution equations.     

Adaptive control of constrained Markov chains: Criteria and policies

We consider the constrained optimization of a finite-state, finite action Markov chain. In the adaptive problem, the transition probabilities are assumed to be unknown, and no prior distribution on their values is given. We consider constrained optimization problems in terms of several cost criteria which are asymptotic in nature. For these criteria we show that it is possible to achieve the same optimal cost as in the non-adaptive case.We first formulate a constrained optimization problem under each of the cost criteria and establish the existence of optimal stationary policies.Since the adaptive problem is inherently non-stationary, we suggest a class ofAsymptotically Stationary (AS) policies, and show that, under each of the cost criteria, the costs of an AS policy depend only on its limiting behavior. This property implies that there exist optimal AS policies. A method for generating adaptive policies is then suggested, which leads to strongly consistent estimators for the unknown transition probabilities. A way to guarantee that these policies are also optimal is to couple them with the adaptive algorithm of [3]. This leads to optimal policies for each of the adaptive constrained optimization problems under discussion.This work was supported in part through United States-Israel Binational Science Foundation Grant BSF 85-00306.     

Constrained Markov decision processes with total cost criteria: Occupation measures and primal LP

This paper is the third in a series on constrained Markov decision processes (CMDPs) with a countable state space and unbounded cost. In the previous papers we studied the expected average and the discounted cost. We analyze in this paper the total cost criterion. We study the properties of the set of occupation measures achieved by different classes of policies; we then focus on stationary policies and on mixed deterministic policies and present conditions under which optimal policies exist within these classes. We conclude by introducing an equivalent infinite Linear Program.     

A Deterministic Approach To Stochastic Optimal Control With Application To Anticipative Control

Using the decomposition of solution of SDE, we consider the stochastic optimal control problem with anticipative controls as a family of deterministic control problems parametrized by the paths of the driving Wiener process and of a newly introduced Lagrange multiplier stochastic process (nonanticipativity equality constraint). It is shown that the value function of these problems is the unique global solution of a robust equation (random partial differential equation) associated to a linear backward Hamilton-Jacobi-Bellman stochastic partial differential equation (HJB SPDE). This appears as limiting SPDE for a sequence of random HJB PDE's when linear interpolation approximation of the Wiener process is used. Our approach extends the Wong-Zakai type results [20] from SDE to the stochastic dynamic programming equation by showing how this arises as average of the limit of a sequence of deterministic dynamic programming equations. The stochastic characteristics method of Kunita [13] is used to represent the value function. By choosing the Lagrange multiplier equal to its nonanticipative constraint value the usual stochastic (nonanticipative) optimal control and optimal cost are recovered. This suggests a method for solving the anticipative control problems by almost sure deterministic optimal control. We obtain a PDE for the “cost of perfect information” the difference between the cost function of the nonanticipative control problem and the cost of the anticipative problem which satisfies a nonlinear backward HJB SPDE. Poisson bracket conditions are found ensuring this has a global solution. The cost of perfect information is shown to be zero when a Lagrangian submanifold is invariant for the stochastic characteristics. The LQG problem and a nonlinear anticipative control problem are considered as examples in this framework     

Stochastic Multiproduct Inventory Models with Limited Storage

This paper studies multiproduct inventory models with stochastic demands and a warehousing constraint. Finite horizon as well as stationary and nonstationary discounted-cost infinite-horizon problems are addressed. Existence of optimal feedback policies is established under fairly general assumptions. Furthermore, the structure of the optimal policies is analyzed when the ordering cost is linear and the inventory/backlog cost is convex. The optimal policies generalize the base-stock policies in the single-product case. Finally, in the stationary infinite-horizon case, a myopic policy is proved to be optimal if the product demands are independent and the cost functions are separable.     

Policy iteration for robust nonstationary Markov decision processes

Policy iteration is a well-studied algorithm for solving stationary Markov decision processes (MDPs). It has also been extended to robust stationary MDPs. For robust nonstationary MDPs, however, an “as is” execution of this algorithm is not possible because it would call for an infinite amount of computation in each iteration. We therefore present a policy iteration algorithm for robust nonstationary MDPs, which performs finitely implementable approximate variants of policy evaluation and policy improvement in each iteration. We prove that the sequence of cost-to-go functions produced by this algorithm monotonically converges pointwise to the optimal cost-to-go function; the policies generated converge subsequentially to an optimal policy.