Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/598
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSastry, Trilochan-
dc.date.accessioned2009-12-12T10:54:10Z-
dc.date.available2009-12-12T10:54:10Z-
dc.date.copyright1999-10-
dc.date.issued2009-12-12T10:54:10Z-
dc.identifier.urihttp://hdl.handle.net/11718/598-
dc.description.abstractWe 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.en
dc.language.isoenen
dc.relation.ispartofseriesWP;99-10-09/1554-
dc.subjectcapacitated network designen
dc.subjectCommodityen
dc.subjectInteger optimaen
dc.titleExact formulation and algorithm for two commodity capacitated network designen
dc.typeWorking Paperen
Appears in Collections:Working Papers

Files in This Item:
File Description SizeFormat 
WP 1999_1554.pdf694.52 kBAdobe PDFView/Open


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.