Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems

This paper presents the first investigation on applying a particle swarm optimization (PSO) algorithm to both the Steiner tree problem and the delay constrained multicast routing problem. Steiner tree problems, being the underlining models of many applications, have received significant research attention within the meta-heuristics community. The literature on the application of meta-heuristics to multicast routing problems is less extensive but includes several promising approaches. Many interesting research issues still remain to be investigated, for example, the inclusion of different constraints, such as delay bounds, when finding multicast trees with minimum cost. In this paper, we develop a novel PSO algorithm based on the jumping PSO (JPSO) algorithm recently developed by Moreno-Perez et al. (Proc. of the 7th Metaheuristics International Conference, 2007), and also propose two novel local search heuristics within our JPSO framework. A path replacement operator has been used in particle moves to improve the positions of the particle with regard to the structure of the tree. We test the performance of our JPSO algorithm, and the effect of the integrated local search heuristics by an extensive set of experiments on multicast routing benchmark problems and Steiner tree problems from the OR library. The experimental results show the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Vertex-Disjoint Packing of Two Steiner Trees: polyhedra and branch-and-cut

Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided. Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minutes. Received: August 1999 / Accepted: January 2001?Published online April 12, 2001     

Packing strong subgraph in digraphs

In this paper, we study two types of strong subgraph packing problems in digraphs, including internally disjoint strong subgraph packing problem and arc-disjoint strong subgraph packing problem. These problems can be viewed as generalizations of the famous Steiner tree packing problem and are closely related to the strong arc decomposition problem. We first prove the NP-completeness for the internally disjoint strong subgraph packing problem restricted to symmetric digraphs and Eulerian digraphs. Then we get inapproximability results for the arc-disjoint strong subgraph packing problem and the internally disjoint strong subgraph packing problem. Finally we study the arc-disjoint strong subgraph packing problem restricted to digraph compositions and obtain some algorithmic results by utilizing the structural properties.     

A deep-submicron steiner tree

An A-Tree is a rectilinear Steiner tree in which every sink is connected to a driver by a shortest length path, while simultaneously minimizing total wire length. This paper presents a polynomial approximation algorithm for the generalized version of an A-Tree problem with upper-bounded delays along each path from the driver to the sinks and with restrictions on the number of Steiner nodes. We refer to it as “Deep-submicron Steiner tree”, as minimizing the number of Steiner nodes is crucial for signal integrity issues in deep-submicron Very-Large-Scaled-Integrated-circuit (VLSI) designs. The idea behind the algorithm is to control two parameters in order to construct a feasible (with respect to the paths delays and the number of Steiner nodes) tree of small cost.The simulation results show the high efficiency of our approach.     

Solving the Graphical Steiner Tree Problem Using Genetic Algorithms

We develop a genetic algorithm (GA) to solve the Steiner Minimal Tree problem in graphs. To apply the GA paradigm, a simple bit string representation is used, where a 1 or 0 corresponds to whether or not a node is included in the solution tree. The standard genetic operators — selection, crossover and mutation — are applied to both random and seeded initial populations of representations. Various parameters within the algorithm have to be set and we discuss how and why we have selected the values used. A standard set of graph problems used extensively in the comparison of Steiner tree algorithms has been solved using our resulting algorithm. We report our results (which are encouragingly good) and draw conclusions.     

Steiner tree packing revisited

The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some ??classical?? STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by employing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.     

The role of Steiner hulls in the solution to Steiner tree problems

ASteiner tree problem on the plane is that of finding a minimum lengthSteiner tree connecting a given setK ofterminals and lying within a given regionR of the Euclidean plane; it includes as special cases the Euclidean Steiner minimal tree problem (ESMT), the rectilinear Steiner tree problem (RST), and the Steiner tree problem on graphs (STG). ASteiner hull forK inR generically refers to any subregion ofR known to contain a Steiner tree. This paper gives a survey of the role of Steiner hulls in the Steiner tree problem. The significance of Steiner hulls in the efficient solution of Steiner tree problems is outlined, and then a compendium is given of the known Steiner hull constructions for ESMT, RST, and STG problems.     

Swap-vertex based neighborhood for Steiner tree problems

Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swap-vertex move operator which can be used as a basic element of any neighborhood search heuristic to solve many STP variants. Given the incumbent solution tree T, the swap-vertex move operator exchanges a vertex in T with another vertex out of T, and then attempts to construct a minimum spanning tree, leading to a neighboring solution (if feasible). We develop a series of dynamic data structures, which allow us to efficiently evaluate the feasibility of swap-vertex moves. Additionally, in order to discriminate different swap-vertex moves corresponding to the same objective value, we also develop an auxiliary evaluation function. We present a computational assessment based on a number of challenging problem instances (corresponding to three representative STP variants) which clearly shows the effectiveness of the techniques introduced in this paper. Particularly, as a key element of our KTS algorithm which participated in the 11th DIMACS implementation challenge, the swap-vertex operator as well as the auxiliary evaluation function contributed significantly to the excellent performance of our algorithm.     

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

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

三维欧氏Steiner最小树的Delaunay四面体网格混合智能算法

Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。     

The steiner tree packing problem in VLSI design

In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.     

Gradient-constrained discounted Steiner trees II: optimally locating a discounted Steiner point

A gradient-constrained discounted Steiner tree is a network interconnecting given set of nodes in Euclidean space where the gradients of the edges are all no more than an upper bound which defines the maximum gradient. In such a tree, the costs are associated with its edges and values are associated with nodes and are discounted over time. In this paper, we study the problem of optimally locating a single Steiner point in the presence of the gradient constraint in a tree so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An edge in the tree is labelled as a b edge, or a m edge, or an f edge if the gradient between its endpoints is greater than, or equal to, or less than the maximum gradient respectively. The set of edge labels at a discounted Steiner point is called its labelling. The optimal location of the discounted Steiner point is obtained for the labellings that can occur in a gradient-constrained discounted Steiner tree. In this paper, we propose the gradient-constrained discounted Steiner point algorithm to optimally locate the discounted Steiner point in the presence of a gradient constraint in a network. This algorithm is applied to a case study. This problem occurs in underground mining, where we focus on the optimization of underground mine access to obtain maximum NPV in the presence of a gradient constraint. The gradient constraint defines the navigability conditions for trucks along the underground tunnels.     

Minimal curvature-constrained networks

This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon.     

On Steiner trees and minimum spanning trees in hypergraphs

The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach.     

A node-based layered graph approach for the Steiner tree problem with revenues,budget and hop-constraints

The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large-scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the underlying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25.     

Steiner Trees on Curved Surfaces

 The Steiner tree problem on surfaces is more complicated than the corresponding one in the Euclidean plane. There are not many results on it to date. In this paper we first make a comparison of Steiner minimal trees on general curved surfaces with Steiner minimal trees in the Euclidean plane. Then, we focus our study on the Steiner trees on spheres. In particular, we detail the properties of locally minimal Steiner points, and the Steiner points for spherical triangles. Received: August 18, 1997 Final version received: March 16, 1998     

A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in <Emphasis Type="Italic">ℜ</Emphasis><Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a heuristic for the Euclidean Steiner tree problem in ℜ ^d for d≥2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in ℜ ^d for 2≤d≤5.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

On properties of geometric random problems in the plane

In this paper, we present results dealing with properties of well-known geometric random problems in the plane, together with their motivations. The paper specifically concentrates on the traveling salesman and minimum spanning tree problems, even though most of the results apply to other problems such as the Steiner tree problem and the minimum weight matching problem.