<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7879</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-07-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Determining all integer vertices of the PESP polytope by flipping arcs</title>
    <abstract language="eng">We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases.  On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-78793</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2020.5</identifier>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Christian Liebchen</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-19</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="MathPlus-Incubator-Timetabling">MathPlus-Incubator-Timetabling</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7879/ZR-20-19.pdf</file>
  </doc>
</export-example>
