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.     

A proportional defense model

This paper considers the problem of defending a set of point targets of differing values. The defense is proportional in that it forces the offense to pay a price, in terms of reentry vehicles expended, that is proportional to the value of the target. The objective of the defense is to balance its resources so that no matter what attack is launched, the offense will have to pay a price greater than or equal to some fixed value for every unit of damage inflicted. The analysis determines which targets should be defended and determines the optimal firing doctrine for interceptors at defended targets. A numerical example is included showing the relationship between the total target damage and the size of the interceptor force for different values of p, the interceptor single shot kill probability. Some generalizations are discussed.     

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.     

A mixed optimization technique for the generalized machine replacement problem

A mixed optimization technique for optimal machine replacement is presented which allows much more flexibility than previous models. Optimal purchase, maintenance and sale of a given machine between any two given points in time is treated as a subproblem, which one may choose to solve via control theory, dynamic programming, or practical engineering considerations. (A control theory formulation is used in the paper as an illustration.) These subproblem solutions are then incorporated into a Wagner-Whitin formulation for solution of the full problem. The technique is particularly useful for problems with such asymmetries as an existing initial machine or uneven technological change. A simple numerical example is solved in the Appendix.