Weighted distances in scale‐free preferential attachment models

We study three preferential attachment models where the parameters are such that the asymptotic degree distribution has infinite variance. Every edge is equipped with a nonnegative i.i.d. weight. We study the weighted distance between two vertices chosen uniformly at random, the typical weighted distance, and the number of edges on this path, the typical hopcount. We prove that there are precisely two universality classes of weight distributions, called the explosive and conservative class. In the explosive class, we show that the typical weighted distance converges in distribution to the sum of two i.i.d. finite random variables. In the conservative class, we prove that the typical weighted distance tends to infinity, and we give an explicit expression for the main growth term, as well as for the hopcount. Under a mild assumption on the weight distribution the fluctuations around the main term are tight.     

Dynamic factorization in large-scale optimization

Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows, and generalized network rows. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.Corresponding author.     

Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems

We consider the problem faced by managers of critical civil interdependent infrastructure systems of restoring essential public services after a non-routine event causes disruptions to these services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. These restoration planning and scheduling decisions are often undertaken in an independent, sequential manner. We provide mathematical models and optimization algorithms that integrate the restoration and planning decisions and specifically account for the interdependencies between the infrastructure systems. The objective function of this problem provides a measure of how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We test our methods on realistic data representing infrastructure systems in New York City. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of integrating the restoration and scheduling decisions.     

Nash equilibria in all-optical networks

We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach

Expressways in China make use of the toll-by-weight scheme, in which expressway tolls are collected based on the weight and traveling distance of the vehicle. Most vehicle routing models assume that the cost of traversing each edge is equivalent to edge length or some constant; as a result, such models cannot be practically applied to the Chinese expressway transportation system. This study addresses a new single vehicle routing problem that takes the vehicle’s (laden and unladen) weight into account. To solve this problem exactly, we provide a branch-and-bound algorithm with a provably valid lower bound measure, along with five dominance checkers for additional pruning. We analyze our algorithm using instances generated from standard TSP test cases, as well as two new sets of test cases based on real expressway information from the Gansu and Jiangxi provinces in China. The algorithm can be applied to any toll scheme in which the toll per unit distance monotonically increases with weight, even if the toll function is non-linear.     

Reservoir operations optimization via fuzzy criterion decision processes

In this paper, we propose the treatment of complex reservoir operation problems via our newly developed tool of fuzzy criterion decision processes. This novel approach has been shown to be a more flexible and useful analysis tool especially when it is desirable to incorporate an expert’s knowledge into the decision models. Additionally, it has been demonstrated that this form of decision models will usually result in an optimal solution, which guarantees the highest satisfactory degree. We provide a practical exemplification procedure for the models presented as well as an application example.     

Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

We study the computational complexity of the Spare Capacity Allocation problem arising in optical networks that use a shared mesh restoration scheme. In this problem we are given a network with edge capacities and point-to-point demands, and the goal is to allocate two edge-disjoint paths for each demand (a working path and a so-called restoration path, which is activated only if the working path fails) so that the capacity constraints are satisfied and the total cost of the used and reserved bandwidth is minimized. We focus on the setting where we deal with a group of demands together, and select their restoration paths simultaneously in order to minimize the total cost. We investigate how the computational complexity of this problem is affected by certain parameters, such as the number of restoration paths to be selected, or the treewidth of the network graph. To analyze the complexity of the problem, we introduce a generalization of the Steiner Forest problem that we call Multicost Steiner Subgraph. We study its parameterized complexity, and identify computationally easy and hard cases by providing hardness proofs as well as efficient (fixed-parameter tractable) algorithms.     

Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints

We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity. This revised version was published online in June 2006 with corrections to the Cover Date.     

增长网络的形成机理和度分布计算

关于增长网络的形成机理,着重介绍由线性增长与择优连接组成的BA模型, 以及加速增长模型.此外,我们提出了一个含反择优概率删除旧连线的模型,这个模型能自组织演化成scale-free(SF)网络.关于计算SF网络的度分布,简要介绍文献上常用的基于连续性理论的动力学方法(包括平均场和率方程)和基于概率理论的主方程方法.另外,我们基于马尔可夫链理论还首次尝试了数值计算方法.这一方法避免了复杂方程的求解困难,所以较有普适性,因此可用于研究更为复杂的网络模型.我们用这种数值计算方法研究了一个具有对数增长的加速增长模型,这个模型也能自组织演化成SF网络.     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

Single PON network design with unconstrained splitting stages

A Passive Optical Network (PON) is a network technology for deploying access networks based on passive optical components. In a single PON access network, the client terminals are connected to a Central Office through optical splitters and interconnecting fibers where each splitter splits in equal parts the input optical signal coming from the Central Office over its different output fibers. In this paper, we consider PON topology solutions where the splitting ratio and the number of splitting stages are not constrained to a given target design but, instead, are decided based on the cost of the solutions. We present different Integer Linear Programming formulations to model this problem and provide computational results showing that the optimal solutions can be computed for realistic problem instances. In addition, we describe how the formulations can be adapted for the traditional PON topology approaches and present computational results showing that significant cost gains are obtained with the unconstrained splitting stage approach.     

Fleet-sizing and service availability for a vehicle rental system via closed queueing networks

In this paper, we address the problem of determining the optimal fleet size for a vehicle rental company and derive analytical results for its relationship to vehicle availability at each rental station in the company’s network of locations. This work is motivated by the recent surge in interest for bicycle and electric car sharing systems, one example being the French program Vélib (2010). We first formulate a closed queueing network model of the system, obtained by viewing the system from the vehicle’s perspective. Using this framework, we are able to derive the asymptotic behavior of vehicle availability at an arbitrary rental station with respect to fleet size. These results allow us to analyze imbalances in the system and propose some basic principles for the design of system balancing methods. We then develop a profit-maximizing optimization problem for determining optimal fleet size. The large-scale nature of real-world systems results in computational difficulties in obtaining this exact solution, and so we provide an approximate formulation that is easier to solve and which becomes exact as the fleet size becomes large. To illustrate our findings and validate our solution methods, we provide numerical results on some sample networks.     

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.     

Large deviations analysis of the generalized processor sharing policy

In this paper we consider a stochastic server (modeling a multiclass communication switch) fed by a set of parallel buffers. The dynamics of the system evolve in discrete-time and the generalized processor sharing (GPS) scheduling policy of [25] is implemented. The arrival process in each buffer is an arbitrary, and possibly autocorrelated, stochastic process. We obtain a large deviations asymptotic for the buffer overflow probability at each buffer. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We view the problem of finding a most likely sample path that leads to an overflow as an optimal control problem. Using ideas from convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow probability and a characterization of most likely modes of overflow. These results have important implications for traffic management of high-speed networks. They extend the deterministic, worst-case analysis of [25] to the case where a detailed statistical model of the input traffic is available and can be used as a basis for an admission control mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

Modeling and optimization of energy efficient routing in wireless sensor networks

Wireless sensor networks (WSNs) have important applications in remote environmental monitoring and target tracking. The development of WSNs in recent years has been facilitated by the availability of sensors that are smaller, less expensive, and more intelligent. The design of a WSN depends significantly on its desired applications and must take into account factors such as the environment, the design objectives of the application, the associated costs, the necessary hardware, and any applicable system constraints. In this study, we propose mathematical models for a routing protocol (network design) under particular resource restrictions within a wireless sensor network. We consider two types of constraints: the distance between the linking sensors and the energy used by the sensors. The proposed models aim to identify energy-efficient paths that minimize the energy consumption of the network from the source sensor to the base station. The computational results show that the presented models can be used efficiently and applied to other network design contexts with resource restrictions (e.g., to multi-level supply chain networks).     

Spatiotemporal Models for Gaussian Areal Data

We introduce a class of spatiotemporal models for Gaussian areal data. These models assume a latent random field process that evolves through time with random field convolutions; the convolving fields follow proper Gaussian Markov random field (PGMRF) processes. At each time, the latent random field process is linearly related to observations through an observational equation with errors that also follow a PGMRF. The use of PGMRF errors brings modeling and computational advantages. With respect to modeling, it allows more flexible model structures such as different but interacting temporal trends for each region, as well as distinct temporal gradients for each region. Computationally, building upon the fact that PGMRF errors have proper density functions, we have developed an efficient Bayesian estimation procedure based on Markov chain Monte Carlo with an embedded forward information filter backward sampler (FIFBS) algorithm. We show that, when compared with the traditional one-at-a-time Gibbs sampler, our novel FIFBS-based algorithm explores the posterior distribution much more efficiently. Finally, we have developed a simulation-based conditional Bayes factor suitable for the comparison of nonnested spatiotemporal models. An analysis of the number of homicides in Rio de Janeiro State illustrates the power of the proposed spatiotemporal framework.

Supplemental materials for this article are available online in the journal’s webpage.     

Finite-difference schemes for parabolic problems on graphs

We consider a reaction–diffusion parabolic problem on branched structures. The Hodgkin–Huxley reaction–diffusion equations are formulated on each edge of the graph. The problems are coupled by some conjugation conditions at branch points. It is important to note that two different types of the flux conservation equations are considered. The first one describes a conservation of the axial currents at branch points, and the second equation defines the conservation of the current flowing at the soma in neuron models. We study three different types of finite-difference schemes. The fully implicit scheme is based on the backward Euler algorithm. The stability and convergence of the discrete solution is proved in the maximum norm, and the analysis is done by using the maximum principle method. In order to decouple computations at each edge of the graph, we consider two modified schemes. In the predictor algorithm, the values of the solution at branch points are computed by using an explicit approximation of the conservation equations. The stability analysis is done using the maximum principle method. In the predictor–corrector method, in addition to the previous algorithm, the values of the solution at the branch points are recomputed by an implicit algorithm, when the discrete solution is obtained on each subdomain. The stability of this algorithm is investigated numerically. The results of computational experiments are presented.