Quick search
Go!

A HYBRID TECHNIQUE FOR A MATRIX BANDWIDTH PROBLEM


GLORIA CERASELA CRIƞAN 1, CAMELIA-M. PINTEA 2
1. Department of Mathematics and Informatics,Faculty of Sciences, “Vasile Alecsandri” University of Bacău,e-mail: ceraselacrisan@ub.ro
2. G. CoƟbuc N.College, Cluj-Napoca, e-mail: cmpintea@yahoo.com

Issue:

SSRSMI, Number 1, Volume XXI

Section:

Volume 21, Number 1

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.

Keywords:

Ant Colony Optimization (ACO), metaheuristics, algorithm performance.

Code [ID]:

SSRSMI201101V21S01A0009 [0003411]

Full paper:

Download pdf


Copyright (c) 1995-2007 University of Bacău