Two commodity network design: the convex hull

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.