@misc{SagnolBlancoSauvage2017, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {The Cone of Flow Matrices: Approximation Hierarchies and Applications}, issn = {1438-0064}, doi = {10.1002/net.21820}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64399}, year = {2017}, abstract = {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 generated by the matrices \$\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}\$, where \$\vec{1}_P\in\RR^n\$ is the incidence vector of the (s,t)-path P. We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over \$\mathcal{K}\$. This cone is intractable: we prove that the membership problem associated to \$\mathcal{K}\$ is NP-complete. However, the affine hull of this cone admits a nice description, and we give an algorithm which computes in polynomial-time the decomposition of a matrix \$X\in \operatorname{span} \mathcal{K}\$ as a linear combination of some \$\vec{1}_P\vec{1}_P^T\$'s. Then, we provide two convergent approximation hierarchies, one of them based on a completely positive representation of~K. We illustrate this approach by computing bounds for the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities.}, language = {en} } @misc{SagnolBlancoSauvage2018, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {Approximation Hierarchies for the cone of flow matrices}, issn = {1438-0064}, doi = {10.1016/j.endm.2018.02.002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68424}, year = {2018}, abstract = {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 generated by the matrices \$1_P 1_P^T \in R^{n\times n}\$, where \$1_P\in R^n\$ is the incidence vector of the \$(s,t)\$-path \$P\$. Several combinatorial problems reduce to a linear optimization problem over \$K\$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of \$K\$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.}, language = {en} } @misc{BlancoBorndoerferHoangetal.2016, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Schlechte, Thomas and Schlobach, Swen}, title = {The Shortest Path Problem with Crossing Costs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61240}, year = {2016}, abstract = {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. 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. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.}, language = {en} } @misc{BlancoBorndoerferHoangetal.2017, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Maristany de las Casas, Pedro and Schlechte, Thomas and Schlobach, Swen}, title = {Cost Projection Methods for the Shortest Path Problem with Crossing Costs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64817}, year = {2017}, abstract = {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 {\`a} posteriori error bounds.}, language = {en} } @misc{MaristanydelasCasasSedenoNodaBorndoerfer2021, author = {Maristany de las Casas, Pedro and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {An Improved Multiobjective Shortest Path Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79712}, year = {2021}, abstract = {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.}, language = {en} } @misc{MaristanydelasCasasBorndoerferKrausetal.2020, author = {Maristany de las Casas, Pedro and Bornd{\"o}rfer, Ralf and Kraus, Luitgard and Sede{\~n}o-Noda, Antonio}, title = {An FPTAS for Dynamic Multiobjective Shortest Path Problems}, doi = {https://doi.org/10.3390/a14020043}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80954}, year = {2020}, abstract = {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.}, language = {en} }