The one facility one commodity network design problem (OFOC) with nonnegative flow costs considers the problem of sending d units of flow from a source to a destination where arc capacity is purchased in batches of C units. The two facility problem (TFOC) is similar, but capacity can be purchased either in batches of C units or one unit. Flow costs are zero. These problems are known to be NP-hard. We describe an exact O(n33n) algorithm for these problems based on the repeated use of a bipartite matching algorithm. We also present a better lower bound of Ω(n2k*) for an earlier Ω(n2k) algorithm described in the literature where k = ⌊d/C⌋ and k* = min{k, ⌊(n − 2)/2⌋}. The matching algorithm is faster than this one for k ≥ ⌊(n − 2)/2⌋. Finally, we provide another reformulation of the problem that is quasi integral. This property could be useful in designing a modified version of the simplex method to solve the problem using a sequence of pivots with integer extreme solutions, referred to as the integral simplex method in the literature.
