Two commodity network design: the convex hull
dc.contributor.author | Sastry, Trilochan | |
dc.date.accessioned | 2010-04-01T09:33:05Z | |
dc.date.available | 2010-04-01T09:33:05Z | |
dc.date.copyright | 1997-11 | |
dc.date.issued | 2010-04-01T09:33:05Z | |
dc.identifier.uri | http://hdl.handle.net/11718/1871 | |
dc.description.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. | en |
dc.language.iso | en | en |
dc.relation.ispartofseries | WP;1997/1411 | |
dc.subject | Convex hull | en |
dc.subject | Network design | en |
dc.subject | commodity network design | en |
dc.title | Two commodity network design: the convex hull | en |
dc.type | Working Paper | en |
Files in this item
This item appears in the following Collection(s)
-
Working Papers [2627]
Working Papers