Suboptimal algorithms for the quadratic assignment problem

The idea of combining relatively simple continuous methods with discrete procedures is used for the construction of suboptimal algorithms for quadratic assignment problems. Depending on the nature of the special problem these steps may vary in complexity. The simplest procedures require minimum storage space and result in tolerable computation times. Different choices of parameters and random variations may be used in order to obtain statistical distributions of suboptimal solutions. Computational results for sample problems indicate improvements on results of Steinberg, Gilmore, and Hillier and Connors.     

Impact of an all volunteer force upon the navy in the 1972-1973 timeframe

This paper develops estimates of true volunteer levels for 1972 and 1973, based on experience gained through 1970 draft lottery data. The paper also formulates estimates of the qualitative characteristics of a 1972-1973 Navy volunteer force, and establishes a relationship between rate of volunteerism and military pay. Utilizing estimates generated in the paper, Navy military personnel budget requirements for FY '72 and '73 are presented.     

A finiteness proof for modified dantzig cuts in integer programming

Let be a basic solution to the linear programming problem subject to: where R is the index set associated with the nonbasic variables. If all of the variables are constrained to be nonnegative integers and x_u is not an integer in the basic solution, the linear constraint is implied. We prove that including these “cuts” in a specified way yields a finite dual simplex algorithm for the pure integer programming problem. The relation of these modified Dantzig cuts to Gomory cuts is discussed.     

Stochastic duels with round-dependent hit probabilities

The effect of round dependent hit probabilities in the fundamental stochastic duel are examined. The general solution and several specific examples are derived where one side's hit probabilities are improved from round to round. For these specific cases the advantages of round to round improvement are explicitly displayed.     

The search for an intelligent evader concealed in one of an arbitrary number of regions

This paper considers the search for an evader concealed in one of an arbitrary number of regions, each of which is characterized by its detection probability. We shall be concerned here with the double-sided problem in which the evader chooses this probability secretly, although he may not subsequently move; his aim is to maximize the expected time to detection, while the searcher attempts to minimize it. The situation where two regions are involved has been studied previously and reported on recently. This paper represents a continuation of this analysis. It is normally true that as the number of regions increases, optimal strategies for both searcher and evader are progressively more difficult to determine precisely. However it will be shown that, generally, satisfactory approximations to each are almost as easily derived as in the two region problem, and that the accuracy of such approximations is essentially independent of the number of regions. This means that so far as the evader is concerned, characteristics of the two-region problem may be used to assess the accuracy of such approximate strategies for problems of more than two regions.     

A problem of restricted partitions

This paper presents a simple algorithm for finding the number of restricted k-partitions of a natural number n. The unrestricted k-partitions of n are expressed as the sum of these restricted k-partitions, called inadmissible, and the admissible k-partitions. The simplicity of the algorithm is striking, though all the implications are unclear.     

Stochastic duels with displacements (suppression)

The stochastic duel is extended to include the possibility of a near-miss on each round fired, which causes the opponent to displace. During displacement, the displacing contestant cannot return the fire but is still a target for his opponent. An alternative interpretation of this model is to consider the displacement time as the time a contestant's fire is suppressed by his opponent's fire and that he does not move, but merely ceases fire temporarily. All times are exponentially distributed.     

Time minimizing flows in directed networks

An important class of network flow problems is that class for which the objective is to minimize the cost of the most expensive unit of flow while obtaining a desired total flow through the network. Two special cases of this problem have been solved, namely, the bottleneck assignment problem and time-minimizing transportation problem. This paper addresses the more general case which we shall refer to as the time-minimizing network flow problem. Associated with each arc is an arc capacity (static) and a transferral time. The objective is to find a maximal flow for which the length (in time) of the longest path carrying flow is minimized. The character of the problem is discussed and a solution algorithm is presented.