Abstract
The Combinatorial Optimization Problems have today many complex real-life instances; even using extensive computing resources, their large dimensions and difficult constraints make the exact solving methods to be inappropriate. This is why heuristic methods are used in order to quickly obtain very good solutions. Here we propose a hybrid heuristic method for the Matrix Bandwidth Minimization Problem, based on an Ant Colony Optimization method and several local-search mechanisms. This well-known NP-complete problem refers to finding a permutation of the rows and columns of a sparse symmetric matrix in order to minimize its bandwidth for the nonzero entries. The Matrix Bandwidth Minimization Problem has broad applications in science, logistics or engineering.