Search

We develop a qualitative analysis theory for the convex-cost dynamic multicommodity production planning problem, which can be used, without performing any computational work, to provide invaluable insight to managers when faced with the task of deciding how to respond to changes in problem environment. We first formulate the problem as a multicommodity flow problem with parameters associated with each arc–commodity pair. We then reduce the problem to an equivalent single-commodity flow problem and develop a complete characterization of conformality among production, sales, and inventory activities in various instances of the problem. By combining the conformality characterizations with the monotonicity theory of Granot and Veinott [Granot F, Veinott AF Jr (1985) Substitutes, complements and ripples in network flow. Math. Oper. Res. 10:471–497] for single-commodity problems, we study the effects of changes in problem environment on optimal production, sales, and inventory schedules in the multicommodity problem. Numerous applications are presented and analyzed.

Finite-state-and-action Markov branching decision chains are studied with bounded endogenous expected population sizes and interest-rate-dependent one-period rewards that are analytic in the interest rate at zero. The existence of a stationary strong-maximum-present-value policy is established. Miller and Veinott's [1969] strong policy-improvement method is generalized to find in finite time a stationary n-present-value optimal policy and, when the one-period rewards are rational in the interest rate, a stationary strong-maximum-present-value policy. This extends previous studies of Blackwell [1962], Miller and Veinott [1969], Veinott [1974], and Rothblum [1974, 1975], in which the one-period rewards are independent of the interest rate, and Denardo [1971] in which semi-Markov decision chains with small interest rates are studied. The problem of finding a stationary n-present-value optimal policy is also formulated as a staircase linear program in which the objective function and right-hand sides, but not the constraint matrix, depend on the interest rate, and solutions for all small enough positive interest rates are sought. The optimal solutions of the primal and dual are polynomials in the reciprocal of the interest rate. A constructive rule is given for finding a stationary n-present-value optimal policy from an optimal solution of the asymptotic linear program. This generalizes the linear programming approaches for finding maximum-reward-rate and maximum-present-value policies for Markov decision chains studied by Manne [1960], d'Epenoux [1960, 1963], Balinski [1961], Derman [1962], Denardo and Fox [1968], Denardo [1970], Derman and Veinott [1972], Veinott [1973], and Hordijk and Kallenberg [1979, 1984].

Gerald J. Lieberman was born on December 31, 1925, in Brooklyn, New York, after a hectic New Year's Eve trip to the hospital. His father, Joseph, spelled his last name Liberman, but his mother, Ida, preferred Lieberman, the spelling that she and some of Joseph's siblings used. Joseph and Ida had come to this country from Lithuania. Joseph worked for the Metropolitan Life Insurance Company, and they lived in an “historic” section of Flatbush. The much wanted baby boy was the center of the family, which included two doting older sisters, Shirley and Rosalind. He grew fast — one of the tallest boys in nearby Public School 197 — and achieved his adult height at about the age of 13. As a boy, he was described as towheaded and gawky. Jerry did not realize that he had a middle initial until he was 15 and needed a birth certificate to get a work permit. Jerry asked his parents if they had given him a middle initial, but they did not remember. In any case, since the J does not stand for anything, Jerry likes to quip that his middle name is Jinitial.

A cumulative-capacitated transportation problem is studied. The supply nodes and demand nodes are each chains. Shipments from a supply node to a demand node are possible only if the pair lies in a sublattice, or equivalently, in a staircase disjoint union of rectangles, of the product of the two chains. There are (lattice) superadditive upper bounds on the cumulative flows in all leading subrectangles of each rectangle. It is shown that there is a greatest cumulative flow formed by the natural generalization of the South-West Corner Rule that respects cumulative-flow capacities; it has maximum reward when the rewards are (lattice) superadditive; it is integer if the supplies, demands and capacities are integer; and it can be calculated myopically in linear time. The result is specialized to earlier work of Hoeffding (1940), Frechet (1951), Lorentz (1953), Hoffman (1963) and Barnes and Hoffman (1985). Applications are given to extreme constrained bivariate distributions, optimal distribution with limited one-way product substitution and, generalizing results of Derman and Klein (1958), optimal sales with age-dependent rewards and capacities.

Let M and N be the set of minimizers of a function f over respective subsets K and L of a lattice, with K being lower than L. This paper characterizes the class of functions f for which M is lower (resp., weakly lower, meet lower, join lower, chain lower) than N for all K lower than L. The resulting five classes of functions, called subextremal variants, have alternate characterizations by variants of the downcrossing-differences property, i.e., their first differences change sign at most once from plus to minus along complementary chains.

It is shown that each element of the lattice of meet (resp., join) sublattices of a product S of n chains has a representation as the intersection of n subsets of S , the i th of which is decreasing (resp., increasing) for each fixed value of the i th coordinate for each i . This result is applied to show that an arbitrary element of the lattice of sublattices of S has a representation as the intersection of n 2 subsets, the ij th of which is decreasing for each fixed value of the i th and increasing for each fixed value of the j th coordinate for each i , j . Irreducible representations are given in each case, providing an alternative proof of an instance of Hashimoto's (1952) representation of sublattices of a distributive lattice. Moreover, irreducible representations are given for the polyhedral members of the lattice of closed convex subsets of n -dimensional Euclidean space that are at once subsemilattices or sublattices. It is alsoshown that the polyhedral subsemilattices and sublattices can be represented as duals respectively of pre-Leontief substitution systems and generalized network-flow problems. Finally, the problems of checking whether a polyhedral set is a subsemilattice or sublattice are reduced to that of solving a system of linear inequalities, thereby showing that these recognition problems can be solved in polynomial time.

This paper is dedicated to our friend and mentor, Cyrus Derman, on the occasion of his 60th birthday. The multi-armed bandit problem arises in sequentially allocating effort to one of N projects and sequentially assigning patients to one of N treatments in clinical trials. Gittins and Jones (Gittins, J. C., Jones, D. M. 1974. A dynamic allocation index for the sequential design of experiments. J. Gani, K. Sarkadi, L. Vince, eds. Progress in Statistics. European Meeting of Statisticians, 1972, 1, North Holland, Amsterdam, 241–266.) have shown that one optimal policy for the N-project problem, an N-dimensional discounted Markov decision chain, is determined by the following largest-index rule. There is an index for each state of each given project that depends only on the data of that project. In each period one allocates effort to a project with largest current index. The purpose of this paper is to give a short proof of this result and a new characterization of the index of a project in state i, viz., as the maximum expected present value in state i for the restart-in-i problem in which, in each state and period, one either continues allocating effort to the project or immediately restarts the project in state i. Moreover, it is shown that an approximate largest-index rule yields an approximately optimal policy. These results lead to more efficient methods of computing the indices on-line and/or for sparse transition matrices in large state spaces than have been suggested heretofore. By using a suitable implementation of successive approximations, a policy whose expected present value is within 100ϵ% of the maximum possible range of values of the indices can be found on-line with at most (N + T − 1)TM operations where M is the number of operations required to calculate one approximation, T is the least integer majorizing the ratio ln ϵ/ln a and 0 < a < 1 is the discount factor.

Many problems from inventory, production and capacity planning, and from network design, exhibit scale economies and can be formulated in terms of finding minimum-additive-concave-cost nonnegative network flows. We reduce the problem to an equivalent one in which the arc flow costs are nonnegative and give a dynamic-programming method, called the send-and-split method, to solve it. The main work of the method entails repeatedly solving set-splitting and minimum-cost-chain problems. In uncapacitated networks with n nodes, a arcs, and d + 1 demand nodes, i.e., nodes with nonzero exogenous demand, the algorithm requires up to n2−13d + s2d operations (additions and comparisons) where s = n log2n + 3a is the number of operations required to solve a minimum-cost-chain problem with nonnegative arc costs on the augmented graph formed by appending a node and an arc thereto from each node in the graph. If also the network is k-planar, i.e., the graph is planar with all demand nodes lying on the boundary of k faces, the method requires at most n2−kd3k + sd2k operations. The algorithm can be applied to capacitated networks because they can be reduced to equivalent uncapacitated ones. These results unify, significantly generalize (e.g., to cyclic problems), and sometimes improve upon (e.g., for tandem facilities) known polynomial-time dynamic-programming algorithms for Wagner and Whitin's (Wagner, H. M., Whitin, T. M. 1958. Dynamic version of the economic lot size model. Management Sci. 5 89–96.) dynamic economic-order-quantity problem, Zangwill's (Zangwill, W. I. 1969. A backlogging model and a multi-echelon model of a dynamic economic lot size production system—A network approach. Management Sci. 15 506–527.) generalization to tandem facilities, and Veinott's (Veinott, Jr., A. F. 1969. Minimum concave-cost solution of Leontief substitution models of multi-facility inventory systems. Oper. Res. 17 262–291.) increasing-capacity warehousing problem. The networks for the finite-period versions of these problems are each 1-planar. The method improves upon Zangwill's (Zangwill, W. I. 1968. Minimum concave cost flows in certain networks. Management Sci. 14 429–450.) related O(and) running-time dynamic-programming method for finding minimum-additive-concave-cost non-negative flows in circuitless single-source networks. We also implement the method to solve in polynomial time the (d + 1)-demand-node and k-planar versions of the minimum-cost forest and Steiner problems in graphs. The running time for the (d + 1)-demand-node Steiner problem in graphs is comparable to that of Dreyfus and Wagner's (Dreyfus, S. E., Wagner, R. A. 1971. The Steiner problem in graphs. Networks 1 195–207.) method.

A multiperiod single product nonstationary inventory problem is studied in which the system is reviewed at the beginning of each of a sequence of periods of equal length. The model has the following features. There are several classes of demand for the product in each period. The demands in different periods are independent but not necessarily identically distributed. The cost structure is nonstationary with the ordering cost being proportional to the amount ordered. Conditions are given that ensure that the base stock ordering policy is optimal and that the base stock levels in each period are easy to calculate. The results are based on the work given in the literature and on properties of stochastically ordered distributions that are developed in the paper. The case of a linear holding cost and a linear shortage cost is studied in detail.

We consider a single product dynamic inventory problem in which the demands in each period are independent and identically distributed random variables. There is a constant lead time, a discount factor 0 ≦ α ≦ 1, a unit ordering cost c and an expected holding and penalty cost function L(·) for which −[c(l − α)y + L(y)] is unimodal, and total backlogging of unfilled demand. In addition each order for stock must be in some nonnegative integral multiple of Q, a fixed positive constant. It is shown that the (k, Q) policy is optimal for the finite and infinite period models. With the (k, Q) policy if the initial inventory on hand and on order in a period is less than k, an order is placed for the smallest multiple of Q that will bring the inventory on hand and on order to at least k; otherwise, no order is placed. The optimal value of k is easy to compute and is the same for the finite and infinite period models. The results are generalized to the case where the demand distributions and cost functions vary over time. The (k, Q) policy is not optimal in general for the case where there is also a fixed charge for placing an order.

This paper surveys the current status of mathematical inventory theory. The review is limited to studies which seek optimal policies for dynamic inventory models. Models with certain and uncertain demands are discussed. Particular attention is focused on multi-item and/or multi-echelon inventory systems.

It is shown that for any feasible network flow model, there is a flow which simultaneously minimizes every d-Schur convex function of the flows emanating from a single distinguished node called the source. The vector of flows emanating from the source in the minimizing flow is unique and is the “least d-majorized” flow. This flow can be found by solving the problem for the special case where the d-Sehur convex function is separable and quadratic. Once this flow is found, the solution of the dual problem is reduced to evaluating the conjugate of a function appearing in the dual objective function at the above flow. This computation is extremely simple when the function is separable. These results are extended to situations in which the variables must be integers. An important special case of the problem can be solved geometrically by choosing, from among all paths joining two points in the plane and lying between two given nonintersecting paths, the path with minimum euclidian length. Applications of the results are given, to deterministic production-distribution models (e.g., the Modigliani-Hohn [30] production smoothing model), certain of the stochastic inventory-redistribution models examined by Ignall and Veinott [27], a deterministic price speculation and storage model (including Cahn's warehouse problem [11]), and a zero lead time case of the Clark-Scarf series multi-echelon model [13]. In addition, applications are given to several maximum likelihood estimation problems in which the parameters satisfy certain linear inequalities, e.g., those surveyed in Brunk [8], [9, pp. 1347–1349], and a few others.

Scarf [6] has shown that the $( {s,S} )$ policy is optimal for a class of discrete review dynamic nonstationary inventory models. In this paper a new proof of this result is found under new conditions which do not imply and are not implied by Scarf’s hypotheses. We replace Scarf’s hypothesis that the one period expected costs are convex by the weaker assumption that the negatives of these expected costs are unimodal. On the other hand we impose the additional assumption not made by Scarf that the absolute minima of the one, period expected costs are (nearly) rising over time. For the infinite period stationary model, this last hypothesis is automatically satisfied. Thus in this case our hypotheses are weaker than Scarf’s. The bounds on the optimal parameter values given by Veinott and Wagner [12] are established for the present case. The bounds in a period are easily computed, and depend only upon the expected costs for that period. Moreover, simple conditions are given which ensure that the optimal param...

A general multiperiod multi-echelon supply system consisting of n facilities each stocking a single product is studied. At the beginning of a period each facility may order stock from an exogenous source with no delivery lag and proportional ordering costs. During the period the (random) demands at the facilities are satisfied according to a given supply policy that determines to what extent stock may be redistributed from facilities with excess stock to those experiencing shortages. There are storage, shortage, and transportation costs. An ordering policy that minimizes expected costs is sought. If the initial stock is sufficiently small and certain other conditions are fulfilled, it is optimal to order up to a certain base stock level at each facility. The special supply policy in which each facility except facility 1 passes its shortages on to a given lower numbered facility called its direct supplier is examined in some detail. Bounds on the base stock levels are obtained. It is also shown that if the demand distribution at facility j is stochastically smaller ('spread' less) than that at another facility k having the same direct supplier and if certain other conditions are fulfilled, then the optimal base stock level ('virtual' stock out probability) at j is less than (greater than) or equal to that at facility k. (Author)

Recently Goldstein has considered the problem of determining conditions on the selection of directions in feasible direction algorithms for unconstrained maximization problems which assure the gradient vanishes in the limit. This paper extends his work (when specialized to Euclidian spaces) in various ways, notably by considering constrained maximization problems and by allowing a wider choice in the selection of the step size. For example we allow the ''optimal'' step size among others. We give conditions on the directions which assure convergence to a stationary point in feasible direction algorithms for maximizing a real valued continuous function on a closed set. We also apply this result to establish convergence to a stationary point of several known methods (e.g., Cauchy's method of steepest ascents, the Newton-Raphson method, and ufrank and Wolfe's method), a simple variant of one of Zoutendijk's methods that eliminates the need for his ''anti-zigzagging'' procedures, and some new second order methods that require quadratic programs to be solved at each stage. (Author)

We consider the problem of choosing the amounts of a single product to produce in each of a finite number of time periods so as to minimize the (convex) production and (convex) inventory carrying costs over the periods while satisfying known requirements. The effect of changes in the various parameters, viz., the requirements and the production and inventory capacity limits, upon the optimal production levels is studied. The results obtained are exploited to provide simple and intuitive computational procedures for finding optimal production schedules for a range of parameter values.

This paper is concerned with a multi-product dynamic nonstationary inventory problem in which the system is reviewed at the beginning of each of a sequence of periods of equal length. The model has the following features. There is a general demand process with no stationarity or independence assumptions, partial or complete backlogging of unfilled demand, a fixed non-negative delivery lag (which may be positive only under complete backlogging), a nonstationary linear ordering cost, a nonstationary holding and shortage cost function, discounting of future costs, and nonstationary restrictions like budget and storage limitations. The objective is to choose an ordering policy that minimizes the expected discounted costs over an infinite time horizon. Conditions are given that ensure that the base stock ordering policy is optimal and that the base stock levels in each period are easy to calculate.

Efficient algorithms are developed optimizing an important class of capacity scheduling models. The specific problem considered can be simply described in terms of contracting for warehousing capacity. Contracts must be let for warehouse capacity over n time periods, with the minimum capacity to be provided in each time period being specified. Savings may be achieved by long-term leasing arrangements or by contracting at favorable periods of time, even though this creates idle capacity at certain time periods. A minimum cost solution to this problem is sought. The mathematical model also applies to problems of equipment replacement and overhaul, checkout, repair, and replacement of stochastically failing equipment, determination of economic lot size, product assortment, and deterministic batch queuing policies, labor-force planning, and multi-commodity warehouse decisions. For some of these problems, such as equipment replacement, the computing algorithms presented are even more efficient than schemes heretofore proposed for simpler versions of the same problem.

Multiproduct inventory systems with proportional ordering costs and stochastic demands are studied. New conditions are obtained under which a myopic ordering policy (a policy of minimizing expected cost in the current period alone) is optimal for a sequence of periods for all initial inventory levels. An important one of these, the substitute property, holds when the myopic policy is such that increasing the initial inventory of one product does not increase the quantity ordered of any product. Conditions on the one period expected holding and shortage cost function, which are of independent interest in nonlinear programming, are shown to imply the substitute property. Applications of these conditions to models with storage or investment limitations and to a multiechelon model are given. Under backlogging the usual extension to a fixed delivery lag is obtained. Some non-stationary cases are also treated.

This expository note develops Rockafellar's (1968, 1970) conjugate-duality theory for convex programs using Gould's (1972) geometric formulation of the dual program. This approach makes the duality theory transparent geometrically and motivates the use of conjugate functions.

A countable system of equations arising in Markovian decision processes is studied. Conditions are given ensuring the existence and uniqueness of an explicit solution to the system. (Author)

Hirsch and Hoffman (1961) studied the problem of minimizing a real-valued concave function on a closed convex set containing no lines. They showed that if the closure of the collection of extreme points is bounded and the function is lower semicontinuous thereon, the function attains its minimum on the set at an extreme point if and only if the function is bounded below on each half-line in the set. It is shown in this paper that this is so if and only if the negative part of the function has uniformly bounded jumps on all line segments in the set and the function is bounded below on the half-lines emanating from a single element of the set in every extreme direction. If also the set is bounded below and the directional derivative of the function at infinity in every extreme direction is linear in the directions, it is shown that the function attains its minimum on the set if and only if a pair of linear functions attains its lexicographic minimum on the set.

In a fundamental paper on stationary finite state and action Markovian decision processes, Blackwell defines an optimal policy to be one that maximizes the expected total discounted rewards for all sufficiently small interest rates rho > 0. He also establishes the existence of a stationary optimal policy by a limit process that does not give a finite algorithm. The purpose of this paper is to prove this result constructively by devising a finite policy improvement method for finding stationary optimal policies. The algorithm is based on a new representation of the vector of expected discounted returns under a stationary policy as a power series in the interest rate for all small enough rho > 0. (Author)

We consider finite state and action discrete time parameter Markov decision chains. The objective is to provide an algorithm for finding a policy that minimizes the long-run expected average cost when there are linear side conditions on the limit points of the expected state-action frequencies. This problem has been solved previously only for the case where every deterministic stationary policy has at most one ergodic class. This note removes that restriction by applying the Dantzig-Wolfe decomposition principle.

It is shown that if A is an integral matrix having linearly independent rows, then the extreme points of the set of nonnegative solutions to Ax = b are integral for all integral b if and only if the determinant of every basis matrix is plus or minus 1. This provides a short proof of the Hoffman- Kruskal theorem characterizing unimodular matrices, i.e., matrices in which the determinant of each nonsingular submatrix is plus or minus 1. Their theorem is that if A is integral, then A is unimodular if and only if the extreme points of the set of nonnegative solutions to Ax = or b are integral for all integral b.