By
notation, cell (i,j) of a matriz is located in row i and in column
j, and it is said to be at distance |i – j| from the main
diagonal of the matrix. The bandwidth of a matrix is the maximum
distance from the main diagonal of a cell with a non-zero value. Given a symmetric
matrix with n rows and n columns, the Bandwidth Problem is
the problem of finding a permutation of n elements such that when
applied to the rows and to the columns, the resulting matrix has the minimum
bandwidth. The problem has been studied since the 60s. This webpage provides
results of some research done to develop an algorithm for this combinatorial
problem.
Differently
from other classical problems, the approach based on stating a suitable integer
linear programming formulation and solving the associated linear programming relaxation
seems to be useless in this case. This makes it nontrivial to design algorithms
capable of solving to optimality instances of reasonable size. In this paper,
we illustrate a new simple lower bound on the optimal bandwidth and its
extension within an enumerative algorithm, leading to integer linear
programming relaxations that can be solved efficiently and provide effective
lower bounds if part of the layout is fixed. Keeping the integrality constraints
in these relaxations is essential for this purpose. We show that the resulting
method can solve to proven optimality 24 out of the 30 instances with less than
200 nodes from the literature, each within less than one minute on a personal
computer. The new approach is also analyzed on randomly generated instances with
up to 1000 nodes. Moreover, we propose for the first time a method to compute
the well-known density lower bound on the optimal bandwidth, that succeeds in finding
this bound within minutes for most literature instances with up to 250 nodes.
Working
paper (submitted for possible publication to INFORMS Journal on Computing): Revised version January 2004
Transparences for a
presentation (presented in Aussois 2003):
Slides in PostScript
Code (source file in
Standard C) of our branch-and-bound algorithm: Our Enumerative
Algorithm
Codes (source files in
Standard C) for computing the “density” lower bound proposed by Chvátal (1970):
MainProgram MaxCliqueRoutine
Code (source file in
Standard C) of a generator of random instances: BWgenerator
Benchmark Library (in a
WinZip file) containing some instances from the Matrix Market Collection
with optimal solutions: Test-Bed
Library