Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

基于MSTP协议的一致性测试设计

MSTP协议是针对STP收敛速度慢，RSTP不能进行基于802.1Q的流量分担等情况下提出的一种新的多域生成树协议。在扼要介绍此协议的实现原理的基础上，设计了针对此协议一致性的测试方法和测试组织，并应用于交换机的实际测试中，同时，给出了具体的测试实例，并对测试结果进行了分析。     

CMST问题的新算法

本文提出了解决按约束条件求最小代价生成树(简称CMST)问题的两个新算法,即给定结点数N,每个结点的负载,链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树结构.两个新算法的计算复杂性均为O(N~2).计算结果表明,新算法所得结果的代价低于几个现有算法,而计算复杂性比现有算法小得多.     

多生成树协议实现负载均衡实验的设计与实施

生成树协议能够解决环路带来的问题,提高网络的健壮性和稳定性。但是,简单地部署生成树协议并不能充分地利用链路资源,造成网络资源浪费。依据多生成树协议（MSTP）理论,设计了一种实验方案能同时实现链路冗余和负载均衡,提高网络整体性能。     

On exact solutions for the Minmax Regret Spanning Tree problem

The Minmax Regret Spanning Tree problem is studied in this paper. This is a generalization of the well-known Minimum Spanning Tree problem, which considers uncertainty in the cost function. Particularly, it is assumed that the cost parameter associated with each edge is an interval whose lower and upper limits are known, and the Minmax Regret is the optimization criterion. The Minmax Regret Spanning Tree problem is an NP-Hard optimization problem for which exact and heuristic approaches have been proposed. Several exact algorithms are proposed and computationally compared with the most effective approaches of the literature. It is shown that a proposed branch-and-cut approach outperforms the previous approaches when considering several classes of instances from the literature.     

An optimization framework for the energy management of carrier ethernet networks with Multiple Spanning Trees

We propose an energy management framework to optimize the energy consumption of networks using the Multiple Spanning Tree Protocol such as Carrier Grade Ethernet networks. The objective is to minimize the energy consumption of nodes and links while considering QoS constraints. The energy management is done through the Multiple Spanning Tree Protocol (MSTP) by choosing from a given set the most appropriate Spanning Trees and the most appropriate edges to operate while respecting the traffic demands. A trade-off framework between energy consumption and network performance is proposed. Results show that it is possible to achieve a good traffic engineering while operating the network closer to the minimum energy value.     

Design of capacitated minimum spanning tree with uncertain cost and demand parameters

The classical Capacitated Minimum Spanning Tree Problem (CMSTP) deals with finding a minimum-cost spanning tree so that the total demand of the vertices in each subtree does not exceed the capacity limitation. In most of the CMSTP models, the edge costs and the demands of the vertices in the network are assumed to be known with certainty. This paper considers the CMSTP model, where the edge costs and/or the demands are only approximately known. A fast approximate reasoning algorithm, which is based on the Esau-Williams savings heuristic and fuzzy logic rules, is proposed. The computational results of the study based on the proposed approach are also reported.     

可持续WSN中基于能量采集感知的中继节点部署算法

基于可持续无线传感网络WSNs(Wireless Sensor Networks),提出基于能量采集感知的中继节点部署EHA-DRN(Energy Harvesting Aware-based Deploying Relay Nodes algorithm)算法.EHA-DRN算法利用功率beacon包给网络内节点补给能量.先依据节点的能量采集率,计算边权重,再利用克鲁斯卡尔(Kruskal)算法构建最小生成树.然后,依据最小生成树,检测不能完成数据传输任务的低能量节点.最后,在这些节点附近部署中继节点,从而修复覆盖空洞,保持网络连通.实验数据表明,与MBA算法相比,提出的EHA-DRN算法降低了部署成本,并提高了数据包传递率.     

Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity,properties and formulations

We consider a variant of the Min-Degree Constrained Minimum Spanning Tree Problem where the central and terminal nodes are fixed a priori. We prove that the optimization problem is NP-Hard even for complete graphs and the feasibility problem is NP-Complete even if there is an edge between each central and each terminal in the input graph. Actually, this complexity result still holds when the minimum degree of each central node is restricted to be a same value d ≥ 2. We derive necessary and sufficient conditions for feasibility. We present several integer linear programming formulations – based on known formulations for the minimum spanning tree problem – along with a theoretical comparison among the lower bounds provided by their linear relaxations. We propose three Lagrangian heuristics. Computational experiments compare the performances of the heuristics and the formulations.     

WDM网络中实时组播的分布式路由与波长分配算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由与波长分配是十分困难的。该文提出了一种用于建立实时组播连接的分布式路由与波长分配算法。该算法将路由与波长分配统一进行,大大减少连接的建立时间。组播路由算法以Prim最小生成树算法和K-度宽度优先搜索方法为基础,生成一棵满足给定延迟时限的最小成本树。波长分配使用最少波长转换和负载平衡策略。     

无线传感器网络延迟约束的MDC分布式轨道规划算法

针对引入移动元素后无线传感器网络数据面临的收集延时问题,提出了一种分布式的移动数据收集器(MDC)轨道规划算法.首先给出基于k跳支配集的MDC最小时延规划问题定义,并证明它是NP-hard.在基于集结的数据收集模式汇总,k跳支配节点作为集结点缓存传感节点收集的数据并在MDC到达时上传.然后,提出了一种高效的基于k跳支配集的MDC轨迹构建算法.算法通过分布式的k-跳支配集算法找出网络中的支配节点,进而通过Prim算法和Christofides近似算法对MDC的移动轨道进行规划.算法的正确性、k-跳支配集的界、时间复杂性和消息交换复杂性通过理论进行分析.最后,通过仿真实验验证了算法的有效性.仿真结论表明,与同类算法相比,所提出算法能够显著缩短MDC的移动轨迹,因而可以降低网络延迟.     

Min‐degree constrained minimum spanning tree problem: complexity,properties, and formulations

This paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead. The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.     

基于欧氏最小生成树的无线Ad Hoc网络容量研究

无线Adhoc网络容量是当前的一个研究热点。在Gupta和Kumar提出的协议模型和物理模型基础上,推导了无线Adhoc网络基于欧氏最小生成树的单播、多播容量,且指出当多播组尺寸小于总的网络节点数时,多播容量比单播容量大。基于NS-2的仿真实验验证了多播容量上限是有效的。     

A Combined column generation and heuristics for railway short-term rolling stock planning with regular inspection constraints

The aim of railway rolling stock planning problem is to find an optimal allocation of train-sets for a given set of trips in the train timetable in order to minimize the total cost. We propose a column generation and Lagrangian relaxation heuristics for short-term rolling stock planning problems with regular inspection constraints. The problem is formulated as a subtour traveling salesman problem to find a set of elementary shortest cycles that cover all trips in the timetable. In the proposed method, a tight lower bound is obtained from the continuous relaxation of Dantzig–Wolfe reformulation by column generation. The pricing problem can be formulated as an elementary shortest cycle problem with resource constraints. A labeling algorithm is applied to solve the pricing problem. In order to reduce the computational effort, we apply a general state space augmenting algorithm to solve the pricing problems. Computational results show that the proposed column generation and Lagrangian relaxation heuristics can find good lower and upper bounds for 300 trips within reasonable computing time.     

最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.     

ABridges: Scalable,self-configuring Ethernet campus networks

This article describes a scalable, self-configuring architecture for campus networks, the ABridges architecture. It is a two-tiered hierarchy of layer two switches in which network islands running independent rapid spanning tree protocols communicate through a core formed by island root bridges (ABridges). ABridges use AMSTP, a simplified and self configuring version of MSTP protocol, to establish shortest paths in the core using multiple spanning tree instances, one instance rooted at each core edge ABridge. The architecture is very efficient in terms of network usage and path length due to the ability of AMSTP to provide optimum paths in the core mesh, while RSTP is used to aggregate efficiently the traffic at islands networks, where sparsely connected, tree-like topologies are frequent and recommended. Convergence speed is as fast as existing Rapid Spanning Tree and Multiple Spanning Tree Protocols.     

On the Huffman and Alphabetic Tree Problem with General Cost Functions

We address generalized versions of the Huffman and Alphabetic Tree Problem where the cost caused by each individual leaf i, instead of being linear, depends on its depth in the tree by an arbitrary function. The objective is to minimize either the total cost or the maximum cost among all leaves. We review and extend the known results in this direction and devise a number of new algorithms and hardness proofs. It turns out that the Dynamic Programming approach for the Alphabetic Tree Problem can be extended to arbitrary cost functions, resulting in a time O(n ⁴) optimal algorithm using space O(n ³). We identify classes of cost functions where the well-known trick to reduce the runtime by a factor of n via a “monotonicity” property can be applied. For the generalized Huffman Tree Problem we show that even the k-ary version can be solved by a generalized version of the Coin Collector Algorithm of Larmore and Hirschberg (in Proc. SODA’90, pp. 310–318, 1990) when the cost functions are nondecreasing and convex. Furthermore, we give an O(n ²logn) algorithm for the worst case minimization variants of both the Huffman and Alphabetic Tree Problem with nondecreasing cost functions. Investigating the limits of computational tractability, we show that the Huffman Tree Problem in its full generality is inapproximable unless P = NP, no matter if the objective function is the sum of leaf costs or their maximum. The alphabetic version becomes NP-hard when the leaf costs are interdependent.     

MSN网络的优化问题研究

研究了由MSN节点组成的应用层组播网络,讨论了度约束最小直径生成树(D-MDST)问题,并给出了求解该问题的BCT算法。提出了一种新的生成树编码方法——过程控制编码,该编码将启发式算法与遗传算法结合起来且具有编码简单、译码方便、适用常规遗传算子等优点。给出了基于该种编码的遗传算法,并将BCT算法作为过程控制编码的译码器。仿真结果表明了该遗传算法的有效性。     

WDM网络中实时组播的分布式优化RWA算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由选择与波长分配是十分困难的。论文提出了一种用于建立实时组播连接的分布式路由选择与波长分配算法。该算法将路由选择与波长分配统一进行,大大减少连接的建立时间。组播路由算法以Prim最小生成树算法为基础,生成一棵满足给定延迟时限的最小成本树。波长分配使用最少波长转换和同一波长最长使用策略。     

The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm

In this paper we consider the quadratic minimum spanning tree problem (QMSTP) which is known to be NP-hard. Given a complete graph, the QMSTP consists of finding a minimum spanning tree (MST) where interaction costs between pairs of edges are prescribed. A Lagrangian relaxation procedure is devised and an efficient local search algorithm with tabu thresholding is developed. Computational experiments are reported on standard test instances, randomly generated test instances and quadratic assignment problem (QAP) instances from the QAPLIB by using a transformation scheme. The local search heuristic yields very good performance and the Lagrangian relaxation procedure gives the tightest lower bounds for all instances when compared to previous lower bounding approaches.