KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 02 Mar 2016 11:29:07 +0100Wed, 02 Mar 2016 11:29:07 +0100Zone-based, Robust Flood Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4297
We consider the problem to evacuate several regions due to river flooding, where sufficient time is given to plan ahead. To ensure a smooth evacuation procedure, our model includes the decision which regions to assign to which shelter, and when evacuation orders should be issued, such that roads do not become congested.
Due to uncertainty in weather forecast, several possible scenarios are simultaneously considered in a robust optimization framework. To solve the resulting integer program, we apply a Tabu search algorithm based on decomposing the problem into better tractable subproblems. Computational experiments on random instances and an instance based on Kulmbach, Germany, data show considerable improvement compared to an MIP solver provided with a strong starting solution.Sabine Büttner; Marc Goerigkpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4297Wed, 03 Feb 2016 11:29:07 +0100Ranking Robustness and its Application to Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4296
We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.
We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.Marc Goerigk; Horst Hamacher; Anika Kinscherffpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4296Wed, 03 Feb 2016 11:26:20 +0100Global existence for a go-or-grow multiscale model for tumor invasion with therapy
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4294
We investigate a PDE-ODE system describing cancer cell invasion in a tissue network. The model is an extension of the multiscale setting in [28,40], by considering two subpopulations of tumor cells interacting mutually and with the surrounding tissue. According to the go-or-grow hypothesis, these subpopulations consist of moving and proliferating cells, respectively. The mathematical setting also accommodates the effects of some therapy approaches. We prove the global existence of weak solutions to this model and perform numerical simulations to illustrate its behavior for different therapy strategies.Christian Stinner; Christina Surulescu; Aydar Uataypreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4294Mon, 01 Feb 2016 09:21:08 +0100Advantage of Filtering for Portfolio Optimization in Financial Markets with Partial Information
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4282
In a financial market we consider three types of investors trading with a finite
time horizon with access to a bank account as well as multliple stocks: the
fully informed investor, the partially informed investor whose only source of
information are the stock prices and an investor who does not use this infor-
mation. The drift is modeled either as following linear Gaussian dynamics
or as being a continuous time Markov chain with finite state space. The
optimization problem is to maximize expected utility of terminal wealth.
The case of partial information is based on the use of filtering techniques.
Conditions to ensure boundedness of the expected value of the filters are
developed, in the Markov case also for positivity. For the Markov modulated
drift, boundedness of the expected value of the filter relates strongly to port-
folio optimization: effects are studied and quantified. The derivation of an
equivalent, less dimensional market is presented next. It is a type of Mutual
Fund Theorem that is shown here.
Gains and losses eminating from the use of filtering are then discussed in
detail for different market parameters: For infrequent trading we find that
both filters need to comply with the boundedness conditions to be an advan-
tage for the investor. Losses are minimal in case the filters are advantageous.
At an increasing number of stocks, again boundedness conditions need to be
met. Losses in this case depend strongly on the added stocks. The relation
of boundedness and portfolio optimization in the Markov model leads here to
increasing losses for the investor if the boundedness condition is to hold for
all numbers of stocks. In the Markov case, the losses for different numbers
of states are negligible in case more states are assumed then were originally
present. Assuming less states leads to high losses. Again for the Markov
model, a simplification of the complex optimal trading strategy for power
utility in the partial information setting is shown to cause only minor losses.
If the market parameters are such that shortselling and borrowing constraints
are in effect, these constraints may lead to big losses depending on how much
effect the constraints have. They can though also be an advantage for the
investor in case the expected value of the filters does not meet the conditions
for boundedness.
All results are implemented and illustrated with the corresponding numerical
findings.Leonie Rudererdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4282Fri, 15 Jan 2016 09:45:44 +0100Isogeometric finite element methods for shape optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4264
In this thesis we develop a shape optimization framework for isogeometric analysis in the optimize first–discretize then setting. For the discretization we use
isogeometric analysis (iga) to solve the state equation, and search optimal designs in a space of admissible b-spline or nurbs combinations. Thus a quite
general class of functions for representing optimal shapes is available. For the
gradient-descent method, the shape derivatives indicate both stopping criteria and search directions and are determined isogeometrically. The numerical treatment requires solvers for partial differential equations and optimization methods, which introduces numerical errors. The tight connection between iga and geometry representation offers new ways of refining the geometry and analysis discretization by the same means. Therefore, our main concern is to develop the optimize first framework for isogeometric shape optimization as ground work for both implementation and an error analysis. Numerical examples show that this ansatz is practical and case studies indicate that it allows local refinement.Daniela Fußederdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4264Thu, 07 Jan 2016 14:50:15 +0100Global existence for a degenerate haptotaxis model of cancer invasion
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4232
We propose and study a strongly coupled PDE-ODE system with tissue-dependent degenerate diffusion and haptotaxis that can serve as a model prototype for cancer cell invasion through the
extracellular matrix. We prove the global existence of weak solutions and illustrate the model behaviour by numerical simulations for a two-dimensional setting.Anna Zhigun; Christina Surulescu; Aydar Uataypreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4232Mon, 30 Nov 2015 08:35:47 +0100Performance Analysis in Robust Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4227
We discuss the problem of evaluating a robust solution.
To this end, we first give a short primer on how to apply robustification approaches to uncertain optimization problems using the assignment problem and the knapsack problem as illustrative examples.
As it is not immediately clear in practice which such robustness approach is suitable for the problem at hand,
we present current approaches for evaluating and comparing robustness from the literature, and introduce the new concept of a scenario curve. Using the methods presented in this paper, an easy guide is given to the decision maker to find, solve and compare the best robust optimization method for his purposes.André Chassein; Marc Goerigkpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4227Wed, 18 Nov 2015 08:25:22 +0100The Inductive Blockwise Alperin Weight Condition for the Finite Groups \( SL_3(q) \) \( (3 \nmid (q-1)) \), \( G_2(q) \) and \( ^3D_4(q) \)
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4225
The central topic of this thesis is Alperin's weight conjecture, a problem concerning the representation theory of finite groups.
This conjecture, which was first proposed by J. L. Alperin in 1986, asserts that for any finite group the number of its irreducible Brauer characters coincides with the number of conjugacy classes of its weights. The blockwise version of Alperin's conjecture partitions this problem into a question concerning the number of irreducible Brauer characters and weights belonging to the blocks of finite groups.
A proof for this conjecture has not (yet) been found. However, the problem has been reduced to a question on non-abelian finite (quasi-) simple groups in the sense that there is a set of conditions, the so-called inductive blockwise Alperin weight condition, whose verification for all non-abelian finite simple groups implies the blockwise Alperin weight conjecture. Now the objective is to prove this condition for all non-abelian finite simple groups, all of which are known via the classification of finite simple groups.
In this thesis we establish the inductive blockwise Alperin weight condition for three infinite series of finite groups of Lie type: the special linear groups \(SL_3(q)\) in the case \(q>2\) and \(q \not\equiv 1 \bmod 3\), the Chevalley groups \(G_2(q)\) for \(q \geqslant 5\), and Steinberg's triality groups \(^3D_4(q)\).Elisabeth Schultedoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4225Mon, 09 Nov 2015 11:04:50 +0100Representative Systems and Decision Support for Multicriteria Optimization Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4220
In this thesis, we investigate several upcoming issues occurring in the context of conceiving and building a decision support system. We elaborate new algorithms for computing representative systems with special quality guarantees, provide concepts for supporting the decision makers after a representative system was computed, and consider a methodology of combining two optimization problems.
We review the original Box-Algorithm for two objectives by Hamacher et al. (2007) and discuss several extensions regarding coverage, uniformity, the enumeration of the whole nondominated set, and necessary modifications if the underlying scalarization problem cannot be solved to optimality. In a next step, the original Box-Algorithm is extended to the case of three objective functions to compute a representative system with desired coverage error. Besides the investigation of several theoretical properties, we prove the correctness of the algorithm, derive a bound on the number of iterations needed by the algorithm to meet the desired coverage error, and propose some ideas for possible extensions.
Furthermore, we investigate the problem of selecting a subset with desired cardinality from the computed representative system, the Hypervolume Subset Selection Problem (HSSP). We provide two new formulations for the bicriteria HSSP, a linear programming formulation and a \(k\)-link shortest path formulation. For the latter formulation, we propose an algorithm for which we obtain the currently best known complexity bound for solving the bicriteria HSSP. For the tricriteria HSSP, we propose an integer programming formulation with a corresponding branch-and-bound scheme.
Moreover, we address the issue of how to present the whole set of computed representative points to the decision makers. Based on common illustration methods, we elaborate an algorithm guiding the decision makers in choosing their preferred solution.
Finally, we step back and look from a meta-level on the issue of how to combine two given optimization problems and how the resulting combinations can be related to each other. We come up with several different combined formulations and give some ideas for the practical approach.Tobias Kuhndoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4220Thu, 05 Nov 2015 08:54:53 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.Horst W. Hamacher; Ines M. Raschendorfer; Davaatseren Baatar; Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206Wed, 28 Oct 2015 14:33:01 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4197
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.Davaatseren Baatar; Matthias Ehrgott; Horst W. Hamacher; Ines M. Raschendorferarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4197Fri, 16 Oct 2015 11:00:21 +0200Application of the Finite Pointset Method to moving boundary problems for the BGK model of rarefied gas dynamics
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4182
The overall goal of the work is to simulate rarefied flows inside geometries with moving boundaries. The behavior of a rarefied flow is characterized through the Knudsen number \(Kn\), which can be very small (\(Kn < 0.01\) continuum flow) or larger (\(Kn > 1\) molecular flow). The transition region (\(0.01 < Kn < 1\)) is referred to as the transition flow regime.
Continuum flows are mainly simulated by using commercial CFD methods, which are used to solve the Euler equations. In the case of molecular flows one uses statistical methods, such as the Direct Simulation Monte Carlo (DSMC) method. In the transition region Euler equations are not adequate to model gas flows. Because of the rapid increase of particle collisions the DSMC method tends to fail, as well
Therefore, we develop a deterministic method, which is suitable to simulate problems of rarefied gases for any Knudsen number and is appropriate to simulate flows inside geometries with moving boundaries. Thus, the method we use is the Finite Pointset Method (FPM), which is a mesh-free numerical method developed at the ITWM Kaiserslautern and is mainly used to solve fluid dynamical problems.
More precisely, we develop a method in the FPM framework to solve the BGK model equation, which is a simplification of the Boltzmann equation. This equation is mainly used to describe rarefied flows.
The FPM based method is implemented for one and two dimensional physical and velocity space and different ranges of the Knudsen number. Numerical examples are shown for problems with moving boundaries. It is seen, that our method is superior to regular grid methods with respect to the implementation of boundary conditions. Furthermore, our results are comparable to reference solutions gained through CFD- and DSMC methods, respectevly.Maria Kobertdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4182Mon, 28 Sep 2015 08:22:27 +0200American-style Option Pricing and Improvement of Regression-based Monte Carlo Methods by Machine Learning Techniques
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4172
In this dissertation, we discuss how to price American-style options. Our aim is to study and improve the regression-based Monte Carlo methods. In order to have good benchmarks to compare with them, we also study the tree methods.
In the second chapter, we investigate the tree methods specifically. We do research firstly within the Black-Scholes model and then within the Heston model. In the Black-Scholes model, based on Müller's work, we illustrate how to price one dimensional and multidimensional American options, American Asian options, American lookback options, American barrier options and so on. In the Heston model, based on Sayer's research, we implement his algorithm to price one dimensional American options. In this way, we have good benchmarks of various American-style options and put them all in the appendix.
In the third chapter, we focus on the regression-based Monte Carlo methods theoretically and numerically. Firstly, we introduce two variations, the so called "Tsitsiklis-Roy method" and the "Longstaff-Schwartz method". Secondly, we illustrate the approximation of American option by its Bermudan counterpart. Thirdly we explain the source of low bias and high bias. Fourthly we compare these two methods using in-the-money paths and all paths. Fifthly, we examine the effect using different number and form of basis functions. Finally, we study the Andersen-Broadie method and present the lower and upper bounds.
In the fourth chapter, we study two machine learning techniques to improve the regression part of the Monte Carlo methods: Gaussian kernel method and kernel-based support vector machine. In order to choose a proper smooth parameter, we compare fixed bandwidth, global optimum and suboptimum from a finite set. We also point out that scaling the training data to [0,1] can avoid numerical difficulty. When out-of-sample paths of stock prices are simulated, the kernel method is robust and even performs better in several cases than the Tsitsiklis-Roy method and the Longstaff-Schwartz method. The support vector machine can keep on improving the kernel method and needs less representations of old stock prices during prediction of option continuation value for a new stock price.
In the fifth chapter, we switch to the hardware (FGPA) implementation of the Longstaff-Schwartz method and propose novel reversion formulas for the stock price and volatility within the Black-Scholes and Heston models. The test for this formula within the Black-Scholes model shows that the storage of data is reduced and also the corresponding energy consumption.Songyin Tangdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4172Mon, 14 Sep 2015 09:21:08 +0200Tropical Geometry in Singular
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4169
Yue Rendoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4169Wed, 09 Sep 2015 10:34:35 +0200Stochastic Modeling and Approximation of Turbulent Spinning Processes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4168
In some processes for spinning synthetic fibers the filaments are exposed to highly turbulent air flows to achieve a high degree of stretching (elongation). The quality of the resulting filaments, namely thickness and uniformity, is thus determined essentially by the aerodynamic force coming from the turbulent flow. Up to now, there is a gap between the elongation measured in experiments and the elongation obtained by numerical simulations available in the literature.
The main focus of this thesis is the development of an efficient and sufficiently accurate simulation algorithm for the velocity of a turbulent air flow and the application in turbulent spinning processes.
In stochastic turbulence models the velocity is described by an \(\mathbb{R}^3\)-valued random field. Based on an appropriate description of the random field by Marheineke, we have developed an algorithm that fulfills our requirements of efficiency and accuracy. Applying a resulting stochastic aerodynamic drag force on the fibers then allows the simulation of the fiber dynamics modeled by a random partial differential algebraic equation system as well as a quantization of the elongation in a simplified random ordinary differential equation model for turbulent spinning. The numerical results are very promising: whereas the numerical results available in the literature can only predict elongations up to order \(10^4\) we get an order of \(10^5\), which is closer to the elongations of order \(10^6\) measured in experiments.Florian Hübschdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4168Tue, 01 Sep 2015 13:27:20 +0200Construction of a Mittag-Leffler Analysis and its Applications
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4157
Motivated by the results of infinite dimensional Gaussian analysis and especially white noise analysis, we construct a Mittag-Leffler analysis. This is an infinite dimensional analysis with respect to non-Gaussian measures of Mittag-Leffler type which we call Mittag-Leffler measures. Our results indicate that the Wick ordered polynomials, which play a key role in Gaussian analysis, cannot be generalized to this non-Gaussian case. We provide evidence that a system of biorthogonal polynomials, called generalized Appell system, is applicable to the Mittag-Leffler measures, instead of using Wick ordered polynomials. With the help of an Appell system, we introduce a test function and a distribution space. Furthermore we give characterizations of the distribution space and we characterize the weak integrable functions and the convergent sequences within the distribution space. We construct Donsker's delta in a non-Gaussian setting as an application.
In the second part, we develop a grey noise analysis. This is a special application of the Mittag-Leffler analysis. In this framework, we introduce generalized grey Brownian motion and prove differentiability in a distributional sense and the existence of generalized grey Brownian motion local times. Grey noise analysis is then applied to the time-fractional heat equation and the time-fractional Schrödinger equation. We prove a generalization of the fractional Feynman-Kac formula for distributional initial values. In this way, we find a Green's function for the time-fractional heat equation which coincides with the solutions given in the literature.
Florian Jahnertdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4157Tue, 18 Aug 2015 08:32:00 +0200Robust storage loading problems with stacking and payload constraints
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4158
We consider storage loading problems where items with uncertain weights have
to be loaded into a storage area, taking into account stacking and
payload constraints. Following the robust optimization paradigm, we propose
strict and adjustable optimization models for finite and interval-based
uncertainties. To solve these problems, exact decomposition and heuristic
solution algorithms are developed.
For strict robustness, we also present a compact formulation based
on a characterization of worst-case scenarios.
Computational results show that computation times and algorithm
gaps are reasonable for practical applications.
Furthermore, we find that the robustness concepts show different
potential depending on the type of data being used.
Marc Goerigk; Sigrid Knust; Xuan Thanh Lepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4158Tue, 18 Aug 2015 08:23:49 +0200Aspects and Applications of the Wilkie Investment Model
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4137
The Wilkie model is a stochastic asset model, developed by A.D. Wilkie in 1984 with a purpose to explore the behaviour of investment factors of insurers within the United Kingdom. Even so, there is still no analysis that studies the Wilkie model in a portfolio optimization framework thus far. Originally, the Wilkie model is considering a discrete-time horizon and we apply the concept of Wilkie model to develop a suitable ARIMA model for Malaysian data by using Box-Jenkins methodology. We obtained the estimated parameters for each sub model within the Wilkie model that suits the case of Malaysia, and permits us to analyse the result based on statistics and economics view. We then tend to review the continuous time case which was initially introduced by Terence Chan in 1998. The continuous-time Wilkie model inspired is then being employed to develop the wealth equation of a portfolio that consists of a bond and a stock. We are interested in building portfolios based on three well-known trading strategies, a self-financing strategy, a constant growth optimal strategy as well as a buy-and-hold strategy. In dealing with the portfolio optimization problems, we use the stochastic control technique consisting of the maximization problem itself, the Hamilton-Jacobi-equation, the solution to the Hamilton-Jacobi-equation and finally the verification theorem. In finding the optimal portfolio, we obtained the specific solution of the Hamilton-Jacobi-equation and proved the solution via the verification theorem. For a simple buy-and-hold strategy, we use the mean-variance analysis to solve the portfolio optimization problem.
Norizarina Ishakdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4137Tue, 11 Aug 2015 11:06:03 +0200Discrete Parallel Machine Makespan ScheLoc Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4129
Scheduling-Location (ScheLoc) Problems integrate the separate fields of
scheduling and location problems. In ScheLoc Problems the objective is to
find locations for the machines and a schedule for each machine subject to
some production and location constraints such that some scheduling object-
ive is minimized. In this paper we consider the Discrete Parallel Machine
Makespan (DPMM) ScheLoc Problem where the set of possible machine loc-
ations is discrete and a set of n jobs has to be taken to the machines and
processed such that the makespan is minimized. Since the separate location
and scheduling problem are both NP-hard, so is the corresponding ScheLoc
Problem. Therefore, we propose an integer programming formulation and
different versions of clustering heuristics, where jobs are split into clusters
and each cluster is assigned to one of the possible machine locations. Since
the IP formulation can only be solved for small scale instances we propose
several lower bounds to measure the quality of the clustering heuristics. Ex-
tensive computational tests show the efficiency of the heuristics.Corinna Heßler; Kaouthar Deghdakpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4129Tue, 28 Jul 2015 09:40:15 +0200A new solution approach for solving the 2-facility location problem in the plane with block norms
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4128
Motivated by the time-dependent location problem over T time-periods introduced in
Maier and Hamacher (2015) we consider the special case of two time-steps, which was shown
to be equivalent to the static 2-facility location problem in the plane. Geometric optimality
conditions are stated for the median objective. When using block norms, these conditions
are used to derive a polygon grid inducing a subdivision of the plane based on normal cones,
yielding a new approach to solve the 2-facility location problem in polynomial time. Combinatorial algorithms for the 2-facility location problem based on geometric properties are
deduced and their complexities are analyzed. These methods differ from others as they are
completely working on geometric objects to derive the optimal solution set.Andrea Maierpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4128Fri, 24 Jul 2015 11:31:09 +0200Competitive Algorithms for Multistage Online Scheduling
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4119
We study an online flow shop scheduling problem where each job consists of several tasks that have to be completed in t different stages and the goal is to maximize the total weight of accepted jobs.
The set of tasks of a job contains one task for each stage and each stage has a dedicated set of identical parallel machines corresponding to it that can only process tasks of this stage. In order to gain the weight (profit) associated with a job j, each of its tasks has to be executed between a task-specific release date and deadline subject to the constraint that all tasks of job j from stages 1, …, i-1 have to be completed before the task of the ith stage can be started. In the online version, jobs arrive over time and all information about the tasks of a job becomes available at the release date of its first task. This model can be used to describe production processes in supply chains when customer orders arrive online.
We show that even the basic version of the offline problem with a single machine in each stage, unit weights, unit processing times, and fixed execution times for all tasks (i.e., deadline minus release date equals processing time) is APX-hard. Moreover, we show that the approximation ratio of any polynomial-time approximation algorithm for this basic version of the problem must depend on the number t of stages.
For the online version of the basic problem, we provide a (2t-1)-competitive deterministic online algorithm and a matching lower bound. Moreover, we provide several (sometimes tight) upper and lower bounds on the competitive ratio of online algorithms for several generalizations of the basic problem involving different weights, arbitrary release dates and deadlines, different processing times of tasks, and several identical machines per stage.
Michael Hopf; Clemens Thielen; Oliver Wendtpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4119Thu, 09 Jul 2015 14:06:19 +0200On the History of Differential-Algebraic Equations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4106
To write about the history of a subject is a challenge that grows with the number of pages as the original goal of completeness is turning more and more into an impossibility. With this in mind, the present article takes a very narrow approach and uses personal side trips and memories on conferences,
workshops, and summer schools as the stage for some of the most important protagonists and their contributions to the field of Differential-Algebraic Equations (DAEs).Bernd Simeonpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4106Tue, 23 Jun 2015 14:32:01 +0200A nonlocal sample dependence SDE-PDE system modeling proton dynamics in a tumor
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4104
A nonlocal stochastic model for intra- and extracellular proton dynamics in a tumor is proposed.
The intracellular dynamics is governed by an SDE coupled to a reaction-diffusion
equation for the extracellular proton concentration on the macroscale. In a more general context
the existence and uniqueness of solutions for local and nonlocal
SDE-PDE systems are established allowing, in particular, to analyze the proton dynamics model both,
in its local version and the case with nonlocal path dependence.
Numerical simulations are performed
to illustrate the behavior of solutions, providing some insights into the effects of randomness on tumor acidity. Peter E. Kloeden; Stefanie Sonner; Christina Surulescupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4104Mon, 22 Jun 2015 15:00:13 +0200Coercive functions from a topological viewpoint and properties of minimizing sets of convex functions appearing in image restoration
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4100
Many tasks in image processing can be tackled by modeling an appropriate data fidelity term \(\Phi: \mathbb{R}^n \rightarrow \mathbb{R} \cup \{+\infty\}\) and then solve one of the regularized minimization problems \begin{align*}
&{}(P_{1,\tau}) \qquad \mathop{\rm argmin}_{x \in \mathbb R^n} \big\{ \Phi(x) \;{\rm s.t.}\; \Psi(x) \leq \tau \big\} \\ &{}(P_{2,\lambda}) \qquad \mathop{\rm argmin}_{x \in \mathbb R^n} \{ \Phi(x) + \lambda \Psi(x) \}, \; \lambda > 0 \end{align*} with some function \(\Psi: \mathbb{R}^n \rightarrow \mathbb{R} \cup \{+\infty\}\) and a good choice of the parameter(s). Two tasks arise naturally here: \begin{align*} {}& \text{1. Study the solver sets \({\rm SOL}(P_{1,\tau})\) and
\({\rm SOL}(P_{2,\lambda})\) of the minimization problems.} \\ {}& \text{2. Ensure that the minimization problems have solutions.} \end{align*} This thesis provides contributions to both tasks: Regarding the first task for a more special setting we prove that there are intervals \((0,c)\) and \((0,d)\) such that the setvalued curves \begin{align*}
\tau \mapsto {}& {\rm SOL}(P_{1,\tau}), \; \tau \in (0,c) \\ {} \lambda \mapsto {}& {\rm SOL}(P_{2,\lambda}), \; \lambda \in (0,d) \end{align*} are the same, besides an order reversing parameter change \(g: (0,c) \rightarrow (0,d)\). Moreover we show that the solver sets are changing all the time while \(\tau\) runs from \(0\) to \(c\) and \(\lambda\) runs from \(d\) to \(0\).
In the presence of lower semicontinuity the second task is done if we have additionally coercivity. We regard lower semicontinuity and coercivity from a topological point of view and develop a new technique for proving lower semicontinuity plus coercivity.
Dropping any lower semicontinuity assumption we also prove a theorem on the coercivity of a sum of functions.René Ciakdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4100Tue, 09 Jun 2015 15:50:38 +0200Upscaling Approaches for Nonlinear Processes in Lithium-Ion Batteries
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4086
Lithium-ion batteries are broadly used nowadays in all kinds of portable electronics, such as laptops, cell phones, tablets, e-book readers, digital cameras, etc. They are preferred to other types of rechargeable batteries due to their superior characteristics, such as light weight and high energy density, no memory effect, and a big number of charge/discharge cycles. The high demand and applicability of Li-ion batteries naturally give rise to the unceasing necessity of developing better batteries in terms of performance and lifetime. The aim of the mathematical modelling of Li-ion batteries is to help engineers test different battery configurations and electrode materials faster and cheaper. Lithium-ion batteries are multiscale systems. A typical Li-ion battery consists of multiple connected electrochemical battery cells. Each cell has two electrodes - anode and cathode, as well as a separator between them that prevents a short circuit.
Both electrodes have porous structure composed of two phases - solid and electrolyte. We call macroscale the lengthscale of the whole electrode and microscale - the lengthscale at which we can distinguish the complex porous structure of the electrodes. We start from a Li-ion battery model derived on the microscale. The model is based on nonlinear diffusion type of equations for the transport of Lithium ions and charges in the electrolyte and in the active material. Electrochemical reactions on the solid-electrolyte interface couple the two phases. The interface kinetics is modelled by the highly nonlinear Butler-Volmer interface conditions. Direct numerical simulations with standard methods, such as the Finite Element Method or Finite Volume Method, lead to ill-conditioned problems with a huge number of degrees of freedom which are difficult to solve. Therefore, the aim of this work is to derive upscaled models on the lengthscale of the whole electrode so that we do not have to resolve all the small-scale features of the porous microstructure thus reducing the computational time and cost. We do this by applying two different upscaling techniques - the Asymptotic Homogenization Method and the Multiscale Finite Element Method (MsFEM). We consider the electrolyte and the solid as two self-complementary perforated domains and we exploit this idea with both upscaling methods. The first method is restricted only to periodic media and periodically oscillating solutions while the second method can be applied to randomly oscillating solutions and is based on the Finite Element Method framework. We apply the Asymptotic Homogenization Method to derive a coupled macro-micro upscaled model under the assumption of periodic electrode microstructure. A crucial step in the homogenization procedure is the upscaling of the Butler-Volmer interface conditions. We rigorously determine the asymptotic order of the interface exchange current densities and we perform a comprehensive numerical study in order to validate the derived homogenized Li-ion battery model. In order to upscale the microscale battery problem in the case of random electrode microstructure we apply the MsFEM, extended to problems in perforated domains with Neumann boundary conditions on the holes. We conduct a detailed numerical investigation of the proposed algorithm and we show numerical convergence of the method that we design. We also apply the developed technique to a simplified two-dimensional Li-ion battery problem and we show numerical convergence of the solution obtained with the MsFEM to the reference microscale one. Vasilena Taralovadoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4086Thu, 28 May 2015 09:01:35 +0200