A thermodynamically motivated simulation procedure for combinatorial optimization problems

DOI10.1016/0377-2217(84)90231-5zbMath0541.90070OpenAlexW2093475907MaRDI QIDQ794925

Franz Rendl, Rainer E. Burkard

Publication date: 1984

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(84)90231-5

zbMATH Keywords

heuristicssimulationcombinatorial optimizationquadratic assignmentexchange algorithmsComputational tests

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (72)

Randomized algorithms in combinatorial optimization: A survey ⋮ A parallel tabu search algorithm for large traveling salesman problems ⋮ The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach ⋮ An extreme point algorithm for a local minimum solution to the quadratic assignment problem ⋮ Experimentation in optimization ⋮ On the use of some known methods for \(T\)-colorings of graphs ⋮ Large-scale layout of facilities using a heuristic hybrid algorithm ⋮ Lower bounds for the quadratic assignment problem ⋮ A new exact algorithm for the solution of quadratic assignment problems ⋮ A simulated annealing approach to the multiconstraint zero-one knapsack problem ⋮ On the convergence of stationary distributions in simulated annealing algorithms ⋮ Boolean query optimization and the 0-1 hyperbolic sum problem ⋮ The quadratic three-dimensional assignment problem: exact and approximate solution methods ⋮ A survey for the quadratic assignment problem ⋮ Variable neighborhood search for the workload balancing problem in service enterprises ⋮ A modification of threshold accepting and its application to the quadratic assignment problem ⋮ Schedule synchronization for public transit networks ⋮ Quadratic assignment problems ⋮ Fast simulated annealing for single-row equidistant facility layout ⋮ Location and layout planning. A survey ⋮ Tabu search techniques. A tutorial and an application to neural networks ⋮ Effects of scatter plot initial solutions on regular grid facility layout algorithms in typical production models ⋮ Probabilistic and deterministic local search for solving the binary multiknapsack problem ⋮ Minimizing makespan for flow shop scheduling by combining simulated annealing with sequencing knowledge ⋮ Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem ⋮ Lower bounds for the bandwidth problem ⋮ Heuristics for biquadratic assignment problems and their computational comparison ⋮ A minimax assignment problem in treelike communication networks ⋮ Two-level modified simulated annealing based approach for solving facility layout problem ⋮ An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems ⋮ Four-bar Mechanism Synthesis for n Desired Path Points Using Simulated Annealing ⋮ A branch-and-bound algorithm for the single-row equidistant facility layout problem ⋮ Global optimality conditions and optimization methods for quadratic assignment problems ⋮ Methods for the one-dimensional space allocation problem ⋮ Probabilistic bounds and algorithms for the maximum satisfiability problem ⋮ Revisiting simulated annealing: a component-based analysis ⋮ Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem ⋮ Problema de asignacion cuadratica multiobjetivo ⋮ Experimental analysis of simulated annealing based algorithms for the layout problem ⋮ Simulated annealing for machine layout problems in the presence of zoning constraints ⋮ Mapping the convergence of genetic algorithms ⋮ An experimental comparison of seriation methods for one-mode two-way data ⋮ Simulated annealing applied to the process allocation problem ⋮ Simulated annealing: An introduction ⋮ Generating quadratic assignment test problems with known optimal permutations ⋮ Embedding signed graphs in the line ⋮ Cell formation in manufacturing systems through simulated annealing: An experimental evaluation ⋮ Discrete optimization: an Austrian view ⋮ Dual ascent: variations of a theme ⋮ Selected topics on assignment problems ⋮ Optimization of cube-per-order index warehouse layouts with zoning constraints ⋮ A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem ⋮ A mathematical model for zoning of protected natural areas ⋮ A parallel heuristic for quadratic assignment problems ⋮ Some experiments with simulated annealing for coloring graphs ⋮ An ejection chain algorithm for the quadratic assignment problem ⋮ A contribution to quadratic assignment problems ⋮ Unnamed Item ⋮ A convex form of the quadratic assignment problem ⋮ Mechanisms for local search ⋮ An improved annealing scheme for the QAP ⋮ Optimizing simulated annealing schedules with genetic programming ⋮ Algorithms for the maximum satisfiability problem ⋮ The single-finger keyboard layout problem ⋮ Heuristic methods and applications: A categorized survey ⋮ Forward Backward Transformation ⋮ An asymptotical study of combinatorial optimization problems by means of statistical mechanics ⋮ A new simulated annealing algorithm for the facility layout problem ⋮ An improved tabu search heuristic for solving facility layout design problems ⋮ A heuristic for cyclic stochastic sequencing of tasks on a drum-like storage system ⋮ Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation ⋮ Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods

Cites Work

• Optimization by Simulated Annealing
• Quadratic assignment problems
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• A heuristic for quadratic Boolean programs with applications to quadratic assignment problems
• Lexicographical problems of linear programming
• The Backboard Wiring Problem: A Placement Algorithm
• Equation of State Calculations by Fast Computing Machines

This page was built for publication: A thermodynamically motivated simulation procedure for combinatorial optimization problems