MC-based Algorithm for a telecommunication network under node and budget constraints

It is an important issue to design some performance indexes in order to measure the performance for a telecommunication network. Network analysis is an available approach to solve the performance problem for a real-life system. We construct a two-commodity stochastic-flow network with unreliable nodes (arcs and nodes all have several possible capacities and may fail) to model the telecommunication network. In which, all types of commodity are transmitted through the same network simultaneously and compete the capacities. This paper defines the system capacity as a 2-tuple vector, and then proposes a performance index, the probability that the upper bound of the system capacity equals a demand vector subject to the budget constraint. An upper boundary point is a vector representing the capacities of arcs and nodes, and is the maximal vector exactly meeting the demand vector. A simple algorithm based on minimal cuts (or named MC-based algorithm) is then presented to generate all upper boundary points in order to evaluate the performance index. The storage and computational time complexity of this algorithm are also analyzed. The performance evaluation for the multicommodity case can be extended easily.     

On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint

From the quality management and decision making view point, reliability and unreliability are important indices to measure the quality level for a stochastic-flow network. In a multicommodity stochastic-flow network with unreliable nodes, the branches and nodes all have several possible capacities and may fail. Different types of the commodity, which are transmitted through the same network simultaneously, compete the capacities of branches and nodes. In this paper we first define the system capacity as a vector for a multicommodity stochastic-flow network with unreliable nodes. Then we design a performance index which is the probability that the upper bound of the system capacity is a given pattern subject to the budget constraint. It can be applied to evaluate the quality level for such a network. A simple approach based on minimal cuts is thus presented to evaluate the performance index.     

Optimal expansion of capacitated transshipment networks

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use properties of the optimum solution to convert this problem into a parametric network flow problem. The concept of optimum basis structure is used which allows us to consider piecewise linear convex functions without introducing additional arcs. The resulting algorithm yields an optimum solution of the capacity expansion problem for all budget levels less than or equal to the given budget. For integer data, the algorithm performs almost all computations in integers. Detailed computational results are also presented.     

Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer networks and telecommunication networks, the capacity of each arc is stochastic due to failure, maintenance, etc. Hence, the minimum transmission time is not a fixed number. Such a network is named a stochastic-flow network. In order to reduce the transmission time, the network allows the data to be transmitted through k minimal paths simultaneously. Including the cost attribute, this paper evaluates the probability that d units of data can be transmitted under both time threshold T and budget B. Such a probability is called the system reliability. An efficient algorithm is proposed to generate all of lower boundary points for (d, T, B), the minimal capacity vectors satisfying the demand, time, and budget requirements. The system reliability can then be computed in terms of such points. Moreover, the optimal combination of k minimal paths with highest system reliability can be obtained.     

An algorithm for optimizing network flow capacity under economies of scale

The problem of optimally allocating a fixed budget to the various arcs of a single-source, single-sink network for the purpose of maximizing network flow capacity is considered. The initial vector of arc capacities is given, and the cost function, associated with each arc, for incrementing capacity is concave; therefore, the feasible region is nonconvex. The problem is approached by Benders' decomposition procedure, and a finite algorithm is developed for solving the nonconvex relaxed master problems. A numerical example of optimizing network flow capacity, under economies of scale, is included.This research was supported by the National Science Foundation, Grant No. GK-32791.     

Analysis of budget for interdiction on multicommodity network flows

In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as \(R_a\), the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and \(R_b\), the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget \(R_b\) for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget \(R_a\) is related to all of these parameters of the network. Additionally, we present formulations to estimate both \(R_a\) and \(R_b\). For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.     

Optimal expansion of an existing network

Given an existing network, a list of arcs which could be added to the network, the arc costs and capacities, and an available budget, the problem considered in this paper is one of choosing which arcs to add to the network in order to maximize the maximum flow from a sources to a sinkt, subject to the budgetary constraint. This problem appears in a large number of practical situations which arise in connection with the expansion of electricity or gas supply, telephone, road or rail networks. The paper describes an efficient tree-search algorithm using bounds calculated by a dynamic programming procedure which are very effective in limiting the solution space explicitly searched. Computational results for a number of medium sized problems are described and computing times are seen to be very reasonable.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

An introduction to dynamic generative networks: Minimum cost flow

What we are dealing with is a class of networks called dynamic generative network flows in which the flow commodity is dynamically generated at source nodes and dynamically consumed at sink nodes. As a basic assumption, the source nodes produce the flow according to time generative functions and the sink nodes absorb the flow according to time consumption functions. This paper tries to introduce these networks and formulate minimum cost dynamic flow problem for a pre-specified time horizon T. Finally, some simple, efficient approaches are developed to solve the dynamic problem, in the general form when the capacities and costs are time varying and some other special cases, as a minimum cost static flow problem.     

A Model-Based Approach and Analysis for Multi-Period Networks

The aim of this contribution is to address a general class of network problems, very common in process systems engineering, where spoilage on arcs and storage in nodes are inevitable as time changes. Having a set of capacities, so-called horizon capacity which limits the total flow passing arcs over all periods, the min-cost flow problem in the discrete-time model with time-varying network parameters is investigated. While assuming a possibility of storage or and spoilage, we propose some approaches employing polyhedrals to obtain optimal solutions for a pre-specified planning horizon. Our methods describe some reformulations based on polyhedrals that lead to LP problems comprising a set of sparse subproblems with exceptional structures. Considering the sparsity and repeating structure of the polyhedrals, algorithmic approaches based on decomposition techniques of block-angular and block-staircase cases are proposed to handle the global problem aiming to reduce the computational resources required.     

Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

Optimal Two-commodity Flows with Non-linear Cost Functions

We consider networks in which two different commodities have to be transported across undirected arcs, subject to a shared capacity on the arcs. For each arc and commodity there is an associated non-linear cost that depends on the amount of the commodity transported across the arc. The aim is to minimize the sum of the costs over all arcs and commodities. Efficient algorithms for solving this problem for two types of objective functions will be presented: in the first the cost depends on the absolute value of the flow and in the second the cost is a quadratic function of the flow. Previous work on multi-commodity flow has concentrated on linear cost problems or tackled non-linear cost problems with Lagrangian relaxation methods and other more general techniques. The algorithms in this paper, on the other hand, provide a very efficient way of dealing with two types of non-linear two-commodity optimal flow problems.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

A heuristic for blocking flow algorithms

This note presents a simple heuristic to speed up algorithms for the maximum flow problem that works by repeatedly finding blocking flows in layered (acyclic) networks. The heuristic assigns a capacity to each vertex of the layered network, which will be an upper bound on the amount of flow that can be transported through that vertex to the sink. This information can be utilized when constructing a blocking flow, since no vertex can ever accommodate more flow than its capacity. The static heuristic computes capacities in a layered network once, while a dynamic variant readjusts capacities during construction of the blocking flow.The effects of both static and dynamic heuristics are evaluated by a series of experiments with the wave algorithm of Tarjan. Although neither give theoretical improvement to the efficiency of the algorithm, the practical effects are in most cases worthwhile, and for certain types of networks quite dramatic.     

Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity k-splittable Maximum Flow Problem consists in routing as much flow as possible through a capacitated network such that each commodity uses at most k paths and the capacities are satisfied. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. The problem has previously been solved to optimality through branch-and-price. In this paper we propose two exact solution methods both based on an alternative decomposition. The two methods differ in their branching strategy. The first method, which branches on forbidden edge sequences, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented. The heuristic is fast and yields good solution values.     

Efficient contraflow algorithms for quickest evacuation planning

The optimization models and algorithms with their implementations on flow over time problems have been an emerging field of research because of largely increasing human-created and natural disasters worldwide. For an optimal use of transportation network to shift affected people and normalize the disastrous situation as quickly and Efficiently as possible, contraflow configuration is one of the highly applicable operations research (OR) models. It increases the outbound road capacities by reversing the direction of arcs towards the safe destinations that not only minimize the congestion and increase the flow but also decrease the evacuation time significantly. In this paper, we sketch the state of quickest flow solutions and solve the quickest contraflow problem with constant transit times on arcs proving that the problem can be solved in strongly polynomial time O(nm²(log n)²), where n and m are number of nodes and number of arcs, respectively in the network. This contraflow solution has the same computational time bound as that of the best min-cost flow solution. Moreover, we also introduce the contraflow approach with load dependent transit times on arcs and present an Efficient algorithm to solve the quickest contraflow problem approximately. Supporting the claim, our computational experiments on Kathmandu road network and on randomly generated instances perform very well matching the theoretical results. For sufficiently large number of evacuees, about double flow can be shifted with the same evacuation time and about half time is sufficient to push the given flow value with contraflow reconfiguration.     

A Note on Feasible Flows in Lower-Bounded Multicommodity Networks

This note considers the feasibility for two types of multicommodity flow problems: maximal flow problems with both upper and lower arc capacities, and capacitated minimal cost trans-shipment problems. Although closed form conditions analogous to those known for single commodity problems cannot be derived, it is shown that feasibility is equivalent to finding a maximal multicommodity flow of a specified value on a related network with zero lower bounds, a direct extension of well-known results for single commodity networks.     

Determining the Optimal Flows in Zero-Time Dynamic Networks

Here we are dealing with minimum cost flow problem on dynamic network flows with zero transit times and a new arc capacity, horizon capacity, which denotes an upper bound on the total flow traversing through on an arc during a pre-specified time horizon T. We develop a simple approach based on mathematical modelling attributes to solve the min-cost dynamic network flow problem where arc capacities and costs are time varying, and horizon capacities are considered. The basis of the method is simple and relies on the appropriate defining of polyhedrons, and in contrast to the other usual algorithms that use the notion of time expanded network, this method runs directly on the original network.     

On transmission time through k minimal paths of a capacitated-flow network

The quickest path problem is to minimize the transmission time for sending a specified amount of data through a single minimal path. Two deterministic attributes are involved herein; the capacity and the lead time. However, in many real-life networks such as computer systems, urban traffic systems, etc., the arc capacity should be multistate due to failure, maintenance, etc. Such a network is named a capacitated-flow network. The minimum transmission time is thus not a fixed number. This paper is mainly to evaluate system reliability that d units of data can be transmitted through k minimal paths under time constraint T. A simple algorithm is proposed to generate all minimal capacity vectors meeting the demand and time constraints. The system reliability is subsequently computed in terms of such vectors. The optimal k minimal paths with highest system reliability can further be derived.     

Multicommodity Flow Problem with Variable Arcs Capacities

The problem of maximizing the sum of the flows of all commodities in a network where the capacities of some arcs can be increased by integer numbers within a fixed budget is solved in this paper. Benders' technique is used to decompose the problem. Then Rosen's primal partitioning and non-linear duality theory are used to solve the subproblems generated by the Benders' decomposition. An application of a multicommodity network to the defence problem is mentioned.