Surendra Nahar
Sartaj Sahni
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.
- ARAG85.C. Aragon, D. Johnson, L. MeGeoeh, C. Seheyon, Optimization by simulated annealing: An experimen tal evaluation.Google Scholar
- BHAS85.J. Bhasker and S. Sahni, Optimal linear arrangement of circuit components, University of Minnesota, Technical Report, 1985.Google Scholar
- COHO83a.J. Cohoon and S. Sahni, Heuristics for the board permutation problem, Proceedings 1988 IC CAD Conference, Sept 1983.Google Scholar
- COHO83b.J. Cohoon and S. Sahni, Heuristics for the circuit realization problem, Proceedings 20th Design Automation Conference, June 1983. Google ScholarDigital Library
- GEMA83.D. Geman and S. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- GREE84.J. Greene and K. Supowit, Simulated annealing without rejected moves, Proceedings ICCD, Oct. 1984, pp 658-663.Google Scholar
- HORO78.E. Horowitz and S. Sahni, Fundamentals of computer algorithms, Computer Science Press, 1978. Google ScholarDigital Library
- JEPS83.D. Jepsen and C. Gelatt Jr., Macro placement by Monte Carlo annealing, Proceedings 1988 IC CAD Conference, Sept 1983, pp. 495-498.Google Scholar
- KANG83.S. Kang, Linear ordering and application to placement, Proceedings 20th Design Automation Conference, 1983, pp ,t57-464. Google ScholarDigital Library
- KERN70.B. Kernighan and S. Lin, An efficient heuristic procedure for the partitioning of graphs, Bell Systems Tech. Jr., Feb. 1970.Google ScholarCross Ref
- KIRK83.S. Kirkpatrick, C. Gelatt, Jr., and M. Vecchi, Optimization by simulated annealing, Science, Vol 220, No 4598, May 1983, pp. 671-680.Google ScholarCross Ref
- LIN73.S. Lin and B. Kernighan, An effective heuristic for the traveling salesman problem, Operations Research, Vol 21, pp. 498-516, 1973.Google ScholarDigital Library
- LUND83.M. Lundy and A. Mees, Convergence of the annealing algorithm, University of Cambridge, 1083.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- NAHA85.S. Nahar, S. Sahni, and E. Shragowitz, Experiments with simulated annealing, 2~nd Design Automation Conference, 1985, pp. 748-752. Google ScholarDigital Library
- NAHA85a.S. Nahar ,S. Sahni and E. Shragowitz, Simulated Annealing and Combinatorial Optimization, University of Minnesota, Minneapolis, Technical report ~ 85-56, 1985.Google Scholar
- 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.Google Scholar
- ROME84a.F. Romeo, A. Vincentelli, and C. Sechen, Research on simulated annealing at Berkeley, Proceedings ICCD, Oct. 1984, pp 652-657.Google Scholar
- ROME84b.F. Romeo and A. Vincentelli, Probabilistic hill climbing algorithms: Properties and applications, University of California, Berkeley, UCB/ERL MS4/34, lgS4.Google Scholar
- SAHN80.S. Sahni and A. Bhatt, Complexity of design automation problems, Proceedings 17th Design Automation Conference, 1980, pp. 402-411. Google ScholarDigital Library
- SAHN85.S. Sahni, Software development in Pascal, Camelot Publishing Co., Fridley, Minnesota, 1985. Google ScholarDigital Library
- SECH84.C. Sechen and A. Sangiovanni-Vincentelli, The Timberwolf placement and routing package, 1984.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- WHIT84.S. White, Concepts of scale in simulated annealing, Proceedings ICCD, Oc~ 198,t, pp 646-651.Google Scholar
- 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.Google Scholar
Index Terms
- Simulated annealing and combinatorial optimization
Recommendations
A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem
The quadratic assignment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP - M-SA-QAP. The novelty of the ...
Benchmarking Tabu Search and Simulated Annealing for the Capacitated Vehicle Routing Problem
ICCMB '21: Proceedings of the 2021 4th International Conference on Computers in Management and BusinessThis paper addresses the Capacitated Vehicle Routing Problem (CVRP) consisting of a single depot and several customers that are supplied with goods by capacitated vehicles from a depot. The main objective of the vehicle routing problem is to minimize ...
Solving the truck and trailer routing problem based on a simulated annealing heuristic
In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (...
Comments