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 simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

A multicast routing algorithm based on searching in directed graph

Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.     

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.     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

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.     

Using a TSP heuristic for routing order pickers in warehouses

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin–Kernighan–Helsgaun) TSP heuristic. Additionally, we examine if combining problem-specific solution concepts from dedicated heuristics with high-quality local search features could be useful. Lastly, we verify whether the sophistication of ‘state-of-the-art’ local search heuristics is necessary for routing order pickers in warehouses, or whether a subset of features suffices to generate high-quality solutions.     

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.      

A branch-and-cut algorithm for the Steiner tree problem with delays

In this paper, we investigate the Steiner tree problem with delays, which is a generalized version of the Steiner tree problem applied to multicast routing. For this challenging combinatorial optimization problem, we present an enhanced directed cut-based MIP formulation and an exact solution method based on a branch-and-cut approach. Our computational study reveals that the proposed approach can optimally solve hard dense instances.     

Hybrid co-evolutionary particle swarm optimization and noising metaheuristics for the delay constrained least cost path problem

This paper presents a co-evolutionary particle swarm optimization (PSO) algorithm, hybridized with noising metaheuristics, for solving the delay constrained least cost (DCLC) path problem, i.e., shortest-path problem with a delay constraint on the total “cost” of the optimal path. The proposed algorithm uses the principle of Lagrange relaxation based aggregated cost. It essentially consists of two concurrent PSOs for solving the resulting minimization-maximization problem. The main PSO is designed as a hybrid PSO-noising metaheuristics algorithm for efficient global search to solve the minimization part of the DCLC-Lagrangian relaxation by finding multiple shortest paths between a source-destination pair. The auxiliary/second PSO is a co-evolutionary PSO to obtain the optimal Lagrangian multiplier for solving the maximization part of the Lagrangian relaxation problem. For the main PSO, a novel heuristics-based path encoding/decoding scheme has been devised for representation of network paths as particles. The simulation results on several networks with random topologies illustrate the efficiency of the proposed hybrid algorithm for the constrained shortest path computation problems.     

Network delay inference from additive metrics

We use computational phylogenetic techniques to solve a central problem in inferential network monitoring. More precisely, we design a novel algorithm for multicast‐based delay inference, that is, the problem of reconstructing delay characteristics of a network from end‐to‐end delay measurements on network paths. Our inference algorithm is based on additive metric techniques used in phylogenetics. It runs in polynomial time and requires a sample of size only poly(log n). We also show how to recover the topology of the routing tree. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Branch-and-price algorithm for a multicast routing problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Variable neighborhood search for the vertex weighted k-cardinality tree problem

This paper presents some new heuristics based on variable neighborhood search to solve the vertex weighted k-cardinality tree problem. An efficient local search procedure is also developed for use within these heuristics. Our computational results demonstrate that the new heuristics substantially outperform the state-of-the-art methodologies, including a tabu search and genetic algorithm recently proposed in the literature. We also show that a decomposition approach is best for larger problem sizes than previously investigated. Thus, our findings advance in a significant way the capacity to solve this important class of problems.     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows

We propose a new population-based hybrid meta-heuristic for the periodic vehicle routing problem with time windows. This meta-heuristic is a generational genetic algorithm that uses two neighborhood-based meta-heuristics to optimize offspring. Local search methods have previously been proposed to enhance the fitness of offspring generated by crossover operators. In the proposed method, neighborhood-based meta-heuristics are used for their capacity to escape local optima, and deliver optimized and diversified solutions to the population of the next generation. Furthermore, the search performed by the neighborhood-based meta-heuristics repairs most of the constraint violations that naturally occur after the application of the crossover operators. The genetic algorithm we propose introduces two new crossover operators addressing the periodic vehicle routing problem with time windows. The two crossover operators are seeking the diversification of the exploration in the solution space from solution recombination, while simultaneously aiming not to destroy information about routes in the population as computing routes is NP-hard. Extensive numerical experiments and comparisons with all methods proposed in the literature show that the proposed methodology is highly competitive, providing new best solutions for a number of large instances.     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming

In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem (BQP). These heuristics are well suited for the incorporation into meta-heuristics such as evolutionary algorithms. Their performance is compared for 115 problem instances. All methods are capable of producing high quality solutions in short time. In particular, the greedy heuristic is able to find near optimum solutions a few percent below the best-known solutions, and the local search procedures are sufficient to find the best-known solutions of all problem instances with n 100. The k-opt local searches even find the best-known solutions for all problems of size n 250 and for 11 out of 15 instances of size n = 500 in all runs. For larger problems (n = 500, 1000, 2500), the heuristics appear to be capable of finding near optimum solutions quickly. Therefore, the proposed heuristics—especially the k-opt local search—offer a great potential for the incorporation in more sophisticated meta-heuristics.