Knowledge that Transforms

A network, in which two integers tıj (the traversal time) and cıj (the capacity) are associated with each arc PıPj, is considered with respect to the following question. What is the maximal amount of goods that can be transported from one node to another in a given number T of time periods, and how does one ship in order to achieve this maximum? A computationally efficient algorithm for solving this dynamic linear-programming problem is presented. The algorithm has the following features (a) The only arithmetic operations required are addition and subtraction (b) In solving for a given time period T, optimal solutions for all lesser time periods are a by-product (c) The constructed optimal solution for a given T is presented as a relatively small number of activities (chain-flows) which are repeated over and over until the end of the T periods. Hence, in particular, hold-overs at intermediate nodes are not required (d) Arcs which serve as bottlenecks for the flow are singled out, as well as the time periods in which they act as such (e) In solving the problem for successive values of T, stabilization on a set of chain-flows (see (c) above) eventually occurs, and an a priori bound on when stabilization occurs can be established. The fact that there exist solutions to this problem which have the simple form described in (c) is remarkable, since other dynamic linear-programming problems that have been studied do not enjoy this property.

The traveling-salesman problem is a generalized form of the simple problem to find the smallest closed loop that connects a number of points in a plane. Efforts in the past to find an efficient method for solving it have met with only partial success. The present paper describes a method of solution that has the following properties (a) It is applicable to both symmetric and asymmetric problems with random elements (b) It does not use subjective decisions, so that it can be completely mechanized (c) It is appreciably faster than any other method proposed (d) It can be terminated at any point where the solution obtained so far is deemed sufficiently accurate.

This paper is concerned with a target assignment model of a probabilistic and nonlinear nature, but nevertheless one which is closely related to the “personnel-assignment” problem. It is shown here that, despite the apparent nonlinearities, it is possible to devise a linear programming formulation that will ordinarily provide a close approximation to the original problem.

Two types of customer behavior are considered: (1) if a customer is acquired for service before he has waited a time τ0, he remains in the queue until served irrespective of whether or not his total waiting time exceeds τ0. Only those customers who wait for a time τ0 without being acquired for service become “lost” customers, and (2) a customer whose total waiting time is τ0 becomes a lost customer irrespective of whether he is acquired for service or not.

This paper reviews some recent successes in the use of linear programming methods for the solution of discrete-variable extremum problems. One example of the use of the multistage approach of dynamic programming for this purpose is also discussed.

In his interesting paper on discrete-variable extremum problems, George Dantzig (Dantzig, G. 1957. Discrete-variable extremum problems. Opns Res. 5 266–277.) discusses the “knapsack” problem. He presents two approximate methods based upon linear programming techniques, and an exact solution based upon the functional equation method of dynamic programming (Bellman, R. 1957. Dynamic Programming. Princeton University Press.).

A simple theory of traffic flow is developed by replacing individual vehicles with a continuous “fluid” density and applying an empirical relation between speed and density. Characteristic features of the resulting theory are a simple “graph-shearing” process for following the development of traffic waves in time and the frequent appearance of shock waves. The effect of a traffic signal on traffic streams is studied and found to exhibit a threshold effect wherein the disturbances are minor for light traffic but suddenly build to large values when a critical density is exceeded.

The traveling-salesman problem is that of finding a permutation P = (1 i2 i3 … in) of the integers from 1 through n that minimizes the quantity [Formula: see text] where the aαβ are a given set of real numbers. More accurately, since there are only (n − 1)′ possibilities to consider, the problem is to find an efficient method for choosing a minimizing permutation. This problem was posed, in 1934, by Hassler Whitney in a seminar talk at Princeton University. There are as yet no acceptable computational methods, and surprisingly few mathematical results relative to the problem.