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.     

Lower and upper bounds for the spanning tree with minimum branch vertices

We study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms.     

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.     

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.     

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.     

Multirate multicast service provisioning I: an algorithm for optimal price splitting along multicast trees

In this two-part paper we present a general framework for addressing the optimal rare control problem in multirate multicast where the objective is the maximization of a social welfare function expressed by the sum of the users’ utility functions. Specifically, we propose a market-based mechanism that satisfies the informational constraints imposed by the decentralization of information in multirate multicast service provisioning, and achieves an optimal solution to the corresponding centralized optimization problem. In Part I we discover properties of an optimal solution to the centralized problem. Based on these properties, we develop a distributed algorithm that determines how link prices are split among users whose connections along a multicast tree share the same link.     

Fast algorithms for fragmentable items bin packing

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92 % of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99 % of all 4500 runs. No run lasted longer than 220 ms.     

Optimal multicast route packing

This paper considers the hop-constrained multicast route packing problem with a bandwidth reservation to build QoS-guaranteed multicast routing trees with a minimum installation cost. Given a set of multicast sessions, each of which has a hop limit constraint and a bandwidth requirement, the problem is to determine the set of multicast routing trees in an arc-capacitated network with the objective of minimizing the cost. For the problem, we propose a branch-and-cut-and-price algorithm, which can be viewed as a branch-and-bound method incorporating both the strong cutting plane algorithm and the column generation method. We implemented and tested the proposed algorithm on randomly generated problem instances with sizes up to 30 nodes, 570 arcs, and 10 multicast sessions. The test results show that the algorithm can obtain the optimal solution to practically sized problem instances within a reasonable time limit in most cases.     

Optimality properties of speed optimization for a vessel operating with time window constraint

We consider speed optimization for a vessel that has to arrive at every port along its voyage within a time window at each port. The objective of the problem is to minimize the vessel’s bunker fuel cost given that fuel consumption rate is a convex function of speed. The intent of this paper is to establish the optimality properties for this problem and show that a solution with such properties (which we refer to as a good solution) is unique and optimal. The optimality properties established in this paper facilitate the proof of exactness for existing and future algorithms, as one needs only to show that the solution provided by an algorithm satisfies the definition of a good solution. As an illustration, we show how we can apply our results to prove the exactness of an existing algorithm in literature. Our work contributes to the understanding of the problem’s optimality structure, which will provide intuition for development of algorithms for this problem.     

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.     

A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem

In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem.     

An exact solution framework for the minimum cost dominating tree problem

The minimum cost dominating tree problem is a recently introduced NP-hard problem, which consists of finding a tree of minimal cost in a given graph, such that for every node of the graph, the node or one of its neighbours is in the tree. We present an exact solution framework combining a primal–dual heuristic with a branch-and-cut approach based on a transformation of the problem into a Steiner arborescence problem with an additional constraint. The effectiveness of our approach is evaluated on testbeds proposed in literature containing instances with up to 500 nodes. Our framework manages to solve all but four instances from literature to proven optimality within 3 h (most of them in a few seconds). We provide optimal solution values for 69 instances from literature for which the optimal solution was previously unknown.     

几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m 1)(log r/√m 1 1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.     

Effective algorithm and heuristic for the generalized assignment problem

We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual, provides an upper bound. Our key contribution in this paper is a new heuristic, applied at each iteration of the SM, which tries to exploit the solution of the relaxed problem, by solving a smaller generalized assignment problem. The feasible solution found is then subjected to a solution improvement heuristic. We consider processing the root node as a Lagrangian heuristic. Computational comparisons are made with new existing methods.     

Solving the post enrolment course timetabling problem by ant colony optimization

In this work we present a new approach to tackle the problem of Post Enrolment Course Timetabling as specified for the International Timetabling Competition 2007 (ITC2007), competition track 2. The heuristic procedure is based on Ant Colony Optimization (ACO) where artificial ants successively construct solutions based on pheromones (stigmergy) and local information. The key feature of our algorithm is the use of two distinct but simplified pheromone matrices in order to improve convergence but still provide enough flexibility for effectively guiding the solution construction process. We show that by parallelizing the algorithm we can improve the solution quality significantly. We applied our algorithm to the instances used for the ITC2007. The results document that our approach is among the leading algorithms for this problem; in all cases the optimal solution could be found. Furthermore we discuss the characteristics of the instances where the algorithm performs especially well.     

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.     

Globally solving a class of optimal power flow problems in radial networks by tree reduction

We devise an algorithm for finding the global optimal solution of the so-called optimal power flow problem for a class of power networks with a tree topology, also called radial networks, for which an efficient and reliable algorithm was not previously known. The algorithm we present is called the tree reduction/expansion method, and is based on an equivalence between the input network and a single-node network. Finally, our numerical experiments demonstrate the reliability and robustness of our algorithm.     

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.     

Register Allocation in Structured Programs

In this article we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted tostructured programswhich we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the previous restriction the resulting coloring problem is NP-complete.We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and to apply our algorithm. We show that this problem is Max SNP hard. However, we define the notion of anapproximate articulation pointand we give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.