Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSolving Splitted Multi-Commodity Flow Problem by Efficient Linear Programming Algorithm
135
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
In this paper, we develop a new algorithm combining the idea of ``boosting with the first-order algorithm to approximately solve a class of (Integer) Linear programs(LPs) arisen in general resource allocation problems. Not only can this algorithm solve LPs directly, but also can be applied to accelerate the Column Generation method. As a direct solver, our algorithm achieves a provable $O(sqrt{n/K})$ optimality gap, where $n$ is the number of variables and $K$ is the number of data duplication bearing the same intuition as the boosting algorithm. We use numerical experiments to demonstrate the effectiveness of our algorithm and several variants.
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.
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.
This paper discusses the odds problem, proposed by Bruss in 2000, and its variants. A recurrence relation called a dynamic programming (DP) equation is used to find an optimal stopping policy of the odds problem and its variants. In 2013, Buchbinder, Jain, and Singh proposed a linear programming (LP) formulation for finding an optimal stopping policy of the classical secretary problem, which is a special case of the odds problem. The proposed linear programming problem, which maximizes the probability of a win, differs from the DP equations known for long time periods. This paper shows that an ordinary DP equation is a modification of the dual problem of linear programming including the LP formulation proposed by Buchbinder, Jain, and Singh.
We introduce a class of specially structured linear programming (LP) problems, which has favorable modeling capability for important application problems in different areas such as optimal transport, discrete tomography and economics. To solve these generally large-scale LP problems efficiently, we design an implementable inexact entropic proximal point algorithm (iEPPA) combined with an easy-to-implement dual block coordinate descent method as a subsolver. Unlike existing entropy-type proximal point algorithms, our iEPPA employs a more practically checkable stopping condition for solving the associated subproblems while achieving provable convergence. Moreover, when solving the capacity constrained multi-marginal optimal transport (CMOT) problem (a special case of our LP problem), our iEPPA is able to bypass the underlying numerical instability issues that often appear in the popular entropic regularization approach, since our algorithm does not require the proximal parameter to be very small in order to obtain an accurate approximate solution. Numerous numerical experiments show that our iEPPA is highly efficient and robust for solving large-scale CMOT problems, in comparison to the (stabilized) Dykstras algorithm and the commercial solver Gurobi. Moreover, the experiments on discrete tomography also highlight the potential modeling power of our model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
