Design of Stacked Self-Healing Rings Using a Genetic Algorithm

Ring structures in telecommunications are taking on increasing importance because of their self-healing properties. We consider a ring design problem in which several stacked self-healing rings (SHRs) follow the same route, and, thus, pass through the same set of nodes. Traffic can be exchanged among these stacked rings at a designated hub node. Each non-hub node may be connected to multiple rings. It is necessary to determine to which rings each node should be connected, and how traffic should be routed on the rings. The objective is to optimize the tradeoff between the costs for connecting nodes to rings and the costs for routing demand on multiple rings. We describe a genetic algorithm that finds heuristic solutions for this problem. The initial generation of solutions includes randomly-generated solutions, complemented by seed solutions obtained by applying a greedy randomized adaptive search procedure (GRASP) to two related problems. Subsequent generations are created by recombining pairs of parent solutions. Computational experiments compare the genetic algorithm with a commercial integer programming package.     

Multicommodity network design with survivability constraints: Some models and algorithms

We survey the main results presented by the author in his PhD thesis, supervised by F. Malucelli, and defended on the 15th March 2003. The thesis is written in English and is available on the Web page http: //www.elet.polimi.it/upload/belotti/thesis.pdf.gz. We investigate three problems, arising in the field of Telecommunication, of networks design with survivability constraints, and solve them through different approaches on a number of real-world network topologies with up to 40 nodes.Received: April 2004MSC classification: 90B10, 90C57     

Two-Connected Augmentation Problems in Planar Graphs

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting subgraph satisfies specified (edge or vertex) connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed.     

A Heuristic Approach for Antenna Positioning in Cellular Networks

The antenna-positioning problem concerns finding a set of sites for antennas from a set of pre-defined candidate sites, and for each selected site, to determine the number and types of antennas, as well as the associated values for each of the antenna parameters. All these choices must satisfy a set of imperative constraints and optimize a set of objectives. This paper presents a heuristic approach for tackling this complex and highly combinatorial problem. The proposed approach is composed of three phases: a constraint-based pre-processing phase to filter out bad configurations, an optimization phase using tabu search, and a post-optimization phase to improve solutions given by tabu search. To validate the approach, computational results are presented using large and realistic data sets.     

Virtual Path Design in Service-Specific ATM Networks

This paper addresses the problem of virtual path management in ATM networks, which is the problem of jointly selecting efficient virtual trunk routes and sizing them to meet end-to-end grade-of-service requirements. The problem is posed over capacitated networks and is formulated as a two-level multi-commodity network flow problem with linear side-constraints (physical layer capacity) and non-linear side constraints (end-to-end/link blocking). Through a variety of examples we show the method (i) generates solutions that agree with engineering judgement, (ii) can solve VP layout management for realistic size networks (of up to 200 nodes) in reasonable time and (iii) provides upper bounds on how far the solution strays from the mathematically optimal design.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

Master-Slave Strategy and Polynomial Approximation

A lot of minimization covering problems on graphs consist in covering vertices or edges by subgraphs verifying a certain property. These problems can be seen as particular cases of set-covering. If the number of subgraphs is polynomial in the order n of the input-graph, then these problems can be approximated within logarithmic ratio by the classical greedy set-covering algorithm. We extend the class of problems approximable by this approach to covering problems where the number of candidate subgraphs is exponential in n, by revisiting an old technique called master-slave and extending it to weighted master or/and slave problems. Finally, we use the master-slave tool to prove some positive approximation results for two network-design and a VLSI-design graph-problems.     

A Comparison of Optimal Methods for Local Access Uncapacitated Network Design

We compare some optimal methods addressed to a problem of local access network design. We see this problem arising in telecommunication as a flow extension of the Steiner problem in directed graphs, thus including as particular cases some alternative approaches based on the spanning tree problem. We work with two equivalent flow formulations for the problem, the first referring to a single commodity and the second being a multicommodity flow model. The objective in both cases is the cost minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center) to every demand node. The weak single commodity flow formulation is solved by a branch-and-bound strategy that applies Lagrangian relaxation for computing the bounds. The strong multicommodity flow model is solved by a branch-and-cut algorithm and by Benders decomposition. The use of a linear programming solver to address both the single commodity and the multicommodity models has also been investigated. Our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where basic optimal solutions to the linear program are automatically integral, so it also solves the combinatorial optimization problem right away. On the other hand, our main conclusion is that a well tailored Benders partitioning approach emerges as a robust method to cope with that fabricated cases where the linear programming relaxation exhibits a gap between the continuous and the integral optimal values.     

A branch-and-cut algorithm for vehicle routing problems

We present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows us to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, we are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. We also present details of the computer implementation and our computational results.     

Financial Optimization Models in Data Networks*

In a competitive market investors in a data network need to give utmost considerations on profitability. They must have clear picture of the size, growth rate and demand for different services. However, the investors’ budget may be limited, and therefore the speed at which the network is rolled out, must be carefully planned to ensure that they can meet profitability targets. We model first the roll out order as combinatorial optimization problems and then extend them as continuous optimization problems. We then implement these models in a practical problem. Numerical studies suggested that the optimization problems have multiple local minima. Therefore, a global optimization technique is used to obtain the global minimum for the continuous variable problem and a combinatorial optimization technique is used to solve the discrete variable problem. Optimal financial indicators are obtained to assess the commercial viability of the network. Finally, we demonstrate that the solution of these optimization problems can provide an investment policy to the investors in data networks. *This network is a combined telephone and data network such as VIP (Voice over Internet Protocol). M. M. Ali: Visitor at the Institute for Mathematics and its Applications, University of Minnesota, USA.     

Homological Properties of Fully Bounded Noetherian Rings

Let R be a fully bounded Noetherian ring of finite global dimension.Then we prove that K dim (R) gldim (R). If, in addition, Ris local, in the sense that R/J(R) is simple Artinian, thenwe prove that R is Auslander-regular and satisfies a versionof the Cohen–Macaulay property. As a consequence, we showthat a local fully bounded Noetherian ring of finite globaldimension is isomorphic to a matrix ring over a local domain,and a maximal order in its simple Artinian quotient ring.     

New coverings of t-sets with (t + 1)-sets

The minimum number of k-subsets out of a v-set such that each t-set is contained in at least one k-set is denoted by C(v, k, t). In this article, a computer search for finding good such covering designs, leading to new upper bounds on C(v, k, t), is considered. The search is facilitated by predetermining automorphisms of desired covering designs. A stochastic heuristic search (embedded in the general framework of tabu search) is then used to find appropriate sets of orbits. A table of upper bounds on C(v, t + 1, t) for v 28 and t 8 is given, and the new covering designs are listed. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 217–226, 1999     

Stochastic Survivable Network Design Problems

In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undirected cut-based model. We use a two-stage branch&cut algorithm for solving the decomposed model to provable optimality. In order to accelerate the computations, we suggest a new cut strengthening technique for the decomposed L-shaped optimality cuts that is computationally fast and easy to implement.     

Fast, Efficient Equipment Placement Heuristics for Broadband Switched or Internet Router Networks

Planning and designing the next generation of IP router or switched broadband networks seems a daunting challenge considering the many complex, interacting factors affecting the performance and cost of such networks. Generally, this complexity implies that it may not even be clear what constitutes a “good” network design for a particular specification. Different network owners or operators may view the same solution differently, depending on their unique needs and perspectives. Nevertheless, we have observed a core common issue arising in the early stages of network design efforts involving leading-edge broadband switched technologies such as ATM, Frame Relay, and SMDS; or even Internet IP router networks. This core issue can be stated as follows: Given a set of service demands for the various network nodes, where should switching or routing equipment be placed to minimize the Installed First Cost of the network? Note that the specified service demands are usually projections for a future scenario and generally entail significant uncertainty. Despite this uncertainty, we have found that network owners and operators generally feel it is worthwhile to obtain high-level advice on equipment placement with a goal of minimizing Installed First Cost. This paper reports on a heuristic approach we have implemented for this problem that has evolved out of real network design projects. A tool with both a Solution Engine and an intuitive Graphical User Interface has been developed. The approach is highly efficient; for example, the tool can often handle LATA-sized networks in seconds or less on a workstation processor. By using only nodal demands rather than the more complex point-to-point demands usually required in tools of this sort, we have created an approach that is not only highly efficient, but is also a better match to real design projects in which demand data is generally scant and highly uncertain.     

几个著名网络的限长路径

设给出了（h,ψ）-η限长路径问题是图论中的Menger定理的变形和推广，在实时容错网络设计和分析中有重要意义。对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数；Bd(D)表示D的顶点子集B中的最小顶点数使得D－B的直径大于d.已证明确定Ad(D)的问题是NPC问题，而且显然有不等式Ad(D)≤Bd(D)。本文考虑D为超立方体网络、De Bruijn网络和Kautz网络，对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D)。     

Commutative Rings Whose Cozero-Divisor Graphs are Unicyclic or of Bounded Degree

Let R be a commutative ring with unity. The cozero-divisor graph of R, denoted by Γ′(R), is a graph with vertex set W*(R), where W*(R) is the set of all nonzero and nonunit elements of R, and two distinct vertices a and b are adjacent if and only if a ? Rb and b ? Ra, where Rc is the ideal generated by the element c in R. Recently, it has been proved that for every nonlocal finite ring R, Γ′(R) is a unicyclic graph if and only if R ? ?₂ × ?₄, ?₃ × ?₃, ?₂ × ?₂[x]/(x ²). We generalize the aforementioned result by showing that for every commutative ring R, Γ′(R) is a unicyclic graph if and only if R ? ?₂ × ?₄, ?₃ × ?₃, ?₂ × ?₂[x]/(x ²), ?₂[x, y]/(x, y)², ?₄[x]/(2x, x ²). We prove that for every positive integer Δ, the set of all commutative nonlocal rings with maximum degree at most Δ is finite. Also, we classify all rings whose cozero-divisor graph has maximum degree 3. Among other results, it is shown that for every commutative ring R, gr(Γ′(R)) ∈ {3, 4, ∞}.     

Cardinality constrained connected balanced partitions of trees under different criteria

In this paper we study the problem of partitioning a tree with $n$ weighted vertices into $p$ connected components. For each component, we measure its gap, that is, the difference between the maximum and the minimum weight of its vertices, with the aim of minimizing the sum of such differences. We present an $O\left(n^3{p}^2\right)$ time and $O\left(n^{3}p\right)$ space algorithm for this problem. Then, we generalize it, requiring a minimum of $ϵ\ge 1$ nodes in each connected component, and provide an $O\left(n^3{p}^2{ϵ}^2\right)$ time and $O\left(n^{3}pϵ\right)$ space algorithm to solve this new problem version. We provide a refinement of our analysis involving the topology of the tree and an improvement of the algorithms for the special case in which the weights of the vertices have a heap structure. All presented algorithms can be straightforwardly extended to other similar objective functions. Actually, for the problem of minimizing the maximum gap with a minimum number of nodes in each component, we propose an algorithm which is independent of $ϵ$ and requires $O(n^{2}logn{p}^2)$ time and $O\left(n^{2}p\right)$ space.     

On Efficient Solutions with Trade-Offs Bounded by Given Values

In this article, efficient solutions of multiple objective optimization problems with trade-offs, bounded by prespecified lower and upper bounds, are investigated. It is shown that one of the existing techniques to obtain these solutions does not work correctly. Furthermore, a new approach is given to approximate the set of such solutions. In addition to theoretical discussions, some clarifying examples are given.     

An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.