Soft Computing approaches on the Bandwidth Problem
Preprint
Abstract
The Matrix Bandwidth Minimization Problem (MBMP) seeks for a simultaneous reordering of the rows and the columns of a square matrix such that the nonzero entries are collected within a band of small width close to the main diagonal. The MBMP is a NP-complete problem, with applications in many scientific domains, linear systems, artificial intelligence, and real-life situations in industry, logistics, information recovery. The complex problems are hard to solve, that is why any attempt to improve their solutions is beneficent. Genetic algorithms and ant-based systems are Soft Computing methods used in this paper in order to solve some MBMP instances. Our approach is based on a learning agent-based model involving a local search procedure. The algorithm is compared with the classical Cuthill-McKee algorithm, and with a hybrid genetic algorithm, using several instances from Matrix Market collection. Computational experiments confirm a good performance of the proposed algorithms for the considered set of MBMP instances. On Soft Computing basis, we also propose a new theoretical Reinforcement Learning model for solving the MBMP problem.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Even Faster Exact BandwidthACM Transactions on Algorithms, 2012
- Two models of two-dimensional bandwidth problemsInformation Processing Letters, 2010
- A Hybrid ACO Approach to the Matrix Bandwidth Minimization Problem2010
- An improved simulated annealing algorithm for bandwidth minimizationEuropean Journal of Operational Research, 2008
- Ant colony optimization with hill climbing for the bandwidth minimization problemApplied Soft Computing, 2005
- GRASP and path relinking for the matrix bandwidth minimizationEuropean Journal of Operational Research, 2004
- Reducing the bandwidth of a sparse matrix with tabu searchEuropean Journal of Operational Research, 2001
- Approximating the Bandwidth via Volume Respecting EmbeddingsJournal of Computer and System Sciences, 2000
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978
- The NP-Completeness of the bandwidth minimization problemComputing, 1976