<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>6439</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>2017-06-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Cone of Flow Matrices: Approximation Hierarchies and Applications</title>
    <abstract language="eng">Let G be a directed acyclic graph with n arcs, a source s and a sink t. We introduce the cone K of flow matrices, which is a polyhedral cone&#13;
generated by the matrices $\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}$, where &#13;
$\vec{1}_P\in\RR^n$ is the incidence vector of the (s,t)-path P.&#13;
We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation&#13;
of a flow, reduce to a linear optimization problem over $\mathcal{K}$.&#13;
This cone is intractable: we prove that the membership problem associated to $\mathcal{K}$&#13;
is NP-complete. However, the affine hull of this cone admits a nice description,&#13;
and we give an algorithm which computes in polynomial-time the decomposition of a matrix&#13;
$X\in \operatorname{span} \mathcal{K}$ as a linear combination of some $\vec{1}_P\vec{1}_P^T$'s.&#13;
Then, we provide two convergent approximation hierarchies, one of them based on a&#13;
completely positive representation of~K.&#13;
We illustrate this approach by computing bounds for &#13;
the quadratic shortest path problem, as well as&#13;
a maximum flow problem with pairwise arc-capacities.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64399</identifier>
    <identifier type="doi">10.1002/net.21820</identifier>
    <enrichment key="SourceTitle">Appeared in: Networks 72(1): 128-150</enrichment>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Marco Blanco</author>
    <author>Thibaut Sauvage</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-32</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Flows in graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Approximation Hierarchies</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Copositive Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Semidefinite Programming</value>
    </subject>
    <collection role="msc" number="05C21">Flows in graphs</collection>
    <collection role="msc" number="90C22">Semidefinite programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6439/matflow_inoc_special_issue_zibreport.pdf</file>
  </doc>
  <doc>
    <id>6842</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>2018-04-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximation Hierarchies for the cone of flow matrices</title>
    <abstract language="eng">Let $G$ be a directed acyclic graph with $n$ arcs, a source $s$ and a sink $t$. We introduce the cone $K$ of flow matrices, which is a polyhedral cone&#13;
generated by the matrices $1_P 1_P^T \in R^{n\times n}$, where &#13;
$1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$.&#13;
Several combinatorial problems reduce to a linear optimization problem over $K$.&#13;
This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a&#13;
completely positive representation of $K$.&#13;
We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-68424</identifier>
    <identifier type="doi">10.1016/j.endm.2018.02.002</identifier>
    <enrichment key="SourceTitle">Appeared in: Electronic Notes in Discrete Mathematics  Volume 64, February 2018, Pages 275–284  INOC 2017 – 8th International Network Optimization Conference</enrichment>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Marco Blanco</author>
    <author>Thibaut Sauvage</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Flows in graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Approximation hierarchies</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Copositive programming</value>
    </subject>
    <collection role="msc" number="90C25">Convex programming</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="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6842/matflow_inoc_zib.pdf</file>
  </doc>
  <doc>
    <id>6124</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>2016-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">We introduce the shortest path problem with crossing costs (SPPCC),  a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. &#13;
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.&#13;
&#13;
In this paper, we provide a comprehensive analysis of the problem. In particular, &#13;
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-61240</identifier>
    <author>Marco Blanco</author>
    <submitter>Nam-Dung Hoang</submitter>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-70</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6124/ZR-16-70.pdf</file>
  </doc>
  <doc>
    <id>6481</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>2017-08-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cost Projection Methods for the Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64817</identifier>
    <enrichment key="FulltextUrl">Appeared in: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)</enrichment>
    <author>Marco Blanco</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Pedro Maristany de las Casas</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-48</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6481/ZR-17-48.pdf</file>
  </doc>
  <doc>
    <id>7971</id>
    <completedYear>2021</completedYear>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-06-18</completedDate>
    <publishedDate>2021-06-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Improved Multiobjective Shortest Path Algorithm</title>
    <abstract language="eng">We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is $\times2$ to $\times9$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-79712</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeno-Noda</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Shortest Path Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Output-Sensitive Multiobjective Combinatorial Problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network Optimization</value>
    </subject>
    <collection role="ccs" number="G.2">DISCRETE MATHEMATICS</collection>
    <collection role="msc" number="05C85">Graph algorithms [See also 68R10, 68W05]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7971/main.pdf</file>
  </doc>
  <doc>
    <id>8095</id>
    <completedYear>2020</completedYear>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-12-01</completedDate>
    <publishedDate>2020-12-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An FPTAS for Dynamic Multiobjective Shortest Path Problems</title>
    <abstract language="eng">We propose in this paper the Dynamic Multiobjective Shortest Problem. It features multidimensional states that can depend on several variables and not only on time; this setting is  motivated by flight planning and electric vehicle routing applications. We give an exact algorithm for the FIFO case and derive from it an FPTAS, which is computationally efficient. It also features the best known complexity in the static case.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-80954</identifier>
    <identifier type="doi">https://doi.org/10.3390/a14020043</identifier>
    <enrichment key="SourceTitle">Appeared in Algorithms 2021, 14(2), 43</enrichment>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Ralf Borndörfer</author>
    <author>Luitgard Kraus</author>
    <author>Antonio Sedeño-Noda</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-31</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Shortest Paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Time Dependent Shortest Paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Approximation Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Flight Planning Problem</value>
    </subject>
    <collection role="msc" number="90B99">None of the above, but in this section</collection>
    <collection role="msc" number="90C29">Multi-objective and goal programming</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-zib/files/8095/main.pdf</file>
  </doc>
</export-example>
