We investigate the procedure on some analytic examples. As applications, we study the gas transport problem under uncertainties in demand and in physical parameters that affect pressure losses in the pipes. Computational results for examples in large realistic gas network instances demonstrate the applicability as well as the efficiency of the metho},
author = {Kuchlbauer, Martina and Liers, Frauke and Stingl, Michael},
doi = {10.1287/ijoc.2021.1122},
faupublication = {yes},
journal = {Informs Journal on Computing},
keywords = {bundle method; nonlinear robust optimization; inexactness; minimax; gas transport problem},
pages = {2106 - 2124},
peerreviewed = {Yes},
title = {{Adaptive} bundle methods for nonlinear robust optimization},
volume = {34},
year = {2022}
}
@article{faucris.213680824,
abstract = {Today’s gas markets demand more flexibility from the network operators which in turn have to invest in their network infrastructure. As these investments are very cost-intensive and long-lasting, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the resulting challenging optimization tasks. In fact, each subproblem consists of a mixed-integer nonlinear optimization problem. Valid bounds on the objective value are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. The results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time.

problems that were deemed intractable just a few decades ago. However, provably optimal solutions may not be accepted due to the perception of optimization software as a black box. Although well understood by scientists, this lacks easy accessibility for practitioners. Hence, we advocate for introducing the explainability of a solution as another evaluation criterion, next to its objective value, which enables us to find trade-off solutions between these two criteria. Explainability is attained by comparing against (not necessarily optimal) solutions that were implemented in similar situations in the past. Thus, solutions are preferred that exhibit similar features. Although we prove that already in simple cases the explainable model is NP-hard, we characterize relevant polynomially solvable cases such as the explainable shortest-path problem. Our numerical experiments on both artificial as well as real-world road networks show the resulting Pareto front. It turns out that the cost of enforcing explainability can be very small.

for involved commodities often have to be considered jointly as separation constraints have to be

respected. This is for example the case in robot motion or air traffic management. Involving

these discrete separation constraints in the planning of best possible continuous trajectories

makes the task even more complex. Hence, in current practice, the resulting optimization

problems are solved sequentially or with restricted planning space. This leads to potential

losses in the usage of sparse resources.

To overcome these drawbacks, we develop a graph based model for disjoint trajectories

optimization. Further, we present a discretization technique to depict the full available space,

while respecting potentially non-convex restricted areas. As a result, an integer linear opti-

mization program needs to be solved whose size scales with the number of discretization points.

Thereby, even for moderately sized instances a sufficiently detailed representation of space and

time leads to models too large for state of the art hard- and software. To tackle this, we develop

an adaptive-refinement algorithm that works as follows: Starting from an optimal solution to

the integer program in a coarse discretization the algorithm re-optimizes trajectories in an

adaptively refined discretized neighborhood of the current solution. This is further integrated

into a rolling horizon approach. We apply our approach to the integrated trajectory optimiza-

tion and runway scheduling in the surrounding of airports. Computational experiments with

realistic instances show efficiency of the method.

optimization (DRO) problems are often intractable, as they contain semiinfinite

dual constraints. Based on such a semiinfinite reformulation, we present a

safe approximation, that allows for the computation of feasible solutions for

DROs that depend on nonconvex multivariate simple functions. Moreover,

the approximation allows to address ambiguity sets that can incorporate

information on moments as well as confidence sets. The typical strong assumptions

on the structure of the underlying constraints, such as convexity in the

decisions or concavity in the uncertainty found in the literature were, at

least in part, recently overcome in [10]. We start from the duality-based

reformulation approach in [10] that can be applied for DRO constraints based

on simple functions that are univariate in the uncertainty parameters. We

significantly extend their approach to multivariate simple functions which leads

to a considerably wider applicability of the proposed reformulation approach.

In order to achieve algorithmic tractability, the presented safe approximation is

then realized by a discretized counterpart for the semiinfinite dual constraints.

The approximation leads to a computationally tractable mixed-integer positive

semidefinite problem for which state-of-the-art software implementations are

readily available. The tractable safe approximation provides sufficient conditions

for distributional robustness of the original problem, i.e., obtained solutions

are provably robust.

process optimization and production planning tasks must often be optimized for a range of time

periods. Usually, these problems incorporating time structure are very large and cannot be solved to global

optimality by modern solvers within a reasonable period of time. Therefore, the so-called rolling-horizon

approach is often adopted. This approach aims to solve the problem periodically, including additional

information from proximately following periods. In this paper, we first investigate several drawbacks of

this approach and develop an algorithm that compensates for these drawbacks both theoretically and

practically. As a result, the rolling horizon decomposition methodology is adjusted to enable large scale

optimization problems to be solved efficiently. In addition, we introduce conditions that guarantee the

quality of the solutions. We further demonstrate the applicability of the method to a variety of challenging

optimization problems. We substantiate the findings with computational studies on the lot-sizing problem

in production planning, as well as for large-scale real-world instances of the tail-assignment problem in

aircraft management. It proves possible to solve large-scale realistic tail-assignment instances efficiently,

leading to solutions that are at most a few percent away from a globally optimum solutio},
author = {Glomb, Lukas and Liers, Frauke and Rösel, Florian},
doi = {10.1016/j.ejor.2021.07.043},
faupublication = {yes},
journal = {European Journal of Operational Research},
keywords = {Large scale optimization, time decomposition, Rolling Horizon, Lot Sizing, Tail Assignment},
peerreviewed = {Yes},
title = {{A} rolling-horizon approach for multi-period optimization},
url = {https://www.sciencedirect.com/science/article/abs/pii/S0377221721006536},
volume = {unbekannt},
year = {2021}
}
@unpublished{faucris.288229871,
abstract = {In this work, we present algorithmically tractable safe approxima-

tions of distributionally robust optimization (DRO) problems. The considered

ambiguity sets can exploit information on moments as well as confidence sets.

Typically, reformulation approaches using duality theory need to make strong

assumptions on the structure of the underlying constraints, such as convexity

in the decisions or concavity in the uncertainty. In contrast, here we present a

duality-based reformulation approach for DRO problems, where the objective of

the adverserial is allowed to depend on univariate indicator functions. This ren-

ders the problem nonlinear and nonconvex. In order to be able to reformulate

the semiinfinite constraints nevertheless, an exact reformulation is presented

that is approximated by a discretized counterpart. The approximation is re-

alized as a mixed-integer linear problem that yields sufficient conditions for

distributional robustness of the original problem. Furthermore, it is proven that

with increasingly fine discretizations, the discretized reformulation converges

to the original distributionally robust problem. The approach is made concrete

for a challenging, fundamental task in particle separation that appears in

material design. Computational results for realistic settings show that the safe

approximation yields robust solutions of high-quality and can be computed

within short time},
author = {Dienstbier, Jana and Liers, Frauke and Rolfes, Jan},
faupublication = {yes},
keywords = {Distributionally Robust Optimization, Robust Optimization, Stochastic Optimization, Mixed-Integer Optimization, Discrete Optimization},
note = {https://cris.fau.de/converis/publicweb/Publication/288229871},
peerreviewed = {automatic},
title = {{A} {Safe} {Approximation} {Based} on {Mixed}-{Integer} {Optimization} for
{Non}-{Convex} {Distributional} {Robustness} {Governed} by {Univariate}
{Indicator} {Functions}},
url = {https://arxiv.org/abs/2301.11185},
year = {2024}
}
@article{faucris.302881441,
abstract = {Recent developments in the field of data analysis offer enormous potential to derive predictions of future aircraft maintenance necessities from observable aircraft attributes. This procedure is called Predictive Maintenance. The Predictive Maintenance generates considerable business benefits compared to alternatives like reactive or preventive maintenance for various reasons. Nevertheless, recognizing a maintenance necessity is only the first step, since the execution of the maintenance action has to fit into the airlines operational schedule. An essential step to realize financial benefits is to integrate Predictive Maintenance into the airlines optimization processes. To contribute to this task, we expand a well-known Tail Assignment model for the assignment of a potentially heterogeneous fleet of aircraft to a schedule of flights by a number of part failure scenarios. This results in a stochastic mixed integer linear optimization program, for which an optimization algorithm with solution guarantees is developed. This optimization algorithm is based on Benders Decomposition, which is concretized for the Tail Assignment problem and optimized for this task. Using this algorithm, a large proportion of the recovery costs for almost all instances tested is saved. The algorithm solves all instances in a reasonable amount of time. The algorithm uses a state-of-the-art mixed-integer linear solver, implementing a decomposition-based solution procedure for stochastic programs, called the L-shaped method. To demonstrate the potential of the approach, we benchmark our results using four strategies, motivated by commonly used preventive, reactive and passive approaches. Our approach leads to considerable cost savings when compared to each of the four benchmark approaches. The algorithms are tested on a set of instances with up to 80 flights based on a pre-pandemic schedule of a larger German airline. To the best of our knowledge, this article presents the first attempt to implement an exact optimization approach integrating malfunction predictions of the form presented into a Tail Assignment model.},
author = {Glomb, Lukas and Liers, Frauke and Rösel, Florian},
doi = {10.1007/s13272-023-00663-0},
faupublication = {yes},
journal = {CEAS Aeronautical Journal},
keywords = {L-shaped method; Predictive maintenance; Stochastic optimization; Tail Assignment},
note = {CRIS-Team Scopus Importer:2023-05-26},
peerreviewed = {Yes},
title = {{A} stochastic optimization approach for optimal {Tail} {Assignment} with knowledge-based predictive maintenance},
year = {2023}
}
@article{faucris.122464804,
abstract = {In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we focus on binary Steiner trees in which all node degrees are required to be at most three. It is shown that finding a binary Steiner tree is NP-complete for arbitrary graphs. We relate the problem to Steiner trees without degree constraints as well as degree-constrained spanning trees by proving approximation ratios. Further, we give integer programming formulations for this problem on undirected and directed graphs and study the associated polytopes for both cases. Some classes of facets are introduced. Based on this study a branch-&-cut approach is developed and evaluated on biological instances coming from the reconstruction of phylogenetic trees. We are able to solve nearly all instances up to 200 nodes to optimality within a limited amount of time. This shows the effectiveness of our approach.},
author = {Liers, Frauke and Martin, Alexander and Pape, Susanne},
doi = {10.1016/j.disopt.2016.05.006},
faupublication = {yes},
journal = {Discrete Optimization},
keywords = {Steiner tree; Degree constraint; Steiner ratio; Integer programming; Polytope; Branch-&-cut},
pages = {85-117},
peerreviewed = {Yes},
title = {{Binary} {Steiner} {Trees}: {Structural} {Results} and an {Exact} {Solution} {Approach}},
volume = {21},
year = {2016}
}
@incollection{faucris.123561064,
author = {Liers, Frauke and Jünger, Michael and Reinelt, Gerhard and Rinaldi, Giovanni},
booktitle = {New Optimization Algorithms in Physics},
doi = {10.1002/3527603794.ch4},
editor = {Alexander K. Hartmann, Heiko Rieger},
faupublication = {no},
keywords = {new optimization algorithms, applications in physics, ground states, maximum cuts, solving hard max-cut problems, linear programming relaxations of max-cut, branch-and-cut},
pages = {47-68},
peerreviewed = {unknown},
publisher = {Wiley-VCH},
title = {{Computing} {Exact} {Ground} {States} of {Hard} {Ising} {Spin} {Glass} {Problems} by {Branch}-and-{Cut}},
year = {2004}
}
@inproceedings{faucris.290212898,
abstract = {A storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality.},
author = {Gronemann, Martin and Juenger, Michael and Liers, Frauke and Mambelli, Francesco},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
date = {2016-09-19/2016-09-21},
doi = {10.1007/978-3-319-50106-2{\_}29},
editor = {Martin Nollenburg, Yifan Hu},
faupublication = {yes},
isbn = {9783319501055},
note = {CRIS-Team Scopus Importer:2023-03-07},
pages = {367-381},
peerreviewed = {unknown},
publisher = {Springer Verlag},
title = {{Crossing} minimization in storyline visualization},
venue = {Athens},
volume = {9801 LNCS},
year = {2016}
}
@incollection{faucris.117660664,
abstract = {A storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality.},
author = {Gronemann, Martin and Jünger, Michael and Liers, Frauke and Mambelli, Francesco},
booktitle = {Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization},
faupublication = {yes},
peerreviewed = {unknown},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {{Crossing} {Minimization} in {Storyline} {Visualization}},
url = {https://arxiv.org/abs/1608.08027},
year = {2016}
}
@article{faucris.277659424,
abstract = {Stochastic Optimization (SO) is a classical approach for optimization
under uncertainty that typically requires knowledge about the
probability distribution of uncertain parameters. As the latter is often
unknown, Distributionally Robust Optimization (DRO) provides a strong
alternative that determines the best guaranteed solution over a set of
distributions (ambiguity set). In this work, we present an approach for
DRO over time that uses online learning and scenario observations
arriving as a data stream to learn more about the uncertainty. Our
robust solutions adapt over time and reduce the cost of protection with
shrinking ambiguity. For various kinds of ambiguity sets, the robust
solutions converge to the SO solution. Our algorithm achieves the
optimization and learning goals without solving the DRO problem exactly
at any step. We also provide a regret bound for the quality of the
online strategy which converges at a rate of $ O(\log T / \sqrt{T})$,
where $T$ is the number of iterations. Furthermore, we illustrate the
effectiveness of our procedure by numerical experiments on mixed-integer
optimization instances from popular benchmark libraries and give
practical examples stemming from telecommunications and routing. Our
algorithm is able to solve the DRO over time problem significantly
faster than standard reformulation},
author = {Aigner, Kevin-Martin and Bärmann, Andreas and Braun, Kristin and Liers, Frauke and Pokutta, Sebastian and Schneider, Oskar and Sharma, Kartikey and Tschuppik, Sebastian},
doi = {10.1287/ijoo.2023.0091},
faupublication = {yes},
journal = {INFORMS Journal on Optimization},
keywords = {distributionally robust optimization; gradient descent; learning over time},
peerreviewed = {Yes},
title = {{Data}-driven {Distributionally} {Robust} {Optimization} over {Time}},
url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/496},
year = {2023}
}
@article{faucris.213691834,
abstract = {In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding whether the uncertainty set is contained within the projection of the feasible region onto the uncertainty-space. Moreover, the considered sets are assumed to be described by polynomials. For answering this question, two very general approaches using methods from polynomial optimization are presented---one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares (SOS) polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a nonconvex feasibility problem where the feasible set is described by a composition of polynomials with the absolute value function. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, the problem can be decided by eliminating the absolute value functions and solving the resulting linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. It turns out that for instances where robust feasibility or infeasibility can be decided successfully, level 2 or level 3 of the Lasserre relaxation hierarchy typically is sufficient.

Mathematical optimization can be used to model and solve these planning problems.

However, in order to convince decision-makers of an alternative solution structure, mathematical solutions must be comprehensible and tangible. In this work, we describe optimized decision-support systems for ambulatory care using the example of four different planning problems that cover a variety of aspects in terms of planning scope and decision support tools. The planning problems that we present are the problem of positioning centers for vaccination against Covid-19 (strategical) and emergency doctors (strategical/tactical), the out-of-hours pharmacy planning problem (tactical), and the route planning of patient transport services (operational). For each problem, we describe the planning question, give an overview of the mathematical model and present the implemented decision support application.

of data. In order to achieve this, it utilizes prior knowledge about the samples that shall be reconstructed. Focusing on image reconstruction in nanotomography, this work proposes enhancements by including additional problem-specific knowledge. In more detail, we propose further classes of algebraic inequalities that are added to the compressed sensing model. The first consists in a valid upper bound on the pixel brightness. It only exploits general information about the projections and is thus applicable to a broad range of reconstruction problems. The second class is applicable whenever the sample material is of roughly homogeneous composition. The model favors a constant density and penalizes deviations from it. The resulting mathematical optimization models are algorithmically tractable and can be solved to global optimality by state-of-the-art available implementations of interior point methods. In order to evaluate the novel models, obtained results are compared to existing image reconstruction methods, tested on simulated and experimental data sets. The experimental data comprise one 360° electron tomography tilt series of a macroporous zeolite particle and

one absorption contrast nano X-ray computed tomography (nano-CT) data set of a copper microlattice structure. The enriched models are optimized quickly and show improved reconstruction quality, outperforming the existing models. Promisingly, our approach yields superior reconstruction results, particularly when information about the samples is available for a small number of tilt angles only.

In this work, we study the runway scheduling problem with aircraft precedences and safety distance constraints. We consider two extreme scenarios. In the best-case scenario, the two planners cooperate completely in order to determine optimized schedules. In the worst-case scenario, however, the planning tools compete and act as adversaries. Using techniques from mathematical optimization, we model these two scenarios. We experimentally evaluate the approaches on randomly generated instances with respect to running times for solving the problems to global optimality and with respect to the computed throughput. On small examples, we show that indeed there can be large differences in the runway utilization in the two scenarios. It would be interesting to investigate whether today’s real schedules are closer to the best-case or closer to the worst-case scenario in order to understand whether the development, implementation and maintenance of an integrated tool could pay off.},
author = {Liers, Frauke and Martin, Alexander and Peter, Andrea},
faupublication = {yes},
peerreviewed = {automatic},
title = {{Mathematical} {Analysis} of {Runway} {Scheduling} with {Aircraft} {Precedences}},
year = {2017}
}
@article{faucris.248597009,
abstract = {We investigate a challenging task in ambulatory care, the minimizing of delays of patient transports. In practice, a limited number of vehicles is available for non-rescue transports. Furthermore, the dispatcher rarely has access to complete information when establishing a transport plan for dispatching the vehicles. If additional transport is requested on demand then schedules need to be updated, which can lead to long delays. We model the scheduling of patient transports as a vehicle routing problem with general time windows and solve it as a mixed-integer linear problem that is modified whenever additional transport information becomes available. We propose a modeling approach that is designed to determine fair and stable plans. Furthermore, we show that the model can easily be modified when transports need to satisfy additional requirements, e.g., during pandemics, exemplarily the Covid-19 pandemic. To show the applicability and efficiency of our modeling approach, we conduct a numerical study using historical data from the region of Middle Franconia. The results reveal and show that, by applying mathematical optimization - or, to be more precise by solving mixed-integer linear problem formulations - one can significantly decrease delays and have considerable potential for optimized patient transports.

The increasing complexity in particle science and
technology requires the ability to deal with multidimensional property
distributions. We present the theoretical background for
multidimensional fractionations by transferring the concepts known from
one dimensional to higher dimensional separations. Particles in fluids
are separated by acting forces or velocities, which are commonly induces
by external fields, e.g., gravitational, centrifugal or
electro-magnetic fields. In addition, short-range force fields induced
by particle interactions can be employed for fractionation. In this
special case, nanoparticle chromatography is a recent example. The
framework for handling and characterizing multidimensional separation
processes acting on multidimensional particle size distributions is
presented. Illustrative examples for technical realizations are given
for shape-selective separation in a hydrocyclone and for
density-selective separation in a disc separator.

Assignment, Tail Assignment and the associated control of ground processes between consecutive flights,

called Turnaround Handling. All of these planning problems have in common that they often need to be

reoptimized on the day of execution due to unplanned events. In many cases, this is still done manually

with the expertise of airline operators in the airline operations center. In order to automate this process and

to be able to find the best possible reoptimization solution, the medium-term aircraft assignments and the

short-term plannable turnaround processes should be optimized in an integrated way. For this purpose we

provide a new integrated mixed integer program, which combines Fleet Assignment, Tail Assignment and

Turnaround Handling. Due to the size of the model, it cannot be solved efficiently as a complete model.

Therefore, we develop a new decomposition algorithm that alternately solves the combined assignment

problems and the turnaround model, and projects the turnaround costs into the objective function of the

combined assignment model. In a computational study with realistic airline data, it is shown that for

many problem instances this method yields feasible and optimal solutions much faster than comparable

benchmark algorithm}, author = {Glomb, Lukas and Liers, Frauke and Rösel, Florian}, doi = {10.1016/j.ejor.2023.03.036}, faupublication = {yes}, journal = {European Journal of Operational Research}, keywords = {OR in Airlines, Mixed Integer Programming, Decomposition, Tail Assignment, Turnaround Optimization}, note = {CRIS-Team Scopus Importer:2023-06-16}, pages = {1051 - 1071}, peerreviewed = {Yes}, title = {{Optimizing} integrated aircraft assignment and turnaround handling}, volume = {310}, year = {2023} } @article{faucris.262995087, abstract = {Currently, few approaches are available for general nonlinear robust optimization. Those that do exist typically require restrictive assumptions on the adversarial problem or do not guarantee robust protection. To address this, we present an algorithm that combines outer approximation with a bundle method. This algorithm is applicable to convex mixed-integer nonlinear robust optimization problems and necessitates only inexact worst-case evaluations. A key feature of this method is that it does not rely on a specific structure of the adversarial problem and allows it to be non-convex. A major challenge of such a general nonlinear setting is ensuring robust protection, as this calls for a global solution of the adversarial problem. However, our method is able to achieve this, requiring worst-case evaluations only up to a certain precision. For example, the necessary assumptions can be met by approximating a non-convex adversarial problem via piecewise linearization and solving the resulting problem up to any requested error as a mixed-integer linear problem.

We model a robust optimization problem as a nonsmooth mixed-integer nonlinear problem and tackle it adopting an outer approximation approach that requires only inexact function values and subgradients. To deal with the arising nonlinear subproblems, we render an adaptive bundle method applicable to this setting. Relying on its convergence to approximate critical points, we prove, as a consequence, finite convergence of the outer approximation approach.

As an application, we study the gas transport problem under uncertainties on realistic instances and provide computational results demonstrating the efficiency of our method},
author = {Kuchlbauer, Martina and Liers, Frauke and Stingl, Michael},
doi = {10.1007/s10957-022-02114-y},
faupublication = {yes},
journal = {Journal of Optimization Theory and Applications},
keywords = {robust optimization; mixed-integer nonlinear optimization; outer approximation; bundle method; gas transport problem},
pages = {1056–1086},
peerreviewed = {Yes},
title = {{Outer} approximation for mixed-integer nonlinear robust optimization},
url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/414},
year = {2022}
}
@article{faucris.123525424,
abstract = {The MAX-CUT problem asks for partitioning the nodes V of a graph G = (V, E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the MAX-CUT problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694-697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25-36, Springer, Berlin, 1999). The running time of the former can be bounded by O(|V| 3/2 log |V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of O(|V| 3/2 (log|V|) 3/2)α(|V|), where α(|V|) is the inverse Ackermann function, it can solve large instances in practice. In this work, we present a new and simple algorithm for determining maximum cuts for arbitrary weighted planar graphs. Its running time is bounded by O(|V| 3/2 log|V|), the same bound achieved by Shih et al. It can easily determine maximum cuts in huge random as well as real-world graphs with up to 10 nodes. We present experimental results for our method using two different matching implementations. We furthermore compare our approach with those of Shih et al. and Berman et al. It turns out that our algorithm is considerably faster in practice than Shih et al. Moreover, it yields a much smaller associated graph. Its expanded graph size is comparable to that of Berman et al. However, whereas the procedure of generating the expanded graph in Berman et al. is very involved (thus needs a sophisticated implementation), implementing our approach is an easy and straightforward task. © Springer Science+Business Media, LLC 2010.},
author = {Liers, Frauke and Pardella, Gregor L.},
doi = {10.1007/s10589-010-9335-5},
faupublication = {no},
journal = {Computational Optimization and Applications},
keywords = {Kasteleyn city; Maximum cut; Perfect matching; Planar graph; T-join},
pages = {323-344},
peerreviewed = {Yes},
title = {{Partitioning} planar graphs: {A} fast combinatorial approach for max-cut},
volume = {51},
year = {2012}
}
@article{faucris.117660444,
abstract = {Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. In this paper, we develop a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Instead of determining arrival/departure times to the minute in this phase yet, we assign *several* aircraft to the same time window of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, we solve a generalized assignment problem on a bipartite graph. To know how many aircraft can be assigned to one time window, we consider separation requirements for consecutive aircraft types. In reality, however, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. Thus, we present approaches to incorporate uncertainty directly in our model in order to achieve a stabilization with respect to changes in the data. Namely, we use techniques from robust optimization and stochastic optimization. Further, we analyze real-world data from a large German airport to obtain realistic delay distributions, which turn out to be two-parametric Γ-distributions. Finally, we describe a simulation environment to test our new solution methods.},
author = {Kapolke, Manu and Fürstenau, Norbert and Heidt, Andreas and Liers, Frauke and Mittendorf, Monika and Weiß, Christian},
doi = {10.1016/j.jairtraman.2016.02.004},
faupublication = {yes},
journal = {Journal of Air Transport Management},
keywords = {Pre-tactical planning; Runway; Optimization; Uncertainty; Robustness; Data analysis},
peerreviewed = {Yes},
title = {{Pre}-tactical optimization of runway utilization under uncertainty},
year = {2016}
}
@incollection{faucris.110458964,
abstract = {Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). In a previous paper, we developed a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Further, we investigated the impact of disturbances on our solutions, since in reality uncertainty and inaccuracy almost always lead to deviations from actual plans. In this paper, we now present approaches to incorporate uncertainty directly in our model in order to achieve a stabilization with respect to changes in the data. Namely, we use techniques from robust optimization and stochastic optimization. Further, we analyze real-world data from a large German airport to obtain realistic delay distributions, which turn out to be two-parametric Γ-distributions. We describe a simulation environment and test our new solution methods against standard algorithms (e.g., First-Come-First-Serve). The encouraging results show that our approaches significantly reduce the number of necessary replan nings.},
author = {Fürstenau, Norbert and Heidt, Andreas and Kapolke, Manu and Liers, Frauke and Mittendorf, Monika and Weiß, Christian},
booktitle = {Proceedings of the SESAR Innovations Days 2015},
editor = {Dirk Schäfer},
faupublication = {yes},
keywords = {runway utilization; planning,pre-tactical; optimization; uncertainties; stochastic; robust; algorithms; models; validation; Monte Carlo simulation},
peerreviewed = {unknown},
publisher = {Eurocontrol},
title = {{Pre}-{Tactical} {Planning} of {Runway} {Utilization} {Under} {Uncertainty}: {Optimization} and {Validation}},
year = {2015}
}
@inproceedings{faucris.290246964,
abstract = {Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. In this paper, we develop a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Instead of determining arrival/departure times to the minute in this phase yet, we assign several aircraft to the same time window of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, we solve a generalized assignment problem on a bipartite graph. To know how many aircraft can be assigned to one time window, we consider distance requirements for consecutive aircraft types. We develop an optimization model, which can be solved fast in practice but may provide unnecessary large time buffers, and extend it to a model that solves the problem to global optimality. In reality, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. We present computational results concerning the abovementioned optimization approaches and investigate the impact of disturbances on our deterministic solutions. As a next step, we will incorporate uncertainties directly in our model. Therefore, we analyze real-world data from a large German airport in order to obtain realistic delay distributions and describe a simulation environment to test current and future solution methods.},
author = {Heidt, Andreas and Kapolke, Manu and Liers-Bergmann, Frauke and Fürstenau, Norbert and Helmke, Hartmut},
booktitle = {SIDs 2014 - Proceedings of the SESAR Innovation Days},
date = {2014-11-25/2014-11-27},
editor = {Dirk Schaefer},
faupublication = {yes},
isbn = {9782874970771},
note = {CRIS-Team Scopus Importer:2023-03-07},
peerreviewed = {unknown},
publisher = {EUROCONTROL},
title = {{Pre}-tactical time window assignment: {Runway} utilization and the impact of uncertainties},
venue = {Madrid, ESP},
year = {2014}
}
@incollection{faucris.117399964,
abstract = {Efficient planning of runway utilisation is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. However, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. In this paper, we develop an optimization approach for the pre-tactical planning phase that provides some flexibility in the face of small disturbances in the input data, so that we need to change our plans less frequently. Instead of determining arrival/departure times to the minute in this phase yet, we assign several aircraft to the same time slot of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, this leads to a generalised assignment problem on a bipartite graph. We develop an integer program (IP), which can be solved very fast but may provide unnecessary large time buffers, and extend it to a mixed integer program (MIP) that solves the problem to global optimality. We present computational results concerning the abovementioned optimization approach and investigate the impact of disturbances on our deterministic solutions. As a next step, we will incorporate uncertainties directly in our model. Therefore, we analyse real-world data from a large German airport in order to obtain realistic delay distributions and describe a simulation environment to test current and future solution methods.},
author = {Heidt, Andreas and Kapolke, Manu and Liers, Frauke and Fürstenau, Norbert and Helmke, Hartmut},
booktitle = {Proceedings of the SESAR Innovation Days 2014},
editor = {Dirk Schaefer, Javier Saez},
faupublication = {yes},
isbn = {978-2-87497-077-1},
keywords = {arrival / departure scheduling; stochastic optimization; robustness; delay statistics; modeling},
peerreviewed = {unknown},
title = {{Pre}-tactical {Time} {Window} assignment: {Runway} {Utilization} and the {Impact} of {Uncertainties}},
url = {http://www.sesarinnovationdays.eu},
year = {2014}
}
@article{faucris.314482087,
author = {Kuchlbauer, Martina and Dienstbier, Jana and Muneer, Adeel and Hedges, Hanna and Stingl, Michael and Liers, Frauke and Pflug, Lukas},
doi = {10.1016/j.compchemeng.2024.108619},
faupublication = {yes},
journal = {Computers & Chemical Engineering},
peerreviewed = {Yes},
title = {{Quality} {Control} in {Particle} {Precipitation} via {Robust} {Optimization}},
year = {2024}
}
@article{faucris.217929705,
abstract = {For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. To the best of our knowledge, the approaches for the RRF presented in the literature are restricted to continuous optimization problems. In this work, we first analyze relations between the RRF of a MIP and its continuous linear programming relaxation. In particular, we derive conditions under which a MIP and its continuous relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied and computed for a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the concept of the RRF to MIPs including “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In this extended setting, we again analyze relations between the RRF for a MIP and its continuous relaxation. Afterward, we present methods for computing the RRF for continuous linear as well as mixed-integer problems with safe constraints and variables. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 library for the calculation of the RR},
author = {Liers, Frauke and Schewe, Lars and Thürauf, Johannes},
doi = {10.1287/ijoc.2020.1030},
faupublication = {yes},
journal = {Informs Journal on Computing},
keywords = {Robust Optimization; Mixed-integer programming; Uncertainty sets; Robust feasibility},
peerreviewed = {Yes},
title = {{Radius} of {Robust} {Feasibility} for {Mixed}-{Integer} {Problems}},
url = {http://www.optimization-online.org/DB{\_}HTML/2019/05/7219.html},
year = {2021}
}
@article{faucris.238177830,
abstract = {We propose a mathematical optimization model and its solution for joint
chance constrained DC Optimal Power Flow. In this application, it is
particularly important that there is a high probability of transmission
limits being satisfied, even in the case of uncertain or fluctuating
feed-in from renewable energy sources. In critical network situations
where the network risks overload, renewable energy feed-in has to be
curtailed by the transmission system operator (TSO). The TSO can reduce
the feed-in in discrete steps at each network node. The proposed
optimization model minimizes curtailment while ensuring that there is a
high probability of transmission limits being maintained. The latter is
modeled via (joint) chance constraints that are computationally
challenging. Thus, we propose a solution approach based on the robust
safe approximation of these constraints. Hereby, probabilistic
constraints are replaced by robust constraints with suitably defined
uncertainty sets constructed from historical data. The uncertainty sets
are calculated by encompassing randomly drawn scenarios using the
scenario approach proposed by Margellos et al. (IEEE Transactions on
Automatic Control, 59 (2014)). The ability to discretely control the
power feed-in then leads to a robust optimization problem with
decision-dependent uncertainties, i.e. the uncertainty sets depend on
decision variables. We propose an equivalent mixed-integer linear
reformulation for box uncertainties with the exact linearization of
bilinear terms. Finally, we present numerical results for different test
cases from the Nesta archive, as well as for a real network. We
consider the discrete curtailment of solar feed-in, for which we use
real-world weather and network data. The experimental tests demonstrate
the effectiveness of this method and run times are very fast. Moreover,
on average the calculated robust solutions lead only to a small increase
in curtailment, when compared to nominal solutions.},
author = {Aigner, Kevin-Martin and Clarner, Jan-Patrick and Liers, Frauke and Martin, Alexander},
doi = {10.1016/j.ejor.2021.10.051},
faupublication = {yes},
journal = {European Journal of Operational Research},
keywords = {OR in energy; optimal power flow; chance constraints; robust optimization; decision-dependent uncertainty; robust approximation; safe approximation; scenario approach; mixed-integer linear optimization;},
peerreviewed = {Yes},
title = {{Robust} {Approximation} of {Chance} {Constrained} {DC} {Optimal} {Power} {Flow} under {Decision}-{Dependent} {Uncertainty}},
url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/312},
year = {2022}
}
@article{faucris.266554642,
abstract = {We present a robust approximation of joint chance constrained DC Optimal Power Flow in combination with a model-based prediction of uncertain power supply via R-vine copulas.

It is applied to optimize the discrete curtailment of solar feed-in in an electrical distribution network and guarantees network stability under fluctuating feed-in.

This is modeled by a two-stage mixed-integer stochastic optimization problem proposed by Aigner et al. (European Journal of Operational Research, (2021)).

The solution approach is based on the approximation of chance constraints via robust constraints using suitable uncertainty sets.

The resulting robust optimization problem has a known equivalent tractable reformulation.%, which can be solved with standard software.

To compute uncertainty sets that lead to an inner approximation of the stochastic problem, an R-vine copula model is fitted to the distribution of the multi-dimensional power forecast error, i.e., the difference between the forecasted solar power and the measured feed-in at several network nodes.

The uncertainty sets are determined by encompassing a sufficient number of samples drawn from the R-vine copula model.

Furthermore, an enhanced algorithm is proposed to fit R-vine copulas which can be used to draw conditional samples for given solar radiation forecasts.

The experimental results obtained for real-world weather and network data demonstrate the effectiveness of the combination of stochastic programming and model-based prediction of uncertainty via copulas.

We improve the outcomes of previous work by showing that the resulting uncertainty sets are much smaller and lead to less conservative solutions while maintaining the same probabilistic guarantees.

and demonstrate computationally that a guaranteed yield is met for all growth rates within previously defined regions. The protection against uncertainties only reduces the maximum amount of product that can be obtained by a negligible margin.

The runway is the main element that combines airside and groundside of the ATM System. Thus, it is crucial to develop efficient models and planning algorithms for its effective usage. The best planning algorithm, however, is useless if the resulting plans cannot be implemented in the real world. This often happens because the input data of the planning algorithms face disturbances or changes over time, respectively. For example, an estimated time of arrival/departure of an aircraft may be changed. It is usually not certain for the next ten hours.

In this work, we study the runway scheduling problem under uncertain conditions. First, we present mathematical optimization models that ignore uncertainties. In the most effective approach, we compute for every discretized point in time whether an aircraft is scheduled and if so, which one is. Then, in each planning step we take uncertainties into account. We then apply different robust optimization methods in order to devise solution approaches that lead to stable plans. These optimization approaches are integrated into a simulation tool and evaluated in different traffic scenarios.

The Monte-Carlo simulations for a mixed-mode runway system show that our robust approaches result in fewer sequence changes and target time updates, when compared to the usual approach in which the plan is simply updated in case of infeasibility. Thus, we show that protection against uncertainties by using robust optimization indeed leads to considerably more stable plans.

}, author = {Heidt, Andreas and Helmke, Hartmut and Kapolke, Manu and Liers, Frauke and Martin, Alexander}, doi = {10.1016/j.jairtraman.2016.02.009}, faupublication = {yes}, journal = {Journal of Air Transport Management}, keywords = {Scheduling; Uncertainty; Time-indexed model; MIP; Mixed-integer programming; Dynamic time-indexed model; Strict robustness; Light robustness}, pages = {28-37}, peerreviewed = {Yes}, title = {{Robust} runway scheduling under uncertain conditions}, volume = {56}, year = {2016} } @inproceedings{faucris.290246720, abstract = {The runway system is the main element that combines airside and groundside of the ATM System. Efficient models and planning algorithms are required. The best planning algorithm, however, is useless if the resulting plans cannot be implemented in the real world. This often happens because the input data of the planning algorithms is disturbed respectively it changes. For example, an estimated time of an aircraft is not stable for the next ten hours. These disturbances are not deterministic, but often their stochastic distributions with mean values and standard deviations are known. We present a robust model together with an optimization algorithm which explicitly incorporates the knowledge of uncertainty into each planning step. Our approach transforms the planning problem into an assignment problem with side constraints. We compute for every discretized point in time whether an aircraft is scheduled and if so, which one is. Experimentally, we show that runtimes are better than when using a different non-linear integer optimization model. Our Monte-Carlo simulation for a mixed-mode runway system shows that our approach results in fewer sequence changes and target time updates compared to the usual approach of just updating the plan if the actual plan is not feasible any more.}, author = {Heidt, Andreas and Helmke, Hartmut and Liers, Frauke and Martin, Alexander}, booktitle = {SIDs 2014 - Proceedings of the SESAR Innovation Days}, date = {2014-11-25/2014-11-27}, editor = {Dirk Schaefer}, faupublication = {yes}, isbn = {9782874970771}, keywords = {Dynamic time-indexed model; MIP; Mixed mode runway scheduling; Mixed-integer programming; Scheduling; Time-indexed model; Uncertainty}, note = {CRIS-Team Scopus Importer:2023-03-07}, peerreviewed = {unknown}, publisher = {EUROCONTROL}, title = {{Robust} runway scheduling using a time-indexed model}, venue = {Madrid}, year = {2014} } @incollection{faucris.123286284, abstract = {

The runway system is the main element that combines airside and groundside of the ATM System. Efficient models and planning algorithms are required. The best planning algorithm, however, is useless if the resulting plans cannot be implemented in the real word. This often happens because the input data of the planning algorithms is disturbed respectively it changes. For example, an estimated time of an aircraft is not stable for the next ten hours. These disturbances are not deterministic, but often their stochastic distributions with mean values and standard deviations are known. We present a robust model together with an optimization algorithm which explicitly incorporates the knowledge of uncertainty into each planning step. Our approach transforms the planning problem into an assignment problem with side constraints. We compute for every discretized point in time whether an aircraft is scheduled and if so, which one is. Experimentally, we show that running times are better than when using a different non-linear integer optimization model. Our Monte-Carlo simulation for a mixed-mode runway system shows that our approach results in fewer sequence changes and target time updates compared to the usual approach of just updating the plan if the actual plan is not feasible any more.

}, author = {Heidt, Andreas and Helmke, Hartmut and Liers, Frauke and Martin, Alexander}, booktitle = {Proceedings of the SESAR Innovation Days 2014}, editor = {D.~Schäfer}, faupublication = {yes}, isbn = {978-2-87497-077-1}, keywords = {scheduling, uncertainty, time-indexed model, MIP, mixed-integer programming, dynamic time-indexed model, mixed mode runway scheduling}, peerreviewed = {unknown}, title = {{Robust} {Runway} {Scheduling} using a time-indexed model}, year = {2014} } @article{faucris.123091804, abstract = {Maximum flow problems occur in a wide range of applications. Although already well studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting path or on pushrelabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (1990) [12] for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm, flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on instances coming from applications in theoretical physics and computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods. © 2011 Elsevier B.V. All rights reserved.}, author = {Liers, Frauke and Pardella, Gregor L.}, doi = {10.1016/j.dam.2011.06.030}, faupublication = {no}, journal = {Discrete Applied Mathematics}, keywords = {Hybrid algorithm; Maximum flow; Minimum cut; Subgraph shrinking}, pages = {2187-2203}, peerreviewed = {Yes}, title = {{Simplifying} maximum flow computations: {The} effect of shrinking and good initial flows}, volume = {159}, year = {2011} } @article{faucris.119916324, abstract = {We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as { 0 , 1 2 } -Chvátal–Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver.}, author = {Cacchiani, Valentina and Jünger, Michael and Liers, Frauke and Lodi, Andrea and Schmidt, Daniel R.}, doi = {10.1007/s10107-016-0991-9}, faupublication = {yes}, journal = {Mathematical Programming}, keywords = {Branch-and-cut; Cut-set inequalities; Polyhedral demand uncertainty; Robust network design; Separation under uncertainty}, pages = {297-342}, peerreviewed = {unknown}, title = {{Single}-commodity robust network design with finite and {Hose} demand sets}, volume = {157}, year = {2016} } @article{faucris.241868444, abstract = {We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions.The latter occur, for instance, in the context of the curtailment of renewables or the

switching of power generation units and transmission lines.

Our approach delivers globally optimal solutions and is provably convergent.

We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs.

The solution method starts from a known framework that uses piecewise linear relaxations.

These relaxations are modeled as as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled.

In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements.

In particular, these are mixed-integer second-order cone programs as well as primal and dual cutting planes.

For example objective cuts and no-good-cuts help to compute good feasible solutions as where outer approximation constraints tighten the relaxations.

We present extensive numerical results for various AC OPF problems where discrete decisions play a major role.

Even for hard instances with a large proportion of discrete decisions, the method is able

to generate high quality solutions efficiently.

Furthermore, we compare our approach with state-of-the-art MINLP solvers.

Our method outperforms all other algorithms.

In this work we study polyhedra in the context of network flow problems, in which the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation—a common and established approach in many applications. Several methods for modeling piecewise linear functions which provide a complete description for a single network arc are known. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on—but not limited to—the connection between binary variables and flow variables that is used in the multiple choice method or the convex combination method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art mixed-integer program solver greatly benefits from using our cutting planes for random and realistic network topologies. }, author = {Liers, Frauke and Merkert, Maximilian}, doi = {10.1137/15M1006751}, faupublication = {yes}, journal = {SIAM Journal on Optimization}, keywords = {combinatorial optimization, complete description, network flow problems, piecewise linear functions}, pages = {2863-2886}, peerreviewed = {Yes}, title = {{Structural} {Investigation} of {Piecewise} {Linearized} {Network} {Flow} {Problems}}, volume = {26}, year = {2016} } @article{faucris.321593774, abstract = {Consider an undirected network with traversal times on its edges and a set of commodities with connection requests from sources to destinations and release dates. The non-stop disjoint trajectories problem is to find trajectories that fulfill all requests, such that the commodities never meet. In this extension to the NP-complete disjoint paths problem, trajectories must satisfy a non-stop condition, which disallows waiting at vertices or along arcs. This problem variant appears, for example, when disjoint aircraft trajectories shall be determined or in bufferless packet routing. We study the border of tractability for feasibility and optimization problems on three graph classes that are frequently used where space and time are discretized simultaneously: the path, the grid, and the mesh. We show that if all commodities have a common release date, feasibility can be decided in polynomial time on paths. For the unbounded mesh and unit-costs, we show how to construct optimal trajectories. In contrast, if commodities have individual release intervals and turns are forbidden, then even feasibility is NP-complete for the path. For the mesh and arbitrary edge costs, with individual release dates and turning abilities of commodities restricted to at most 90°, we show that optimization and approximation are not fixed-parameter tractable.}, author = {Hoch, Benno and Liers-Bergmann, Frauke and Neumann, Sarah and Zaragoza Martínez, Francisco Javier}, doi = {10.1016/j.disopt.2024.100837}, faupublication = {yes}, journal = {Discrete Optimization}, keywords = {Combinatorial optimization; Complexity; Disjoint paths; Trajectory planning}, note = {CRIS-Team Scopus Importer:2024-04-26}, peerreviewed = {Yes}, title = {{The} non-stop disjoint trajectories problem}, volume = {52}, year = {2024} } @misc{faucris.231258652, abstract = {Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method for the convex hull of constrained sets. It relies on determining the convex envelope of linear combinations of the constraints and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.

}, author = {Adelhütte, Dennis and Liers, Frauke}, faupublication = {yes}, keywords = {Budget Uncertainty; Discrete Optimization; Combinatorial Optimization; Mixed-Integer Nonlinear Optimization; Robust Optimization; Gamma-Uncertainty}, peerreviewed = {automatic}, title = {{Γ}–counterparts for robust nonlinear combinatorial and discrete optimization}, url = {http://www.optimization-online.org/DB{\_}HTML/2020/05/7806.html}, year = {2021} }