Heuristics for Matrix Bandwidth Reduction

Author

Andrew LIM, Hong Kong University of Science and Technology
Brian RODRIGUES, Singapore Management UniversityFollow
Fei XIAO, National University of Singapore

Publication Type

Journal Article

Publication Date

10-2006

Abstract

In this work, we provide two heuristic algorithms for the matrix bandwidth reduction problem. The first is a genetic algorithm and the second uses node label adjustments. Experiments show these heuristics improve solution quality when compared with the well-known GPS algorithm and recently-developed methods using tabu search and GRASP with Path Relinking. Further, the node adjustment approach obtains solutions at speeds comparable to the fast GPS algorithm.

Keywords

Matrix bandwidth, Genetic algorithm, Node adjustments, Hill climbing

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

174

Issue

1

First Page

69

Last Page

91

ISSN

0377-2217

Identifier

10.1016/j.ejor.2005.02.066

Publisher

Elsevier

Citation

LIM, Andrew; RODRIGUES, Brian; and XIAO, Fei. Heuristics for Matrix Bandwidth Reduction. (2006). European Journal of Operational Research. 174, (1), 69-91.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/562

Additional URL

https://doi.org/10.1016/j.ejor.2005.02.066