Refine
Document Type
- ZIB-Report (5)
- Article (1)
Language
- English (6)
Has Fulltext
- yes (6) (remove)
Is part of the Bibliography
- no (6)
Keywords
Institute
A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.
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.
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.
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.
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.
We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra's algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft's tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs.
We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90\% in our setting.