Refine
Year of publication
Language
- English (1103) (remove)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
Error estimates for the numerical approximation of boundary semilinear elliptic control problems
(2004)
We study the numerical approximation of boundary optimal control problems governed
by semilinear elliptic partial differential equations with pointwise constraints on the control.
The analysis of the approximate control problems is carried out. The uniform convergence of discretized
controls to optimal controls is proven under natural assumptions by taking piecewise constant
controls. Finally, error estimates are established.
Regular Lagrange multipliers for control problems with mixed pointwise control-state constraints
(2004)
A class of quadratic optimization problems in Hilbert spaces is considered, where
pointwise box constraints and constraints of bottleneck type are given. The main focus is to prove the
existence of regular Lagrange multipliers in L2-spaces. This question is solved by investigating the
solvability of a Lagrange dual quadratic problem. The theory is applied to different optimal control
problems for elliptic and parabolic partial differential equations with mixed pointwise control-state
constraints.
Let Ex be a collection of i.i.d. exponential random
variables. Symmetric Bouchaud’s model on Z2 is a Markov chain
X(t) whose transition rates are given by wxy = ν exp(−βEx ) if x,
y are neighbours in Z2 . We study the behaviour of two correlation functions: P[X(tw + t) = X(tw )] and P X(t ) = X(tw )∀t ∈
[tw , tw + t] . We prove the (sub)aging behaviour of these functions
when β > 1.
A popular model to describe credit risk in practice is CreditRisk
+
and in
this paper a Fourier inversion to obtain the distribution of the credit loss is
proposed. A deeper analysis of the Fourier transformation showed that there
are at least two methods to obtain the distribution although the corresponding
characteristic function is not integrable.
The CreditRisk
+
model will be extended such, that general dependent sec-
tor variables can be taken into consideration, for example dependent lognormal
sector variables. Then the transfer to a continuous time model will be per-
formed and the sector variables become processes, more precisely geometric
Brownian motions.
To have a time continuous credit risk model is an important step to combine
this model with market risk. Additionally a portfolio model will be presented
where the changes of the spreads are driven by the sector variables. Using a
linear expansion of the market risk, the distribution of this portfolio can be
determined. In the special case that there is no credit risk, this model yields
the well known Delta normal approach for market risk, hence a link between
credit risk and market risk has been established.
The CreditRisk model launched by CSFB in 1997 is widely used by practitioners in the banking sector as a simple means for the quantification of credit
risk, primarily of the loan book. We present an alternative numerical recursion scheme for CreditRisk, equivalent to an algorithm recently proposed by
Giese, based on well-known expansions of the logarithm and the exponential
of a power series. We show that it is advantageous to the Panjer recursion
advocated in the original CreditRisk
document, in that it is numerically stable. The crucial stability arguments are explained in detail. Furthermore, the
computational complexity of the resulting algorithm is stated.
We introduce a new Monte Carlo method for constructing the exercise
boundary of an American option in a generalized Black-Scholes framework.
Based on a known exercise boundary, it is shown how to price and hedge the
American option by Monte Carlo simulation of suitable probabilistic represen-
tations in connection with the respective parabolic boundary value problem.
The methods presented are supported by numerical simulation experiments.
In this paper we investigate the use of parallel computing to deal with the high computational cost of numerical algorithms for model reduction of large linear descriptor systems. The state-space truncation methods considered here are composed of iterative schemes which can be efficiently implemented on parallel architectures using existing parallel linear algebra libraries. Our experimental results on a cluster of Intel Pentium processors show the performance of the parallel algorithms.
We discuss a parallel library of efficient algorithms for model reduction of largescale
systems with state-space dimension up to O(104). We survey the numerical
algorithms underlying the implementation of the chosen model reduction methods.
The approach considered here is based on state-space truncation of the system
matrices and includes absolute and relative error methods for both stable and unstable
systems. In contrast to serial implementations of these methods, we employ
Newton-type iterative algorithms for the solution of the major computational tasks.
Experimental results report the numerical accuracy and the parallel performance of
our approach on a cluster of Intel Pentium II processors.
We describe a prototype web service for model reduction of very large-scale linear systems, with
dimension in the order of millions of states, that includes a user-friendly interface designed so that the computation
can be easily performed via the HTTP protocol. Access via a web browser isolates the user of the service from the
complexities of installing and using the parallel model reduction codes and the maintenance of the hardware. In case
the routines are found to be appropriate for the problem the user needs to solve, the library can be then downloaded
and installed on the user’s own computing resources.
This paper illustrates the major issues of the access procedure by means of graphical examples, and describes
the structure and implementation of the remote model reduction service. The service is offered in a cluster of Linux
machines.
A Structure-Preserving Method for Generalized Algebraic RiccatiEquations Based on Pencil Arithmetic
(2004)
This paper describes a numerical method for extracting the stable
right deflating subspace of a matrix pencil Z Y using
a spectral projection method. It has several advantages compared
to other spectral projection methods like the sign function
method. In particular it avoids the rounding error induced
loss of accuracy associated with matrix inversions. The new algorithm
is particularly well adapted to solving continuous-time
algebraic Riccati equations. In numerical examples, it solves
Riccati equations to high accuracy.
We study the optimization of three dimensional curved rods and of shells
under minimal regularity assumptions for the geometry. The results that we
establish concern the existence of optimal shapes and the sensitivity analysis.
We also compute several numerical examples for the curved rods. The models
that we use have been investigated in our previous work [11], [16] and a
complete study of the Kirchhoff-Love arches and their optimization has been
performed in [10].
We prove new properties for the linear isotropic elasticity system and for
thickness minimization problems. We also present very recent results concerning
shape optimization problems for three-dimensional curved rods and
for shells. The questions discussed in this paper are related to the control
variational method and to control into coefficients problems.
In this paper a nonlocal phase-field model for non-isothermal phase transitions
with a non-conserved order parameter is studied. The paper complements
recent investigations by S. Zheng and the second author and treats
the case when the part of the free energy density forcing the order parameter
to attain values within the physically meaningful range [0; 1] is not given
by a logarithmic expression but by the indicator function of [0; 1] . The resulting
field equations form a system of integro-partial differential inclusions
that are highly nonlinearly coupled. For this system, results concerning global
existence, uniqueness and large-time asymptotic behaviour are derived. The
main results are proved by first transforming the system of inclusions into an
equivalent system of equations in which hysteresis operators occur, and then
employing techniques similar to those recently developed by the authors for
phase-field systems involving hysteresis operators.
Motivated by optimal investment problems in mathematical finance, we consider
a variational problem of Neyman-Pearson type for law-invariant robust utility functionals
and convex risk measures. Explicit solutions are found for quantile-based coherent
risk measures and related utility functionals. Typically, these solutions exhibit a critical
phenomenon: If the capital constraint is below some critical value, then the solution will
coincide with a classical solution; above this critical value, the solution is a superposition
of a classical solution and a less risky or even risk-free investment. For general risk measures
and utility functionals, it is shown that there exists a solution that can be written
as a deterministic increasing function of the price density.
We study a stationary Schrödinger-Poisson system on a bounded interval of the real axis. The Schrödinger operator is defined on the bounded domain with transparent boundary conditions. This allows us to model a non-zero current through the boundary of the interval. We prove that the system always admits a solution and give explicit a priori estimates for the solutions.
We suggest a new model for the design of telecommunication networks which integrates
decisions about the topology, configuration of the switching hardware, link dimensioning,
and protected routing of communication demands. Applying the branch-andcut-
algorithm implemented in our network planning and optimization tool discnet, we
demonstrate that real-world based network planning instances of such an enhanced model
can be solved.
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into
an hierarchy of network levels? We propose a mixed-integer program and a Lagrangian relaxation
based algorithm to model and solve this planning task. As one big advantage of this approach, not
only solutions but also worst-case quality gurarantees can be provided. We present a solution for
a G-WiN planning instance of DFN with 759 locations which has been computed in less than 30
minutes and which is (provably) less than 0.5 percent away from optimality.
Der scharfeWettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu,
ihre Investitionen genau zu planen und immer wieder Einsparungsmaßnahmen durchzuführen.
Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue
Kunden zu gewinnen und langfristig an sich zu binden.
Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend
geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung
speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand
von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie
sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche
Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten
Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen
auch eine Qualitätsgarantie liefern, mit der sich die Lösungen fundiert bewerten lassen. Die dokumentierten
Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der
mathematischen Optimierung für die Praxis.
This paper demonstrates simulation tools for edge-emitting multi quantum well (MQW) lasers.
Properties of the strained MQW active region are simulated by eight-band kp calculations. Then, a 2D
simulation along the transverse cross section of the device is performed based on a drift-diffusion model,
which is self-consistently coupled to heat transport and equations for the optical field. Furthermore, a
method is described, which allows for an efficient quasi 3D simulation of dynamic properties of multisection
edge-emitting lasers.
Let H be a semi–bounded self–adjoint operator in a separable Hilbert space.
For a certain class of positive, continuous, decreasing, and convex functions
F we show the convexity of trace functionals tr(F (H + U − ε(U ))) − ε(U ),
where U is a bounded self–adjoint operator on H and ε(U ) is a normalizing
real function—the Fermi level—which may be identical zero. If additionally
F is continuously differentiable, then the corresponding trace functional is
Fréchet differentiable and there is an expression of its gradient in terms off
the derivative of F . The proof of the differentiability of the trace functional
is based upon Birman and Solomyak’s theory of double Stieltjes operator
integrals. If, in particular, H is a Schrödinger–type operator and U a real-valued function, then the gradient of the trace functional is the quantum
mechanical expression of the particle density with respect to an equilibrium
distribution function f = −F . Thus, the monotonicity of the particle density
in its dependence on the potential U of Schrödinger’s operator—which has
been understood since the late 1980s—follows as a special case.
We propose a class of Markovian agent based models for the time evolution of a share price in an interactive market. The models rely on a microscopic description of a market of buyers and sellers who change their opinion about the stock value in a stochastic way. The actual price is determined in realistic way by matching (clearing) offers until no further transactions can be performed. Some analytic results for a non-interacting model are presented. We also propose basic interaction mechanisms and show in simulations that these already reproduce certain particular features of prices in real stock markets.
For a refined network analysis, we are interested in circuit simulation
including distributed models of semiconductors. We construct a mathematical
model for nonlinear electric networks containing semiconductors
described by the drift-diffusion equations. The focus lies on the coupling
of the network DAEs and the semiconductor PDEs.
Furthermore, we study the behavior of the coupled systems with respect to
time dependent perturbations using an index concept for abstract DAEs.
We present a network topological criterion that guarantees index-1 systems.
We consider the problem of utility maximization for small traders on incomplete
financial markets. As opposed to most of the papers dealing with this
subject, the investors’ trading strategies we allow underly constraints described
by closed, but not necessarily convex, sets. The final wealths obtained by trading
under these constraints are identified as stochastic processes which usually are
supermartingales, and even martingales for particular strategies. These strategies
are seen to be optimal, and the corresponding value functions determined
simply by the initial values of the supermartingales. We separately treat the
cases of exponential, power and logarithmic utility.
We consider financial markets with agents exposed to an external source of
risk which cannot be hedged through investments on the capital market alone.
The sources of risk we think of may be weather and climate. Therefore we face
a typical example of an incomplete financial market. We design a model of a
market on which the external risk becomes tradable. In a first step we complete
the market by introducing an extra security which valuates the external risk
through a process parameter describing its market price. If this parameter is
fixed, risk has a price and every agent can maximize the expected exponential
utility with individual risk aversion obtained from his risk exposure on the one
hand and his investment into the financial market consisting of an exogenous set
of stocks and the insurance asset on the other hand. In the second step, the
market price of risk parameter has to be determined by a partial equilibrium
condition which just expresses the fact that in equilibrium the market is cleared
of the second security. This choice of market price of risk is performed in the
framework of nonlinear backwards stochastic differential equations.
Equilibrium trading of climate and weather risk and numerical simulation in a Markovian framework
(2004)
We consider financial markets with agents exposed to external sources of risk
caused for example by short term climate events such as the South Pacific sea
surface temperature anomalies widely known under the name El Nino. Since
such risks cannot be hedged through investments on the capital market alone,
we face a typical example of an incomplete financial market. In order to make
this risk tradable, we use a financial market model in which an additional insurance
asset provides another possibility of investment besides the usual capital
market. Given one of many possible market prices of risk each agent can maximize
his individual exponential utility from his income obtained from trading in
the capital market, the additional security, and his risk exposure function. Under
the equilibrium market clearing condition for the insurance security the market
price of risk is uniquely determined by a backward stochastic differential equation.
We translate these stochastic equations via the Feynman-Kac formalism
into semi-linear parabolic partial differential equations. Numerical schemes are
available by which these semilinear pde can be simulated. We choose two simple
qualitatively interesting models to describe sea surface temperature, and with
an ENSO risk exposed fisher and farmer and a climate risk neutral bank three
model agents with simple risk exposure functions. By simulating the expected
appreciation price of risk trading, the optimal utility of the agents as a function
of temperature, and their optimal investment into the risk trading security we
obtain first insight into the dynamics of such a market in simple situations.
We consider financial markets with two kinds of small traders: regular traders
who perceive the asset price process S through its natural filtration, and insid-
ers who possess some information advantage which makes the filtrations through
which they perceive the evolution of the market richer. The basic question we dis-
cuss is the link between (NFLVR), the semimartingale property of S viewed from
the agent’s perspective, and bounded expected utility. We show that whenever
an agent’s expected utility is finite, S is a semimartingale with a Doob-Meyer
decomposition featuring a martingale part and an information drift. The ex-
pected utility gain of an insider with respect to a regular trader is calculated in
a completely general setting. In particular, for the logarithmic utility function,
utility gain is a function of the relative information drift alone, regardless of the
completeness of the market.
Invariant measures of dynamical systems generated e. g. by difference equations
can be computed by discretizing the originally continuum state space, and
replacing the action of the generator by the transition mechanism of a Markov
chain. In fact they are approximated by stationary vectors of these Markov
chains. Here we extend this well known approximation result and the underlying
algorithm to the setting of random dynamical systems, i.e. dynamical systems
on the skew product of a probability space carrying the underlying stationary
stochasticity and the state space, a particular non-autonomous framework. The
systems are generated by difference equations driven by stationary random processes
modelled on a metric dynamical system. The approximation algorithm
involves spatial discretizations and the definition of appropriate random Markov
chains with stationary vectors converging to the random invariant measure of
the system.
The work presents a novel method for the detection of mutual
phase synchronization in non-stationary time series. We show how the
application of a cluster algorithmthat considers spatio-temporal struc-
tures of data follows from the general condition of phase-synchronized
data. In view of the topology of phasic data, we re-formulate the
K-Means cluster algorithm on a flat torus and apply a segmentation
index derived in an earlier work (Physica D 177,203-232(2003)). This index is extended by means of averaging in order to reflect phase syn-
chronization in ensembles of multivariate time series. The method is
illustrated using simulated multivariate phase dynamics and arrays of
chaotic systems, in which temporal segments of phase-synchronized
states are registered. A comparison with results from an existing bi-
variate synchronization index reveals major advantages of our method.
A stability analysis is presented for neural field equations in the presence
of axonal delays and for a general class of connectivity kernels and synap-
tic properties. Sufficient conditions are given for the stability of equilibrium
solutions. It is shown that the delays play a crucial role in non-stationary
bifurcations of equilibria, whereas the stationary bifurcations depend only on
the kernel. Bounds are determined for the frequencies of bifurcating periodic
solutions. A perturbative scheme is used to calculate the types of bifurca-
tions leading to spatial patterns, oscillatory solutions, and traveling waves.
For high transmission speeds a simple method is derived that allows the de-
termination of the bifurcation type by visual inspection of the Fourier trans-
forms of the connectivity kernel and its first moment. Results are numerically
illustrated on a class of neurologically plausible second order systems with
combinations of Gaussian excitatory and inhibitory connections.
This work studies dynamical properties of spatially extended neu-
ronal ensembles. We first derive an evolution equation from tem-
poral properties and statistical distributions of synapses and somata.
The obtained integro-differential equation considers both synaptic and
axonal propagation delay, while spatial synaptic connectivities ex-
hibit gamma-distributed distributions. This familiy of connectivity
kernels also covers the cases of divergent, finite, and negligible self-
connections. The work derives conditions for both stationary and
nonstationary instabilities for gamma-distributed kernels.It turns out
that the stability conditions can be formulated in terms of the mean spatial interaction ranges and the mean spatial interaction times. In
addition, a numerical study examines the evoked spatiotemporal re-
sponse activity caused by short local stimuli and reveals maximum
response activity after the mean interaction time at a distance from
stimulus offset location equal to the mean interaction range. These
findings propose new insights to neuronal mechanisms of experimen-
tally observed evoked brain activity.
An optimal control problem for a 2-d elliptic equation is investigated with pointwise control constraints.
This paper is concerned with discretization of the control by piecewise linear functions. The state and the
adjoint state are discretized by linear finite elements. Approximation of order h in the L1-norm is proved in the
main result.
This work studies the stability of spatially extended neuronal ensembles. We first
derive the model equation from statistical properties of the neuron population. The
obtained integro-differential equation considers synaptic and space-dependent transmission
delay for both general and gamma-distributed synaptic connectivities. The
latter connectivity type reveals infinite, finite and vanishing self-connectivities. The
work derives conditions for stationary and nonstationary instabilities for both kernel
types. In addition, a nonlinear analysis for general kernels yields the order parameter
equation of the Turing instability. To compare the results to findings for partial
differential equations (PDEs), two typical PDE-types are derived from the examined
model equation. In case of the gamma-distributed kernels, the stability conditions
are formulated in terms of the mean excitatory and inhibitory interaction ranges. As
a novel finding, we obtain Turing instabilities in fields with local inhibition-lateral
excitation, while wave instabilities occur in fields with local excitation and lateral
inhibition. Numerical simulations support the analytical results.
Single–hop WDM networks with a central Passive
Star Coupler (PSC), as well as single–hop networks with a central
Arrayed–Waveguide Grating (AWG) and a single transceiver at
each node, have been extensively studied as solutions for the
quickly increasing amounts of unicast and multicast traffic in
the metropolitan area. The main bottlenecks of these networks
are the lack of spatial wavelength reuse in the studied PSC based
networks and the single transceiver in the studied AWG based
metro WDM networks. In this paper we develop and evaluate
the FT? ? FR? AWG network, which is based on a central
AWG and has arrays of fixed–tuned transmitters and receivers
at each node. Transceiver arrays are a mature technology, making
the proposed network practical. In addition, the transmitter
arrays allow for high speed signaling over the AWG while
the receiver arrays relieve the receiver bottleneck arising from
multicasting in conjunction with spatial wavelength reuse on the
AWG. Our results from probabilistic analysis and simulation
indicate that the FT? ? FR? AWG network gives particularly
good throughput–delay performance for multicast traffic with
small multicast group sizes or localized destination nodes, as
well as for a mix of unicast and multicast traffic.
We investigate the impact of link and path restoration
on the cost of telecommunication networks. The surprising
result is the following: the cost of an optimal network configuration
is almost independent of the restoration concept if (i)
the installation of network elements (ADMs, DXCs, or routers)
and interface cards, (ii) link capacities, and (iii) working and
restoration routings are simultaneously optimized.
We present a mixed-integer programming model which integrates
all these decisions. Using a branch-and-cut algorithm
(with column generation to deal with all potential routing paths),
we solve structurally different real-world problem instances and
show that the cost of optimal solutions is almost independent of
the used restoration concept.
In addition, we optimize spare capacities for given shortest
working paths which are predetermined with respect to different
link metrics. In comparison to simultaneous optimization of
working and restoration routings, it turns out that this approach
does not allow to obtain predictably good results.
We investigate the impact of hop-limited routing
paths on the total cost of a telecommunication network. For
different survivability settings (no survivability, link and path
restoration), the optimal network cost without restrictions on
the admissible path set is compared to the results obtained with
two strategies to impose hop limits on routing paths.
Based on optimal solutions for 10 real-world based problem
instances, we show that hop limits may lead to an unpredictable
raise in total network cost - even with large hop limits. The total
network cost with a hop limit of 7 hops for all demands can be up
to 25% higher than without restrictions on the admissible path
set. With our second strategy, which imposes demand-dependent
hop limits based on the shortest hop count, we obtain similar
results. This indicates that column generation techniques should
be applied to deal with all admissible paths.
Balancing a matrix by a simple and accurate similarity transformation can improve
the speed and accuracy of numerical methods for computing eigenvalues. We describe
balancing strategies for a large and sparse Hamiltonian matrix H. It is first shown how
to permute H to irreducible form while retaining its structure. This form can be used to
decompose the Hamiltonian eigenproblem into smaller-sized problems. Next, we discuss
the computation of a symplectic scaling matrix D so that the norm of D 1 HD is reduced.
The considered scaling algorithm is solely based on matrix-vector products and thus particularly
suitable if the elements of H are not explicitly given. The merits of balancing
for eigenvalue computations are illustrated by several practically relevant examples.
The periodic QR algorithm is a strongly backward stable method for computing the
eigenvalues of products of matrices, or equivalently for computing the eigenvalues of
block cyclic matrices. The main purpose of this paper is to show that this algorithm
is numerically equivalent to the standard QR algorithm. It will be demonstrated
how this connection may be used to develop a better understanding of the periodic
QR algorithm.
Two algorithms for the solution of discrete-time periodic Lyapunov
equations are presented. The first one is a variant of the
squared Smith iteration, which is solely based on matrix multiplications
and thus attractive to parallel computing environments.
The second algorithm is based on Krylov subspaces and
employs a recently developed variant of the block Arnoldi algorithm.
It is particularly suited for periodic Lyapunov equations
with large and sparse coefficient matrices. We also demonstrate
how these methods can be applied to balanced truncation model
reduction of periodic discrete-time systems and the solution of
periodic Riccati equations.
For linear differential-algebraic equations (DAEs) with properly
stated leading terms the property of being numerically qualified
guarantees that qualitative properties of DAE solutions are reflected
by the numerical approximations. In this case BDF and Runge-Kutta
methods integrate the inherent regular ODE.
Here, we extend these results to general linear methods. We show
how general linear methods having stiff accuracy can be applied to
linear DAEs of index 1 and 2. In addition to the order conditions for
ODEs, general linear methods for DAEs have to satisfy additional
conditions.
As general linear methods require a starting procedure to start the
integration we put special emphasis on finding suitable starting
methods for index-2 DAEs.
Cyclic timetabling for public transportation companies is usually modeled by the periodic
event scheduling problem. To deduce a mixed-integer programming formulation, artificial integer
variables have to be introduced. There are many ways to define these integer variables.
We show that the minimal number of integer variables required to encode an instance is
achieved by introducing an integer variable for each element of some integral cycle basis. An
integral cycle basis consists of |A|-|V|+1 oriented cycles of a directed graph D = (V;A) that
enable any oriented cycle of the directed graph to be expressed as an integer linear combination.
The solution times for the originating application vary extremely with different integral
cycle bases. However, our computational studies show that the width of integral cycle bases
is a good empirical measure for the solution time of the MIP. Clearly, integral cycle bases
permit a much wider choice than the former standard approach, in which integer variables are
associated with the co-tree arcs of some spanning tree. Hence, to formulate better solvable
integer programs, we present algorithms that construct integral cycle bases of small width.
To that end, we investigate classes of directed cycle bases that are closely related to integral
cycle bases, namely (generalized) fundamental and undirected cycle bases. This gives rise to
both, a compact classification of directed cycle bases and notable reductions of running times
for cyclic timetabling.
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
This paper is concerned with transparent boundary conditions
(TBCs) for the time-dependent Schrödinger equation in one and two
dimensions. Discrete TBCs are introduced in the numerical simulations
of whole space problems in order to reduce the computational
domain to a finite region. Since the discrete TBC for the Schrödinger
equation includes a convolution w.r.t. time with a weakly decaying
kernel, its numerical evaluation becomes very costly for large-time
simulations.
As a remedy we construct approximate TBCs with a kernel having
the form of a finite sum-of-exponentials, which can be evaluated
in a very efficient recursion. We prove stability of the resulting initialboundary
value scheme, give error estimates for the considered approximation
of the boundary condition, and illustrate the efficiency of
the proposed method on several examples.
In this paper we introduce the notion of smoothed competitive analysis of online
algorithms. Smoothed analysis has been proposed by Spielman and Teng [22] to explain
the behaviour of algorithms that work well in practice while performing very poorly
from a worst case analysis point of view. We apply this notion to analyze the Multi-
Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of
jobs released over time when the processing time of a job is only known at time of
completion.
The initial processing times are integers in the range [1, 2K ]. We use a partial bit
randomization model, where the initial processing times are smoothened by changing
the k least significant bits under a quite general class of probability distributions. We
show that MLF admits a smoothed competitive ratio of O(max((2k /σ)3 , (2k /σ)2 2K−k )),
where σ denotes the standard deviation of the distribution. In particular, we obtain a
competitive ratio of O(2K−k ) if σ = Θ(2k ). We also prove an Ω(2K−k ) lower bound for
any deterministic algorithm that is run on processing times smoothened according to
the partial bit randomization model. For various other smoothening models, including
the additive symmetric smoothening model used by Spielman and Teng [22], we give a
higher lower bound of Ω(2K ).
A direct consequence of our result is also the first average case analysis of MLF. We
show a constant expected ratio of the total flow time of MLF to the optimum under
several distributions including the uniform distribution.
The paper presents a new affine invariant theory on asymptotic mesh
independence of Newton’s method for discretized nonlinear operator equations.
Compared to earlier attempts, the new approach is both much simpler
and more intuitive from the algorithmic point of view. The theory
is exemplified at collocation methods for ODE boundary value problems
and at finite element methods for elliptic PDE problems.
In this article, we use numerical simulation to investigate transient temperature
phenomena during sublimation growth of SiC single crytals via physical
vapor transport (also called the modified Lely method). We consider the evolution
of temperatures at the SiC source and at the SiC seed crystal, which
are highly relevant to the quality of the grown crystals, but inaccessible to
direct measurements. The simulations are based on a transient mathematical
model for the heat transport, including heat conduction, radiation, and radio
frequency (RF) induction heating. Varying the position of the induction coil
as well as the heating power, it is shown that the measurable temperature difference
between the bottom and the top of the growth apparatus can usually
not be used as a simple indicator for the respective temperature difference
between SiC source and seed. Moreover, it is shown that there can be a time
lack of 1.5 hours between the heating of the temperature measuring points
and the heating of the interior of the SiC source.
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly
at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n
be the density of the graph of Pd,n (i.e., the number of one-dimensional
faces of Pd,n divided by n ). Our main result is that, for any function 2
n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √
for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √
converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.