## Mathematisches Institut

### Refine

#### Language

- English (4) (remove)

#### Keywords

- Decodierung (1)
- Evacuation modeling (1)
- Flow decomposition (1)
- Kanalcodierung (1)
- Mathematik (1)
- Optimierung (1)
- Optimization (1)
- flows over time (1)

The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.

In summary, this study revealed the widespread occurrence of antiviral drugs in the aquatic environment. Furthermore, it could be shown that the elimination of pharmaceuticals in both biological and oxidative treatment do not necessarily result in their mineralization but rather leads to the formation of a variety of transformation and oxidation products.
This is one of the first studies in which the fate and in particular the transformation of pharmaceuticals has been comprehensively investigated in almost the complete water cycle, from biological wastewater treatment to advanced oxidation processes via ozone. It was shown that the transformation of pharmaceuticals in the urban water cycle can ultimately result in the formation of toxic transformation products.

While reading this sentence, you probably gave (more or less deliberately) instructions to approximately 100 to 200 muscles of your body. A sceptical face or a smile, your fingers scrolling through the text or holding a printed version of this work, holding your head, sitting, and much more.
All these processes take place almost automatically, so they seem to be no real achievement. In the age of digitalization it is a defined goal to transfer human (psychological and physiological) behavior to machines (robots). However, it turns out that it is indeed laborious to obtain human facial expression or walking from robots. To optimize this transfer, a deeper understanding of a muscle's operating principle is needed (and of course an understanding of the human brain, which will, however, not be part of this thesis).
A human skeletal muscle can be shortened willingly, but not lengthened, thereto it takes an antagonist. The muscle's change in length is dependent on the incoming stimulus from the central nervous system, the current length of the muscle itself, and certain muscle--specific quantities (parameters) such as the maximum force. Hence, a muscle can be mathematically described by a differential equation (or more exactly a coupled differential--algebraic system, DAE), whose structure will be revealed in the following chapters. The theory of differential equations is well-elaborated. A multitude of applicable methods exist that may not be known by muscle modelers. The purpose of this work is to link the methods from applied mathematics to the actual application in biomechanics.
The first part of this thesis addresses stability theory. Let us remember the prominent example from middle school physics, in which the resting position of a ball was obviously less susceptible towards shoves when lying in a bowl rather than balancing at the tip of a hill. Similarly, a dynamical (musculo-skeletal) system can attain equilibrium states that react differently towards perturbations.
We are going to compute and classify these equilibria.
In the second part, we investigate the influence of individual parameters on model equations or more exactly their solutions. This method is known as sensitivity analysis.
Take for example the system "car" containing a value for the quantity "pressure on the break pedal while approaching a traffic light". A minor deviation of this quantity upward or downward may lead to an uncomfortable, abrupt stop or even to a collision, instead of a smooth stop with a sufficient gap.
The considered muscle model contains over 20 parameters that, if changed slightly, have varying effects on the model equation solutions at different instants of time. We will investigate the sensitivity of those parameters regarding different sub--models, as well as the whole model among different dynamical boundary conditions.
The third and final part addresses the \textit{optimal control} problem (OCP).
The muscle turns a nerve impulse (input or control) into a length change and therefore a force response (output). This forward process is computable by solving the respective DAE. The reverse direction is more difficult to manage. As an everyday example, the OCP is present regarding self-parking cars, where a given path is targeted and the controls are the position of the
steering wheel as well as the gas pedal.
We present two methods of solving OCPs in muscle modeling: the first is a conjunction of variational calculus and optimization in function spaces, the second is a surrogate-based optimization.

In Part I: "The flow-decomposition problem", we introduce and discuss the flow-decomposition problem. Given a flow F, this problem consists of decomposing the flow into a set of paths optimizing specific properties of those paths. We introduce different types of decompositions, such as integer decompositions and alpha-decompositions, and provide two formulations of the set of feasible decompositions.
We show that the problem of minimizing the longest path in a decomposition is NP-hard, even for fractional solutions. Then we develop an algorithm based on column generation which is able to solve the problem.
Tight upper bounds on the optimal objective value help to improve the performance.
To find upper bounds on the optimal solution for the shortest longest path problem, we develop several heuristics and analyze their quality. On pearl graphs we prove a constant approximation ratio of 2 and 3 respectively for all heuristics. A numerical study on random pearl graphs shows that the solutions generated by the heuristics are usually much better than this worst-case bound.
In Part II: "Construction and analysis of evacuation models using flows over time", we consider two optimization models in the context of evacuation planning. The first model is a parameter-based quickest flow model with time-dependent supply values. We give a detailed description of the network construction and of how different scenarios are modeled by scenario parameters. In a second step we analyze the effect of the scenario parameters on the evacuation time. Understanding how the different parameters influence the evacuation time allows us to provide better advice for evacuation planning and allows us to predict evacuation times without solving additional optimization problems. To understand the effect of the time-dependent supply values, we consider the quickest path problem with time-dependent supply values and provide a solution algorithm. The results from this consideration are generalized to approximate the behavior of the evacuation times in the context of quickest flow problems.
The second model we consider is a path-based model for evacuation in the presence of a dynamic cost function. We discuss the challenges of this model and provide ideas for how to approach the problem from different angles. We relate the problem to the flow-decomposition problem and consider the computation of evacuation paths with dynamic costs for large capacities. For the latter method we provide heuristics to find paths and compare them to the optimal solutions by applying the methods to two evacuation scenarios. An analysis shows that the paths generated by the heuristic yield close to optimal solutions and in addition have several desirable properties for evacuation paths which are not given for the optimal solution.