<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7768</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2020-03-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited</title>
    <abstract language="eng">In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-77684</identifier>
    <author>Kai-Helge Becker</author>
    <submitter>Benjamin Hiller</submitter>
    <author>Benjamin Hiller</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-05</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>acyclic orientations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>enumeration algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>multiple sources and sinks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>bipolar orientations</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <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="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMATH-MI10">ECMATH-MI10</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7768/ZR-20-05-pdf</file>
  </doc>
  <doc>
    <id>7534</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-12-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Improved optimization models for potential-driven network flow problems via ASTS orientations</title>
    <abstract language="eng">The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-75347</identifier>
    <identifier type="doi">10.12752/7534</identifier>
    <author>Kai-Helge Becker</author>
    <submitter>Benjamin Hiller</submitter>
    <author>Benjamin Hiller</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-58</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>potential-driven network flows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer nonlinear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ASTS orientations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>bipolar orientations</value>
    </subject>
    <collection role="ccs" number="F.">Theory of Computation</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMATH-MI10">ECMATH-MI10</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7534/ZR-19-58.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7534/ZR-19-58_July2020_ZIB.pdf</file>
  </doc>
</export-example>
