A Feasibility Pump and a Local Branching Heuristics for the Weight-Constrained Minimum Spanning Tree Problem

Abstract

The Weight-constrained Minimum Spanning Tree problem (WMST) is a combinatorial optimization problem aiming to find a spanning tree of minimum cost with total edge weight not exceeding a given specified limit. This problem has important applications in the telecommunications network design and communication networks.

In order to obtain optimal or near optimal solutions to the WMST problem we use heuristic methods based on formulations for finding feasible solutions. The feasibility pump heuristic starts with the LP solution, iteratively fixes the values of some variables and solves the corresponding LP problem until a feasible solution is achieved. In the local branching heuristic a feasible solution is improved by using a local search scheme in which the solution space is reduced to the neighborhood of a feasible solution that is explored for a better feasible solution. Extensive computational results show that these heuristics are quite effective in finding feasible solutions and present small gap values. Each heuristic can be used independently, however the best results were obtained when they are used together and the feasible solution obtained by the feasibility pump heuristic is improved by the local branching heuristic.

1 Introduction

Given a graph with edge costs and edge weights, the aim of the Weight-constrained Minimum Spanning Tree (WMST) problem is to find a spanning tree with minimum cost, such that its total weight does not exceed a given specified integer positive limit W. The WMST problem is a NP-hard [2, 21] combinatorial optimization problem with important applications in the telecommunications network design and communication networks.

Several algorithms have already been proposed to the problem, either with exact or approximation approaches for determining a feasible solution. Aggarwal et al. [2] and Shogan [18] propose exact algorithms that use a Lagrangian relaxation to approximate a solution combined with a Branch and Bound strategy. Ravi and Goemans [15], Xue [20], Hong et al. [11] and Hassin and Levin [9] propose approximation schemes. A compilation of results and existing algorithms to solve the problem can be found in Henn [10].

Requejo et al. [16] describe several Integer Linear Programming (ILP) formulations, Agra et al. [4] describe new valid inequalities for the WMST problem, and Requejo and Santos [17] discuss algorithms based on Lagrangian relaxations and propose a Lagrangian relaxation combined with valid inequalities.

Another approach to the problem is to include the weight of the tree as a second objective instead of a hard constraint. The resulting problem is the bicriteria/biobjective spanning tree problem. Many references can be found for this approach, see [19] among many others.

In this paper we present heuristics for the WMST problem that use mixed integer models of the problem and allow interaction with a mixed integer programming (MIP) solver. We describe two heuristics and, additionally these heuristics are used together in one heuristic procedure. In the first one, the heuristic should provide a “good” feasible solution. In the second one, the heuristic should allow the improvement of an available feasible solution. For the first heuristic, a Feasibility Pump scheme is used. Such scheme was proposed by Fischetti, Glover and Lodi [6] with the goal of finding feasible solutions (if any exists) for generic Mixed Integer Linear Programming (MILP) problems and improved by Fischetti, Bertacco and Lodi [5] and by Achterberg and Berthold [1]. A mixed integer formulation for the WMST problem together with a MIP solver are used to obtain (fractional) linear relaxation solutions. These fractional solutions are rounded such that a feasible solution (if any exists) is found. For the second heuristic we consider a Local Branching method proposed by Fischetti and Lodi [7] to solve MIP problems. This enumerative scheme constructs a sequence of feasible solutions with improving (decreasing) value of costs which is considered a very effective improving method for large scale problems. Again a mixed integer formulation for the WMST problem together with a MIP solver are used with the objective to explore reduced feasible regions.

The structure of this paper is as follows. In Sect. 2 we describe the WMST problem and a general formulation that will be used in the heuristic schemes. In Sect. 3 we present a Feasibility Pump heuristic applied to the WMST problem. In Sect. 4 we present a Local Branching heuristic applied to the WMST problem. In Sect. 5, we present computational results for the Feasibility Pump and Local Branching schemes applied to the WMST problem. In the last section, Sect. 6, we conclude the paper.

2 The Weighted-Constrained Minimum Spanning Tree Problem

To define the WMST problem we consider an undirected complete graph $G = (V,E)$, with node set $V = \{0,1,\ldots ,n-1\}$ and edge set $E = \{ \{i,j\}, \ i,j \in V, i \ne j \}$. Associated with each edge $e=\{i,j\} \in E$ consider positive integer costs $c_{e}$ and weights $w_{e}$. The WMST problem is to find a spanning tree $T = (V ,E_T )$ in G, $E_T \subset E$, of minimum cost $C(T) = \sum _{e \in E_T} c_e$ and with total weight $W(T) = \sum _{e \in E_T} w_e$ not exceeding a given limit W.

To obtain formulations for the WMST problem one can easily adapt a Minimum Spanning Tree (MST) formulation. For the MST several formulations are well known (see Magnanti and Wolsey [12]) and in [16] natural and extended formulations for the WMST problem are discussed.

It is well known (see Magnanti and Wolsey [12]) that oriented formulations (based on the underlying directed graph) leads, in general, to tighter formulations (formulations whose lower bounds provided by the linear relaxations are closer to the optimum values). Thus, henceforward consider the corresponding directed graph, with root node 0, where each edge $e=\{0,j\} \in E$ is replaced with arc (0, j) and each edge $e=\{i,j\} \in E, i \not = 0,$ is replaced with two arcs, arc (i, j) and arc (j, i). Thus we obtain the arc set $A = \{ (i,j), \ i \in V ,j \in V\setminus \{0\}, i \ne j \}$. Each arc $(i,j) \in A$ inherits the cost and weight of the corresponding ancestor edge $\{i,j\}$.

Consider the binary variables $x_{ij}$ (for all $(i,j) \in A$) indicating whether arc (i, j) is in the MST solution. Two classical formulations for the MST on the space of the binary variables $x_{ij}$ can be considered [12]. To prevent the existence of circuits in the feasible solutions, and thus ensuring the connectivity of the feasible solutions, one formulation uses the cut-set inequalities and the other formulation uses the circuit elimination inequalities. The linear relaxation of both models provide the same bound value [12]. However the number of inequalities in both sets of constraints increase exponentially with the size of the model. In order to ensure connectivity/prevent circuits, instead of using one of those families with an exponential number of inequalities, one can use compact extended formulations. The well-known multicommodity flow formulation using additional flow variables can be considered. In this formulation the connectivity of the solution is ensured through the flow conservation constraints together with the connecting constraints, see [12]. These three formulations for the MST are easily adapted for the WMST problem through the inclusion of a weight constraint.

A generic formulation for the WMST problem is as follows.

$$\begin{aligned} \text{(WMST): } \qquad \min&\quad \sum _{(i,j) \in A} c_{ij} x_{ij} \end{aligned}$$

(1)

$$\begin{aligned} \text{ s.t. }&\quad x \in (MST) \end{aligned}$$

(2)

$$\begin{aligned}&\quad \sum _{(i,j) \in A} w_{ij} x_{ij} \le W \end{aligned}$$

(3)

Where $x = (x_{ij}) \in \mathbb {R}^{|A|}$ is the solution vector and (MST) represents a set of inequalities describing the convex hull of the integer solutions of the MST. As referred, several sets of inequalities can be used. We use the multicommodity flow formulation. Consider the additional set of flow variables $f_{ij}^{k} \ge 0$, for all $(i,j) \in A$ and $k \in V\backslash \{0,i\}$, indicating weather arc $(i,j) \in A$ is used in the path from the root node to node k. The following flow conservation constraints

$$\begin{aligned}&\quad \sum _{i \in V \backslash \{k\} } f_{ij}^{k} - \sum _{i \in V\backslash \{0\}} f_{ji}^{k} = \left\{ \begin{array}{rl} -1 &{} j=0 \\ 0 &{} j \ne 0,k \\ 1 &{} j=k \\ \end{array} \right. , \qquad&j \in V, \ k \in V \backslash \{0\}, \end{aligned}$$

and the connecting constraints $f_{ij}^{k} \le x_{ij}$, for all $(i,j) \in A, k \in V \backslash \{0,i\}$ are used to ensure the connectivity of the solution and to represent the set (2) of constraints, together with the set of constraints $\sum _{i \in V} x_{ij} = 1$, for all $j \in V$, guarantying each non-root node receives an arc. Additionally, include the variables integrality constraints $x_{ij} \in \{ 0,1\}$, for all $(i,j) \in A$ and the variables non-negativity constraints $f_{ij}^{k} \ge 0$, for all $(i,j) \in A$ and $k \in V\backslash \{0,i\}$. Constraint (3) is the weight constraint.

3 The Feasibility Pump Heuristic for the WMST Problem

In this heuristic procedure the objective is to obtain a “good” feasible solution to the WMST problem. This objective is achieved through a relax-and-fix approach. We use the Feasibility Pump scheme, proposed by Fischetti, Glover and Lodi [6].

The first step of this procedure, the relax step, is to obtain the optimal solution of a linear relaxation formulation for the WMST problem, the LP solution. Let $\bar{x}$ be such solution. If $\bar{x}$ is an integer solution, then it is the optimal solution of the problem.

The second step is the rounding and fixing variables value step. Let the rounding $\tilde{x}$ of vector x be obtained by setting $\tilde{x}_{ij}=round(x_{ij})$, the usual scalar rounding, for all $(i,j) \in A$. The obtained vector $\tilde{x}$ is integer and, in general, $\tilde{x}$ is not a feasible solution.

The third step is to obtain the closest feasible solution to vector $\tilde{x}$. For that define a distance function $\varDelta (x,\tilde{x})$ between a generic vector x and the given integer solution $\tilde{x}$. To define the distance function use the following $L_1$-norm function $\varDelta (x,\tilde{x}):=\sum _{(i,j) \in A} |x_{ij}-\tilde{x}_{ij}|.$ Notice that this function is equivalent to the linear function defined by $\sum _{(i,j) \in S} (1-x_{ij}) + \sum _{(i,j) \in \overline{S}} x_{ij}$, with set $S=\{(i,j) \in A: \tilde{x}_{ij}=1\}$ and its complement set $\overline{S}=\{(i,j) \in A: \tilde{x}_{ij}=0\}$. Thus consider the distance function

$$\begin{aligned} \varDelta (x,\tilde{x}):=\sum _{(i,j) \in S} (1-x_{ij}) + \sum _{(i,j) \in \overline{S}} x_{ij}. \end{aligned}$$

(4)

Hence, given an integer $\tilde{x}$, the closest vector x satisfying constraints (2) and (3) can be determined by minimizing the value of the distance function $\varDelta (x,\tilde{x})$ as follows

$$\begin{aligned} \text{(D-WMST): } \qquad \min&\quad \varDelta (x,\tilde{x}) \\ \text{ s.t. }&\quad (2),(3). \nonumber \end{aligned}$$

(5)

Let $\hat{x}$ be the optimal solution of the LP relaxation of problem (5), the D-WMST problem, and the value $\varDelta (\hat{x},\tilde{x})$ is its optimal value. The vector $\hat{x}$ is the closest solution to the integer $\tilde{x}$ and two cases may occur. If $\varDelta (\hat{x},\tilde{x})=0$, then $\hat{x}=\tilde{x}$ is an integer feasible solution for the WMST problem. If $\varDelta (\hat{x},\tilde{x})>0$, then a new integer $\tilde{\hat{x}}$ is going to be obtained by rounding $\hat{x}$. By rounding $\hat{x}$ two cases may occur. Either $\tilde{\hat{x}} \not = \tilde{x}$, a different vector was obtained, or $\tilde{\hat{x}} = \tilde{x}$. When $\tilde{\hat{x}} \not = \tilde{x}$ occurs the iterative process continues by solving the D-WMST problem again and a new solution closest to the new integer vector $\tilde{\hat{x}}$ is going to be obtained. When $\tilde{\hat{x}} = \tilde{x}$, the same solution was obtained and a cycle occurs. To avoid cycling the following perturbation mechanism [6] is applied to an integer solution $\tilde{x}$. For a given parameter $\delta > 0$, modify $\tilde{x}$ such that $|x_{ij}-\tilde{x}_{ij}|+max\{\rho _{ij},0\}>\delta$, for all $(i,j) \in A$ and $\rho _{ij}$ randomly selected in $[-0.3,0.7]$. Notice that this perturbation mechanism gives the possibility to modify the variables such that $|x_{ij}-\tilde{x}_{ij}|=0$.

Iteratively another step is performed in order to further reduce the distance $\varDelta (\hat{x},\tilde{x})$ between the vector $\tilde{x}$, the integer rounded vector, and the closer solution $\hat{x}$ of the LP problem (5). Therefore the pair $(\hat{x},\tilde{x})$ is iteratively updated by performing this relax-and-fix procedure until a feasible solution to the WMST problem is found.

In practice it may be much time consuming to achieve such feasible solution. Therefore a time limit, denoted maxtime, and a maximum number of iterations, denoted maxiter, are imposed. Hence we obtain a heuristic procedure, the feasibility pump heuristic which is briefly described in Algorithm 1.

In the first line of Algorithm 1 a solver is used to obtain the LP solution $\hat{x}$. A solver is again used in line 9 to obtain a solution to the D-WMST problem.

In Algorithm 1 all the solutions, except the first LP solution that uses the objective function of the WMST problem, are obtained by using as objective function the distance function (4). This objective function does not take into account the objective function of the WMST problem. As a consequence the solution obtained at the end of the procedure may have a value far from the best objective value of the WMST problem. To overcome this disadvantage, Achterberg and Berthold [1] propose the use of a different objective function that is a convex linear combination of the objective function (1) of the WMST problem and the distance function (4) of the D-WMST problem. The proposed objective function is

$$\begin{aligned} \varDelta _{\alpha }(x,\tilde{x}):=(1-\alpha ) \varDelta (x,\tilde{x})+\alpha \frac{\sqrt{|A|}}{||c||} \sum _{(i,j) \in A} c_{ij} x_{ij}, \end{aligned}$$

(6)

with $\alpha \in [0,1]$ and where ||c|| is the Euclidean norm of the cost vector c and |A| is the cardinality of set A. Thus $\sqrt{|A|}$ is the Euclidean norm of the objective function vector in (4). In the objective function (6), the influence of the objective function (1) of the WMST problem is controlled by the $\alpha$ parameter. For values of $\alpha$ near to 1 the influence of the objective function is high.

In order to obtain an Improved Feasibility Pump heuristic for the WMST problem (IFP) one has to obtain, in line 9 of the Algorithm 1, the optimal solution $\hat{x}$ of (5) with (6) as the objective function.

Both the FP and the IFP return an integer solution, which may not satisfy constraints (2) and (3), and a solution satisfying constraints (2) and (3), but not necessarily integer. Two trajectories of solutions, hopefully convergent, are constructed. One is formed by a sequence of solutions satisfying constraints (2) and (3), solutions $\hat{x}$ that may not be integer. The other sequence is formed by integer solutions $\tilde{x}^t$ that may not satisfy constraints (2) and (3).

4 The Local Branching for the WMST Problem

The improvement of a previously obtained feasible solution to the WMST problem is the objective of the second heuristic we describe. The improvement is done through a local search scheme that uses a local branching method based on the method proposed by Fischetti and Lodi [7].

Consider, as a reference solution, a previously obtained feasible solution $\tilde{x}$ to the WMST problem. This integer solution corresponds to a spanning tree $T_{\tilde{x}}$ with cost $C(\tilde{x})=C(T_{\tilde{x}})$ and weight $W(\tilde{x})=W(T_{\tilde{x}})$. Define two sets, set $S=\{(i,j) \in A: \tilde{x}_{ij}=1\}$ and its complement set $\overline{S}=\{(i,j) \in A: \tilde{x}_{ij}=0\}$. For a given positive integer parameter $k^{\prime }$, define the neighborhood of $\tilde{x}$ as the set of feasible solutions of the WMST problem satisfying the additional local branching constraint:

$$\begin{aligned} \varDelta (x,\tilde{x})=\sum _{(i,j) \in S}(1-x_{ij})+\sum _{(i,j) \in \overline{S}}x_{ij}\le k^{\prime }. \end{aligned}$$

(7)

The linear constraint (7) limits to $k^{\prime }$ the total number of binary variables flipping their value with respect to the solution $\tilde{x}$, either from 1 to 0 or from 0 to 1, respectively. Notice that the local branching constraint uses the same distance function $\varDelta (x,\tilde{x})$ that is used in the FP heuristic as the objective function (4).

For every feasible solution to the WMST problem the cardinality of the set S is constant and equal to the number of edges of the corresponding feasible tree $T_{\tilde{x}}$. Further the number of variables exchanging from 1 to 0 must be equal to the number of variables exchanging from 0 to 1. Thus the local branching constraint may assume the asymmetric form:

$$\begin{aligned} \varLambda (x,\tilde{x})=\sum _{(i,j) \in S}(1-x_{ij})\le k \end{aligned}$$

(8)

with $k=\frac{k^{\prime }}{2} .$ Constraint (8) can be used as a branching criterion within an enumerative scheme and the solution space associated with the current branching node can be partitioned by means of the disjunction

(i) $\varLambda (x,\tilde{x})\le k$ (left branch) or (ii) $\varLambda (x,\tilde{x})\ge k+1$ (right branch).

With each one of those constraints the solution space is reduced. Define the neighborhood $\mathcal {N}(\tilde{x},k)$ of $\tilde{x}$ as the set of feasible solutions of the WMST problem satisfying the additional local branching constraint $\varLambda (x,\tilde{x})\le k$, and the neighborhood $\mathcal {N}_+(\tilde{x},k)$ of $\tilde{x}$ as the set of feasible solutions of the WMST problem satisfying the additional local branching constraint $\varLambda (x,\tilde{x})\ge k+1$. The choice of the size of the neighborhoods given by the parameter k is a problem which may depend on the size and structure of the instances used. On one hand, the k must be large enough so that the neighborhood $\mathcal {N}(\tilde{x},k)$ contains better valued solutions than $\tilde{x}$. On the other hand, the k should be small enough to ensure that the neighborhood $\mathcal {N}(\tilde{x},k)$ is quickly explored. Note that neighborhood $\mathcal {N}(\tilde{x},k)$ of $\tilde{x}$ has solutions similar to $\tilde{x}$ and neighborhood $\mathcal {N}_+(\tilde{x},k)$ contains solutions that differ from $\tilde{x}$ in more than $2 \times (k+1)$ variables. The method explores both neighborhoods, but the neighborhood $\mathcal {N}_+(\tilde{x},k)$ is only explored when a feasible solution better valued than $\tilde{x}$ is not found in the neighborhood $\mathcal {N}(\tilde{x},k)$. Algorithm 2 displays a brief description of the local branching scheme applied to the WMST problem.

In the first line of Algorithm 2 a solver is used to obtain the first feasible integer solution $\tilde{x}^1$ which is taken as a reference solution. A solver is again used in lines 7 and 13 to obtain the solutions in the reduced solution space. The sequence of solutions $\tilde{x}^t$ generated by the LB, corresponds to a decreasing sequence of costs.

The Local Branching is a MIP technique planned to be an exact method, but that acts as a heuristic method when a time limit is set and reached before the optimal solution is found [8]. In case the time limit is exceeded, the obtained solution $\tilde{x}$ is not the optimal solution and the exploration of the neighborhood is not complete. In that case the size of the neighborhood that is to be explored has to be modified in order to either reduce or enlarge the region where the solution is sought. The following mechanisms, see [13], modify the size of the neighborhood.

Intensification mechanism. The intensification mechanism aims to reduce the size of the neighborhood in an attempt to speed-up its exploration. The right hand side of the constraint $\varLambda (x,\tilde{x})\le k$ is reduced to $\lfloor \frac{k}{2}\rfloor$.

Diversification mechanism. The diversification mechanism aims to enlarge the size of the neighborhood. However, and consequently the exploration time is also increased. First apply a “weak” diversification mechanism, in which the right hand side of the constraint $\varLambda (x,\tilde{x})\le k$ is increased by $\lceil \frac{k}{2}\rceil$, i.e., it is introduced the constraint $\varLambda (x,\tilde{x})\le k+\lceil \frac{k}{2}\rceil$. In case an improved solution is not found, apply a “strong” diversification mechanism, in which the right hand side of the constraint $\varLambda (x,\tilde{x})\le k$ is increased with $2\times \lceil \frac{k}{2}\rceil$, i.e., it is introduced the constraint $\varLambda (x,\tilde{x})\le k+2 \lceil \frac{k}{2}\rceil$.

When a time limit is exceeded and the obtained solution $\tilde{x}$ is not the optimal solution the following cases may occur. (i) If the solution $\tilde{x}$ has an improved value, then the reference solution is updated, but the value of parameter k is not modified. (ii) If the solution $\tilde{x}$ does not have an improved value, $C(\tilde{x}) > C(\tilde{x}^t)$, then apply the intensification mechanism in order to reduce the neighborhood. If again an improved solution is not found, apply a “weak” diversification mechanism. (iii) If the solution $\tilde{x}$ is infeasible, then apply the “strong” diversification mechanism in order to enlarge the neighborhood.

5 Computational Experience

In this section we report computational tests of the FP and of the LB heuristics applied to the WMST problem. We compare the performance of the heuristics against an upper bound obtained by a branch-and-cut algorithm based on the strengthened weighted Miller-Tucker-Zemlin formulation (Agra et al. [3] and Requejo et al. [16]).

All the tests were performed using a computer with an Intel(R) Core(TM)2 Duo CPU (T7100) 2.00 GHz processor and 4 GB of RAM, and were conducted using the Xpress-Optimizer 23.01.03 solver with the default options.

We present computational results for instances to the WMST problem defined on complete graphs with a number of nodes varying between 10 and 1000, in a total of 215 instances.

5.1 Instances Generation Description

To generate an instance of the WMST problem, the cost $c_e$ and the weight $w_e$ of each edge e have to be defined. Afterwards, a (feasible) value to the weight limit W must also be defined. We built three sets of instances, constituting three different ways of generating costs and weights.

In a first set of instances, costs $c_e$ and weights $w_e$ are generated similarly to a set of instances described in Pisinger [14] and named therein as Spanner instances. A value for W is selected between 1000 and 3500 proportional to the number n of nodes of the instance. The costs and the weights are multiples of a small set (the spanner set in [14]) of costs and weights following one particular distribution, we use the Uncorrelated distribution (which is in the Pisinger’s [14] proposed list of distributions), and the following two parameters $s=2$ and $m=10$. At the end, the weights of some edges are manipulated in such a way that the optimal solution has a desired predefined structure. After testing a few structures we obtained some challenging instances when the optimal structure of the WMST problem instance solution has large diameter values, almost $n-1$, but not equal to $n-1$, in such way that the tree is almost a path. Thus we name this instance’s set as “Almost Path” (AP).

For the second set of instances, named Random (R) instances, the costs $c_e$ and the weights $w_e$ are uniformly generated in the interval [1, 1000].

For the third set of instances, named Euclidean (E) instances, costs $c_e$ and weights $w_e$ are obtained using Euclidean distances. After randomly generating the coordinates of n points/nodes in a $100 \times 100$ grid, the cost $c_e$ of each edge $e=\{ i,j\}$ is the integer part of the Euclidean distance between points/nodes i and j. We proceed independently and similarly to obtain the weights.

To define a (feasible) value to the weight limit W for each instance of these two sets of instances (sets R and E), we start by obtaining the weight of the minimum spanning tree $W(T_c)$ and the weight of the minimum weight spanning tree $W(T_w)$ and we select W to be one of the values $W_i=\frac{W(T_c)\,+\,W(T_w)}{2^i}$, for $i \in \{1,\ldots ,10\}$.

A total of 215 instances were generated, 95 of the set AP and 60 of each set R and E. For each set AP and each instance size between 10 and 150 we have 10 instances and for each instance size between 200 and 1000 we have 5 instances. For each set R and E and each instance size we have 5 instances.

5.2 Computational Tests for the FP and IFP Heuristics

Computational tests performed in all groups of instances allow us to conclude that the heuristics FP and IFP, described in Sect. 3, obtain similar quality solutions. However the heuristic FP uses less computational time in all groups of instances, see Fig. 1. Also the number of iterations used by the IFP heuristic is approximately three times higher than the number of iterations used by the FP heuristic. On average the number of iterations of the FP is 4 and the number of iterations of the IFP is 14. Therefore, the remaining computational results will be presented only for the FP heuristic.

Fig. 1.

Comparing the mean execution times (in seconds) for FP and IFP heuristics.

Table 1. Mean execution time (in seconds) and mean number of iterations of the four LB strategies.

5.3 Computational Tests for the LB Heuristic

Computational experiments performed with the LB heuristic, described in Sect. 4, showed that when the value k of the local branching constraints (8) increases, the mean execution times also increases. To obtain the computational results of the LB heuristic we used the value $k=5$ and several strategies were tested. First strategy (LB1): a time limit of 10000 s is imposed. Second strategy (LB2): in addition to the time limit, the solver is stopped when the first integer solution is obtained, and intensification and diversification mechanisms are used. Third strategy (LB3): in addition to the second strategy conditions, the reference solution is the first integer solution found by the solver and a time limit is imposed for the exploration of the neighborhoods. Fourth strategy (LB4): differs from the third strategy because the reference solution is obtained with the FP heuristic. To evaluate these four strategies some preliminary computational tests were performed to instances with up to $n=100$ nodes in a total of 120 instances. Table 1 displays mean computational times and mean number of iterations for the four LB strategies. The LB1 strategy obtained good valued solutions, but it uses high computational times and 18.3% of the instances (13 AP instances and 9 E instances) exceed a computational time limit imposed. The LB2 and LB3 strategies use less computational time than strategy LB1, however the LB4 strategy uses less computational time, obtains the best valued solutions and the optimal solution was obtained in 83.3% of the instances (in 100 of the 120 instances). Table 1 shows that the LB4 strategy presents the lowest average execution times and also uses the smallest average number of iterations, for all group of instances. Therefore we report results obtained with this LB4 strategy, denoted as LB in what follows. Notice that this strategy corresponds to the FP heuristic followed by a LB heuristic.

Table 2. Mean gap values (in percentage) of the HP procedure, the FP and the LB heuristics.

Table 3. Mean execution time (in seconds) for the HP procedure, the FP and the LB heuristics.

5.4 Results Description and Analysis

We compare the performance of the FP and of the LB heuristics with the performance of the HP procedure.

In [3, 16] the best results to obtain the optimal value using the software Xpress 7.3 (Xpress Release 2012 with Xpress-Optimizer 23.01.03 and Xpress-Mosel 3.4.0), were obtained with the Branch and Cut algorithm based on a weighted MTZ (Miller-Tucker-Zemlin) formulation with the inclusion of cuts preventing cycles at the root node. This procedure will be denoted by HP (Hybrid Procedure) and is used to access the quality of the solutions obtained with the FP and LB heuristics.

Having an upper bound on the value of the cost, the upper bound gap is $gap=\frac{UB\,-\,OPT}{OPT} \times 100,$ where UB is the upper bound obtained through the considered method (HP procedure, FP heuristic, LB heuristic) and OPT is the optimal value obtained with the HP procedure or the best obtained value with this procedure within a time limit of 10000 s.

For each instance set AP, R, and E and each instance size set we display in the upper part of the Table 2 the average upper bound gap (in percentage) and the corresponding standard deviation values, in the lower part of the Table 2. In the upper part of the Table 3 are displayed the average execution times (in seconds) and corresponding standard deviation values, in the lower part of the Table 3.

The LB heuristic improves the solutions obtained by the FP heuristic in 68.37% of the instances (147 from 215 instances). In 75.34% of the instances (162 from 215 instances) the gap is null, i.e. the optimal solution was obtained, when using the LB heuristic. The set of instances with the highest gap is the E instance set, the Euclidean instances.

For every procedure the computational time increases as the size of the instance (number of nodes) increases. In 61.86% of the instances (133 from 215 instances), the computational time of the LB heuristic is smaller than the computational time of the HP procedure. The set of instances with the highest computational time is, again, the instance set E. Using the HP procedure it was not possible to obtain an upper bound within the time limit imposed for two E instances.

6 Conclusions

We describe two heuristic procedures to the WMST problem, the FP (feasibility pump) and the LB (local branching) heuristics. The FP heuristic is a constructive heuristic and uses a relax-and-fix strategy to obtain a good feasible solution. The LB heuristic uses a local branch strategy to improve a feasible solution. Our computational results show that the FP heuristic is fast in obtaining feasible solutions for the WMST problem, and the LB heuristic can be used to improve the obtained feasible solution. Both heuristics can be used independently, however the best strategy is to use the heuristics together, the FP followed by the LB. This process is faster than the HP procedure, a branch-and-cut procedure used to access the quality of the described heuristics, and obtains good valued solutions.

The FP and the LB heuristics are a good choice in obtaining feasible solutions for the WMST problem and can be used together for better quality solutions and with very competitive computational times.