A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.     

RAMP for the capacitated minimum spanning tree problem

This paper introduces dual and primal-dual RAMP algorithms for the solution of the capacitated minimum spanning tree problem (CMST). A surrogate constraint relaxation incorporating cutting planes is proposed to explore the dual solution space. In the dual RAMP approach, primal-feasible solutions are obtained by simple tabu searches that project dual solutions onto primal feasible space. A primal-dual approach is achieved by including a scatter search procedure that further exploits the adaptive memory framework. Computational results from applying the methods to a standard set of benchmark problems disclose that the dual RAMP algorithm finds high quality solutions very efficiently and that its primal-dual enhancement is still more effective.     

A simple enhancement of the Esau–Williams heuristic for the capacitated minimum spanning tree problem

The Esau–Williams algorithm is one of the best known heuristics for the capacitated minimum spanning tree problem. This paper describes a simple enhancement of this heuristic. On benchmark test problems, the modified method does not result in much larger computation times and almost always produces lower solution values than does the Esau–Williams algorithm. The improvements are often significant.     

Dynamic programming based heuristics for the topological design of local access networks

This paper deals with the terminal layout problem, which is a problem arising in data communication network design. The problem consists of finding the best way to link terminals to a computer site and, in graph-theoretical terms, it resorts to determining a minimal spanning tree with an additional constraint (CMST). We present a class of heuristics that combine dynamic programming with clustering and decomposition techniques. More specifically, the original problem is transformed, either by clustering or decomposition, in order to obtain smaller size problems that can be handled by a dynamic programming approach. Such heuristics were specifically aimed at improving solutions produced by the Esau-Williams algorithm, which is one of the most effective heuristics presented in the literature for the CMST. Actually, computational experience confirms that such improvements can be achieved by the new heuristic.This research was partially supported by JNICT (Junta Nacional de Investigação Científica e Tecnológica) under Research Contract No. 87383/MIC.     

Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree with an additional cardinality constraint on the sizes of the subtrees incident to a given root node. The CMST problem is an NP-complete problem, and existing exact algorithms can solve only small size problems. Currently, the best available heuristic procedures for the CMST problem are tabu search algorithms due to Amberg et al. and Sharaiha et al. These algorithms use two-exchange neighborhood structures that are based on exchanging a single node or a set of nodes between two subtrees. In this paper, we generalize their neighborhood structures to allow exchanges of nodes among multiple subtrees simultaneously; we refer to such neighborhood structures as multi-exchange neighborhood structures. Our first multi-exchange neighborhood structure allows exchanges of single nodes among several subtrees. Our second multi-exchange neighborhood structure allows exchanges that involve multiple subtrees. The size of each of these neighborhood structures grows exponentially with the problem size without any substantial increase in the computational times needed to find improved neighbors. Our approach, which is based on the cyclic transfer neighborhood structure due to Thompson and Psaraftis and Thompson and Orlin transforms a profitable exchange into a negative cost subset-disjoint cycle in a graph, called an improvement graph, and identifies these cycles using variants of shortest path label-correcting algorithms. Our computational results with GRASP and tabu search algorithms based on these neighborhood structures reveal that (i) for the unit demand case our algorithms obtained the best available solutions for all benchmark instances and improved some; and (ii) for the heterogeneous demand case our algorithms improved the best available solutions for most of the benchmark instances with improvements by as much as 18%. The running times our multi-exchange neighborhood search algorithms are comparable to those taken by two-exchange neighborhood search algorithms. Received: September 1998 / Accepted: March 2001?Published online May 18, 2001     

Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem

This paper studies heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree using edges that are as similar as possible. Given an undirected labelled connected graph, the minimum labelling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. This problem has been shown to be NP-hard. A Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighbourhood Search (VNS) are proposed in this paper. They are compared with other algorithms recommended in the literature: the Modified Genetic Algorithm and the Pilot Method. Nonparametric statistical tests show that the heuristics based on GRASP and VNS outperform the other algorithms tested. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristics.     

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.     

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.     

Flows on hypergraphs

We consider the capacitated minimum cost flow problem on directed hypergraphs. We define spanning hypertrees so generalizing the spanning tree of a standard graph, and show that, like in the standard and in the generalized minimum cost flow problems, a correspondence exists between bases and spanning hypertrees. Then, we show that, like for the network simplex algorithms for the standard and for the generalized minimum cost flow problems, most of the computations performed at each pivot operation have direct hypergraph interpretations.     

Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree.     

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.     

Local search for the Steiner tree problem in the Euclidean plane

Most heuristics for the Steiner tree problem in the Euclidean plane perform a series of iterative improvements using the minimum spanning tree as an initial solution. We may therefore characterize them as local search heuristics. In this paper, we first give a survey of existing heuristic approaches from a local search perspective, by setting up solution spaces and neighbourhood structures. Secondly, we present a new general local search approach which is based on a list of full Steiner trees constructed in a preprocessing phase. This list defines a solution space on which three neighbourhood structures are proposed and evaluated. Computational results show that this new approach is very competitive from a cost–benefit point of view. Furthermore, it has the advantage of being easy to apply to the Steiner tree problem in other metric spaces and to obstacle avoiding variants.     

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.     

An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

This paper presents a new edge-swap heuristic for generating spanning trees with a minimum number of branch vertices, i.e. vertices of degree greater than two. This problem was introduced in Gargano et al. (Lect Notes Comput Sci 2380:355–365, 2002) and has been called the minimum branch vertices problem by Cerulli et al. (Comput Optim Appl 42:353–370, 2009). The heuristic starts with a random spanning tree and iteratively reduces the number of branch vertices by swapping tree edges with edges not currently in the tree. It can be easily implemented as a multi-start heuristic. We report on extensive computational experiments comparing single-start and multi-start variants on our heuristic with other heuristics previously proposed in the literature.     

Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

Neural and delay based heuristics for the Steiner problem in networks

High speed networks such as the B-ISDN must be adequately equipped to handle multipoint communication in a fast and economical manner. Multicast applications include desktop video conferencing, distance learning, distributed database applications, etc. In networks employing the asynchronous transfer mode (ATM) technology, routing a multicast is achieved by constructing a tree that spans the source and all the destinations. For the purpose of routing, the network is modeled as a weighted, undirected graph. The graph-theoretic solution is to find a minimum Steiner tree for the graph given a set of destinations. This formulation suffices for building multicast trees with a single optimization constraint as would be the xcase for best effort transport. For real-time traffic, however, it is necessary to ensure that the delay between the sender and each of the receivers is bounded. In this case the network is modeled as an undirected graph, where the edges have both a cost and a delay associated with them. The graph-theoretic solution is then to find a constrained minimum Steiner tree such that the delay between the source and each of the destinations does not violate the specified bound. Both of these problems are NP-complete. In this paper we review prior work on the multipoint routing problem and discuss the formulation of the unconstrained and constrained Steiner problems. We use the random neural network (RNN) to significantly improve the quality of trees found by the two existing best heuristics for finding Steiner trees - the minimum spanning tree heuristic and the average distance heuristic. We also develop a new heuristic for finding delay constrained Steiner trees. Experimental results are presented which show that the new heuristics improve significantly over existing ones.     

A Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem

In this paper we propose a hybrid memory adaptive heuristic for solving the Capacitated Minimum Spanning Tree (CMST) problem. We augment the problem formulation with additional non-redundant constraints via use of adaptive memory, to improve upon the performance of an elementary heuristic (the Esau-Williams heuristic). Our methodology is tested against many of the previously reported heuristics for the CMST. We conclude that our generalized procedure performs on par with the best of these approaches in terms of solution quality, while expending a very modest amount of computational effort.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

带区间数据的最小风险斯坦纳树问题

考虑了在带区间数据的不确定网络中, 最小风险和模型以及最小最大风险模型下的斯坦纳树问题. 它们推广了相应模型下的最短路问题和最小支撑树问题, 在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法, 并对算法性能做了理论分析和证明. 结果显示我们的算法具有优良的常数逼近的性质, 能在多项式时间内算出令人满意的解.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.