Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning

Source

Operations Research archive
Volume 37 , Issue 6 (Nov–Dec. 1989) table of contents

Pages: 865 - 892

Year of Publication: 1989

ISSN:0030-364X

Authors

David S. Johnson	AT&T Bell Labs., Murray Hill, NJ
Cecilia R. Aragon	Univ. of California, Berkeley
Lyle A. McGeoch	Amherst College, MA
Catherine Schevon	Johns Hopkins Univ., Baltimore, MD

Publisher

INFORMS Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 93

Additional Information:

cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1287/opre.37.6.865

CITED BY 93

	Saul B. Gelfand , Peter C. Doerschuk , Mohamed Nahhas-Mohandes, Theory and application of annealing algorithms for continuous optimization, Proceedings of the 24th conference on Winter simulation, p.494-499, December 13-16, 1992, Arlington, Virginia, United States
	Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
	Marcos Ribeiro Pereira Barretto , Leonardo Chwif , Tillal Eldabi , Ray J. Paul, Simulation optimization with the linear move and exchange move optimization algorithm, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.806-811, December 05-08, 1999, Phoenix, Arizona, United States
	Ron Davidson , David Harel, Drawing graphs nicely using simulated annealing, ACM Transactions on Graphics (TOG), v.15 n.4, p.301-331, Oct. 1996
	Mark Fleischer, Simulated annealing: past, present, and future, Proceedings of the 27th conference on Winter simulation, p.155-161, December 03-06, 1995, Arlington, Virginia, United States
	Thang Nguyen Bui , Byung Ro Moon, A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs, Proceedings of the 31st annual conference on Design automation, p.664-669, June 06-10, 1994, San Diego, California, United States
	Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, United States
	Brian White , Jay Lepreau , Shashi Guruprasad, Lowering the barrier to wireless and mobile experimentation, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.47-52, January 2003
	Chingwei Yeh , Yin-Shuin Kang, Cell-based layout techniques supporting gate-level voltage scaling for low power, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.983-986, 12/1/2001
	Chao-Wei Ou , Manoj Gunwani , Sanjay Ranka, Architecture-independent locality-improving transformations of computational graphs embedded in k-dimensions, Proceedings of the 9th international conference on Supercomputing, p.289-298, July 03-07, 1995, Barcelona, Spain
	Dimitris Papadias , Marios Mantzourogiannis , Panos Kalnis , Nikos Mamoulis , Ishfaq Ahmad, Content-based retrieval using heuristic search, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.168-175, August 15-19, 1999, Berkeley, California, United States
	A. d'Anjou , M. Graña , F. J. Torrealdea , M. C. Hernandez, Solving Satisfiability Via Boltzmann Machines, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.5, p.514-521, May 1993
	Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
	Yoshinori Hara , Arthur M. Keller , Gio Wiederhold, Implementing hypertext database relationships through aggregations and exception, Proceedings of the third annual ACM conference on Hypertext, p.75-90, December 15-18, 1991, San Antonio, Texas, United States
	Jonathan Berry , Mark Goldberg, Path optimization and near-greedy analysis for graph partitioning: an empirical study, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 22-24, 1995, San Francisco, California, United States
	Azzedine Boukerche , Carl Tropper, A static partitioning and mapping algorithm for conservative parallel simulations, ACM SIGSIM Simulation Digest, v.24 n.1, p.164-172, July 1994
	H. X. Lin , H. J. Sips, Parallel direct solution of large sparse systems in finite element computations, Proceedings of the 7th international conference on Supercomputing, p.261-270, July 19-23, 1993, Tokyo, Japan
	Eric Angela , Vassilis Zissimopoulosb, On the landscape ruggedness of the quadratic assignment problem, Theoretical Computer Science, v.263 n.1-2, p.159-172, July 28 2001
	Stefan Boettcher, Evolutionary local-search with extremal optimization, Neural, Parallel & Scientific Computations, v.10 n.2, p.249-258, June 2002
	Martin Feldmann , Dirk Biskup, Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches, Computers and Industrial Engineering, v.44 n.2, p.307-323, February 2003
	Stefan Boettcher , Allon G. Percus, Optimization with extremal dynamics, Complexity, v.8 n.2, p.57-62, November 2002
	Thelma D. Mavridou , Panos M. Pardalos, Simulated Annealing and Genetic Algorithms for the Facility LayoutProblem: A Survey, Computational Optimization and Applications, v.7 n.1, p.111-126, Jan. 1997
	Ted Carson , Russell Impagliazzo, Hill-climbing finds random planted bisections, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.903-909, January 07-09, 2001, Washington, D.C., United States
	Jon Christensen , Joe Marks , Stuart Shieber, An empirical study of algorithms for point-feature label placement, ACM Transactions on Graphics (TOG), v.14 n.3, p.203-232, July 1995
	Jordi Petit, Experiments on the minimum linear arrangement problem, Journal of Experimental Algorithmics (JEA), 8, 2003
	Stefan Boettcher, Extremal optimization: heuristics via coevolutionary avalanches, Computing in Science and Engineering, v.2 n.6, p.75-82, Nov. 2000
	J. Haralambides , F. Makedon, Iterative compaction: an improved approach to graph and circuit bisection, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	C. Gil , J. Ortega , M. G. Montoya , R. Baños, A Mixed Heuristic for Circuit Partitioning, Computational Optimization and Applications, v.23 n.3, p.321-340, December 2002
	B. John Oommen , Edward V. de St. Croix, Graph Partitioning Using Learning Automata, IEEE Transactions on Computers, v.45 n.2, p.195-208, February 1996
	Peter Merz, Advanced fitness landscape analysis and the performance of memetic algorithms, Evolutionary Computation, v.12 n.3, p.303-325, September 2004
	Scott L. Rosen , Catherine M. Harmonosky, An improved simulated annealing simulation optimization method for discrete parameter stochastic systems, Computers and Operations Research, v.32 n.2, p.343-358, February 2005
	Roberto Battiti , Alan Albert Bertossi, Greedy, Prohibition, and Reactive Heuristics for Graph Partitioning, IEEE Transactions on Computers, v.48 n.4, p.361-385, April 1999
	Xianyang Jiang , Xubang Shen , Tianxu Zhang , Huayu Liu, An improved circuit-partitioning algorithm based on min-cut equivalence relation, Integration, the VLSI Journal, v.36 n.1-2, p.55-68, September 2003
	Youssef G. Saab, A Fast and Robust Network Bisection Algorithm, IEEE Transactions on Computers, v.44 n.7, p.903-913, July 1995
	Yong-Hyuk Kim , Byung-Ro Moon, New topologies for genetic search space, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Walid Ben-Ameur, Computing the Initial Temperature of Simulated Annealing, Computational Optimization and Applications, v.29 n.3, p.369-385, December 2004
	Andrea Schaerf, Local Search Techniques for Constrained Portfolio SelectionProblems, Computational Economics, v.20 n.3, p.177-190, December 2002
	Thang Nguyen Bui , Byung Ro Moon, Genetic Algorithm and Graph Partitioning, IEEE Transactions on Computers, v.45 n.7, p.841-855, July 1996
	John R. Feehrer , Lars H. Ramfelt, Packet Synchronization for Synchronous Optical Deflection-Routed Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.6, p.605-611, June 1996
	Vipul Gupta , Eugen Schenfeld, Annealed Embeddings of Communication Patterns in an Interconnection Cached Network, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1153-1167, November 1995
	Chih-Ping Chiang , Shine-Der Lee, Joint determination of machine cells and linear intercell layout, Computers and Operations Research, v.31 n.10, p.1603-1619, September 2004
	Hyung-Soo Cho , Chun-Hyun Paik , Hang-Mook Yoon , Ho-Gyun Kim, A robust design of simulated annealing approach for mixed-model sequencing, Computers and Industrial Engineering, v.48 n.4, p.753-764, June 2005
	Youssef G. Saab, An Effective Multilevel Algorithm for Bisecting Graphs and Hypergraphs, IEEE Transactions on Computers, v.53 n.6, p.641-652, June 2004
	Timo Poranen, A simulated annealing algorithm for determining the thickness of a graph, Information Sciences—Informatics and Computer Science: An International Journal, v.172 n.1-2, p.155-172, 9 June 2005
	Mahmoud H. Alrefaei , Ameen J. Alawneh, Solution quality of random search methods for discrete stochastic optimization, Mathematics and Computers in Simulation, v.68 n.2, p.115-125, April 2005
	Marcus Randall , David Abramson, A General Meta-Heuristic Based Solver for Combinatorial Optimisation Problems, Computational Optimization and Applications, v.20 n.2, p.185-210, November 2001
	Yong-Hyuk Kim , Yourim Yoon , Alberto Moraglio , Byung-Ro Moon, Geometric crossover for multiway graph partitioning, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
	Lin-Yu Tseng , Shyi-Ching Liang, A Hybrid Metaheuristic for the Quadratic Assignment Problem, Computational Optimization and Applications, v.34 n.1, p.85-113, May 2006
	Nestor F. Michelena , Panos Y. Papalambros, A Hypergraph Framework for Optimal Model-Based Decomposition ofDesign Problems, Computational Optimization and Applications, v.8 n.2, p.173-196, Sept 1997
	Shihyu Chou , Min-Chiang Wang, Simulated annealing procedure for on-line control with process dynamics, International Journal of Systems Science, v.38 n.8, p.677-688, August 2007
	Alberto Moraglio , Yong-Hyuk Kim , Yourim Yoon , Byung-Ro Moon, Geometric crossovers for multiway graph partitioning, Evolutionary Computation, v.15 n.4, p.445-474, Winter 2007
	Inwook Hwang , Yong-Hyuk Kim , Byung-Ro Moon, Multi-attractor gene reordering for graph bisection, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
	Jacob G. Martin, Spectral techniques for graph bisection in genetic algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
	Zvia Agur , Refael Hassin , Sigal Levy, Optimizing Chemotherapy Scheduling Using Local Search Heuristics, Operations Research, v.54 n.5, p.829-846, September 2006
	Peter Merz , Bernd Freisleben, Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning, Evolutionary Computation, v.8 n.1, p.61-91, March 2000
	Genetha Anne Gray , Tamara G. Kolda , Ken Sale , Malin M. Young, Optimizing an Empirical Scoring Function for Transmembrane Protein Structure Determination, INFORMS Journal on Computing, v.16 n.4, p.406-418, Fall 2004
	Jeffrey W. Ohlmann , Barrett W. Thomas, A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows, INFORMS Journal on Computing, v.19 n.1, p.80-90, January 2007
	Sunwoo Park , C. Anthony Hunt , Bernard P. Zeigler, Cost-based Partitioning for Distributed and Parallel Simulation of Decomposable Multiscale Constructive Models, Simulation, v.82 n.12, p.809-826, January 2006
	Pascal Hentenryck , Laurent Michel , Liyuan Liu, Contraint-Based Combinators for Local Search, Constraints, v.10 n.4, p.363-384, October 2005
	Petri Myllymäki, Massively Parallel Probabilistic Reasoning with Boltzmann Machines, Applied Intelligence, v.11 n.1, p.31-44, July-August 1999
	Panagiotis K. Linos , Michael Breen, Improving bipartite graphs using multi-strategy simulated annealing, Proceedings of the 37th annual Southeast regional conference (CD-ROM), p.35-es, April 1999
	Ariel Felner, Finding optimal solutions to the graph partitioning problem with heuristic search, Annals of Mathematics and Artificial Intelligence, v.45 n.3-4, p.293-322, December 2005
	Zhiru Zhang , Yiping Fan , Miodrag Potkonjak , Jason Cong, Gradual Relaxation Techniques with Applications to Behavioral Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.529, November 09-13, 2003
	Timo Poranen, Heuristics for the Maximum Outerplanar Subgraph Problem, Journal of Heuristics, v.11 n.1, p.59-88, January 2005
	Pascal Hentenryck , Laurent Michel, Control Abstractions for Local Search, Constraints, v.10 n.2, p.137-157, April 2005
	Youssef Saab, Combinatorial Optimization by Dynamic Contraction, Journal of Heuristics, v.3 n.3, p.207-224, November 1997
	Woan Sun Chang , Robert Simon, End-Host Multicasting in Support of Distributed Real-Time Simulation Systems, Proceedings of the 37th annual symposium on Simulation, p.7, April 18-22, 2004
	Yong-Hyuk Kim , Byung-Ro Moon, Investigation of the Fitness Landscapes in Graph Bipartitioning: An Empirical Study, Journal of Heuristics, v.10 n.2, p.111-133, March 2004
	Thomas Emden-Weinert , Mark Proksch, Best Practice Simulated Annealing for the Airline Crew Scheduling Problem, Journal of Heuristics, v.5 n.4, p.419-436, December 1999
	F. Janabi-Sharifi , W. J. Wilson, A Fast Approach for Robot Motion Planning, Journal of Intelligent and Robotic Systems, v.25 n.3, p.187-212, July 1999
	Jacques A. Ferland , Ilham Berrada , Imene Nabli , B. Ahiod , Philippe Michelon , Viviane Gascon , Éric Gagné, Generalized Assignment Type Goal Programming Problem: Application to Nurse Scheduling, Journal of Heuristics, v.7 n.4, p.391-413, July 2001
	Yong-Hyuk Kim , Byung-Ro Moon, Lock-Gain Based Graph Partitioning, Journal of Heuristics, v.10 n.1, p.37-57, January 2004
	P. A. Borisovskii , A. V. Eremeev, Comparison of Certain Evolutionary Algorithms, Automation and Remote Control, v.65 n.3, p.357-362, March 2004
	Eric Angel , Vassilis Zissimopoulos, On the Hardness of the Quadratic Assignment Problem with Metaheuristics, Journal of Heuristics, v.8 n.4, p.399-414, July 2002
	Josep Díaz , Mathew D. Penrose , Jordi Petit , María Serna, Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs, Combinatorics, Probability and Computing, v.9 n.6, p.489-511, November 2000
	Dirk Thierens, A bivariate probabilistic model-building genetic algorithm for graph bipartitioning, Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Pierre Chardaire , Musbah Barake , Geoff P. McKeown, A PROBE-Based Heuristic for Graph Partitioning, IEEE Transactions on Computers, v.56 n.12, p.1707-1720, December 2007
	Todd W. Kolb , Lixin Tao , Michael W. Tao, Efficient solutions to a class of generalized time-dependent combinatorial optimization problems, Proceedings of the 7th WSEAS International Conference on Applied Mathematics, p.1-5, May 11-14, 2005, Cancun, Mexico
	Yongluan Zhou , Beng Chin Ooi , Kian-Lee Tan, Disseminating streaming data in a dynamic environment: an adaptive and cost-based approach, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1465-1483, November 2008
	Seong-Woo Choi , Yeong-Dae Kim, Minimizing makespan on an m-machine re-entrant flowshop, Computers and Operations Research, v.35 n.5, p.1684-1696, May, 2008
	Reid Andersen , Kevin J. Lang, An algorithm for improving graph partitions, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.651-660, January 20-22, 2008, San Francisco, California
	Eduardo Rodriguez-Tello , Jin-Kao Hao , Jose Torres-Jimenez, An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem, Computers and Operations Research, v.35 n.10, p.3331-3346, October, 2008
	Ming-Jong Yao , Weng-Ming Chu , Yen-Fei Lin, Determination of replenishment dates for restricted-storage, static demand, cyclic replenishment schedule, Computers and Operations Research, v.35 n.10, p.3230-3242, October, 2008
	Themis Palpanas , Nick Koudas , Alberto Mendelzon, On space constrained set selection problems, Data & Knowledge Engineering, v.67 n.1, p.200-218, October, 2008
	Yan Wan , Sandip Roy , Ali Saberi , Bernard Lesieutre, A Flexible Stochastic Automaton-Based Algorithm for Network Self-Partitioning, International Journal of Distributed Sensor Networks, v.4 n.3, p.223-246, July 2008
	Hui-Ling Hu , Yen-Liang Chen, Mining typical patterns from databases, Information Sciences: an International Journal, v.178 n.19, p.3683-3696, October, 2008
	Haixia Jia , Cristopher Moore , Doug Strain, Generating hard satisfiable formulas by hiding solutions deceptiveily, Proceedings of the 20th national conference on Artificial intelligence, p.384-389, July 09-13, 2005, Pittsburgh, Pennsylvania
	Outi Räihä , Erkki Mäkinen , Timo Poranen, Using simulated annealing for producing software architectures, Proceedings of the 11th annual conference companion on Genetic and evolutionary computation conference, July 08-12, 2009, Montreal, Québec, Canada
	Dimitris Achlioptas , Haixia Jia , Cristopher Moore, Hiding satisfying assignments: two are better than one, Proceedings of the 19th national conference on Artifical intelligence, p.131-136, July 25-29, 2004, San Jose, California
	Dimitris Achlioptas , Haixia Jia , Cristopher Moore, Hiding satisfying assignments: two are better than one, Journal of Artificial Intelligence Research, v.24 n.1, p.623-639, July 2005
	Haixia Jia , Cristopher Moore , Doug Strain, Generating hard satisfiable formulas by hiding solutions deceptively, Journal of Artificial Intelligence Research, v.28 n.1, p.107-118, January 2007
	Henry Aigbedo, On bills of materials structure and optimum product-level smoothing of parts usage in JIT assembly systems, International Journal of Systems Science, v.40 n.8, p.787-798, August 2009
	Hyung-Soo Cho , Chun-Hyun Paik , Hang-Mook Yoon , Ho-Gyun Kim, A robust design of simulated annealing approach for mixed-model sequencing, Computers and Industrial Engineering, v.48 n.4, p.753-764, June 2005