I am working on a problem that can be modeled as a minimum-cost network flow problem where the capacity of edges is 1.

I found Exercise 3.8, Chapter 5 of Parallel and Distributed Computation: Numerical Methods (D. P. Bertsekas and J. N. Tsitsiklis), which says the linear network flow problem for the case where the feasible flow range of each arc is $[0, 1]$ can be converted into a transportation problem, but I cannot come up with a construction or find references to this problem.

To clarify, a transportation problem is in the form of $$\min \sum_{(i,j)\in A} a_{ij}x_{ij},$$ subject to $$\sum_{j|(i,j)\in A}x_{ij}=\alpha_i, \forall\ i=1,\dots,m,$$ $$\sum_{i|(i,j)\in A}x_{ij}=\beta_j,\forall\ j=1,\dots,n,$$ $$x_{ij}\ge 0,\forall\ (i,j)\in A.$$



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.