<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8048</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-11-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Length-Constrained Cycle Partition with an Application to UAV Routing</title>
    <abstract language="eng">In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflict hypergraphs, whose cliques yield valid constraints for the MIP models.&#13;
We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a fleet of uncrewed aerial vehicles (UAVs) patrols a set of areas.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-80489</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Kai Hoppmann-Baum</author>
    <submitter>Kai Hoppmann-Baum</submitter>
    <author>Gioni Mexi</author>
    <author>Oleg Burdakov</author>
    <author>Carl Johan Casselgren</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-30</number>
    </series>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="mexi">Mexi, Gioni</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8048/zib_report_20_30.pdf</file>
  </doc>
  <doc>
    <id>8006</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>273</pageFirst>
    <pageLast>282</pageLast>
    <pageNumber>10</pageNumber>
    <edition/>
    <issue/>
    <volume>12296</volume>
    <type>bookpart</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace>Cham</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-09-19</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Minimum Cycle Partition with Length Requirements</title>
    <abstract language="eng">In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances.</abstract>
    <parentTitle language="eng">Integration of Constraint Programming, Artificial Intelligence, and Operations Research</parentTitle>
    <identifier type="isbn">978-3-030-58941-7</identifier>
    <identifier type="doi">10.1007/978-3-030-58942-4_18</identifier>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <editor>Emmanuel Hebrard</editor>
    <submitter>Kai Hoppmann-Baum</submitter>
    <author>Kai Hoppmann-Baum</author>
    <editor>Nysret Musliu</editor>
    <author>Gioni Mexi</author>
    <author>Oleg Burdakov</author>
    <author>Carl Johan Casselgren</author>
    <author>Thorsten Koch</author>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="mexi">Mexi, Gioni</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7709</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>bachelorthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Node Partitioning and Subtours Creation Problem (NPSC)</title>
    <identifier type="urn">urn:nbn:de:0297-zib-77094</identifier>
    <advisor>Thorsten Koch</advisor>
    <author>Gioni Mexi</author>
    <submitter> Hoppmann</submitter>
    <advisor>Kai Hoppmann</advisor>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="persons" number="mexi">Mexi, Gioni</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/7709/ba_mexi.pdf</file>
  </doc>
</export-example>
