Exact formulation and algorithm for two commodity capacitated network design

Abstract

We study the capacitated version of the two commodity network design problem, where capacity can be purchased in batches of C units on each arc at a cost of wij greater than equal 0, dk greater than equal 0 units of flow are sent from source to sink for each commodity k. we characterize optimal solutions for the problem with fixed costs and no flow costs, and show that either [dk/C]C or ([dk/C] 1)C units of each commodity are sent on a shortest path, and the remaining flows possibly share arcs. We show that the problem can be solved in polynomial time. Next, we describe an exact linear programming formulation, i.e., one that guarantees integer optimal solutions, using O(m) variables and O(n) constraints. We also interpret the dual variables and constraints of the formulation as generalizations of the arc constraints and node potential for the shortest path problem. Finally, we discuss several other variations of the single and two commodity problems.