An Exact Formulation and Algorithm for Two Commodity Capacitated Network Design
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.
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,
-
Two Commodity Network Design: The Convex HULL
Trilochan, Sastry,
-
An Exact Algorithm for the Uncapacitated Network Design Problem
Trilochan, Sastry,
- More ...