A Reinforcement Learning Approach for Solving the Matrix Bandwidth Minimization Problem

Abstract

In this paper we aim at investigating and experimentally evaluating the reinforcement learning based model that we have previously introduced to solve the well-known matrix bandwidth minimization problem (MBMP). The MBMP is an NP-complete problem, which is to permute rows and columns of a matrix in order to keep its nonzero elements in a band lying as close as possible to the main diagonal. The MBMP has been found to be relevant to a wide range of applications including circuit design, network survivability, data storage and information retrieval. The potential of the reinforcement learning model proposed for solving the MBMP was confirmed by the computational experiment, which has provided encouraging results.