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.     

A memetic algorithm for the virtual network mapping problem

The Internet has ossified. It has lost its capability to adapt as requirements change. A promising technique to solve this problem is the introduction of network virtualization. Instead of directly using a single physical network, working just well enough for a limited range of applications, multiple virtual networks are embedded on demand into the physical network, each of them perfectly adapted to a specific application class. The challenge lies in mapping the different virtual networks with all the resources they require into the available physical network, which is the core of the virtual network mapping problem. In this work, we introduce a memetic algorithm that significantly outperforms the previously best algorithms for this problem. We also offer an analysis of the influence of different problem representations and in particular the implementation of a uniform crossover for the grouping genetic algorithm that may also be interesting outside of the virtual network mapping domain. Furthermore, we study the influence of different hybridization techniques and the behaviour of the developed algorithm in an online setting.     

Visualization of network structure by the application of hypernodes

In the literature several authors describe methods to construct simplified models of networks. These methods are motivated by the need to gain insight into the main properties of medium sized or large networks. The present paper contributes to this research by setting focus on weighted networks, the geographical component of networks and introducing a class of functions to model how the weights propagate from one level of abstraction to the next. Hierarchies of network models can be constructed from reordering of the adjacency matrix of the network; this is how “hypernodes” are derived in the present paper. The hypernode algorithm is explored and it is shown how it can be formulated to handle weighted networks. Weighted networks enable handling the uncertainty or the strength of the components which make up the network. The hypernode algorithm can be run in an iterative manner so that a hierarchy of simplified models of the network can be derived. Some case studies demonstrate the hypernode algorithm. In the first case the algorithm is compared with a similar implementation described in the literature. In the second case an airline dataset is analysed. This study shows that when networks are embedded in the geographical space hypernodes may relate to clusters in the spatial domain. The selection of the visual variables to illustrate the strength of the edges and nodes in a weighted network is discussed.     

A model for the capacitated,hop-constrained,per-packet wireless mesh network design problem

Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.     

Towards a queueing-based framework for in-network function computation

We seek to develop network algorithms for function computation in sensor networks. Specifically, we want dynamic joint aggregation, routing, and scheduling algorithms that have analytically provable performance benefits due to in-network computation as compared to simple data forwarding. To this end, we define a class of functions, the Fully-Multiplexible functions, which includes several functions such as parity, MAX, and kth-order statistics. For such functions we characterize the maximum achievable refresh rate of the network in terms of an underlying graph primitive, the min-mincut. In acyclic wireline networks we show that the maximum refresh rate is achievable by a simple algorithm that is dynamic, distributed, and only dependent on local information. In the case of wireless networks we provide a MaxWeight-like algorithm with dynamic flow-splitting, which is shown to be throughput-optimal.     

Performance modeling of heterogeneous data networks

A heterogeneous data network consists of Local Area Networks (LANs) interconnected with either leased lines, packet-switched networks, Metropolitan Area Networks (MANs), or combinations thereof. Heterogeneous networks are characterized by bursty traffic, nested segmentation and reassembly of packets, window flow control and round-robin channel access. We develop a performance methodology for estimating user perceived delay and buffer overflow in heterogeneous data networks. The methodology is based on well-known two-moment approximation schemes. Modifications of these schemes are proposed in order to model the bandwidth allocation policies of the MANs and to capture the burstiness of the traffic. The methodology is applied to several LAN-MAN and LAN-MAN-WAN network examples.Supported partially through AT&T Grant No. 5-20491 and partially through NSF Grant No. NCR-8914447.     

Generalized loopy 2U: A new algorithm for approximate inference in credal networks

Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.     

Numerical algorithms for simulations of a traffic model on road networks

We introduce a simulation algorithm based on a fluid-dynamic model for traffic flows on road networks, which are considered as graphs composed by arcs that meet at some junctions. The approximation of scalar conservation laws along arcs is made by three velocities Kinetic schemes with suitable boundary conditions at junctions. Here we describe the algorithm and we give an example.     

A simplicial decomposition algorithm for solving the variational inequality formulation of the general traffic assignment problem for large scale networks

Summary The class of simplicial decomposition methods has been shown to constitute efficient tools for the solution of the variational inequality formulation of the general traffic assignment problem. This paper presents a particular implementation of such an algorithm, with emphasis on its ability to solve large scale problems efficiently. The convergence of the algorithm is monitored by the primal gap function, which arises naturally in simplicial decomposition schemes. The gap function also serves as an instrument for maintaining a reasonable subproblem size, through its use in column dropping criteria. The small dimension and special structure of the subproblems also allows for the use of very efficient algorithms; several algorithms in the class of linearization methods are presented. When restricting the number of retained extremal flows in a simplicial decomposition scheme, the number of major iterations tends to increase. For large networks the shortest path calculations, leading to new extremal flow generation, require a large amount of the total computation time. A special study is therefore made in order to choose the most efficient extremal flow generation technique. Computational results on symmetric problems are presented for networks of some large cities, and on asymmetric problems for some of the networks used in the literature. Computational results for bimodal models of some large cities leading to asymmetric problems are also discussed.     

The cross-entropy method with patching for rare-event simulation of large Markov chains

There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a general state-dependent importance sampling method which partitions the state space and applies the cross-entropy method to each partition. We investigate two versions of our algorithm and apply them to several examples of reliability and queueing models. In all these examples we compare our method with other importance sampling schemes. The performance of the importance sampling schemes is measured by the relative error of the estimator and by the efficiency of the algorithm. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.     

The dynamics of spreading and immune strategies of sexually transmitted diseases on scale-free network

We examine epidemic threshold and dynamics for sexually transmitted diseases (STDs) spread using a multiple susceptible-infected-removed-susceptible ODE model on scale-free networks. We derive the threshold for the epidemic to be zero in infinite scale-free network. For a hard cut off scale-free network, we also prove the stability of disease-free equilibrium and the persistence of STDs infection. The effects of two immunization schemes, including proportional scheme and targeted vaccination, are studied and compared. We find that targeted strategy compare favorably to a proportional scheme in terms of effectiveness. Theory and simulations both prove that an appropriate condom using has prominent effect to control STDs spread on scale-free networks.     

Stability with file arrivals and departures in multichannel cellular wireless networks

This paper studies scheduling in multichannel wireless networks with flow-level dynamics. We consider a downlink network with a single base station, M channels (frequency bands), and multiple mobile users (flows). We also assume mobiles dynamically join the network to receive finite-size files and leave after downloading the complete files. A recent study van de Ven et al. (in Proc. IEEE Infocom., pp. 1701?C1709, 2009) has shown that the MaxWeight algorithm fails to be throughput-optimal under these flow-level dynamics. The main contribution of this paper is the development of joint channel-assignment and workload-based scheduling algorithms for multichannel downlink networks with dynamic flow arrivals/departures. We prove that these algorithms are throughput-optimal. Our simulations further demonstrate that a hybrid channel-assignment and workload-based scheduling algorithm significantly improves the network performance (in terms of both file-transfer delay and blocking probability) compared to the existing algorithms.     

Deadlock properties of queueing networks with finite capacities and multiple routing chains

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.     

An Algorithm for Solving Inverse Geoelectrics Problems Based on the Neural Network Approximation

A neural network approximation algorithm for solving inverse geoelectrics problems in the class of grid (block) models of media is presented. The algorithm is based on using neural networks for constructing an approximate inverse operator and enables formalized construction of solutions of inverse geoelectrics problem with a total number of sought-for medium parameters of ~ n · 10³. The correctness of the problem of constructing neural network inverse operators is considered. A posteriori estimates of the degree of ambiguity of solutions of the resulting inverse problem are calculated. The operation of the algorithm is illustrated by examples of 2D and 3D inversions of synthetic and field geoelectric data obtained by the MTS method.     

A Neural Network-Based Policy Iteration Algorithm with Global $$H^2$$ -Superlinear Convergence for Stochastic Games on Domains

In this work, we propose a class of numerical schemes for solving semilinear Hamilton–Jacobi–Bellman–Isaacs (HJBI) boundary value problems which arise naturally from exit time problems of diffusion processes with controlled drift. We exploit policy iteration to reduce the semilinear problem into a sequence of linear Dirichlet problems, which are subsequently approximated by a multilayer feedforward neural network ansatz. We establish that the numerical solutions converge globally in the \(H^2\)-norm and further demonstrate that this convergence is superlinear, by interpreting the algorithm as an inexact Newton iteration for the HJBI equation. Moreover, we construct the optimal feedback controls from the numerical value functions and deduce convergence. The numerical schemes and convergence results are then extended to oblique derivative boundary conditions. Numerical experiments on the stochastic Zermelo navigation problem are presented to illustrate the theoretical results and to demonstrate the effectiveness of the method.

     

Robust synchronization of singular complex switched networks with parametric uncertainties and unknown coupling topologies via impulsive control

This paper presents a general model of singular complex switched networks, in which the nodes can be singular dynamic systems and switching behaviors act on both nodes and edges. The parametric uncertainties and unknown coupling topologies are also considered in this model. Two robust synchronization schemes are discussed respectively. In one scheme, the network is synchronized to a homogeneous orbit and in the other one the network is synchronized to a weighted average of all the nodes. Based on the Lyapunov stability theory, different robust synchronization conditions for the two schemes are obtained for this singular complex switched network model via impulsive control. The similarities and differences between these synchronization conditions for the two schemes are discussed. In addition, three useful robust results for the special cases of the singular complex switched networks are presented. Two systematic-design procedures are presented for the two schemes, and three numerical examples are provided for illustrations.     

An Algorithmic Framework for the Exact Solution of the Prize-Collecting Steiner Tree Problem

The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree. PCST appears frequently in the design of utility networks where profit generating customers and the network connecting them have to be chosen in the most profitable way. Our main contribution is the formulation and implementation of a branch-and-cut algorithm based on a directed graph model where we combine several state-of-the-art methods previously used for the Steiner tree problem. Our method outperforms the previously published results on the standard benchmark set of problems. We can solve all benchmark instances from the literature to optimality, including some of them for which the optimum was not known. Compared to a recent algorithm by Lucena and Resende, our new method is faster by more than two orders of magnitude. We also introduce a new class of more challenging instances and present computational results for them. Finally, for a set of large-scale real-world instances arising in the design of fiber optic networks, we also obtain optimal solution values. Received: April, 2004 This work has been partly supported by the RTNADONET, 504438, by the Doctoral Scholarship Program of the Austrian Academy of Sciences (DOC) and by CNR and MIUR, Italy.A preliminary version of this paper appeared as [21].     

State-Dependent Coupling in General Networks

In this paper we extend a result which holds for the class of networks of quasireversible nodes to a class of networks constructed by coupling Markov chains. We begin with a network in which the transition rates governing the stochastic behaviour of the individual nodes depend only on the state of the node. Assuming that the network has an invariant measure, we construct another network with transition rates at each node depending on the state of the entire network, and obtain its invariant measure.     

An Improved Multi-parametric Programming Algorithm for Flux Balance Analysis of Metabolic Networks

Flux balance analysis has proven an effective tool for analyzing metabolic networks. In flux balance analysis, reaction rates and optimal pathways are ascertained by solving a linear program, in which the growth rate is maximized subject to mass-balance constraints. A variety of cell functions in response to environmental stimuli can be quantified using flux balance analysis by parameterizing the linear program with respect to extracellular conditions. However, for most large, genome-scale metabolic networks of practical interest, the resulting parametric problem has multiple and highly degenerate optimal solutions, which are computationally challenging to handle. An improved multi-parametric programming algorithm based on active-set methods is introduced in this paper to overcome these computational difficulties. Degeneracy and multiplicity are handled, respectively, by introducing generalized inverses and auxiliary objective functions into the formulation of the optimality conditions. These improvements are especially effective for metabolic networks because their stoichiometry matrices are generally sparse; thus, fast and efficient algorithms from sparse linear algebra can be leveraged to compute generalized inverses and null-space bases. We illustrate the application of our algorithm to flux balance analysis of metabolic networks by studying a reduced metabolic model of Corynebacterium glutamicum and a genome-scale model of Escherichia coli. We then demonstrate how the critical regions resulting from these studies can be associated with optimal metabolic modes and discuss the physical relevance of optimal pathways arising from various auxiliary objective functions. Achieving more than fivefold improvement in computational speed over existing multi-parametric programming tools, the proposed algorithm proves promising in handling genome-scale metabolic models.