| 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 |
|