One and two facility network design revisited

Abstract

The one facility one commodity network design problem OFOC with flow costs considers the problem of sending d units of flow from a source to a destination where capacity is purchased in batches of C units. The two commodity 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?. We next consider an extended formulation of the problem, describe an efficient heuristic based on this formulation, and use it to show that for problems with up to five nodes, the formulation guarantees integer optimal solutions. We also give an example of a six node graph for which the extended formulation has a fractional solution. Finally, we provide another reformulation of the problem that is quasi integral, i.e. every edge of the integer polytopes is an edge of the polytopes associated with the linear programming relaxation of the reformulation. 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