The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

On optimal aiming to hit a linear target

Typically weapon systems have an inherent systematic error and a random error for each round, centered around its mean point of impact. The systematic error is common to all aimings. Assume such a system for which there is a preassigned amount of ammunition of n rounds to engage a given target simultaneously, and which is capable of administering their fire with individual aiming points (allowing “offsets”). The objective is to determine the best aiming points for the system so as to maximize the probability of hitting the target by at least one of the n rounds. In this paper we focus on the special case where the target is linear (one‐dimensional) and there are no random errors. We prove that as long as the aiming error is symmetrically distributed and possesses one mode at zero, the optimal aiming is independent of the particular error distribution, and we specify the optimal aiming points. Possible extensions are further discussed, as well as civilian applications in manufacturing, radio‐electronics, and detection. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 323–333, 1999     

Response surface analysis of two‐stage stochastic linear programming with recourse

We apply the techniques of response surface methodology (RSM) to approximate the objective function of a two‐stage stochastic linear program with recourse. In particular, the objective function is estimated, in the region of optimality, by a quadratic function of the first‐stage decision variables. The resulting response surface can provide valuable modeling insight, such as directions of minimum and maximum sensitivity to changes in the first‐stage variables. Latin hypercube (LH) sampling is applied to reduce the variance of the recourse function point estimates that are used to construct the response surface. Empirical results show the value of the LH method by comparing it with strategies based on independent random numbers, common random numbers, and the Schruben‐Margolin assignment rule. In addition, variance reduction with LH sampling can be guaranteed for an important class of two‐stage problems which includes the classical capacity expansion model. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 753–776, 1999     

Civil Wars and Contemporary State Building: Rebellion,Conflict Duration,and Lootable Resources

Regardless of the outcome, civil wars are destructive events. They not only devastate the physical and human capital of a society, but also have a direct effect on state capacity. The capacity of the state is critical as it attempts to rebuild society and minimize the risk of a new civil conflict; yet, it is still not clear how civil war precisely affects state capacity. In general, we argue that incumbent victors are more likely to end with a stronger state when the conflict is short and the victory is decisive. In contrast, rebel victors require more time to build their internal capacity and thus have stronger states after a longer conflict, especially when they had access to lootable resources.     

Degeneracy in inventory models

In order‐quantity reorder‐point formulations for inventory items where backordering is allowed, some of the more common ways to prevent excessive stockouts in an optimal solution are to impose either a cost per unit short, a cost per stockout occasion, or a target fill rate. We show that these popular formulations, both exact and approximate, can become “degenerate” even with quite plausible parameters. By degeneracy we mean any situation in which the formulation either cannot be solved, leads to nonsensical “optimal” solutions, or becomes equivalent to something substantially simpler. We explain the reasons for the degeneracies, yielding new insight into these models, and we provide practical advice for inventory managers. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 686–705, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10037     

Forecast horizons for the discounted dynamic lot-size problem allowing speculative motive

This article considers the dynamic lot-size problem under discounting, allowing speculative motive for holding inventory. A variable rolling-horizon procedure is presented, which, under certain regularity conditions, is guaranteed to generate an infinite-horizon optimal-production plan. We also discuss a fixed rolling-horizon procedure which provides a production plan that achieves an infinite-horizon cost within a user-specified tolerance ϵ of optimality. The fixed-horizon length T* needed in this procedure is given in terms of a closed-form formula that is independent of specific forecasted demands. We also present computational results for problems with a range of cost parameters and demand characteristics.