<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>951</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-04-17</completedDate>
    <publishedDate>2007-04-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the strength of cut-based inequalities for capacitated network design polyhedra</title>
    <abstract language="eng">In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR).</abstract>
    <identifier type="serial">07-08</identifier>
    <identifier type="opus3-id">951</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9512</identifier>
    <author>Christian Raack</author>
    <author>Arie M.C.A. Koster</author>
    <author>Roland Wessäly</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-08</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cutset-polyhedra</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>flow-cutset inequalities</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>network design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="BMBF-Eibone">BMBF-Eibone</collection>
    <collection role="projects" number="MATHEON-B3">MATHEON-B3</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/951/ZR_07_08.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/951/ZR-07-08.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/951/ZR_07_08.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/951/ZR-07-08.ps</file>
  </doc>
</export-example>
