Search

The well-known Steiner problem on networks is an NP-complete problem for which there are many deterministic algorithms and heuristics. In this paper a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. Two different types of cooling algorithms are tailored to the Directed Steiner Problem. Computations are done on a test bed of 480 random graphs in order to study the performance of these algorithms. In addition to the quality of the final answers, the study looks at the distribution of first occurrences during the execution of the cooling schedules of answers that are within 3% of the optimum. The study suggests that these near-optimal answers appear according to an approximately exponential distribution and that they can be obtained in polynomial time. Experiments also indicate that for random graphs annealing usually gives near-optimal answers in less time than does branch and bound. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper describes a research project that was designed to provide a group of bright undergraduate students with a meaningful research experience that would encourage and motivate them to attend graduate school for further education and research. The project illustrated basic research techniques and the nature of the job of a researcher to undergraduates who had had limited or no opportunities for research. The students were involved in all phases of the project to ensure that they would gain the confidence needed to do research on their own. In this project the students were given an opportunity to do research that involved parallel processing.

This paper introduces the Multi-Terminal Sweep Algorithm, a heuristic algorithm for obtaining an approximate solution to the multiple terminal vehicle-dispatch problem. The procedure determines a set of routes by which vehicles from two or more terminals can service a collection of demand points so that the total distance traveled is kept near to the minimum. This solution also satisfies constraints on the vehicle load and on the length of each route. Application of the algorithm to eleven multiple terminal vehicle-dispatch problems shows that near-optimal solutions to large-scale problems can be found in a reasonable amount of computer time.

Water temperature residuals, which are taken as the difference between the daily average water temperature (Missouri River, Boonville, Missouri) and the Fourier series regression fit to the data points, are analyzed. A 1-yr record length is used as a base period. The Kolmogorov-Smirnov test is used to determine, for a given number of extracted harmonics, the sample size required to yield a set of normal random variates with mean zero. It is also shown that with only the fundamental harmonic removed, a sample size of at least 180 is required to yield a sample average residual of less than 0.2°F. When the fundamental and higher order harmonics are removed, this sample size is reduced considerably.

A branch and bound algorithm is designed to solve the general integer linear programming problem with parametric right-hand sides. The right-hand sides have the form b + θd where b and d are comformable vectors, d consists of nonnegative constants, and θ varies from zero to one. The method consists of first determining all possible right-hand side integer constants and appending this set of integer constants to the initial tableau to form an expanded problem with a finite number of family members. The implicit enumeration method gives a lower bound on the integer solutions. The branch and bound method is used with fathoming tests which allow one family member possibly to fathom other family members. A cutting plane option applies a finite number of cuts to each node before branching. In addition, the cutting plane method is invoked whenever some members are feasible at a node and others are infeasible. The branching and cutting process is repeated until the entire family of problem has been solved.

This paper introduces and illustrates an efficient algorithm, called the sweep algorithm, for solving medium- as well as large-scale vehicle-dispatch problems with load and distance constraints for each vehicle. The locations that are used to make up each route are determined according to the polar-coordinate angle for each location. An iterative procedure is then used to improve the total distance traveled over all routes. The algorithm has the feature that the amount of computation required increases linearly with the number of locations if the average number of locations for each route remains relatively constant. For example, if the average number of locations per route is 7.5, the algorithm takes approximately 75 seconds to solve a 75-location problem on an IBM 360/67 and approximately 115 seconds to solve a 100-location problem. In contrast, the time to solve a problem with a fixed number of locations increases quadratically with the average number of locations per route. The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell's and is slightly less so than Christofides and Eilon's.

The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model.

The major problem in “layout” is to determine the most economical relative location of facilities. MAT is a construction technique utilizing the distances between all pairs of locations and the loads transported between all pairs of facilities per unit time to approximate the optimal allocation of the facilities to the locations. The MAT general algorithm, an example problem and a theorem relating the MAT solution to the optimal solution are given. A computer program has been written that will apply MAT to the allocation problem for a maximum of 40 facilities.

The stepwise multiple regression technique is used in a model building process to develop predictors of temperature, salinity, and sound velocity as functions of geographical location, time, and depth. Models which give reasonable results are obtained through successive trials using higher order terms of the independent variables. The model for sound velocity yields values which are nearly identical to the Wilson sound velocities contained in the ocean station file and values computed using a modified version of the MacKenzie equation. The distribution of residuals resulting from comparisons of the Wilson equation sound velocities to those obtained from the regression model (both computed from actual temperature and salinities) shows that 98% fall within the range of plus or minus 2 m/sec. A comparison of the regression model sound velocity values computed from regression predictions of temperature and salinity with the Wilson values shows that 88% of the residuals fall in the range of plus or minus 12 m/sec. The results, which are valid for the 4 degrees square centered at 37.5 degrees North latitude and 69.5 degrees West longitude, are discussed in terms of the statistical significance of the distribution of the residuals. Since the physical characteristics of the area selected are rather complex, the application of this technique to other parts of the ocean is recommended.

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.