Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5334Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.creator | Magnanti, Thomas L. | - |
| dc.creator | Raghavant, S. | - |
| dc.date | 2004-05-28T19:34:17Z | - |
| dc.date | 2004-05-28T19:34:17Z | - |
| dc.date | 1999-04 | - |
| dc.date.accessioned | 2013-10-09T02:39:08Z | - |
| dc.date.available | 2013-10-09T02:39:08Z | - |
| dc.date.issued | 2013-10-09 | - |
| dc.identifier | http://hdl.handle.net/1721.1/5334 | - |
| dc.identifier.uri | http://koha.mediu.edu.my:8181/xmlui/handle/1721 | - |
| dc.description | The network design problem with connectivity requirements (NDC) models a wide variety of celebrated combinatorial optimization problems including the minimum spanning tree, Steiner tree, and survivable network design problems. We develop strong formulations for two versions of the edge-connectivity NDC problem: unitary problems requiring connected network designs, and nonunitary problems permitting non-connected networks as solutions. We (i) present a new directed formulation for the unitary NDC problem that is stronger than a natural undirected formulation, (ii) project out several classes of valid inequalities-partition inequalities, odd-hole inequalities, and combinatorial design inequalities-that generalize known classes of valid inequalities for the Steiner tree problem to the unitary NDC problem, and (iii) show how to strengthen and direct nonunitary problems. Our results provide a unifying framework for strengthening formulations for NDC problems, and demonstrate the strength and power of flow-based formulations for network design problems with connectivity requirements. | - |
| dc.format | 3208312 bytes | - |
| dc.format | application/pdf | - |
| dc.language | en_US | - |
| dc.publisher | Massachusetts Institute of Technology, Operations Research Center | - |
| dc.relation | Operations Research Center Working Paper;OR 332-99 | - |
| dc.title | Strong Formulations for Network Design Problems with Connectivity Requirements | - |
| dc.type | Working Paper | - |
| Appears in Collections: | MIT Items | |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.