Strong Formulations for Network Design Problems with Connectivity Requirements

Simple item page
dc.contributor.authorMagnanti, Thomas L.en_US
dc.contributor.authorRaghavan, S.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T10:07:09Z
dc.date.available2007-05-23T10:07:09Z
dc.date.issued1999en_US
dc.description.abstractThe network design problem with connectivity requirements (NDC)models a wide variety of celebrated combinatorial optimizationproblems including the minimum spanning tree, Steiner tree, andsurvivable network design problems. We develop strong formulationsfor two versions of the edge-connectivity NDC problem: unitaryproblems requiring connected network designs, and nonunitaryproblems permitting non-connected networks as solutions. <p>We(i) present a new directed formulation for the unitary NDC problemthat is stronger than a natural undirected formulation,(ii) project out several classes of valid inequalities---partitioninequalities, odd-hole inequalities, and combinatorial designinequalities---that generalize known classes of valid inequalitiesfor the Steiner tree problem to the unitary NDC problem, and(iii) show how to strengthen and direct nonunitary problems.<p>Our results provide a unifying framework forstrengthening formulations for NDC problems, and demonstratethe strength and power of flow-based formulations fornetwork design problems with connectivity requirements.en_US
dc.format.extent669662 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/6018
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1999-28en_US
dc.subjectnetwork managementen_US
dc.subjectgraph theoryen_US
dc.subjectoptimizationen_US
dc.subjectMixed Integer Programmingen_US
dc.subjectNetwork Designen_US
dc.subjectSystems Integration Methodologyen_US
dc.titleStrong Formulations for Network Design Problems with Connectivity Requirementsen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_99-28.pdf
Size:
653.97 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports