The traveling salesman problem: An update of research

During the course of the last few years, attacks on the traveling salesman problem have resulted in a variety of often innovative and rather powerful computational procedures. In this article, we present a review of these results for problems defined on weighted and unweighted graphs. Some account of computational behavior for exact algorithms is provided; however, the primary coverage deals with the strategy of particular procedures. In addition, we include some aspects of nonexact algorithms with major interest confined to the establishment of worst-case bounds.     

Calculation of the cost of warranty policies as a function of estimated life distributions

Two types of warranties are analyzed. These are the free-replacement warranty, under which failed items are replaced free of charge until a specified total operating time has been achieved, and the pro rata warranty, under which items that fail prior to a specified time are replaced at pro rata cost to the buyer. Both the buyer's and seller's points of view are considered. The basis of the analysis is a comparison of warranted and unwarranted (otherwise identical) items with regard to long-run cost to the buyer and long-run profit to the seller. Application of the results requires knowledge of certain characteristics of the life distribution of the items in question. Parametric and nonparametric methods of estimation of these characteristics from incomplete data are discussed. Single and multiple failure-mode situations are considered. Some solutions to the problem are illustrated using incomplete data on failure times of an aircraft component.     

Upper and lower bounds for a pattern bombing problem

This paper includes two simple analytic formulas for kill probability that are applicable in circumstances where shots should be fired in a pattern. The two formulas bracket the maximum kill probability achievable with an optimal pattern. The upper bound corresponds to an optimal nonfeasible pattern, and the lower bound to a nonoptimal feasible pattern.     

On the evaluation of investment proposals having multiple attributes

A framework is developed for analyzing the likelihood of acceptance of an investment project proposal when objectives are uncertain. The foundation is a utility model of top management's choice process, modified if need be through a Bayesian approach which takes into account any apparent inconsistency in the history of past proposal acceptances and rejections.     

Optimal inventory policy when stockouts alter demand

An inventory model in which future demand is affected by stockouts has been considered recently by B. L. Schwartz. Some generalizations of Schwartz's model are presented in this paper and properties of the optimal policies are determined. In the case of deterministic demand, a set-up cost is included and a mixture of backlogged and nonbacklogged orders is allowed during stockout. It is proved that the optimal policy entails either no stockout or continual stockout, depending on the values of three parameters. For stochastic demand, the effect of stockouts on demand density is postulated, the resulting optimal inventory policy is discussed, and an example involving an exponential density function is then analyzed in detail.     

Armor configurations via dynamic programming

The problem of selecting materials, their thicknesses and order for armor designed for the defeat of shaped charge threats, has been formulated as a constrained optimization problem. The mathematical model provides an optimal order and thickness of each layer of material such that the resulting armor configuration will be of minimum mass per unit area subject to constraints on total thickness and shaped charge jet tip exit velocity.     

Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.