One and Two Facility Network Design Revisited

Sastry Trilochan

No WP1998-08-05, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

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 polytope is an edge of the polytope 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.

Date: 1998-08-05
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01547

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().