## 90C35 Programming involving graphs or networks [See also 90C27]

### Refine

#### Year of publication

#### Document Type

- ZIB-Report (24)
- Article (2)
- Doctoral Thesis (1)

#### Is part of the Bibliography

- no (27)

#### Keywords

- integer programming (3)
- network design (3)
- Pooling Problem (2)
- Relaxation (2)
- Steiner tree packing (2)
- discrete optimization (2)
- discrete-continuous algorithm (2)
- flight planning (2)
- free flight (2)
- mixed integer programming (2)

#### Institute

- Mathematical Optimization (12)
- ZIB Allgemein (12)
- Network Optimization (4)
- Energy Network Optimization (2)
- Mathematical Algorithmic Intelligence (2)
- Mathematics for Life and Materials Science (2)
- Mathematics of Transportation and Logistics (2)
- Modeling and Simulation of Complex Processes (2)
- Computational Medicine (1)
- Mathematics of Health Care (1)

We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.

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.

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.

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 investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. In this technical report, we characterize the extreme points of the convex hull of our non-convex set, and show that they are not finite, i.e., the convex hull is not polyhedral. This analysis was used to derive valid nonlinear convex inequalities and show that, for a specific case, they characterize the convex hull of our set. The new valid inequalities and computational results are presented in ZIB Report 18-12.

We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound.

Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.

The Steiner tree packing problem (STPP) in graphs is a long studied
problem in combinatorial optimization. In contrast to many other problems,
where there have been tremendous advances in practical problem
solving, STPP remains very difficult. Most heuristics schemes are ineffective
and even finding feasible solutions is already NP-hard. What makes
this problem special is that in order to reach the overall optimal solution
non-optimal solutions to the underlying NP-hard Steiner tree problems
must be used. Any non-global approach to the STPP is likely to fail.
Integer programming is currently the best approach for computing optimal
solutions. In this paper we review some “classical” STPP instances
which model the underlying real world application only in a reduced form.
Through improved modelling, including some new cutting planes, and by
emplyoing recent advances in solver technology we are for the first time
able to solve those instances in the original 3D grid graphs to optimimality.

We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL, DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on three realistic network topologies as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks. These results are independent of the ratio between the demand and capacity granularities, the time scale and the network topology, and show little dependency on the demand structure.