Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

Degree-constrained minimum spanning tree problem with uncertain edge weights

Uncertainty theory has shown great advantages in solving many nondeterministic problems, one of which is the degree-constrained minimum spanning tree (DCMST) problem in uncertain networks. Based on different criteria for ranking uncertain variables, three types of DCMST models are proposed here: uncertain expected value DCMST model, uncertain α-DCMST model and uncertain most chance DCMST model. In this paper, we give their uncertainty distributions and fully characterize uncertain expected value DCMST and uncertain α-DCMST in uncertain networks. We also discover an equivalence relation between the uncertain α-DCMST of an uncertain network and the DCMST of the corresponding deterministic network. Finally, a related genetic algorithm is proposed here to solve the three models, and some numerical examples are provided to illustrate its effectiveness.     

Enhanced second order algorithm applied to the capacitated minimum spanning tree problem

Given a centralized undirected graph with costs associated with its edges, the capacitated minimum spanning tree problem is to find a minimum cost spanning tree of the given graph, subject to a capacity constraint in all subtrees incident in the central node. As the problem is NP-hard, we propose an enhanced version of the well-known second order algorithm, described in [Karnaugh M. A new class of algorithms for multipoint network optimization. IEEE Transactions on Communications 1976;COM-24:500–5.]. The original version of this algorithm is based on a look-ahead strategy, used for a tentative inclusion of a constraint to the problem, performed in each iteration. In the new enhanced version, we propose the inclusion of look-behind steps, which can be seen as the reverse of the look-ahead procedure. Therefore and using some memory features, the method can continue even when facing the traditional stopping criterion of the original algorithm. Computational experiments showing the effectiveness of the new method on benchmark instances are reported.     

最小耗费生成树剔除算法及其正确性证明

文章提出了一种新的最小耗费生成树的算法,并对其正确性进行了证明。该算法通过从原图中逐步别除边来形成生成树,特别适用于当原图中边数较少(相对于顶点数),或原图规模不大的情形。     

A multiobjective swarm intelligence approach based on artificial bee colony for reliable DNA sequence design

The design of reliable DNA sequences is crucial in many engineering applications which depend on DNA-based technologies, such as nanotechnology or DNA computing. In these cases, two of the most important properties that must be controlled to obtain reliable sequences are self-assembly and self-complementary hybridization. These processes have to be restricted to avoid undesirable reactions, because in the specific case of DNA computing, undesirable reactions usually lead to incorrect computations. Therefore, it is important to design robust sets of sequences which provide efficient and reliable computations. The design of reliable DNA sequences involves heterogeneous and conflicting design criteria that do not fit traditional optimization methods. In this paper, DNA sequence design has been formulated as a multiobjective optimization problem and a novel multiobjective approach based on swarm intelligence has been proposed to solve it. Specifically, a multiobjective version of the Artificial Bee Colony metaheuristics (MO-ABC) is developed to tackle the problem. MO-ABC takes in consideration six different conflicting design criteria to generate reliable DNA sequences that can be used for bio-molecular computing. Moreover, in order to verify the effectiveness of the novel multiobjective proposal, formal comparisons with the well-known multiobjective standard NSGA-II (fast non-dominated sorting genetic algorithm) were performed. After a detailed study, results indicate that our artificial swarm intelligence approach obtains satisfactory reliable DNA sequences. Two multiobjective indicators were used in order to compare the developed algorithms: hypervolume and set coverage. Finally, other relevant works published in the literature were also studied to validate our results. To this respect the conclusion that can be drawn is that the novel approach proposed in this paper obtains very promising DNA sequences that significantly surpass other results previously published.     

求解度约束最小生成树的新的快速算法

针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。     

A filter-and-fan algorithm for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new CMST heuristic algorithm that effectively combines the classical node-based and tree-based neighborhoods embodied in a filter-and-fan (F&F) approach, a local search procedure that generates compound moves in a tree search fashion. The overall algorithm is guided by a multi-level oscillation strategy used to trigger each type of neighborhood while allowing the search to cross feasibility boundaries. Computational results carried out on a standard set of 135 benchmark problems show that a simple F&F design competes effectively with prior CMST metaheuristics, rivaling the best methods, which are significantly more complex.     

Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

The multi-criteria minimum spanning tree problem based genetic algorithm

Minimum spanning tree (MST) problem is of high importance in network optimization and can be solved efficiently. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problems in the real world, but it is difficult for traditional optimization technique to deal with. In this paper, a non-generational genetic algorithm (GA) for mc-MST is proposed. To keep the population diversity, this paper designs an efficient crossover operator by using dislocation a crossover technique and builds a niche evolution procedure, where a better offspring does not replace the whole or most individuals but replaces the worse ones of the current population. To evaluate the non-generational GA, the solution sets generated by it are compared with solution sets from an improved algorithm for enumerating all Pareto optimal spanning trees. The improved enumeration algorithm is proved to find all Pareto optimal solutions and experimental results show that the non-generational GA is efficient.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

A simpler minimum spanning tree verification algorithm

The problem considered here is that of determining whether a given spanning tree is a minimal spanning tree. In 1984 Komlós presented an algorithm which required only a linear number of comparisons, but nonlinear overhead to determine which comparisons to make. We simplify his algorithm and give a linear-time procedure for its implementation in the unit cost RAM model. The procedure uses table lookup of a few simple functions, which we precompute in time linear in the size of the tree.     

A new grouping genetic algorithm approach to the multiple traveling salesperson problem

The multiple traveling salesperson problem (MTSP) is an extension of the well known traveling salesperson problem (TSP). Given m > 1 salespersons and n > m cities to visit, the MTSP seeks a partition of cities into m groups as well as an ordering among cities in each group so that each group of cities is visited by exactly one salesperson in their specified order in such a way that each city is visited exactly once and sum of total distance traveled by all the salespersons is minimized. Apart from the objective of minimizing the total distance traveled by all the salespersons, we have also considered an alternate objective of minimizing the maximum distance traveled by any one salesperson, which is related with balancing the workload among salespersons. In this paper, we have proposed a new grouping genetic algorithm based approach for the MTSP and compared our results with other approaches available in the literature. Our approach outperformed the other approaches on both the objectives.     

Computing all efficient solutions of the biobjective minimum spanning tree problem

A common way of computing all efficient (Pareto optimal) solutions for a biobjective combinatorial optimisation problem is to compute first the extreme efficient solutions and then the remaining, non-extreme solutions. The second phase, the computation of non-extreme solutions, can be based on a “k-best” algorithm for the single-objective version of the problem or on the branch-and-bound method. A k-best algorithm computes the k-best solutions in order of their objective values. We compare the performance of these two approaches applied to the biobjective minimum spanning tree problem. Our extensive computational experiments indicate the overwhelming superiority of the k-best approach. We propose heuristic enhancements to this approach which further improve its performance.     

基于改进遗传算法的最小生成树算法

以图论和改进遗传算法为基础,提出了一种求最小生成树的遗传算法。该算法采用二进制表示最小树问题,并设计出相应的适应度函数、算子以及几种控制策略,以提高执行速度和进化效率。传统算法一次只能得到一个候选解。用该算法对其求解,可以在较短的时间内以较高的概率获得多个候选解。应用实例表明该算法优于传统算法。     

VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (md$\mathit{md}$-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NP$\mathit{NP}$-hard.     

A faster distributed protocol for constructing a minimum spanning tree

This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27], where Λ(G) denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253-261] have shown that time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].In this paper we refine this claim, and devise a protocol that constructs the MST in rounds, where μ(G,ω) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27] by a factor of . Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.     

基于阈值约束最小生成树算法的区域合并方法

为了解决基于形态学的分水岭分割算法受噪声影响而产生的“过分割”问题,提出了基于阈值约束最小生成树算法的区域合并方法.利用图论中最小生成树算法(prim算法、kruskal算法和boruvka算法),把分割后的区域看作是图的顶点,有相邻关系的区域看作是图的边,相邻区域的特征差异看作是边的权值,通过设置合适的阈值和迭代次数进行区域合并.实验结果表明,该方法保持地物边界的同时能够快速有效地合并“过分割”区域,尤其适用于地物复杂、尺寸较大的遥感图像.