An Exact Formulation and Algorithm for Two Commodity Capacitated Network Design

Sastry Trilochan

No WP1999-10-09, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

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.

Date: 1999-10-09
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01635

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().