<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1105</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>Warsaw University of Technology</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-12-18</completedDate>
    <publishedDate>2008-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the complexity of column generation in survivable network design with path-based survivability mechanisms</title>
    <abstract language="eng">This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures.</abstract>
    <identifier type="serial">08-51</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1146</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11058</identifier>
    <author>Sebastian Orlowski</author>
    <submitter>unknown unknown</submitter>
    <author>Michal Pióro</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-51</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Netzplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Dimensionierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Spaltengenerierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mehrfachausfälle</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>survivable network design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pricing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>complexity</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="68M10">Network design and communication [See also 68R10, 90B18]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="90C08">Special problems of linear programming (transportation, multi-index, etc.)</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1105/ZR_08_51.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1105/ZR_08_51.ps</file>
  </doc>
</export-example>
