The minimum bandwidth problem as an assignment problem with side constraints

A mathematical programming formulation of the minimum bandwidth problem is presented. The problem arises in the numerical solution of systems of linear equations containing sparsely-populated matrices. These matrices arise in the numerical solution of elliptic partial differential equations (e.g. by the finite element method). The computational effort and storage requirements associated with the solution of such a system of equations can be reduced by reordering the variables and equations so that the semibandwidth of the coefficient matrix is minimum. The graph theoretic form of the minimum bandwidth problem is to find an ordering of the graph associated with the coefficient matrix for which the largest absolute difference between two adjacent nodes is as small as possible. Heuristic algorithms which reduce bandwidth exist, but cannot guarantee an exact minimum. Here, the exact solution to the problem is cast as a mixed binary linear program. This formulation is shown to be equivalent to a sequence of assignment problems with side constraints (APSC’s). The formulation provides the basis for employing the approximate solution methods of integer programming.