Netting, the process through which companies offset mutual debts while conducting transactions, plays a critical role in conserving liquidity and reducing settlement costs [7]. To execute netting, companies must disclose invoices to a central authority, such as the government. However, this requirement poses a significant barrier. In Slovenia, only 1.2% of companies have participated in the network due to this challenge [8]. To address this issue, there is a growing demand for Private Netting processes that enable the execution of netting while keeping invoice details confidential.
The Netting process can be mapped to the Minimum Cost Flow Problem, a type of mathematical optimization, as proposed by Fleischman et al. [7]. Therefore, this paper focuses on the Network Simplex Method, a well-known algorithm for this problem, and proposes an MPC-based (Multi-Party Computation) algorithm to ensure privacy in the netting process.
The Network Simplex Method is a technique for solving the minimum cost flow problem by repeatedly swapping edges of an initial solution. The overall algorithm becomes more efficient by efficiently searching for the edges to be swapped. Benchmarking by Goldberg [1] has reported it to be the most efficient among MCF algorithms. It is also implemented in the minimum_cost_flow function of NetworkX [2]. However, the algorithm is not simple. The following example will explain the algorithm step-by-step, based on Orlin's polynomial-time algorithm [3] and Brunovsky's blog [4].
To explain using a sample, let's consider the following graph. It consists of four nodes labeled 0, 1, 2, and 3. The numbers on the edges indicate the original flow. The red numbers on the nodes represent the demand.
First, define the original graph's flow as the capacity and set the flow to zero to create graph $L$. This is where the algorithm starts.
To obtain the initial feasible solution, we create an artificial graph $T$. Here, we define a dummy node 4 and add edges from each supply node to node 4 and from node 4 to each demand node, with flow and capacity equal to their respective supply and demand.
Each edge in this graph satisfies the optimality conditions. Here's how the graph $(L,T)$ looks:
Next, we need to find the entering edge $e_{in}$ from the set $L$. The $e_{in}$ refers to the edge that extends from a supply node to a demand node. Orlin's algorithm defines another variable called "potential" to search for this edge. Now, edge $(0,1)$ is selected as $e_{in}$.
3-1. Find cycle including $T+\{e_{in}\}$
We add the entering edge $e_{in}$ to $T$ and identify a cycle within $T$. Then we will look for a cycle in the graph, ignoring the edge directions. The cycle is $0 \rightarrow 1 \rightarrow 4 \rightarrow 0$.
