Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTarget Location Problem for Multi-commodity Flow
75
0
0.0
(
0
)
Added by
Zhida Pan
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Motivated by scheduling in Geo-distributed data analysis, we propose a target location problem for multi-commodity flow (LoMuF for short). Given commodities to be sent from their resources, LoMuF aims at locating their targets so that the multi-commodity flow is optimized in some sense. LoMuF is a combination of two fundamental problems, namely, the facility location problem and the network flow problem. We study the hardness and algorithmic issues of the problem in various settings. The findings lie in three aspects. First, a series of NP-hardness and APX-hardness results are obtained, uncovering the inherent difficulty in solving this problem. Second, we propose an approximation algorithm for general undirected networks and an exact algorithm for undirected trees, which naturally induce efficient approximation algorithms on directed networks. Third, we observe separations between directed networks and undirected ones, indicating that imposing direction on edges makes the problem strictly harder. These results show the richness of the problem and pave the way to further studies.
rate research
Read More
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we introduce a dynamics for the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterization of the optimum solution.
Modern networks run middleboxes that offer services ranging from network address translation and server load balancing to firewalls, encryption, and compression. In an industry trend known as Network Functions Virtualization (NFV), these middleboxes run as virtual machines on any commodity server, and the switches steer traffic through the relevant chain of services. Network administrators must decide how many middleboxes to run, where to place them, and how to direct traffic through them, based on the traffic load and the server and network capacity. Rather than placing specific kinds of middleboxes on each processing node, we argue that server virtualization allows each server node to host all middlebox functions, and simply vary the fraction of resources devoted to each one. This extra flexibility fundamentally changes the optimization problem the network administrators must solve to a new kind of multi-commodity flow problem, where the traffic flows consume bandwidth on the links as well as processing resources on the nodes. We show that allocating resources to maximize the processed flow can be optimized exactly via a linear programming formulation, and to arbitrary accuracy via an efficient combinatorial algorithm. Our experiments with real traffic and topologies show that a joint optimization of node and link resources leads to an efficient use of bandwidth and processing capacity. We also study a class of design problems that decide where to provide node capacity to best process and route a given set of demands, and demonstrate both approximation algorithms and hardness results for these problems.
Column generation is often used to solve multi-commodity flow problems. A program for column generation always includes a module that solves a linear equation. In this paper, we address three major issues in solving linear problem during column generation procedure which are (1) how to employ the sparse property of the coefficient matrix; (2) how to reduce the size of the coefficient matrix; and (3) how to reuse the solution to a similar equation. To this end, we first analyze the sparse property of coefficient matrix of linear equations and find that the matrices occurring in iteration are very sparse. Then, we present an algorithm locSolver (for localized system solver) for linear equations with sparse coefficient matrices and right-hand-sides. This algorithm can reduce the number of variables. After that, we present the algorithm incSolver (for incremental system solver) which utilizes similarity in the iterations of the program for a linear equation system. All three techniques can be used in column generation of multi-commodity problems. Preliminary numerical experiments show that the incSolver is significantly faster than the existing algorithms. For example, random test cases show that incSolver is at least 37 times and up to 341 times faster than popular solver LAPACK.
This paper gives a localized method for the multi-commodity flow problem. We relax both the capacity constraints and flow conservation constraints, and introduce a congestion function $psi$ for each arc and $height$ function $h$ for each vertex and commodity. If the flow exceeds the capacity on arc $a$, arc $a$ would have a congestion cost. If the flow into the vertex $i$ is not equal to that out of the vertex for commodity $k$, vertex $i$ would have a height, which is positively related to the difference between the amount of the commodity $k$ into the vertex $i$ and that out of the vertex. Based on the height function $h$ and the congestion function $psi$, a new conception, stable pseudo-flow, is introduced, which satisfies the following conditions: ($mathrm{i}$) for any used arc of commodity $k$, the height difference between vertex $i$ and vertex $j$ is equal to the congestion of arc $(i,j)$; ($mathrm{ii}$) for any unused arc of commodity $k$, the height difference between vertex $i$ and vertex $j$ is less than or equal to the congestion of arc $(i,j)$. If the stable pseudo-flow is a nonzero-stable pseudo-flow, there exists no feasible solution for the multi-commodity flow problem; if the stable pseudo-flow is a zero-stable pseudo-flow, there exists feasible solution for the multi-commodity flow problem and the zero-stable pseudo-flow is the feasible solution. Besides, a non-linear description of the multi-commodity flow problem is given, whose solution is stable pseudo-flow. And the non-linear description could be rewritten as convex quadratic programming with box constraints. Rather than examine the entire network to find path, the conclusion in this paper shows that the multi-commodity flow problem could be solved in a localized manner by looking only at the vertex and its neighbors.
Designing and optimizing different flows in networks is a relevant problem in many contexts. While a number of methods have been proposed in the physics and optimal transport literature for the one-commodity case, we lack similar results for the multi-commodity scenario. In this paper we present a model based on optimal transport theory for finding optimal multi-commodity flow configurations on networks. This model introduces a dynamics that regulates the edge conductivities to achieve, at infinite times, a minimum of a Lyapunov functional given by the sum of a convex transport cost and a concave infrastructure cost. We show that the long time asymptotics of this dynamics are the solutions of a standard constrained optimization problem that generalizes the one-commodity framework. Our results provide new insights into the nature and properties of optimal network topologies. In particular, they show that loops can arise as a consequence of distinguishing different flow types, complementing previous results where loops, in the one-commodity case, were obtained as a consequence of imposing dynamical rules to the sources and sinks or when enforcing robustness to damage. Finally, we provide an efficient implementation of our model which convergences faster than standard optimization methods based on gradient descent.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
