Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. In this paper, we compare the optimal capacity allocation costs for six routing sets: affine routing, volume routing and its two simplifications, the routing based on an unrestricted 2-cover of the uncertainty set, and the routing … Read more
We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected … Read more
Network analysis is of great interest for the study of social, biological and technological networks, with applications, among others, in business, marketing, epidemiology and telecommunications. Researchers are often interested in assessing whether an observed feature in some particular network is expected to be found within families of networks under some hypothesis (named conditional random networks, … Read more
We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides … Read more
In this paper we consider a network with P nodes, where each node has exclusive access to a local cost function. Our contribution is a communication-efficient distributed algorithm that finds a vector x* minimizing the sum of all the functions. We make the additional assumption that the functions have intersecting local domains, i.e., each function … Read more
We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a $K$-shortest paths finding algorithm … Read more
This paper presents optimal scaling of the alternating directions method of multipliers (ADMM) algorithm for a class of distributed quadratic programming problems. The scaling corresponds to the ADMM step-size and relaxation parameter, as well as the edge-weights of the underlying communication graph. We optimize these parameters to yield the smallest convergence factor of the algorithm. … Read more
In this paper, we consider relocating facilities, where we have demand changes in the network. Relocations are performed by closing some of the existing facilities from low demand areas and opening new ones in newly emerging areas. However, the actual changes of demand are not known in advance. Therefore, di erent scenarios with known probabilities are … Read more
We introduce a class of incremental network design problems focused on investigating the optimal choice and timing of network expansions. We concentrate on an incremental network design problem with shortest paths. We investigate structural properties of optimal solutions, we show that the simplest variant is NP-hard, we analyze the worst-case performance of natural greedy heuristics, … Read more
In this paper, we consider the network loading problem under demand uncertainties with static routing, i.e, a single routing scheme based on the fraction of the demands has to be determined. We generalize the class of metric inequalities to the Γ-robust setting and show that they yield a formulation in the capacity space. We describe … Read more