Note: On the set-union knapsack problem

We consider a generalization of the 0-1 knapsack problem called the set-union knapsack problem (SKP). In the SKP, each item is a set of elements, each item has a nonnegative value, and each element has a nonnegative weight. The total weight of a collection of items is given by the total weight of the elements in the union of the items' sets. This problem has applications to data-base partitioning and to machine loading in flexible manufacturing systems. We show that the SKP remains NP-hard, even in very restricted cases. We present an exact, dynamic programming algorithm for the SKP and show sufficient conditions for it to run in polynomial time. © 1994 John Wiley & Sons, Inc.     

Stochastic linear programs with simple recourse: The equivalent deterministic convex program for the normal,exponential, and erlang cases

We consider here stochastic linear programs with simple recourse when all the elements of the technology matrix and the resource vector have certain specific distributions. The distributions considered are the Normal, Exponential and Erlang. For the first two instances we extend the equivalent deterministic program to include the variance of the recourse. Finally, a simple example is given to illustrate the application of the formulas for the Erlang case.     

Auxiliary procedures for solving long transportation problems

An efficient auxiliary algorithm for solving transportation problems, based on a necessary but not sufficient condition for optimum, is presented.     

Spike swapping in basis reinversion

During basis reinversion of either a product form or elimination form linear programming system, it may become necessary to swap spike columns to effect the reinversion and maintain the desired sparsity characteristics. This note shows that the only spikes which need be examined when an interchange is required are those not yet processed in the current external bump.     

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.     

Adjacent vertices on transportation polytopes

To solve linear fixed charge problems with Murty's vertex ranking algorithm, one uses a simplex algorithm and a procedure to determine the vertices adjacent to a given vertex. In solving fixed charge transportation problems, the simplex algorithm simplifies to the stepping-stone algorithm. To find adjacent vertices on transportation polytopes, we present a procedure which is a simplification of a more general procedure for arbitrary polytopes.     

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.     

Stock control in a many depot system

The chief problems considered are: (1) In a parallel set of warehouses, how should stocks be allocated? (2) In a system consisting of a central warehouse and several subsidiary warehouses, how much stock should be carried in each? The demands may have known, or unknown, distribution functions. For problem (1), the i-th stock n_i should usually be allocated in proportion to the i-th demand m_i; in special cases, a significant improvement is embodied in the formula (N = total allocable stock)

     

A simple Markov model for the analysis of multiple air combat

It is proposed to describe multiple air-to-air combat having a moderate number of participants with the aid of a stochastic process based on end-game duels. A simple model describing the dominant features of air combat leads to a continuous time discrete-state Markov process. Solution of the forward Kolmogorov equations enables one to investigate the influence of initial force levels and performance parameters on the outcome probabilities of the multiple engagement. As is illustrated, such results may be useful in the decision-making process for aircraft and weapon system development planning. Some comparisons are made with Lanchester models as well as with a semi-Markov model.     

Mexico: a model for success

In Mexico, a 40 year period of political stability and economic advancement, hailed for its high rates of growth in income per capita, rapid urbanization, and impressive gains in indicators of health and education, seemed to come to a halt in the early 1980s. Since the early 1970s, fertility has declined sharply in chronological association with a new population policy and the implementation of a national family planning program. If in 1940 there was no apparent reason for the Mexican state to have much interest in limiting fertility, such was no longer the case by 1970. The General Law of Population that had been passed in 1947 was laced with the expansionist ideology that dominated demographic issues for more that a century; its pro-natalism had been reinforced by health regulations prohibiting the sale and use of contraceptives and by a penal code that made abortion a crime. Between 1970 and 1981 the total fertility rate fell by about 39%. Since 1975, change in contraceptive practice accounts for the bulk of the measured fertility decline. Between 1976 and 1982 there was a 66% increase in contraceptive prevalence. The government's involvement in family planning activities helped to: 1) develop an effective contraceptive distribution system; 2) circulate extensive information, education, and communication publicizing fertility and images of the small family; and 3) mobilize health practitioners in public institutions to counsel and persuade their clients to accept and practice contraception. The emerging debate over population policy in Brazil may well prefigure debates in other Latin American countries; the recent democratization in Brazil is the vocalization of a demand from women's groups and the left for government provided family planning services. Overall, Mexico's willingness to take the long view tackle the birth rate issue head on is likely to remain an exception in Latin America.