Solving Large Multicommodity Network Flow Problems on GPUs

Fangzhao Zhang, Stephen Boyd · 2025

Read Solving Large Multicommodity Network Flow Problems on GPUs by Fangzhao Zhang, Stephen Boyd (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17996.txt.

Introduction

Fangzhao Zhang and Stephen Boyd built a GPU solver in twenty twenty-five for huge multicommodity flow problems. Such problems route many goods through one capacitated network at once, from data packets to freight. Tracking each source-destination pair separately explodes the variable count.

Their formulation merges flows that share a destination, cutting variables by a factor of the network size. The solver runs a primal-dual hybrid gradient method tuned to the problem's structure for graphics processors. It handles problems with up to a billion variables. In tests it outran top commercial solvers by one hundred to one thousand times. The authors release the code openly. The work shows how problem-aware design can move optimization from hours to seconds on modern hardware.

Catalog record

CREATORFangzhao Zhang, Stephen Boyd
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17996

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving Large Multicommodity Network Flow Problems on GPUs Fangzhao Zhang, Stephen Boyd Abstract We consider the all-pairs multicommodity network flow problem on a network with capacitated edges. The usual treatment keeps track of a separate flow for each source-destination pair on each edge; we rely on a more efficient formulation in which flows with the same destination are aggregated, reducing the number of variables by a factor equal to the size of the network. Problems with hundreds of nodes, with a total number of variables on the order of a million, can be solved using standard generic interior-point methods on CPUs; we focus on GPU-compatible algorithms that can solve such problems much faster, and in addition scale to much larger problems, with up to a billion variables. Our method relies on the primal-dual hybrid gradient algorithm, and exploits several specific features of the problem for efficient GPU computation. Numerical experiments show that our primal-dual multicommodity network flow method accelerates state of the art generic commercial solvers by 100 × 100\times to 1000 × 1000\times , and scales to problems that are much larger. We provide an open source implementation of our method. 1 Multicommodity network flow optimization 1.1 Multicommodity network flow problem Our formulation of the multicommodity network flow (MCF) problem, given below, follows [ YDLB19 ] . Network. We consider a directed network with n nodes and m edges which is completely connected, i.e. , there is a directed path between each pair of nodes. Let A\in{\mbox{\bf R}}^{n\times m} denote its incidence matrix, i.e. , A_{i\ell}=\left\{\begin{array}[]{rl}+1&\mbox{edge $\ell$ enters node $i$}\\ -1&\mbox{edge $\ell$ leaves node $i$}\\ 0&\mbox{otherwise}.\end{array}\right. Edge \ell has a positive capacity c_{\ell} . The total flow on edge \ell (to be defined below) cannot exceed c_{\ell} . Traffic matrix. We consider the all-pairs multicommodity flow setting, i.e. , there is traffic that originates at every node, destined for every other node. We characterize the traffic between all source-destination pairs via the traffic matrix T\in{\mbox{\bf R}}^{n\times n} . For any pair of distinct nodes i,j , T_{ij}\geq 0 is the traffic from (source) node j to (destination) node i . There is no traffic from a node to itself; for mathematical convenience we define the diagonal traffic matrix entries as T_{ii}=-\sum_{j\neq i}T_{ij} , the negative of the total traffic with destination node i . With this definition of the diagonal entries we have T\mathbf{1}=0 , where \mathbf{1} is the vector with all entries one. Network utility. Let u_{ij} denote the strictly concave increasing utility function for traffic from node j to node i , for j\neq i . We will assume utility functions are differentiable with domains {\mbox{\bf R}}_{++} , the set of positive numbers. (The methods we describe are readily extended to nondifferentiable utilities using subgradients instead of gradients.) The total utility, which we wish to maximize, is \sum_{i\neq j}u_{ij}(T_{ij}) . For simplicity we take u_{ii}=0 , so we can write the total utility as U(T)=\sum_{i,j}u_{ij}(T_{ij}). The domain of U is \mathcal{T}=\{T\mid T_{ij}>0~\mbox{for}~i\neq j\} , i.e. , the traffic matrix must have positive off-diagonal entries. Common examples of utility functions include the weighted log utility u(s)=w\log s , and the weighted power utility u(s)=ws^{\gamma} , with \gamma\in(0,1) , where w>0 is the weight. Destination-based flow matrix. Following [ YDLB19 ] we aggregate all flows with the same destination, considering it to be one commodity that is conserved at all nodes except the source and destination, but can be split and combined. The commodity flows are given by the (destination-based) flow matrix F\in{\mbox{\bf R}}^{n\times m} , where F_{i\ell}\geq 0 denotes the flow on edge \ell that is destined to node i . The edge capacity constraint can be expressed as F^{T}\mathbf{1}\leq c , where the inequality is elementwise. A similar flow aggregation formulation, though source-based, was considered in [ BGB03 ] . Flow conservation. The flow destined for node i is conserved at all nodes j\neq i , including the additional injection of traffic T_{ij} that originates at node j and is destined for node i . This means that T_{ij}+\sum_{\ell}A_{j\ell}F_{i\ell}=0,\quad i,j=1,\ldots,n,\quad j\neq i. At the destination node, all traffic exits and we have (using our definition of T_{ii} ) T_{ii}+\sum_{\ell}A_{i\ell}F_{i\ell}=0,\quad i=1,\ldots,n. Combining these two, and using our specific definition of T_{ii} , flow conservation can be compactly written in matrix notation as T+FA^{T}=0. Multicommodity flow problem. In the MCF problem we seek a flow matrix that maximizes total network utility, subject to the edge capacity and flow conservation constraints. This can be expressed as the problem \begin{array}[]{ll}\mbox{maximize}&U(T)\\ \mbox{subject to}&F\geq 0,\quad F^{T}\mathbf{1}\leq c,\quad T+FA^{T}=0,\\ \end{array} (1) with variables F and T , and implicit constraint T\in\mathcal{T} . The problem data are the network topology A , edge capacities c , and the traffic utility functions u_{ij} . We can eliminate the traffic matrix T using T=-FA^{T} and state the MCF problem in terms of the variable F alone as \begin{array}[]{ll}\mbox{maximize}&U(-FA^{T})\\ \mbox{subject to}&F\geq 0,\quad F^{T}\mathbf{1}\leq c,\end{array} (2) with variable F , and implicit constraint -FA^{T}\in\mathcal{T} . The number of scalar variables in this problem is nm . For future use we define the feasible flow set as \mathcal{F}=\{F\mid F\geq 0,~F^{T}\mathbf{1}\leq c\}. Existence and uniqueness of solution. First let us show the MCF problem ( 1 ) is always feasible. Consider a unit flow from each source to each destination, over the shortest path, i.e. , smallest number of edges, which exists since the graph is completely connected. We denote this flow matrix as F^{\text{sp}} . Now take F=\alpha F^{\text{sp}} , where \alpha=1/\max_{\ell}(({F^{\text{sp}}}^{T}\mathbf{1})_{\ell}/c_{\ell})>0 , so we have F^{T}\mathbf{1}\leq c . Evidently F is feasible, and we have T_{ij}=\alpha>0 for i\neq j , so T=-FA^{T}\in\mathcal{T} . This shows that the problem is always feasible. Let U^{\text{sp}} denote the corresponding objective function. We can add the constraint U(T)\geq U^{\text{sp}} to the problem, without changing the solution set. With this addition, the feasible set is compact. It follows that the MCF problem ( 1 ) always has solution. The solution need not be unique. The optimal T , however, is unique. We also note that the argument above tells us that the implicit constraint T=-FA^{T}\in\mathcal{T} is redundant. Solving MCF. The multicommodity flow problem ( 2 ) is convex [ BV04 ] , and so in principal can be efficiently solved. In [ YDLB19 ] the authors use standard generic interior-point solvers such as the commercial solver MOSEK [ ApS19 ] , together with CVXPY [ DB16 ] , to solve instances of the problem with tens of nodes, and thousands of variables, in a few seconds on a CPU. In this paper we introduce an algorithm for solving the MCF problem that fully exploits GPUs. For small and medium size problems our method gives a substantial speedup over generic methods; in addition it scales to much larger problems that cannot be solved by generic methods. 1.2 Optimality condition and residual Optimality condition. Let \tilde{\mathcal{F}} denote the closure of the feasible set, including the implicit constraint T=-FA^{T}\in\mathcal{T} , \tilde{\mathcal{F}}=\mathcal{F}\cap\{F\mid-FA^{T}\in\textbf{cl}(\mathcal{T})\}, where \textbf{cl}(\mathcal{T}) denotes the closure of \mathcal{T} . Then F is optimal for ( 2 ) if and only if F\in\mathcal{F} , -FA^{T}\in\mathcal{T} , and \mathop{\bf Tr}(Z-F)^{T}G\geq 0 holds for all Z\in\tilde{\mathcal{F}} , where G=\nabla_{F}(-U)(-FA^{T}) (see, e.g. , [ BV04 , §4.2.3] ). We have G=U^{\prime}A

Read the complete text