Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning

DOI10.1287/OPRE.37.6.865zbMath0698.90065OpenAlexW2128193809MaRDI QIDQ3476605

Catherine A. Schevon, Cecilia R. Aragon, L. A. McGeoch, David S. Johnson

Publication date: 1989

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.37.6.865

zbMATH Keywords

heuristicssimulated annealinggraph partitioningexperimental results

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

Parallel physical optimization algorithms for allocating data to multicomputer nodes ⋮ Heuristics for laying out information graphs ⋮ Simulated annealing procedures for forming machine cells in group technology ⋮ Multiple-type, two-dimensional bin packing problems: Applications and algorithms ⋮ Vertex packing problem application to the design of electronic testing fixtures ⋮ Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search ⋮ A computational study of graph partitioning ⋮ A unified framework of multi-objective cost functions for partitioning unstructured finite element meshes ⋮ Optimization by ghost image processes in neural networks ⋮ Simulated annealing and tabu search: Lessons from a line search ⋮ New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation ⋮ A new adaptive multi-start technique for combinatorial global optimizations ⋮ A step counting hill climbing algorithm applied to university examination timetabling ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ Contraint-based combinators for local search ⋮ Meta-heuristics for placing strategic safety stock in multi-echelon inventory with differentiated service times ⋮ Simulated annealing with noisy or imprecise energy measurements ⋮ A molecular structure matching problem ⋮ Simulated annealing for the machine reassignment problem ⋮ A multi-period shelter location-allocation model with evacuation orders for flood disasters ⋮ Partitioning of sequentially ordered systems using linear programming ⋮ Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem ⋮ Moving clusters within a memetic algorithm for graph partitioning ⋮ Efficient heuristic algorithm for scheduling two-stage hybrid flowshop with sequence-dependent setup times ⋮ Performance of a genetic algorithm for the graph partitioning problem ⋮ An extended mind evolutionary computation model for optimizations ⋮ An experimental evaluation of local search heuristics for graph partitioning ⋮ The Metropolis algorithm for graph bisection ⋮ Autocorrelation coefficient for the graph bipartitioning problem ⋮ A comparative study of both standard and adaptive versions of threshold accepting and simulated annealing algorithms in three scheduling problems ⋮ Job-shop scheduling: Computational study of local search and large-step optimization methods ⋮ Stochastic annealing for synthesis under uncertainty ⋮ Simulated annealing for manufacturing systems layout design ⋮ A new extension of local search applied to the Dial-A-Ride problem ⋮ A systematic procedure for setting parameters in simulated annealing algorithms ⋮ Improvement heuristics for the vehicle routing problem based on simulated annealing ⋮ An effective multilevel tabu search approach for balanced graph partitioning ⋮ Quotient geometric crossovers and redundant encodings ⋮ Simulated annealing for complex portfolio selection problems. ⋮ The late acceptance hill-climbing heuristic ⋮ A composite heuristic for the single machine early/tardy job scheduling problem. ⋮ Local search and lower bounds for the patient admission scheduling problem ⋮ Solving the continuous flow-shop scheduling problem by metaheuristics. ⋮ Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand ⋮ A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem ⋮ Introduction to computation and learning in artificial neural networks ⋮ Heuristic methods for gang-rip saw arbor design. ⋮ Design method using hybrid of line-type and circular-type routes for transit network system optimization ⋮ Determination of initial temperature in fast simulated annealing ⋮ Graph clustering ⋮ Revisiting simulated annealing: a component-based analysis ⋮ A simulated annealing channel routing algorithm ⋮ A note on the effect of neighborhood structure in simulated annealing ⋮ Nested annealing: A provable improvement to simulated annealing ⋮ Experimental analysis of simulated annealing based algorithms for the layout problem ⋮ Optimal design of LAN-WAN internetworks: An approach using simulated annealing ⋮ Large-step Markov chains for the TSP incorporating local search heuristics ⋮ The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks ⋮ Experiments with, and on, algorithms for maximum likelihood clustering ⋮ Simulated annealing applied to the process allocation problem ⋮ Good solutions to discrete noxious location problems via metaheuristics ⋮ Avoiding local optima in the \(p\)-hub location problem using tabu search and GRASP ⋮ Comparison of the performance of modern heuristics for combinatorial optimization on real data ⋮ On the heuristic solution of the permutation flow shop problem by path algorithms ⋮ Hybrid flowshop scheduling with machine and resource-dependent processing times ⋮ Extended neighborhood: Definition and characterization ⋮ Negotiation-based collaborative planning between supply chains partners ⋮ Optimization and analysis of the profitability of tariff structures with two-part tariffs ⋮ Experimental evaluation of simulated annealing algorithms for the time-cost trade-off problem ⋮ Automatic radio planning of GSM cellular networks ⋮ Long-term staffing based on qualification profiles ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ Combinatorial optimization by stochastic automata ⋮ Models and algorithms for solving combined vehicle and crew scheduling problems with rest constraints: An application to road feeder service planning in air cargo transportation ⋮ Mechanisms for local search ⋮ An SA/TS mixture algorithm for the scheduling tardiness problem ⋮ A simulated annealing heuristic for the one-dimensional cutting stock problem ⋮ General local search methods ⋮ The life span method -- a new variant of local search ⋮ Path optimization for graph partitioning problems ⋮ Scheduling jobs on parallel machines with sequence-dependent setup times ⋮ An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling ⋮ Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process ⋮ Scheduling projects to maximize net present value -- the case of time-dependent, contingent cash flows ⋮ Nature's way of optimizing ⋮ Generating irregular partitionable data structures ⋮ The node capacitated graph partitioning problem: A computational study ⋮ Heuristics for unrelated machine scheduling with precedence constraints ⋮ An optimal tree search method for the manufacturing systems cell formation problem ⋮ Simulated annealing for resource-constrained scheduling ⋮ Method to solve the travelling salesman problem using the inverse of diffusion process ⋮ Efficient simulated annealing on fractal energy landscapes ⋮ Routeing winter gritting vehicles ⋮ Simulated annealing and the mapping problem: A computational study ⋮ Best-so-far vs. where-you-are: Implications for optimal finite-time annealing ⋮ The noising method: A new method for combinatorial optimization ⋮ Solution of large weighted equicut problems ⋮ Simulated annealing: Practice versus theory ⋮ Control abstractions for local search ⋮ ``Miniaturized linearizations for quadratic 0/1 problems

This page was built for publication: Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning