Simulated annealing and combinatorial optimization

ABSTRACT

We formulate a class of adaptive heuristics for combinatorial optimization. Recently proposed methods such as simulated annealing, probabilistic hill climbing, and sequence heuristics, as well as classical perturbation methods are all members of this class of adaptive heuristics. We expose the issues involved in using an adaptive heuristic in general, and simulated annealing, probabilistic hill climbing, and sequence heuristics in particular. These issues are investigated experimentally.

REFERENCES

• ARAG85: C. Aragon, D. Johnson, L. MeGeoeh, C. Seheyon, Optimization by simulated annealing: An experimen tal evaluation.
• BHAS85: J. Bhasker and S. Sahni, Optimal linear arrangement of circuit components, University of Minnesota, Technical Report, 1985.
• COHO83a: J. Cohoon and S. Sahni, Heuristics for the board permutation problem, Proceedings 1988 IC CAD Conference, Sept 1983.
• COHO83b: James Cohoon , Sartaj Sahni, Heuristics for the Circuit Realization Problem, Proceedings of the 20th conference on Design automation, p.560-566, June 27-29, 1983, Miami Beach, Florida, United States
• GEMA83: D. Geman and S. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.
• GOLD84: B. Golden and C. Skiscim, Using simulated annealing to solve routing and location problems, University of Maryland, College of Business Administration, Technical Report, Jan. 1984.
• GOTO77: S. Goto, I. Cederbaum, and B.S. Ting, uboptimal Solution of the Backboard Ordering with Channel Capacity Constraint", IEEE Trans. Circuits and Systems, Nov. 1977, pp. 645- 652.
• GREE84: J. Greene and K. Supowit, Simulated annealing without rejected moves, Proceedings ICCD, Oct. 1984, pp 658-663.
• HORO78: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• JEPS83: D. Jepsen and C. Gelatt Jr., Macro placement by Monte Carlo annealing, Proceedings 1988 IC CAD Conference, Sept 1983, pp. 495-498.
• KANG83: Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
• KERN70: B. Kernighan and S. Lin, An efficient heuristic procedure for the partitioning of graphs, Bell Systems Tech. Jr., Feb. 1970.
• KIRK83: S. Kirkpatrick, C. Gelatt, Jr., and M. Vecchi, Optimization by simulated annealing, Science, Vol 220, No 4598, May 1983, pp. 671-680.
• LIN73: S. Lin and B. Kernighan, An effective heuristic for the traveling salesman problem, Operations Research, Vol 21, pp. 498-516, 1973.
• LUND83: M. Lundy and A. Mees, Convergence of the annealing algorithm, University of Cambridge, 1083.
• METR53: N. Metropolis, A. Rosenbluth, A. Teller, and E. Teller, Equation of state calculations by fast computing machines, Jr. Chem. Phys., Vol 21, p. 1087, 1953.
• MITR85: D. Mitra, and F. Romeo, and A. Sangiovanni- Vincentelli, Convergence and finite-time behavior of simulated annealing, Technical Report UCB/ERL M85/23, University of California, Berkeley, March 1985.
• NAHA85: Surendra Nahar , Sartaj Sahni , Eugene Shragowitz, Experiments with simulated annealing, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.748-752, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317977]
• NAHA85a: S. Nahar ,S. Sahni and E. Shragowitz, Simulated Annealing and Combinatorial Optimization, University of Minnesota, Minneapolis, Technical report ~ 85-56, 1985.
• RAGH84: R. Raghavan and S. Sahni, The complexity of single row routing, IEEE Trans. On Circuits and Systems, Vol CAS-31, No 5, May 1984, pp. 462-471.
• ROME84a: F. Romeo, A. Vincentelli, and C. Sechen, Research on simulated annealing at Berkeley, Proceedings ICCD, Oct. 1984, pp 652-657.
• ROME84b: F. Romeo and A. Vincentelli, Probabilistic hill climbing algorithms: Properties and applications, University of California, Berkeley, UCB/ERL MS4/34, lgS4.
• SAHN80: Sartaj Sahni , Atul Bhatt, The complexity of design automation problems, Proceedings of the 17th conference on Design automation, p.402-411, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804562]
• SAHN85: Sartaj Sahni, Software Development in Pascal, Camelot Publishing Co., Ormond Beach, FL, 1985
• SECH84: C. Sechen and A. Sangiovanni-Vincentelli, The Timberwolf placement and routing package, 1984.
• STEW77: W. Stewart, A computationally efficient heuristic for the travelling salesman problem, Proceedings of the 18th Annual Meeting of Southeastern TIMS, Myrtle Beach, S.C., pp 75-83, 1977.
• TING78: B. Ting and E. Kuh, An approach to the routing of multilayer printed circuit boards, Proc. IEEE Symp. On Circuits and Systems, pp. 902-911, 1978.
• WHIT84: S. White, Concepts of scale in simulated annealing, Proceedings ICCD, Oc~ 198,t, pp 646-651.
• VECC83: M. Vecchi and S. Kirkpatrick, Global wiring by simulated annealing, IEEE Trans. On computer Aided Design, Vol CAD-2, No 4, Oct. 1983, pp 215-222.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
Monte Carlo methods, adaptive heuristics, design automation, optimization, perturbation functions, simulated annealing