Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
From MaRDI portal
Publication:3978838
DOI10.1287/opre.39.3.378zbMath0739.90055OpenAlexW2153638045MaRDI QIDQ3978838
L. A. McGeoch, Cecilia R. Aragon, Catherine A. Schevon, David S. Johnson
Publication date: 25 June 1992
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.39.3.378
graph coloringSimulated annealinglocal optimizationoptimal planningnumber partitioningextremal permutation problems
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items (only showing first 100 items - show all)
Routing and wavelength assignment by partition colouring ⋮ Local optima topology for the \(k\)-coloring problem ⋮ GOAL solver: a hybrid local search based solver for high school timetabling ⋮ Integrating and accelerating tabu search, simulated annealing, and genetic algorithms ⋮ The hardest constraint problems: A double phase transition ⋮ Multiple-type, two-dimensional bin packing problems: Applications and algorithms ⋮ Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search ⋮ Problems of discrete optimization: challenges and main approaches to solve them ⋮ Simulated annealing and tabu search: Lessons from a line search ⋮ Applying tabu search with influential diversification to multiprocessor scheduling ⋮ Exploiting the deep structure of constraint problems ⋮ A comparison of \(p\)-dispersion heuristics ⋮ Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm ⋮ A step counting hill climbing algorithm applied to university examination timetabling ⋮ Reinforcement learning based tabu search for the minimum load coloring problem ⋮ Meta-heuristics for placing strategic safety stock in multi-echelon inventory with differentiated service times ⋮ Towards objective measures of algorithm performance across instance space ⋮ Two metaheuristic approaches for solving multidimensional two-way number partitioning problem ⋮ GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem ⋮ A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks ⋮ The multiple team formation problem using sociometry ⋮ Constructing efficient simulated annealing algorithms ⋮ Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue ⋮ Efficient heuristics for robot acquisition planning for a CIM system ⋮ Simple decentralized graph coloring ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ A comparison of neighborhood search techniques for multi-objective combinatorial problems ⋮ Easily searched encodings for number partitioning ⋮ Simulated annealing metaheuristics for the vehicle routing problem with time windows ⋮ Focused simulated annealing search: An application to job shop scheduling ⋮ Genetic and hybrid algorithms for graph coloring ⋮ Problem space local search for number partitioning ⋮ Metaheuristics: A bibliography ⋮ Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs ⋮ An effective hybrid algorithm for university course timetabling ⋮ Autocorrelation coefficient for the graph bipartitioning problem ⋮ Unit disk graph recognition is NP-hard ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Job-shop scheduling: Computational study of local search and large-step optimization methods ⋮ Simulated annealing for manufacturing systems layout design ⋮ Improvement heuristics for the vehicle routing problem based on simulated annealing ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Integer linear programming model for multidimensional two-way number partitioning problem ⋮ An algebraic expression of the number partitioning problem ⋮ The late acceptance hill-climbing heuristic ⋮ A composite heuristic for the single machine early/tardy job scheduling problem. ⋮ A robust simulated annealing based examination timetabling system. ⋮ Local search and lower bounds for the patient admission scheduling problem ⋮ Heuristics for a project management problem with incompatibility and assignment costs ⋮ An exact approach for the vertex coloring problem ⋮ Quantum annealing of the graph coloring problem ⋮ A variable neighborhood search for graph coloring. ⋮ Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable ⋮ Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand ⋮ Determination of initial temperature in fast simulated annealing ⋮ On the classification of NP-complete problems in terms of their correlation coefficient ⋮ Revisiting simulated annealing: a component-based analysis ⋮ A cooperative search method for the \(k\)-coloring problem ⋮ Isomorphism testing via polynomial-time graph extensions ⋮ A graph coloring heuristic using partial solutions and a reactive tabu scheme ⋮ Compiling problem specifications into SAT ⋮ COSINE: A new graph coloring algorithm ⋮ CHECKCOL: improved local search for graph coloring ⋮ An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem ⋮ An ant-based algorithm for coloring graphs ⋮ Coloring graphs by iterated local search traversing feasible and infeasible solutions ⋮ Hybrid evolutionary algorithm for the b-chromatic number ⋮ Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems ⋮ A wide-ranging computational comparison of high-performance graph colouring algorithms ⋮ Coloring large graphs based on independent set extraction ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring ⋮ Optimization and analysis of the profitability of tariff structures with two-part tariffs ⋮ Improving the extraction and expansion method for large graph coloring ⋮ A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem ⋮ Long-term staffing based on qualification profiles ⋮ Guided local search and its application to the traveling salesman problem ⋮ Constraint satisfaction problems: Algorithms and applications ⋮ An incremental search heuristic for coloring vertices of a graph ⋮ An adaptive, multiple restarts neural network algorithm for graph coloring ⋮ General local search methods ⋮ A fuzzy clustering method of construction of ontology-based user profiles ⋮ The life span method -- a new variant of local search ⋮ Combinatorial optimization in system configuration design ⋮ Path optimization for graph partitioning problems ⋮ A complete anytime algorithm for number partitioning ⋮ An efficient memetic algorithm for the graph partitioning problem ⋮ Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process ⋮ Graph coloring by multiagent fusion search ⋮ Heuristics and exact methods for number partitioning ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ A search space ``cartography for guiding graph coloring heuristics ⋮ A memetic algorithm for graph coloring ⋮ A new tabu search procedure for an audit-scheduling problem ⋮ Determination of optimal path under approach and exit constraints ⋮ A Lagrangian reconstruction of GENET ⋮ An information-based neural approach to generic constraint satisfaction. ⋮ Compiling constraint satisfaction problems ⋮ Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation
This page was built for publication: Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
