JCL v. Exact Solution

        JCL is a heuristic algorithm, which cannot guarantee to find the exact minimal bandwidth but provides a practical and reliable way to find a bandwidth that is either the exact minimal bandwidth or very close to the exact minimal bandwidth. Exact solution algorithm which searches the set of n! possible permutations of vertices definitely can find the exact minimal bandwidth. The problem with exact solution is the computational costs, taking a long time and nearly useless for a big size n. A comparison of speed can show a significant difference between heuristic algorithm and exact solution algorithm.

        The following applies the source code ("mbidf" & "mbpsf"), which is under GNU GPL, of the article "Finding Exact Solutions to the Bandwidth Minimization Problem" by G. Del Corso and G. Manzini in Computing. Vol. 62, (1999), 189-203, to demonstrate the computational time.

COMPARISON 1

        Here applies the example of Fig.15 (size n=37) in the article "Algorithms for reducing the bandwidth and profile of a sparse matrix", published in computers & structures, vol. 44, no. 3, 1992, for the comparison. The result on an Pentium II Xeon 400 MHZ is as:


Both algorithms find the bandwidth, 6. However, the exact solution algorithm is about 3700 times slower than JCL. The big problem with exact solution algorithm is the computing time. When the problem size n is big, exact solution algorithm is nearly useless. In this small example, exact solution algorithm takes 74 seconds. Rational people may think 74 seconds is not a big deal. Exact solution algorithm "could" be applied to small-sized problems. The real issue is the computing time is unpredictable, even in small-sized problem. We have an example below.

COMPARISON 2

        For the example of Fig. 6 (n=48) in the same article published in computers & structures, an implementation by JCL and "mbidf" is as:


JCL takes 0.03 seconds; While the exact solution software "mbidf" could not find the bandwidth in 4 hours. It seems endless, which makes the exact solution algorithm is inapplicable.