GRASP and path relinking for the matrix bandwidth minimization.

DOI10.1016/S0377-2217(02)00715-4zbMath1053.90057MaRDI QIDQ1417505

Isaac Plana, Vicente Campos, Estefanía Piñana, Rafael Martí

Publication date: 5 January 2004

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

zbMATH Keywords

Tabu searchMetaheuristicsMatrix bandwidthPath relinkingGreedy randomized adaptive search procedure

Mathematics Subject Classification ID

Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Variable neighbourhood search for bandwidth reduction, A multi-layer line search method to improve the initialization of optimization algorithms, Particle swarm optimization and hill climbing for the bandwidth minimization problem, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, Tabu search for the cyclic bandwidth problem, Heuristics for matrix bandwidth reduction, Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking, Reducing the bandwidth of a sparse matrix with a genetic algorithm, Population-based iterated greedy algorithm for the S-labeling problem, A branch and bound algorithm for the matrix bandwidth minimization, An improved simulated annealing algorithm for bandwidth minimization, A constructive bandwidth reduction algorithm -- a variant of GPS algorithm, A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs, Scatter search for the cutwidth minimization problem, Adaptive memory programming for matrix bandwidth minimization, Multistart search for the cyclic cutwidth minimization problem, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, An evaluation of low-cost heuristics for matrix bandwidth and profile reductions, Data-Mining-Driven Neighborhood Search, Level-based heuristics and hill climbing for the antibandwidth maximization problem, GRASP with path relinking heuristics for the antibandwidth problem, Scatter search --- wellsprings and challenges, Principles of scatter search, Addressing the envelope reduction of sparse matrices using a genetic programming system, A general variable neighborhood search for the cyclic antibandwidth problem

Uses Software

• Harwell-Boeing sparse matrix collection
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• The NP-completeness of the bandwidth minimization problem
• Finding exact solutions to the bandwidth minimization problem
• Greedy randomized adaptive search procedures
• On the Probable Performance of Heuristics for Bandwidth Minimization
• The bandwidth problem for graphs and matrices—a survey
• Algorithms for reducing the bandwidth and profile of a sparse matrix
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• A Comparison of Several Bandwidth and Profile Reduction Algorithms
• Complexity Results for Bandwidth Minimization
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
• Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices