Two Commodity Network Design: The Convex HULL
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.
Authors: | Trilochan, Sastry |
---|---|
Institutions: | Economics, Indian Institute of Management |
Saved in:
Saved in favorites
Similar items by person
-
Competitiveness of Indian Manufacturing: Findings of the 1997 Manufacturing Futures Survey
Trilochan, Sastry,
-
An Exact Formulation and Algorithm for Two Commodity Capacitated Network Design
Trilochan, Sastry,
-
An Exact Algorithm for the Uncapacitated Network Design Problem
Trilochan, Sastry,
- More ...