Heuristics for the central tree problem

This paper addresses the central spanning tree problem (CTP). The problem consists in finding a spanning tree that minimizes the so-called robust deviation, i.e. deviation from a maximally distant tree. The distance between two trees is measured by means of the symmetric difference of their edge sets. The central tree problem is known to be NP-hard. We attack the problem with a hybrid heuristic consisting of: (1) a greedy construction heuristic to get a good initial solution and (2) fast local search improvement. We illustrate computationally efficiency of the proposed approach.     

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

A Benders decomposition approach for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.This paper describes a new exact method, based on Benders decomposition, for the robust spanning tree problem with interval data. Computational results highlight the efficiency of the new method, which is shown to be very fast on all the benchmarks considered, and in particular on those that were harder to solve for the methods previously known.     

Variable neighbourhood search for the minimum labelling Steiner tree problem

We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times.     

A heuristic for the Steiner problem in graphs

In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.     

A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme.     

A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations

In this paper, we consider spanning tree situations, where players want to be connected to a source as cheap as possible. These situations involve the construction of a spanning tree with the minimum cost as well as the allocation of the cost of this minimum cost spanning tree among its users in a fair way. Feltkamp, Muto and Tijs 1994 introduced the equal remaining obligations rule to solve the cost allocation problem in these situations. Recently, it has been shown that the equal remaining obligations rule satisfies many appealing properties and can be obtained with different approaches. In this paper, we provide a new approach to obtain the equal remaining obligations rule. Specifically, we show that the equal remaining obligations rule can be obtained as the average of the cost allocations provided by a vertex oriented construct-and-charge procedure for each order of players.     

On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem

Considering an arbitrary undirected n-vertex graph with nonnegative edge weights, we seek to construct a spanning tree minimizing the sum over all vertices of the maximal weights of the incident edges. We find some particular cases of polynomial solvability and show that the minimal span whose edge weights lie in the closed interval [a, b] is a $\left( {2 - \frac{{2a}} {{a + b + 2b/(n - 2)}}} \right) $ -approximate solution, and the problem of constructing a 1.00048-approximate solution is NP-hard. We propose a heuristic polynomial algorithm and perform its a posteriori analysis.     

Intelligent variable neighbourhood search for the minimum labelling spanning tree problem

Given a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some effective heuristics have been proposed and analyzed. In a currently ongoing project, we investigate an intelligent optimization algorithm to solve the problem. It is obtained by the basic Variable Neighbourhood Search heuristic with the integration of other complements from machine learning, statistics and experimental algorithmics, in order to produce high-quality performance and to completely automate the resulting optimization strategy. Computational experiments show that the proposed metaheuristic has high-quality performance for the MLST problem and it is able to obtain optimal or near-optimal solutions in short computational running time.     

A structured solution framework for fuzzy minimum spanning tree problem and its variants under different criteria

This paper develops a unified and structured solution framework for the minimum spanning tree (MST) problem and its variants (e.g., constrained MST problem and inverse MST problem) on networks with fuzzy link weights. It is applicable to any additive decision criterion under fuzziness (e.g., expected value, value at risk, and conditional value at risk), for generalized cases that the link weights may be represented by arbitrary types of fuzzy variables. It also applies to the entropy criterion while the link weights are continuous fuzzy variables. Following the optimality conditions of the fuzzy MST under different decision criteria proved first in this paper, it is shown that the MST problem and its variants on a fuzzy network can be converted into equivalent deterministic counterparts on their corresponding crisp networks. Consequently, these problems can be effectively solved via their deterministic counterparts without fuzzy simulation, and meanwhile, the performance of the trees under a specified criterion is precisely measured. The accuracy and efficiency are both significantly improved compared with other fuzzy simulation-based approaches. Numerical examples illustrate the superiority of the proposed solution framework. Furthermore, some new theoretical conclusions on the MST problem under fuzziness are also presented.

     

The robust minimum spanning tree problem: Compact and convex uncertainty

We consider the robust minimum spanning tree problem where edges costs are on a compact and convex subset of Rⁿ. We give the location of the robust deviation scenarios for a tree and characterizations of strictly strong edges and non-weak edges leading to recognition algorithms.     

On Minimum Edge Ranking Spanning Trees

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.     

Minimum cut bases in undirected networks

Given an undirected, connected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem.For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs.We present heuristics, integer programming formulations and summarize first experiences with numerical tests.     

An evolutionary approach for tuning parametric Esau and Williams heuristics

Owing to its inherent difficulty, many heuristic solution methods have been proposed for the capacitated minimum spanning tree problem. On the basis of recent developments, it is clear that the best metaheuristic implementations outperform classical heuristics. Unfortunately, they require long computing times and may not be very easy to implement, which explains the popularity of the Esau and Williams heuristic in practice, and the motivation behind its enhancements. Some of these enhancements involve parameters and their accuracy becomes nearly competitive with the best metaheuristics when they are tuned properly, which is usually done using a grid search within given search intervals for the parameters. In this work, we propose a genetic algorithm parameter setting procedure. Computational results show that the new method is even more accurate than an enumerative approach, and much more efficient.     

Frequency optimization in public transportation systems: Formulation and metaheuristic approach

We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines.     

Enumeration of Pareto optimal multi-criteria spanning trees – a proof of the incorrectness of Zhou and Gen's proposed algorithm

The minimum spanning tree (MST) problem is a well-known optimization problem of major significance in operational research. In the multi-criteria MST (mc-MST) problem, the scalar edge weights of the MST problem are replaced by vectors, and the aim is to find the complete set of Pareto optimal minimum-weight spanning trees. This problem is NP-hard and so approximate methods must be used if one is to tackle it efficiently. In an article previously published in this journal, a genetic algorithm (GA) was put forward for the mc-MST. To evaluate the GA, the solution sets generated by it were compared with solution sets from a proposed (exponential time) algorithm for enumerating all Pareto optimal spanning trees. However, the proposed enumeration algorithm that was used is not correct for two reasons: (1) It does not guarantee that all Pareto optimal minimum-weight spanning trees are returned. (2) It does not guarantee that those trees that are returned are Pareto optimal. In this short paper we prove these two theorems.     

Efficient algorithms for a family of matroid intersection problems

Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.     

Greedy heuristics for the diameter-constrained minimum spanning tree problem

The diameter-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem that seeks a minimum cost spanning tree with a limit D imposed upon the length of any path in the tree. We begin by presenting four constructive greedy heuristics and, secondly, we present some second-order heuristics, performing some improvements on feasible solutions, hopefully leading to better objective function values. We present a heuristic with an edge exchange mechanism, another that transforms a feasible spanning tree solution into a feasible diameter-constrained spanning tree solution, and finally another with a repetitive mechanism. Computational results show that repetitive heuristics can improve considerably over the results of the greedy constructive heuristics, but using a huge amount of computation time. To obtain computational results, we use instances of the problem corresponding to complete graphs with a number of nodes between 20 and 60 and with the value of D varying between 4 and 9.     

Interactive decision making for uncertain minimum spanning tree problems with total importance based on a risk-management approach

This paper deals with a minimum spanning tree problem where each edge cost includes uncertainty and importance measure. In risk management to avoid adverse impacts derived from uncertainty, a d-confidence interval for the total cost derived from robustness is introduced. Then, by maximizing the considerable region as well as minimizing the cost-importance ratio, a biobjective minimum spanning tree problem is proposed. Furthermore, in order to satisfy the objects of the decision maker and to solve the proposed model in mathematical programming, fuzzy goals for the objects are introduced as satisfaction functions, and an exact solution algorithm is developed using interactive decision making and deterministic equivalent transformations. Numerical examples are provided to compare our proposed model with some previous models.     

An algorithm for finding a matroid basis which maximizes the product of the weights of the elements

Consider the problem of finding a spanning tree in an edge-weighted connected graph that maximizes the product of its edge weights, where negative edge weights are allowed. We generalize this problem to matroids and give a polynomial time algorithm for its solution.