Target problems for approximation routines:
Since 1985 the group has been using and studying algorithms for the design of complex systems. The initial project dealt with the design of large distributed database networks, defined by a model developed by Ward Morgan of Drexel University (now at Clemson) and his group.
Optimization consists of allocating database to nodes, specifying the existence and speeds of links between nodes, and routing queries and updates - given the query and update traffic from each node to each database. The model accounts for all installation and operational costs and traffic delays, and is highly non-linear. Full optimization of a linearized version with an integer linear programming package is not feasible for systems of more than a half-dozen or so nodes. We thus began a search for randomized algorithms which would provide useful approximate solutions in a reasonable time.
Our initial experiments demonstrated that simulated annealing could solve exactly small network problems (3 - 5 nodes) exactly in a matter of seconds [Laferriere]. Larger problems (10 - 20 nodes and above) still required minutes or hours, however, so we began to look at parallel implementations of annealing and hybrid approaches using annealing and branch & bound.
In the past few years we have concentrated on developing more efficient
parallel annealing algorithms, and have looked at several additional
problems, including task allocation and configuration
on multi computers, electrostatic problems, the
Our major accomplishment in the past few years has been the development of a fully adaptive parallel annealing algorithm by Allisen Lee. The algorithm requires essentially no input from the user, other than routines to generate, evaluate, and modify the model; start and stop temperatures, cooling, and the run length are automatically determined. This package, which is written under the CHIMP message-passing interface, is designed for distributed-memory systems. The CHIMP version will soon be ported to MPI, and should run on any system supporting that interface. The algorithm is described in Allisen's dissertation (download).
One of the side-effects of this project has been a deeper understanding of the sequential annealing algorithm itself - particularly with respect to the effect of machine precision upon the algorithm's performance. We have found, for example, that the machine precision places a lower bound on the useful temperatures; if the temperature drops below this bound, continued annealing may actually lead to an increase in the expected cost. These results are described in a recent paper in Physics Letters A.
We have recently developed a simple implementation of simulated annealing that uses a fixed set of parameters on all problems, does not become trapped, eventually matches or exceeds the performance of single standard annealing runs on all problems tested, offers ample opportunity for run-time optimization, and is trivial to parallelize (parallel implementation available also); check this place.
Thesis:Speedup of a branch and bound network optimization algorithm, R. J. Pennington, March, 1988Papers:Bosworth, K. W., G. S. Stiles and Rick Pennington, A parallel nonlinear integer programming algorithm based on branch and bound and simulated annealing, Proc. Third Conference on Parallel Processing for Scientific Computing, SIAM, Los Angeles, December, 1987.
Pennington, R. J., K. Bosworth, G. S. Stiles, P. Wheeler, and A. Raghuram, Parallel implementations of a branch and bound algorithm for the optimization of distributed database computer networks, Proc. IEEE Region 5 Conference, Colorado Springs, March, 1988
Stiles, G. S., K. W. Bosworth, T. W. Morgan, F. H. Lee, and R. J. Pennington, Parallel optimization of distributed database networks, Proc. First Int'l Conf. Applications of Transputers, Amsterdam, IOS Press, 1989.
Nandan Udiavar and Jamshed Khan developed an annealing package to allocate and schedule a parallel task graph on a processor graph such that the total execution time is minimized; if desired, the package can also establish the connections between the processors. The task graph includes information on the computation time of each task and the communication between nodes. The processor graph includes the processor speed, the number of links, and the communication parameters for the links; the connections between processors may be specified or left for the annealing to establish.
Theses:Stochastic Optimization of Task Allocation & Scheduling in a Multiprocessor System, N. Udiavar, 1991
Abstract
Optimal Allocation of Tasks with Virtual Shared Memory, Jamshed Khan, 1992
Abstract
Papers/presentations:Udiavar, N., and G. S. Stiles, A simple and flexible model for the allocation of tasks to a system of transputers, Transputer Research and Applications 1, Amsterdam, IOS Press, 1989.
Theses:Parallel stochastic optimization of distributed database networks, F. H. Lee, Sept., 1988.Dissertation:
Abstract
Parallel annealing under TROLLIUS, Bhavesh Shah, 1992.
Abstract
postcript
Parallel simulated annealing on a message-passing multi- computer, F. H. Allisen Lee, June, 1995.Papers and Presentations:
Abstract
Download
Hardcopy available by request to dyke.stiles@ece.usu.edu
Slides from the Moscow paper on this project can be found in the Gallery.
Stiles, G. S., K. W. Bosworth, T. W. Morgan, F. H. Lee, and R. J. Pennington, Parallel optimization of distributed database networks, Proc. First Int'l Conf. Applications of Transputers, Amsterdam, IOS Press, 1989.
Lee, F. H., and G. S. Stiles, Parallel simulated annealing: several approaches, Transputer Research and Applications 2, Amsterdam, IOS Press, 1989.
Stiles, G. S., K. W. Bosworth, T. W. Morgan, F. H. Lee, and R. J. Pennington, Parallel optimization of distributed database networks, Proc. Int'l. Conf. Applications of Transputers, Liverpool, Aug., 1989.
Lee, F. H., G. S. Stiles, and Viswanathan Swaminathan, Simulated annealing on massively parallel machines, World Transputer Conference '94, Lake Como, Italy, Sept. 4-7, 1994.
Lee, F. H., G. S. Stiles, and Viswanathan Swaminathan, Parallel annealing on distributed memory systems, Second Int'l. Conf. Software for Multiprocessors and Supercomputers: Theory, Practice, Experience, Moscow, Sept. 19-22, 1994.
We have experimented with some step-wise or systolic parallel annealing algorithms. Some of our results may be found in the Gallery and in Lee's dissertation.
We have developed some interesting results on the effect of the precision of the random floating-point numbers used in the acceptance check on the performance of annealing. The results show that there are cases where extending the run-length can lead to increased expected costs. A lower bound on the useful temperature is also presented.
Paper:Stiles, G. S., The effect of numerical precision upon simulated annealing, Phys. Lett. A, 185, 3, 13 Feb. 1994.
Compressed Postscript
Some figures can be found in the Gallery.
The network model used in much of our research is described in the following paper - as well as in Julien-Laferriere's and Lee's theses and dissertation.
Paper:Raghuram, A., T. W. Morgan, K. Bosworth, G. S. Stiles and P. Wheeler, A multi-criteria model for determining the optimal topology and database allocation for computer networks, Proc. Montech '87, Montreal, November, 1987
We presently have a generic single-processor annealing package that is available. The basic annealing shell is provided, and the user needs only to supply a set of routines to generate a random solution, perturb and unperturb a solution randomly, calculate the cost of a solution, and print specific results. The package has been used in our research over the past 10 years, and provides (if desired) a great deal of information on the performance of the algorithm. Look here.
This version also allows an easy parallel annealing implementation. The approach is simply multiple independent runs - which we have found to be very easy and often as good as any other parallel approach (see Lee's work above); it definitely applies to any problem! We presently have a networked Java version of this package; email (bottom of this page) if you are interested.
This, our only continuous problem, finds the distribution of charged particles which are confined to move on the surface of a sphere. The algortihm is from ter Laak et al. [28].
The mincut problem involves finding the partition of a graph into two subgraphs, each with the same number of nodes, such that the number of edges between the partitions is minimized.
Csaba Gyulai has developed a genetic algorithm - annealing - nonlinear least squares hybrid package to fit laser spectroscopy data to theoretical models.
Dissertation:Combination of Parallel Stochastic Algorithms and a Deterministic Nonlinear Least Squares Algorithm for the Analysis of Extended X-Ray Absorption Fine Structure (EXAFS) Data, Csaba Gyulai, 1999.
This project investigates the construction of random topologies for multi-computer networks. Given a number of nodes of fixed degree, annealing is used to find the graph of minimum diameter. The program is based on a generic parallel annealing package developed with the MPI message-passing interface. If you have an interest in this package, let us know.