<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>953</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-05-18</completedDate>
    <publishedDate>2007-05-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts</title>
    <abstract language="eng">Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or $\frac{1}{2}$, such cuts are known as $\{0,\frac{1}{2}\}$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of $\{0,\frac{1}{2}\}$-cuts is NP-hard. In this paper, we study ways to separate $\{0,\frac{1}{2}\}$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated $\{0,\frac{1}{2}\}$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.</abstract>
    <identifier type="serial">07-10</identifier>
    <identifier type="opus3-id">953</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9531</identifier>
    <enrichment key="SourceTitle">An extended abstract appears in: Proc. 15th annual European Symposium on Algorithms, ESA 2007, Eilat, Israel, Lecture Notes in Computer Science 4698, 2007, pp. 693-704</enrichment>
    <author>Arie M.C.A. Koster</author>
    <submitter>unknown unknown</submitter>
    <author>Adrian Zymolka</author>
    <author>Manuel Kutschka</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-10</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>{0</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>1/2}-Chvatal-Gomory cuts</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>separation algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/953/ZR_07_10.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/953/ZR_07_10.ps</file>
  </doc>
  <doc>
    <id>4793</id>
    <completedYear/>
    <publishedYear>2014</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>178</pageFirst>
    <pageLast>185</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>52</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Network planning under demand uncertainty with robust optimization</title>
    <parentTitle language="eng">IEEE Communications Magazine</parentTitle>
    <identifier type="doi">10.1109/MCOM.2014.6736760</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-42557</enrichment>
    <enrichment key="FulltextUrl">http://opus4.kobv.de/opus4-zib/files/4255/ZR-13-59.pdf</enrichment>
    <author>Thomas Bauschert</author>
    <submitter>Fabio D'Andreagiovanni</submitter>
    <author>Christina Büsing</author>
    <author>Fabio D'Andreagiovanni</author>
    <author>Arie M.C.A. Koster</author>
    <author>Manuel Kutschka</author>
    <author>Uwe Steglich</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="tele">Mathematics of Telecommunication</collection>
    <collection role="projects" number="BMBF-ROBUKOM">BMBF-ROBUKOM</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>4255</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2013-09-25</completedDate>
    <publishedDate>2013-09-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Network Planning under Demand Uncertainty with Robust Optimization</title>
    <abstract language="eng">The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-42557</identifier>
    <identifier type="doi">10.1109/MCOM.2014.6736760</identifier>
    <enrichment key="SourceTitle">Accepted for publication in IEEE Communications Magazine, special issue Advances in Network Planning, on September 8th 2013</enrichment>
    <author>Thomas Bauschert</author>
    <submitter>Fabio D'Andreagiovanni</submitter>
    <author>Christina Büsing</author>
    <author>Fabio D'Andreagiovanni</author>
    <author>Arie M.C.A. Koster</author>
    <author>Manuel Kutschka</author>
    <author>Uwe Steglich</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-59</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network Design, Demand Uncertainty, Robust Optimization, Telecommunications</value>
    </subject>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="tele">Mathematics of Telecommunication</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4255/ZR-13-59.pdf</file>
  </doc>
  <doc>
    <id>3294</id>
    <completedYear>2010</completedYear>
    <publishedYear>2010</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Next Generation Internet</publisherName>
    <publisherPlace>Paris, France</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Towards Robust Network Design using Integer Linear Programming Techniques</title>
    <parentTitle language="eng">Proceedings of the NGI 2010, Paris, France</parentTitle>
    <identifier type="url">http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5534462</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Arie M.C.A. Koster</author>
    <author>Manuel Kutschka</author>
    <author>Christian Raack</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MATHEON-B3">MATHEON-B3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>1389</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-09-01</completedDate>
    <publishedDate>2011-09-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Robust Network Design: Formulations, Valid Inequalities, and Computations</title>
    <abstract language="eng">Traffic in communication networks fluctuates heavily over time.&#13;
  Thus, to avoid capacity bottlenecks, operators highly overestimate&#13;
  the traffic volume during network planning. In this paper we&#13;
  consider telecommunication network design under traffic uncertainty,&#13;
  adapting the robust optimization approach of Bertsimas and Sim [2004]. We&#13;
  present three different mathematical formulations for this problem,&#13;
  provide valid inequalities, study the computational implications,&#13;
  and evaluate the realized robustness.&#13;
&#13;
  To enhance the performance of the mixed-integer programming solver&#13;
  we derive robust cutset inequalities generalizing their&#13;
  deterministic counterparts. Instead of a single cutset inequality&#13;
  for every network cut, we derive multiple valid&#13;
  inequalities by exploiting the extra variables available in the&#13;
  robust formulations. We show that these inequalities define facets&#13;
  under certain conditions and that they completely describe a projection&#13;
  of the robust cutset polyhedron if the cutset consists of a single edge.&#13;
&#13;
  For realistic networks and live traffic measurements we compare the&#13;
  formulations and report on the speed up by the valid inequalities.&#13;
  We study the "price of robustness" and evaluate the&#13;
  approach by analyzing the real network load. The results show that&#13;
  the robust optimization approach has the potential to support&#13;
  network planners better than present methods.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-34</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-13890</identifier>
    <author>Arie M.C.A. Koster</author>
    <submitter>Christian Raack</submitter>
    <author>Manuel Kutschka</author>
    <author>Christian Raack</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-34</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>robust network design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cutset inequalities</value>
    </subject>
    <collection role="msc" number="90Bxx">Operations research and management science</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MATHEON-B3">MATHEON-B3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1389/20110901-ZIB-Report-11-34.pdf</file>
  </doc>
</export-example>
