Two Commodity Network Design: The Convex HULL

Sastry Trilochan

IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: We study the uncapacitated and capacitated one facility versions of the two commodity network design problem. We characterize optimal solutions and show that we can restrict the search for optimal solutions to feasible solutions with at most one shared path. Using this characterization, we describe the convex hull of integer solutions to the uncapcitated problem using O(m) variables and O(n) constraints. We also describe how Dijkstra’s shortest path algorithm can be used to solve the problem in a transformed graph with O(n) nodes and O(m) arcs. For the capacitated two commodity problem, we show that the problem can be solved either by using any standard shortest path algorithm or by the algorithm described for the uncapacitated case.

Date: 1997-11-01
References: Add references at CitEc
Citations:

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:wp01487

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 ().