1 Introduction

Combinatorial optimisation is a field that aims to address discrete optimisation problems with the use of combinatorial techniques. In discrete optimisation problems, the main purpose is to determine an optimal solution from a finite set of possible solutions. The Travelling Salesman Problem (TSP) is a classical example of problems in combinatorial optimisation. Such problems are generally very hard to solve [1].

Graph layout problems are a category of combinatorial optimisation problems. In these problems, the goal is to discover a layout or a linear arrangement of a given graph in such a way as to optimise a specific objective function. A layout is generated by labeling the vertices of a graph with distinct integers (i.e., from the set \(\left \{1, 2, {\ldots }, n\right \}\)) [2].

Minimum Linear Arrangement, Bandwidth, Cutwidth, Sum Cut, Modified Cut, Envelope, Vertex Separation, Vertex Bisection and Edge Bisection problems are considered the most important graph layout problems. Most of these problems are known to be NP-complete, meaning that finding optimal solutions cannot be guaranteed in polynomial time. However, because feasible solutions with near-optimal cost are usually sufficient, approximation algorithms and heuristics can also be employed for solving them [2, 3].

The Graph Bandwidth Problem (GBP) is a well-known and important graph layout problem, that was originally proposed to speed up a number of computations on sparse matrices [4]. The GBP is to label the vertices of a graph with distinct integers such that the maximum absolute difference between the labels of adjacent vertices is reduced. The problem can also be defined in the context of a symmetric matrix. In that case, the rows and columns of the matrix are reordered such that its non-zero elements are as close as possible to the main diagonal [4].

The GBP has a large number of applications in scientific and engineering fields, e.g., numerical analysis, large linear systems, circuit design, large scale power transmission systems, chemical kinetics, VLSI design, numerical geophysics, data storage, saving large hypertext media, finite element methods, network survivability, industrial electromagnetics and topology compression of road networks [5,6,7,8].

Minimising the bandwidth size is an NP-complete problem [9]. The GBP is also NP-complete even for trees having a maximum degree of three, and finding the optimal ordering in polynomial time is possible only in very special cases [10].

Highly effective methods for addressing the GBP are mainly informed search methodologies (i.e., Heuristics and Metaheuristics) in which a metric is required to guide the search towards better areas of the search space. The most frequently used metric in previous studies is simply the bandwidth itself, which is in fact the most obvious quality measure (See Section 2.3).

In this study, we show that this metric is not always suitable for comparing the quality of solutions produced by different informed search methods, and its utilisation may cause a remarkable reduction in the performance and effectiveness of such methods. In order to deal with this issue, a new metric is proposed, and its effectiveness is tested and verified by a large set of numerical experiments on standard benchmark problems from the University of Florida Sparse Matrix Collection [11]. The results are very promising and indicate that further progress on search-based GBP solvers can be expected from incorporating the proposed new metric into these solvers.

This paper is organised as follows. In Section 2, some background information about the GBP, search methods and relevant existing algorithms is provided. In Section 3, the motivation for the present study is described. In Section 4, the new metric is defined, and its application is discussed. In Section 5, the numerical experiments carried out to assess the effectiveness of the proposed metric are presented and analysed, followed by a discussion. In Section 6, the conclusions of this research are summarised.

2 Background

2.1 Problem definition

The GBP can be formally defined as follows. Let \(G\left (V, E\right )\) be a graph with vertex set V and edge set E. Further, let \(\lvert V \rvert = n\). A labeling f of G assigns the integers \(\left \{1, {\ldots }, n\right \}\) to the vertices of G. Let \(f\left (v\right )\) be the label of vertex v. Note that each vertex of G has a different label.

The bandwidth of a vertex v ∈ V, \(B_{f}\left (v\right )\), is the maximum of the differences between \(f\left (v\right )\) and the labels of its adjacent vertices with respect to the following conditions:

$$ B_{f}\left( v\right) = \left\{\begin{array}{ll} max\left( f\left( v\right)-f\left( u\right)\right)& \text{if} \left\{\exists u: (u\in N\left( v\right)) \wedge (f\left( u\right) < f\left( v\right))\right\} \enspace, \\ 0&\text{otherwise}\enspace. \end{array} \right. $$
(1)

where \(N\left (v\right )\) is the set of vertices adjacent to v. Considering (1), the bandwidth of G with respect to f can be expressed as:

$$ B_{f}\left( G\right) = max\left\{B_{f}\left( v\right) : v\in V\right\}. $$
(2)

The GBP, therefore, consists of finding a labeling f that minimises \(B_{f}\left (G\right )\). Note that a labeling is simply a renumbering of the vertices of G.

The notion of profile is a key concept regarding the bandwidth. Given a graph \(G\left (V, E\right )\), its profile (or of the corresponding sparse matrix) is:

$$ P_{f}\left( G\right) = {\sum}_{v=1}^{n} B_{f}\left( v\right). $$
(3)

Figure 1 shows an undirected graph having 6 vertices and 7 edges. The bandwidth and profile of this graph are calculated as follows:

Fig. 1
figure 1

An undirected graph

Full size image

2.2 Search methods

The solution to a large number of problems in science and engineering can be obtained by discovering a series of related actions leading to a particular goal. The state of a problem is altered by applying each action, and the main aim is obviously finding a series of states and actions by which reaching a goal state from an initial state is possible. The search space can be defined as the set of possible states with their associated operators (actions). Search can then be defined as systematically examining problem states with the aim of finding a path from an initial state to a goal state. Therefore, an algorithm with the ability of performing such a search is called search method [12].

There are generally two types of search methods, namely uninformed search methods and informed search methods. Breadth-First Search (BFS) and Depth-First Search (DFS) are examples of uninformed search methods. In these methods, the information provided in the problem definition is the only information that is available and can be used by the algorithm. Tabu search (TS) and Simulated Annealing (SA) are examples of informed search methods. In these methods, domain-specific information is available that can be used by the algorithm to decide which path is more promising for continuing the search. Informed search methods are much more effective compared to uninformed search methods and employed extensively for solving hard problems. Informed search methods use a heuristic function (also called a fitness function) for evaluating the fitness of a solution (i.e., the distance to a goal state). The heuristic function is responsible for guiding the search towards desirable areas of the search space. This is accomplished by returning a metric which indicates how effective a solution is. It is therefore clear that the quality of the metric returned by the heuristic function is a key factor in the performance of informed search methods [12].

Heuristics are informed search methods. They are, in fact, intelligent search strategies, which are employed for addressing problems in different fields. One of the main characteristics of heuristics is that they are problem-specific. This means that heuristics are normally designed for the solution of a particular problem. Metaheuristics are also informed search methods. They are actually higher-level heuristics. One of the key differences between heuristics and metaheuristics is that metaheuristics are problem-independent, meaning that they can solve a wide range of problems [13].

2.3 Relevant existing algorithms

The first exact method for the GBP was proposed by Harary [14]. Gurari and Sudborough [15] and Corso and Manzini [16] also proposed three other exact methods for solving the problem. It should be noted that these methods have only been applied to relatively small-sized matrices, i.e., up to 100 × 100. Cygan and Pilipczuk [17] proposed an exact exponential-time algorithm for the GBP. Their algorithm consists of two phases, including generating segment assignments and depth-first search.

Cuthill and McKee [18] introduced one of the most well-known graph theoretic-based search methods for the reduction of the bandwidth of sparse symmetric matrices. Their algorithm (i.e., the CM) is heuristic in nature, and still widely used. In this algorithm, the vertices of a graph associated with a symmetric matrix are divided into classes with respect to their distances from a root vertex. This structure is called a level structure. The best candidates for the root vertex in the level structure are those vertices with the minimum degree. If the vertices in the level structure are visited in increasing-distance order, a permutation is generated. The permutation is then applied to the matrix or its associated graph with the aim of reducing the bandwidth. It was observed that renumbering the CM ordering in a reverse way (RCM) could produce even better solutions compared to the original ordering [19].

Gibbs et al. [20] developed another well-known graph-theoretic heuristic search method (i.e., the GPS). This algorithm also uses the concept of the level structure as described earlier. An important feature of the algorithm is that it incorporates a very effective heuristic for detecting the endpoints of a pseudo-diameter to be employed as a suitable starting vertex. The GPS algorithm can generally outperform the CM algorithm in terms of effectiveness [21]. The GPS has been very successful in reducing the bandwidth of finite-element stiffness matrices that typically arise from problems in structural engineering. Wang and Shi [22] proposed an improved version of the GPS. This algorithm uses a heuristic parameter for detecting appropriate pseudo-peripheral vertices.

Gonzaga de Oliveira et al. [23] presented a heuristic search method for addressing the problem. Their algorithm employs both the Wonder bandwidth reduction algorithm and George-Liu algorithm. The George-Liu algorithm is used to provide a starting vertex. Gonzaga de Oliveira et al. [24] also proposed an improved version of the George-Liu algorithm for obtaining pseudo-peripheral vertices.

Metaheuristics, which are higher-level informed search methods, have been comprehensively examined to see whether they can be effective alternatives for solving the GBP. Marti et al. [25] employed a Tabu Search method for this purpose. A Genetic Algorithm combined with a Hill-climbing algorithm was used by Lim et al. [26] in order to solve this problem. Another genetic algorithm-based approach was given by Pop et al. [27] as well. A greedy randomized adaptive search method combined with a path relinking strategy (GRASP-PR) for addressing the GBP was proposed by Piñana et al. [28]. Lim et al. also presented an Ant Colony Optimization algorithm combined with a Hill-climbing algorithm [29] and a Particle Swarm Optimization algorithm combined with a Hill-climbing algorithm [30].

Czibula et al. [31] presented a Reinforcement Learning approach for solving the matrix bandwidth minimisation problem. They also applied genetic algorithms and ant-based systems to the problem [32]. Koohestani and Poli introduced two Genetic Programming systems in which genetic programming was used as a meta-heuristic [33] and as a hyper-heuristic [34]. Pop and Matei [35] also introduced an improved heuristic based on genetic programming.

A dual representation simulated annealing (DRSA) for the bandwidth minimisation problem was developed by Torres-Jimenez et al. [36]. In addition, in Chagas and Gonzaga de Oliveira [37] and Gonzaga de Oliveira et al. [38], metaheuristic-based approaches and low-cost heuristics for matrix bandwidth reduction were reviewed and evaluated, respectively. Mafteiu-Scai et al. [39] presented two hybrid methods based on Brain Storm Optimization, which is a swarm intelligence algorithm, for reducing the bandwidth.

Gonzaga de Oliveira and Silva [40] proposed a hyper-heuristic approach based on ant colony optimization (ACHH) for reducing the bandwidth of symmetric and non-symmetric matrices. The ACHH evolves graph-theoretic heuristic search methods for specific application areas. These heuristics are used to achieve low execution times for addressing the bandwidth reduction of large sparse matrices. The ACHH is provided with the main structure of the RCM-GL, KP-band heuristics, and a variation of King’s algorithm. The algorithm is then asked to evolve low-cost bandwidth reduction heuristics. Finally, the resulting heuristics are evaluated and compared against the most promising low-cost heuristics available in the literature.

Gonzaga de Oliveira and Silva [41] also proposed another hyper-heuristic approach based on ant colony optimization. The structure of this hyper-heuristic is similar to their work described above. This ACHH evolves low-cost heuristics for bandwidth reduction with the aim of accelerating the convergence of the zero-fill incomplete Cholesky-preconditioned conjugate gradient method (ICCG method). In [42], a modified version of the ACHH is introduced. The modified version is combined with a Hill-Climbing algorithm and uses the components of the RCM, KP-band, RBFS-GL, and RLK heuristics. The heuristics generated by this hyper-heuristic are capable of producing better solutions than those delivered by low-cost bandwidth reduction heuristics.

The most recent metaheuristic approach to the GBP is probably that of Silva et al. [43] who presented a Biased Random-Key Genetic Algorithm (BRKGA). In BRKGA, each gene in a chromosome is a random real number (i.e., a key) uniformly generated from the interval [0,1]. During the selection process, one parent is always selected at random from elite individuals in the current population, whereas the other is a non-elite individual (i.e., the selection is biased). In crossover operation, a parameterized uniform crossover scheme is first applied to a chromosome. A decoder is then used to map the altered chromosome into a feasible solution (i.e., a permutation).

3 Motivation

As mentioned in the previous section, informed search methods require a metric by which the search is guided towards high-quality solutions. In the case of heuristics and metaheuristics applied to the GBP, the most obvious metric, normally used in previous studies, is the bandwidth (See Section 2.3).

However, in spite of the fact that the bandwidth value is the quantity that should be minimised, it cannot be considered an ideal metric for a heuristic search. The most important reason for this issue is that if two or more candidate solutions have the same bandwidth (i.e., which is very likely), this does not necessarily mean that their qualities are the same. They may actually be quite different in terms of being closer to more promising solutions.

For instance, in Figs. 3 and 4, at first sight, it might seem that labeling 2 and labeling 3 have no priority over each other considering their bandwidth measures, which are both equal to 4. However, there is no doubt that labeling 2 is much closer to an ideal solution (i.e., labeling 1 in Fig. 2) than labeling 3. In fact, by a simple exchange of vertices labeled by 3 and 6, we can easily obtain labeling 1 from labeling 2 (Figs. 3 and 4).

Fig. 2
figure 2

Labeling 1, \(B_{f}\left (G\right ) = 2\)

Full size image
Fig. 3
figure 3

Labeling 2, \(B_{f}\left (G\right ) = 4\)

Full size image
Fig. 4
figure 4

Labeling 3, \(B_{f}\left (G\right ) = 4\)

Full size image

This clearly shows that the bandwidth is not always a suitable metric for comparing the quality of solutions produced by different search methods. If the comparison of the solution quality is not done properly, it is not possible to guide the search towards promising solutions, which in turn results in a remarkable reduction in the performance of such methods. In order to deal with this issue, in this study, a new metric is proposed with the aim of increasing the effectiveness of heuristic search methods for the GBP, as described in the next section.

4 Proposed new metric

Considering the issues mentioned in Section 3, the development of a new metric seems to be necessary for addressing the GBP using informed search methods. This metric should be more informative and able to clearly differentiate between the quality of candidate solutions in comparison with the standard metric. In order to reach this aim, a new metric is proposed in this study for the GBP, called Modified Profile (MP) as follows:

$$ MP_{f}\left( G\right) = {\sum}_{v=1}^{n} B_{f}\left( v\right)^{k}. $$
(4)

The reason behind the name chosen is that there is a relation between the profile and this new metric. For calculating the MP of a given graph G , the bandwidth of each vertex is raised to the power of k, where k is a positive integer, and then all of these terms are summed. Now, if k is equal to 1, the MP will be exactly the same as the profile. Figure 5 illustrates the process of determining the bandwidth, profile and modified profile. The MP has an interesting property as described below.

Fig. 5
figure 5

Determination of bandwidth, profile and modified profile

Full size image

If vertex m is a single vertex with maximum bandwidth, the following relations are valid:

$$ B_{f}\left( m\right) = B_{f}\left( G\right). $$
(5)
$$ MP_{f}\left( G\right) = B_{f}\!\left( 1\right)^{k} + B_{f}\left( 2\right)^{k} + {\ldots} + B_{f}\left( m\right)^{k} + {\ldots} + B_{f}\left( n\right)^{k} . $$
(6)
$$ \begin{array}{@{}rcl@{}} MP_{f}\left( G\right) &=& B_{f}\left( m\right)^{k} \left[\left( \frac{B_{f}\left( 1\right)}{B_{f}\left( m\right)}\right)^{k} + \left( \frac{B_{f}\left( 2\right)}{B_{f}\left( m\right)}\right)^{k}\right.\\ &&\left.+ {\ldots} + 1 + {\ldots} + \left( \frac{B_{f}\left( n\right)}{B_{f}\left( m\right)}\right)^{k}\right]. \end{array} $$
(7)
$$ \begin{array}{@{}rcl@{}} \lim_{k\rightarrow\infty} MP_{f}\left( G\right) &=& \lim_{k\rightarrow\infty} B_{f}\left( m\right)^{k} \left[\left( \frac{B_{f}\left( 1\right)}{B_{f}\left( m\right)}\right)^{k}\right.\\ &&\left.+ \left( \frac{B_{f}\left( 2\right)}{B_{f}\left( m\right)}\right)^{k} + {\ldots} + 1 + {\ldots} + \left( \frac{B_{f}\left( n\right)}{B_{f}\left( m\right)}\right)^{k}\right]. \end{array} $$
(8)

Now, for i≠m & i = 1…n, we have:

$$ \frac{B_{f}\left( i\right)}{B_{f}\left( m\right)} < 1 , \lim_{k\rightarrow\infty} \left( \frac{B_{f}\left( i\right)}{B_{f}\left( m\right)}\right)^{k} = 0. $$
(9)

Thus, we can conclude that

$$ \lim_{k\rightarrow\infty} MP_{f}\left( G\right) = B_{f}\left( m\right)^{k} = B_{f}\left( G\right)^{k}. $$
(10)

For a general case in which there is a set of vertices with maximum bandwidth (take its cardinality as α), the equation above reads as follows:

$$ \lim_{k\rightarrow\infty} MP_{f}\left( G\right) = \alpha B_{f}\left( m\right)^{k} = \alpha B_{f}\left( G\right)^{k}. $$
(11)
$$ MP_{f}\left( G\right) = \left\{\begin{array}{ll} P_{f}\left( G\right)&\text{if} k=1 \enspace, \\ \alpha B_{f}\left( G\right)^{k}&\text{if} k\rightarrow\infty \enspace. \end{array} \right. $$
(12)

As it is clear, the limit of \(MP_{f}\left (G\right )\) as k approaches infinity is the bandwidth of G raised to the power of k. Also, if k is equal to 1, then \(MP_{f}\left (G\right )\) will be the profile of G. This is interesting because, in fact, the proposed new metric (i.e., the MP) appropriately incorporates information about both the bandwidth and profile at the same time, enabling us to control the dominance of the bandwidth over the profile and vice versa by increasing and decreasing the power k. Therefore, if the aim is to optimize the bandwidth and profile simultaneously, there is no need to define the problem as a multi-objective optimization problem, which is highly desirable and advantageous.

Also, in the case of using the MP as a metric returned by a fitness function for a heuristic search applied to the GBP, it is more informative than the bandwidth itself. The reason is that the MP indicates the quality of solutions and also encapsulates an indication of how far a particular solution is from better solutions in the search space.

In Section 3, the problem with the use of the bandwidth as a fitness measure was shown by an illustrative example. In this example, if the MP (with k = 2) is used instead, then for labeling 1 in Fig. 2, \(MP_{f}\left (G\right ) = 11\); for labeling 2 in Fig. 3, \(MP_{f}\left (G\right ) = 22\); and for labeling 3 in Fig. 4, \(MP_{f}\left (G\right ) = 42\). Here, we see that labeling 1 is still the best solution as before. In terms of labeling 2 and labeling 3, we can easily choose labeling 2 (the second best solution) over labeling 3 with respect to their MP measures, which is impossible to do by considering their bandwidth measures. This is very important for heuristic search methods applied to the GBP because of enabling such methods to more precisely assess the quality of solutions and choose the most promising ones, resulting in a considerable increase in their effectiveness.

5 Numerical experiments

In this section, we describe the experiments performed on the proposed new metric (i.e., the MP) for the GBP. In order to evaluate the effectiveness of the MP, it was employed within a Genetic Algorithm (GA) [44] and a Generalized Pattern Search algorithm (GPS) [45] as their objective functions. These two algorithms are well-known heuristic search methods, differing in several respects, some of which are as follows.

The GPS algorithm does not explore the global structure of the objective function. Therefore, it can be attracted by a local or global minimum. The GPS algorithm forms a sequence of iterates, converging to a stationary point if the objective function is smooth. If the objective function is discontinuous, the GPS algorithm may fail at a discontinuity. For the GPS algorithm, the parameters are generally continuous. However, it is also possible to have discrete parameters.

The GA starts with a population of candidate solutions randomly distributed in the search space. This decreases the possibility of being trapped in a local minimum which is not global. However, it is impossible to know for certain about the convergence of the GA even on smooth objective functions. In fact, during the optimization process, the population of candidate solutions may collapse to a small subset of the search space. In such a situation, the GA can fail to find a minimum.

The reason we used two informed search methods, each of which belongs to a different class of search methodologies, was to verify the effectiveness of the proposed new metric in a more conclusive manner.

Our GA, called GA-GBP, is an implementation of the standard Genetic Algorithm described in [44], but we used permutation encoding to represent candidate solutions and adapt the algorithm to cope with the GBP. In GA-GBP, we also used the graph representation, introduced in [46], and the crossover operator, introduced in [47]. Our GPS algorithm, called GPS-GBP, is an implementation of the Generalized Pattern Search algorithm presented in [45] that we adapted it to deal with the GBP. Algorithms 1 and 2 provide a high-level description of these two algorithms, and Fig. 6 illustrates their flowcharts. For more details on the implementations, the interested reader is referred to the references given here.

Fig. 6
figure 6

(a) Flowchart of GPS-GBP. (b) Flowchart of GA-GBP

Full size image
figure c
figure d

In the present study, we performed three sets of experiments to examine the effect of employing the MP as an objective function on the performance of the GA-GBP and GPS-GBP algorithms, as follows:

5.1 Initial testing

In this first stage, we used the Buckyball graph [48] (better known as a soccer ball, a Buckminster Fuller geodesic dome, or a 60-atom carbon molecule) as a test problem. This graph has 60 vertices and 90 edges as shown in Fig. 7.

Fig. 7
figure 7

The Buckyball graph

Full size image

To compare the proposed new metric (i.e., \(MP_{f}\left (G\right )\)) with the standard metric (i.e., \(B_{f}\left (G\right )\)), they were incorporated into the GA-GBP and GPS-GBP algorithms as their objective functions. In terms of the MP, three different values of the parameter k (i.e., from 1 to 3) were used. For each of the two algorithms, 30 independent runs were executed for each of the four objective functions employed (i.e., \(MP_{f}\left (G\right )\) with k = 1,2,3 and \(B_{f}\left (G\right )\)), and the bandwidth and profile were calculated for every run.

The parameters of the runs related to the GA-GBP were as follows: Number of generations = 1000, Population size = 100, Crossover rate = 80%, Mutation rate = 10%, Reproduction rate = 9%, Elitism rate = 1%. Also, the parameters of the runs related to the GPS-GBP were as follows: Mesh size = 1, Expansion factor = 2, Contraction factor = 0.5, Max iterations = 100 * number of variables. Tables 1 and 2 show the results obtained for the experiments mentioned above.

Table 1 A comparison of \(MP_{f}\left (G\right )\) with \(B_{f}\left (G\right )\), both incorporated into the GA-GBP as its objective function
Full size table
Table 2 A comparison of \(MP_{f}\left (G\right )\) with \(B_{f}\left (G\right )\), both incorporated into the GPS-GBP as its objective function
Full size table

As described in Section 4, if k = 1, then the MP is the same as the profile. Also, by increasing the value of the parameter k (up to infinity), the MP gradually approaches the bandwidth of G raised to the power of k. However, it should be noted that by increasing the value of k, the term (or terms) related to a vertex (or vertices) with maximum bandwidth in (6) grows considerably, which may not be desirable when the MP is used as a fitness function. The reason is that this will result in a strong bias towards such a term (or terms), and the search will mostly focus on reducing the bandwidth of such a vertex (or vertices) and ignore other vertices. Therefore, it is important to find an appropriate value for the power k.

Considering the results of the experiments reported in Tables 1 and 2, in particular the mean of the bandwidth values and the best results obtained (marked in bold) by both algorithms under test, it is clear that the proposed new metric is superior to the standard metric.

5.2 Advanced testing 1

This stage deepens the former by employing the HB/can, HB/dwt and HB/bcspwr sets from University of Florida Sparse Matrix Collection (available at: https://www.cise.ufl.edu/research/sparse/matrices/HB/index.html) as test problems on which to compare the \(MP_{f}\left (G\right )\) against the \(B_{f}\left (G\right )\).

The HB/can set consists of 18 sparse matrices arising from finite-element applications with sizes ranging from 24 × 24 to 1072 × 1072 (the complete set was used). The HB/dwt set consists of 30 sparse matrices from NASTRAN (i.e., a finite element analysis program) users working in U.S. Navy, Army, Air Force and NASA laboratories. We employed two largest sparse matrices from this set (i.e., dwt_1242 and dwt_2680 with sizes 1242 × 1242 and 2680 × 2680 respectively). The HB/bcspwr set which includes matrices related to power networks, consists of 10 sparse matrices. We employed five largest sparse matrices from this set (i.e., bcspwr06, bcspwr07, bcspwr08, bcspwr09 and bcspwr10 with sizes 1454 × 1454, 1612 × 1612, 1624 × 1624, 1723 × 1723 and 5300 × 5300, respectively). These sets are subsets of the Harwell–Boeing sparse matrix collection, and have been used extensively by researchers.

Identical to the initial testing stage, first, the \(MP_{f}\left (G\right )\) and the \(B_{f}\left (G\right )\) were incorporated into the GA-GBP and GPS-GBP algorithms as their objective functions. 30 independent runs (with the same parameter setting as before) were then carried out per algorithm per objective function per test problem, and the bandwidth were calculated for every run.

The results associated with the tests are summarised in Table 3. The results reported clearly reveal that the GA-GBP and GPS-GBP algorithms with the proposed new metric significantly outperform the GA-GBP and GPS-GBP algorithms with the standard metric, considering the sum of the best bandwidth values, the number of the best bandwidth values and the number of the best mean bandwidth values (shown in the “Wins/Draws” row) obtained from 30 runs for each benchmark problem.

Table 3 A comparison of \(MP_{f}\left (G\right )\) against \(B_{f}\left (G\right )\) (both included in the GA-GBP and GPS-GBP algorithms) on a set of 25 instances from the University of Florida Sparse Matrix Collection
Full size table

In order to examine whether or not the relative performance differences observed in this set of experiments were statistically significant, the Wilcoxon signed-rank test was used for performing nonparametric statistical tests. The tests were carried out using the SPSS 16.0 software package, and the Exact method was used for calculating the significance levels of the statistics. The p-values obtained from the statistical analysis, summarised in Table 4, demonstrate that the performance differences caused by the use of the new metric are statistically highly significant.

Table 4 Statistical analysis of the results summarised in Table 3
Full size table

The results of the numerical experiments reported in this section also support the theoretical conclusion previously presented in Section 4 and confirm that the proposed metric is capable of increasing the effectiveness of informed search methods designed to solve the GBP.

5.3 Advanced testing 2

In the second round of the experiments described in the previous section, we observed that the GA-GBP significantly outperforms the GPS-GBP in all cases. Therefore, we selected the GA-GBP to conduct more experiments and make comparisons with other GBP solvers as follows.

Unlike the previous experiments, in this set of experiments, the initial population in the GA-GBP was generated by performing a Breadth-First Search (BFS) algorithm on a given graph from randomly selected start vertices. We remind that the BFS is a very well-known uninformed search method for traversing a graph. This non-random population initialisation mechanism has been used in several bandwidth reduction studies mentioned in this paper (See Section 1). Based on these studies and our own, it might be unlikely that by using a random initialisation, optimal or near optimal solutions could be found. It should be noted that the first and second experiments described before were not designed to find optimal or near optimal bandwidth values for the test problems, but rather to disclose the weakness of the standard metric and to demonstrate the effectiveness of the proposed alternative metric.

In order to further assess the performance of the GA-GBP, including the proposed new metric as its objective function, we compared it against three different algorithms designed for bandwidth reduction, i.e., BRKGA (the most recent metaheuristic approach), GRASP (a high-performance multistart metaheuristic) and RCM (the most well-known graph theoretic-based search method). Each algorithm was tested on a set of 43 standard benchmark problems from the SuiteSparse matrix collection (available at: https://sparse.tamu.edu). This set was used in [43] for performance comparison.

In this series of experiments, an AMD Athlon(TM) processor operating at 2.2 GHz was used to run the GA-GBP. The parameters of the runs were as follows: Number of generations = 100, Population size = 100, Crossover rate = 90%, Mutation rate = 8%, Reproduction rate = 1%, Elitism rate = 1%. We report the best bandwidth obtained for each benchmark problem as well as the time needed to find the best bandwidth for each problem instance on this computer. It should be emphasised that all the results associated with the BRKGA, GRASP and RCM were taken from [43].

In Table 5, we report the bandwidth values resulting from the permutations generated by the GA-GBP, BRKGA, GRASP and RCM algorithms as well as their corresponding CPU times for the 43 test problems. With respect to the sum of the bandwidth values and the number of the best bandwidth values obtained, it is clear that the GA-GBP outperforms all three algorithms under test in terms of solution quality. The results of the Wilcoxon signed-rank tests, carried out using the SPSS 16.0 software package and summarised in Table 6, also confirms that there is a statistically significant difference between the performance of GA-GBP and the other three algorithms.

Table 5 A comparison of the GA-GBP against BRKGA, GRASP and RCM algorithms
Full size table
Table 6 Statistical analysis of the results summarised in Table 5
Full size table

Considering the fact that BRKGA, GRASP and RCM were executed on an Intel(R) Core(TM) i7 processor operating at 4.2 GHz (as reported in [43]), we could not directly compare the CPU times of these algorithms (all rounded to the nearest integer) with the GA-GBP. However, since the processor used in [43] is substantially faster than the processor we used, by a simple inspection of the CPU times reported in Table 5, it can be concluded that the GA-GBP outperforms both metaheuristics under consideration (i.e., the BRKGA and GRASP), especially the BRKGA, in terms of execution speed. Note that the RCM is a graph theoretic-based search method. Such algorithms typically have a simple structure and can run hundreds to even hundreds of thousands of times faster than metaheuristics (e.g., the GA-GBP). Therefore, a runtime comparison between them is not reasonable.

The results obtained by the DRSA, a metaheuristic approach based on simulated annealing, is also presented in [43]. According to these results, the DRSA produces high quality solutions on the 43 benchmark problems used and outperforms the BRKGA, GRASP and RCM algorithms. The DRSA also outperforms the GA-GBP, our proposed algorithm. However, the disadvantage of DRSA is that it is very slow in execution. As reported in [43], the mean of the CPU times obtained by the DRSA is 470 seconds (rounded to the nearest integer) on an AMD Opteron(TM) operating at 2.2 GHz, while the mean of the CPU times obtained by the GA-GBP is 3 seconds (rounded to the nearest integer) on an AMD Athlon(TM) operating at 2.2 GHz. Since the two processors used are almost identical, we can reasonably compare the runtimes obtained by the DRSA and GA-GBP algorithms and conclude that the DRSA is approximately 156 times slower than the GA-GBP when applied to these 43 standard benchmark problems.

5.4 Discussion

In this work, we show that the standard metric used in previous studies on the GBP is not ideal for comparing the quality of solutions produced by search-based solvers and thus for guiding the search. We address this issue by proposing an alternative metric (i.e., the MP). The results of experiments reported here give clear evidence on the validity of the theoretical conclusions presented earlier and on the effectiveness of the MP in improving the performance of search-based GBP solvers.

The MP offers some advantages as follows: being more informative and providing better guidance for the search, incorporating information about both the bandwidth and profile at the same time, controlling the dominance of the bandwidth over the profile and vice versa by increasing and decreasing the power k, providing the possibility of optimizing the bandwidth and profile simultaneously without the need to define the problem as a multi-objective optimization problem, and encapsulating an indication of how far a particular solution is from better solutions in the search space.

The main disadvantage of using the MP for a heuristic search applied to the GBP is that an appropriate value for the power k should be found, otherwise this will result in a strong bias towards the term (or terms) related to a vertex (or vertices) with maximum bandwidth, and the search will mostly focus on reducing the bandwidth of such a vertex (or vertices) and ignore other vertices, which is not desirable.

In future work, we will investigate the possibility of improving the MP as well as developing a more robust metric for the GBP. With respect to the findings of the present study, we will also examine the standard metrics associated with other graph layout problems to see whether more effective alternatives can be introduced for solving these problems by means of informed search methods.

6 Conclusions

In this paper, a new metric for the Graph Bandwidth Problem has been introduced. This problem is proved to be NP-complete and has a significant number of applications in scientific and engineering domains. Therefore, many different types of algorithms have been developed for its solution. These algorithms are generally informed search methodologies in which a metric is needed for guiding the search towards good quality solutions. The most obvious and frequently used metric in earlier studies on the Graph Bandwidth Problem is the bandwidth itself. In this work, we have shown that this standard metric is not always appropriate for comparing the quality of solutions generated by different heuristic search methods, and its use may significantly reduce the performance of such methods. In order to tackle this issue, a new metric was proposed, and its effectiveness was tested and verified by a large number of numerical experiments on 68 standard benchmark problems from well-known sparse matrix collections. The results obtained were promising and showed that the proposed new metric was highly effective. Therefore, we believe that its incorporation into more sophisticated informed search methodologies previously used for addressing the Graph Bandwidth Problem may lead to further progress on these methods.