Refine
Year of publication
- 2004 (167) (remove)
Our main result is that every n-dimensional polytope can be
described by at most 2n ? 1 polynomial inequalities and, moreover, these
polynomials can explicitly be constructed. For an n-dimensional pointed
polyhedral cone we prove the bound 2n ? 2 and for arbitrary polyhedra we
get a constructible representation by 2n polynomial inequalities.
Traveling wave equations are used to model the dynamics of multisection semiconductor lasers. To perform a bifurcation analysis of this system of 1-D partial differential equations its low dimensional approximations are constructed and considered. Along this paper this analysis is used for the extensive study of the pulsations in a three section distributed feedback laser. Namely, stability of pulsations, different bifurcation scenaria, tunability of the pulsation frequency and its locking by the frequency of electrical modulation are considered. All these pulsation qualities are highly important when applying lasers in optical communication systems.
We present an integer linear programming model for the design of multi-layer telecommunication
networks which are based on connection-oriented routing protocols. The formulation integrates hardware,
capacity, routing, and grooming decisions in any number of network layers. Practical hardware
restrictions and cost can accurately be taken into account.
We present a new iterative procedure for solving the multiple stopping
problem in discrete time and discuss the stability of the algorithm.
The algorithm produces monotonically increasing approximations of the
Snell envelope, which coincide with the Snell envelope after finitely many
steps. Contrary to backward dynamic programming, the algorithm allows
to calculate approximative solutions with only a few nestings of conditional
expectations and is, therefore, tailor-made for a plain Monte-Carlo
implementation.
We consider a sequence of curved rods which consist of isotropic material and which are clamped on the lower base or on both bases. We study the asymptotic behaviour of the stress tensor and displacement under the assumptions of linearized elasticity when the cross-sectional diameter of the rods tends to zero and the body force is given in the particular form. The analysis covers the case of a non-smooth limit line of centroids. We show how the body force and the choice of the approximating curved rods can affect the strong convergence and the limit form of the stress tensor for the curved rods clamped on both bases.
We prove the existence, uniqueness, regularity and smooth dependence
of the weak solution on the initial data for a certain class of semilinear first order
dissipative hyperbolic systems with spacially discontinuous coefficients. Such
kind of hyperbolic problems have succesfully been used to describe the dynamics
of distributed feedback multisection semiconductor lasers in recent years. We
show that in a suitable function space of continuous functions the weak solutions
generate a smooth semiflow.
The Modified Nodal Analysis leads to differential algebraic equations
with properly stated leading terms. In this article a special structure of the DAEs
modelling electrical circuits is exploited in order to derive a new decoupling for
nonlinear index-2 DAEs. This decoupling procedure leads to a solvability result and
is also used to study general linear methods, a class of numerical schemes that covers
both Runge-Kutta and linear multistep methods. Convergence for index-2 DAEs is
proved.
We simulate and analyse a 1D-PDE model describing the dynamics of multisection semiconductor lasers. We demonstrate how a semi-analytical computation of the spectrum and the corresponding eigenfunction expansion of the computed solutions provides a useful information allowing to achieve a better understanding of the laser dynamics. Basic algorithms implemented into a corresponding software tool are described.
An in-depth theoretical as well as experimental analysis of the nonlinear dynamics in semiconductor lasers
with active optical feedback is presented. Use of a monolithically integrated multisection device of submillimeter
total length provides access to the short-cavity regime. By introducing an amplifier section as a special
feature, phase and strength of the feedback can be separately tuned. In this way, the number of modes involved
in the laser action can be adjusted. We predict and observe specific dynamical scenarios. Bifurcations mediate
various transitions in the device output, from single-mode steadystate to self-pulsation and between different
kinds of self-pulsations, reaching eventually chaotic behavior in the multimode limit.
Im Zentrum der Arbeiten soll die Chaos- und Kohärenzkontrolle von Halbleiterlasern mit gegenseitiger optischer Kopplung stehen. Diese Fragestellung ist von erheblicher praktischer Relevanz, da Rauschen und chaotisches Verhalten generelle Probleme in der optischen Hochgeschwindigkeitskommunikation sind. Die Kontrolle von optischen Systemen mit komplexer Selbstorganisation stellt aber auch aus grundsätzlicher Sicht Neuland dar. Hierfür geeignete Konzepte sind bisher weder überzeugend theoretisch beschrieben noch experimentell umgesetzt.
We describe the basic ideas behind the concept of distributed
feedback (DFB) lasers with short optical feedback for the
generation of high-frequency self-pulsations and show the theoretical
background describing realized devices. It is predicted by
theory that the self-pulsation frequency increases with increasing
feedback strength. To provide evidence for this, we propose a novel
device design which employs an amplifier section in the integrated
feedback cavity of a DFB laser.We present results from numerical
simulations and experiments. It has been shown experimentally
that a continuous tuning of the self-pulsation frequency from 12
to 45 GHz can be adjusted via the control of the feedback strength.
The numerical simulations, which are in good accordance with experimental
investigations, give an explanation for a self-stabilizing
effect of the self-pulsations due to the additional carrier dynamic
in the integrated feedback cavity.
Abstract. We consider a mathematical model (the so-called traveling-wave system) which describes longitudinal
dynamical effects in semiconductor lasers. This model consists of a linear hyperbolic system
of PDEs, which is nonlinearly coupled with a slow subsystem of ODEs. We prove that a corresponding
initial-boundary value problem is well posed and that it generates a smooth infinite-dimensional dynamical
system. Exploiting the particular slow–fast structure, we derive conditions under which there exists a lowdimensional
attracting invariant manifold. The flow on this invariant manifold is described by a system
of ODEs. Mode approximations of that system are studied by means of bifurcation theory and numerical
tools.
We introduce a transformation between the generalized symplectic
pencils and the skew-Hermitian/Hermitian pencils. Under the transformation
the regularity of the matrix pencils is preserved, and the
equivalence relations about their eigenvalues and deflating subspaces
are established. The eigenvalue problems of the generalized symplectic
pencils and skew-Hermitian/Hermitian pencils are strongly related to
the discrete-time and continuous-time robust control problems, respectively.
With the transformation a simple connection between these two
types of robust control problems is made. The connection may help
to develop unified methods for solving the robust control problems.
An initial-value problem for a Fokker-Planck type equation on an unbounded space
domain is discretized in time by an implicit Euler scheme and in space by a Galerkin
scheme. It is shown that this scheme conserves mass, positivity and decay of the
entropy. The approximation properties are investigated and numerical experiments
are provided.
In this project we propose the use of some widespread prediction techniques in the last few years for modeling derivatives. In order to do that, we have reviewed the state-of-the-art of the prediction models dealing with stochastic processes. In the oil futures sector, Schwartz suggested a model in which the oil futures price was split in two factors: the long-term equilibrium price and the short-term variations. As a result, we propose a Hull-White discrete-time two-factor interest rate model, whose factors are the short and the long term.
We investigate the condition number for a complex eigenvalue of a real matrix under
real perturbations. Based on an explicit formula, it is shown that this number is never
smaller than 1/
p
2 times the corresponding condition number with respect to complex
perturbations. This result can be generalized to the condition number of an arbitrary
complex-valued function under real perturbations. This extends to related condition
numbers.
We consider the linear-quadratic optimal control problem for a controlled differential
algebraic equation (DAE). Under minimal assumptions on the DAE concerning index and regularity
it will be possible to prove that the sufficient optimality condition given in papers of G. Kurina
and R. März is also a necessary condition. This condition includes the solution of an appropriate
boundary value problem and, in the special case of an explicit ordinary differential equation, the
condition is equal to the well known necessary and sufficient condition of the classical linear-quadratic
optimal control problem.
The aim of this paper is to study the behaviour of a weak solution to Navier-Stokes equations for isothermal fluids with a nonlinear stress tensor for time going to infinity. In an analogous way as in [18], we construct a suitable function which approximates the density for time going to infinity. Using properties of this function, we can prove the strong convergence of the density to its limit state. The behaviour of the velocity field and kinetic energy is mentioned as well.
In this paper, we investigate the decay rate of stabilization of the solution of the system of partial differential equations governing the dynamics of martensitic phase transitions in shape memory alloys under the presence of a viscous stress. The corresponding free energy is assumed in Landau-Ginzburg form and nonconvex as a function of the order parametr. We prove that for appropriate constants, which appear in the above-mentioned model, we can decide upon the exponencial decrease of the solution to its attractor for time tending to infinity.
Es wird eine notwendige Optimalitäts-Bedingung für das linearquadratische
Optimierungsproblem mit differentiell-algebraischen Gleichungen
im Fall Index 2 bewiesen. Im ersten Schritt wird die kausale
DAE betrachtet. Im zweiten Schritt wird ein neuer Lösungs-Begriff für
nicht-kausale DAEs eingeführt und ein spezielles Kostenfunktional betrachtet,
welches für stetige Steuer-Funktionen nur den stetigen Teil
der Zustands-Variablen bewertet. Es stellt sich heraus, dass die adjungierte
Gleichung dann kausal ist und somit eine stetige Lösung besitzt.
Es wird die erweiterte Hessenberg-Form für DAEs eingeführt, die es
unter anderem ermöglicht, Beziehungen der DAE zu ihrer adjungierten
Gleichung im Optimierungs-Problem einfacher zu untersuchen.
We consider a control constrained optimal control problem governed by a semilinear
elliptic equation with nonlocal interface conditions. These conditions occur during the modeling of
diffuse-gray conductive-radiative heat transfer. The problem arises from the aim to optimize the
temperature gradient within crystal growth by the physical vapor transport (PVT) method. Based
on a minimum principle for the semilinear equation as well as L1-estimates for the weak solution,
we establish the existence of an optimal solution as well as necessary optimality conditions. The
theoretical results are illustrated by results of numerical computations.
Several qualitative properties of equilibria in electrical circuits are analyzed in this paper. Specifically, non-singularity, hyperbolicity, and asymptotic stability are addressed in terms of the circuit topology, which is captured through the use of Modified Nodal Analysis (MNA) models. The differential-algebraic or semistate nature of these models drives the analysis of the spectrum to a matrix pencil setting, and puts the results beyond the ones already known for state-space models, unfeasible in many actual problems. The topological conditions arising in this qualitative study are proved independent of those supporting the index, and therefore they apply to both index-1 and index-2 configurations. The analysis combines results coming from graph theory, matrix analysis, matrix pencil theory, and Lyapunov theory for DAEs. The study is restricted to problems with independent sources; qualitative properties of circuits including controlled sources are the focus of future research.
We investigate numerical methods for passive
model reduction of linear dynamical systems. This
is an important task in circuit simulation when
modeling parasitic effects of interconnect. We will
show how positive real balancing, based on balancing
the solutions of two algebraic Riccati equations,
can be used for passive model reduction
of large-scale systems on parallel computers. Numerical
experiments demonstrate the performance
of the parallel algorithms using several examples
from circuit simulation.
The randomized k-number partitioning problem is the task to distribute N i.i.d. random variables into k groups in such a way that the sums of the variables in each group are as similar as possible. The restricted k-partitioning problem refers to the case where the number of elements in each group is fixed to N/k. In the case k = 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the case k > 2 in the restricted problem and show that the vector of differences between the k sums converges to a k - 1-dimensional Poisson point process.
In this paper we give a survey on balanced truncation model order
reduction for linear time-invariant continuous-time systems in descriptor form. We
first give a brief overview of the basis concepts from linear system theory and then
present balanced truncation model reduction methods for descriptor systems and
discuss their algorithmic aspects. The efficiency of these methods is demonstrated
by numerical experiments.
The purpose of this paper is the analysis of relaxation methods for the numerical integration
of coupled systems of ODEs and DAEs. We will investigate convergence of relaxation methods and put
special emphasis on the Jacobi- and Gauss-Seidel methods. Furthermore, the fundamental difference
in the convergence behaviour of coupled ODEs and DAEs is pointed out. This difference is used to explain
why certain relaxation methods for coupled DAEs may fail. Finally, a remedy to this undesirable effect
is proposed that makes use of a so-called preconditioned dynamic iteration strategy. This regularization
also allows significant reduction of relaxation steps.
The paper addresses primal interior point method for state constrained PDE optimal
control problems. By a Lavrentiev regularization, the state constraint is transformed to a mixed
control-state constraint with bounded Lagrange multiplier. Existence and convergence of the central
path are established, and linear convergence of a short-step pathfollowing method is shown. The
behaviour of the regularizations are demonstrated by numerical examples.
Time-lag in Derivative Convergence Time-lag in Derivative Convergence for Fixed Point Iterations
(2004)
In an earlier study it was proven and experimentally confirmed on a 2D Euler code
that fixed point iterations can be differentiated to yield first and second order derivatives of
implicit functions that are defined by state equations. It was also asserted that the resulting
approximations for reduced gradients and Hessians converge with the same R-factor as the
underlying fixed point iteration.
A closer look reveals now that nevertheless these derivative values lag behind the functions
values in that the ratios of the corresponding errors grow proportional to the iteration counter
or its square towards infinity. This rather subtle effect is caused mathematically by the
occurrence of nontrivial Jordan blocks associated with degenerate eigenvalues. We elaborate
the theory and report its confirmation through numerical experiments.
We compare different multiperiod risk measures taken from the class of polyhedral risk measures with respect to the effect
they show when used in the objective of a stochastic program. For this purpose, simulation results of a stochastic programming
model for optimizing the electricity portfolio of a German municipal power utility are presented and analyzed. This model
aims to minimize risk and expected overall cost simultaneously.
Today's telecommunication networks are configured statically. Whenever a connection
is established, the customer has permanent access to it. However, it is
observed that usually the connection is not used continuously. At this point, dynamic
provisioning could increase the utilization of network resources. WDM
based Optical Transport Networks (OTNs) will shortly allow for fast dynamic
network reconfiguration. This enables optical broadband leased line services on
demand. Since service requests competing for network resources may lead to service
blocking, it is vital to use appropriate strategies for routing and wavelength
assignment in transparent optical networks. We simulate the service blocking
probabilities of various dynamic algorithms for this problem using a well-founded
traffic model for two realistic networks. One of the algorithms using shortest path
routings performs best on all instances. Surprisingly, the tie-breaking rule between
equally short paths in different wavelengths decides between success or
failure.
Automatic, or algorithmic, differentiation addresses the need for the accurate
and efficient calculation of derivative values in scientific computing. To this
end procedural programs for the evaluation of problem-specific functions are
transformed into programs that also compute the required derivative values
at the same numerical arguments in floating point arithmetic. Disregarding
many important implementation issues, we examine in this article complexity
bounds and other more mathematical aspects of the program transformation
task sketched above.
Uniform lower and upper bounds for positive finite-element approximations
to semilinear elliptic equations in several space dimensions subject to
mixed Dirichlet-Neumann boundary conditions are derived. The main feature is
that the non-linearity may be non-monotone and unbounded. The discrete minimum
principle provides a positivity-preserving approximation if the discretization
parameter is small enough and if some structure conditions on the non-linearity
and the triangulation are assumed. The discrete maximum principle also holds
for degenerate diffusion coefficients. The proofs are based on Stampacchia's truncation
technique and on a variational formulation. Both methods are settled on
careful estimates on the truncation operator.
We study linear, possibly over- or under-determined, differentialalgebraic
equations that have the same solution behavior as linear
differential-algebraic equations with well-dened strangeness index. In
particular, we give three different characterizations for differentialalgebraic
equations, namely by means of solution spaces, canonical
forms, and derivative arrays. We distinguish two levels of generalization,
where the more restrictive case contains an additional assumption
on the structure of the set of consistent inhomogeneities.
In this paper we discuss the time integration of multibody system model equations
following a novel approach that has originally been developed for the time integration of linear
differential-algebraic equations of arbitrary high index. We do not restrict ourselves to classical
constrained mechanical systems but consider the more complex model equations that are actually
used in state-of-the-art multibody system simulation packages. The equations of motion form a
system of differential-algebraic equations of differentiation index 3 with a special structure that we
will exploit in the numerical solution. We replace the equations of motion by a so-called projected
differentiation index-one differential-algebraic equation with the same solution set.
The role of larger bulges in the QR algorithm is controversial. Large bulges are infamous
for having a strong, negative influence on the convergence of the implicit shifted QR algorithm.
This paper provides a new explanation of this shift blurring effect by connecting the computation of
the first column of the shift polynomial to the notoriously ill-conditioned pole placement problem.
To avoid shift blurring, modern variants of the QR algorithm employ chains of tightly coupled tiny
bulges instead of one large bulge. It turns out that larger bulges still play a positive role in these
variants; a slight increase of the bulge sizes often results in considerable performance improvements.
Dirigententraining für Mathematiker/innen - Ein "musikalisches" Konzept für ein Vortragstraining
(2004)
We consider a non-preemptive, stochastic parallel machine
scheduling model with the goal to minimize the weighted completion
times of jobs. In contrast to the classical stochastic model where jobs
with their processing time distributions are known beforehand, we assume
that jobs appear one by one, and every job must be assigned
to a machine online. We propose a simple online scheduling policy for
that model, and prove a performance guarantee that matches the currently
best known performance guarantee for stochastic parallel machine
scheduling. For the more general model with job release dates we derive
an analogous result, and for NBUE distributed processing times we
even improve upon the previously best known performance guarantee for
stochastic parallel machine scheduling. Moreover, we derive some lower
bounds on approximation.
This paper deals with the numerical solution of the time{dependent Schroedinger-
Poisson system in the spherically symmetric case. Since the problem is posed on an
unbounded domain one has to introduce artificial boundary conditions to confine
the computational domain. The main topic of this work is the construction of a
so-called discrete transparent boundary condition (TBC) for a Crank-Nicolsontype
predictor-corrector scheme for solving the Schroedinger-Poisson system. This
scheme has the property of mass and energy conservation exactly on the discrete
level. We propose different strategies for the discrete TBC and present an efficient
implementation. Finally, a numerical example illustrate the findings and shows the
comparison results between the different approaches.
A 1D coupled drift-diffusion dissipative Schroedinger model (hybrid model), which
is capable to describe the transport of electrons and holes in semi-conductor devices
in a non-equilibrium situation, is mathematically analyzed. The device domain is
split into a part where the transport is well-described by the drift-diffusion equations
(classical zone) and a part where a quantum description via a dissipative Schroedinger
system (quantum zone) is used. Both system are coupled such that the continuity
of the current densities is guaranteed. The electrostatic potential is self-consistently
determined by Poisson's equation on the whole device. We show that the hybrid
model is well-posed, prove existence of solutions and show their uniform boundedness
provided the distribution function satisfy a so-called balance condition. The current
densities are different from zero in the non-equilibrium case and uniformly bounded.
We revisit here the situation of a thin liquid film driven up an
inclined substrate by a thermally induced Marangoni shear stress against
the counter-acting parallel component of gravity. In contrast to previous
studies, we focus here on the meniscus region, in the case where the substrate
is nearly horizontal, so there is a significant contribution from the
normal component of gravity. Our numerical simulations show that the
time-dependent lubrication model for the film profile can reach a steady
state in the meniscus region that is unlike the monotonic solutions found
in [MÄunch, SIAM J. Appl. Math., 62(6):2045-2063, 2002]. A systematic
investigation of the steady states of the lubrication model is carried out by
studying the phase space of the corresponding third order ODE system. We
find a rich structure of the phase space including multiple non-monotonic
solutions with the same far-field film thickness.
Transient analysis in industrial chip design leads to very large systems
of differential-algebraic equations (DAEs). The numerical solution of these
DAEs strongly depends on the so called index of the DAE. In general,
the higher the index of the DAE is, the more sensitive the numerical
solution will be to errors in the computation. So, it is advisable to use
mathematical models with small index or to reduce the index.
This paper presents an index reduction method that uses information
based on the topology of the circuit. In addition, we show that the
presented method retains structural properties of the DAE.
This work studies the stability and the stochastic properties of neural activity evoked by external
stimulation. The underlying model describes the spatiotemporal dynamics of neural populations
involving both synaptic delay and axonal transmission delay. We show, that the linear model
recasts to a set of affne delay differential equations in spatial Fourier space. Besides a stability
study for general kernels and general external stimulation, the power spectrum of evoked activity
is derived analytically in case of external Gaussian noise. Further applications to specific kernels
reveal critical
uctuations at Hopf- and Turing bifurcations and allow the numerical detection of
1/f fluctuations near the stability threshold.
During the last 15 years, there have been proposed many solution methods
for the important task of constructing periodic timetables for public transportation
companies. We first point out the importance of an objective function, where we
observe that in particular a linear objective function turns out to be a good compromise
between essential practical requirements and computational tractability. Then,
we enter into a detailed empirical analysis of various Mixed Integer Programming
procedures { such using nodes variables and such using arcs variables { genetic algorithms,
simulated annealing and constraint programming. To our knowledge, this
is the first comparison of five conceptually different solution approaches.
On rather small instances, an arc-based MIP formulation behaves best, when
refined by additional valid inequalities. On bigger instances, the solutions obtained
by a genetic algorithm are competitive to the solutions CPLEX was investigating
until it reached a time or memory limit. For Deutsche Bahn AG, the genetic algorithm
was most convincing on their various data sets, and it will become the first
automated timetable optimization software in use.
In the planning process of railway companies, we propose to integrate important
decisions of network planning, line planning, and vehicle scheduling into the task of periodic
timetabling. From such an integration, we expect to achieve an additional potential for
optimization.
Models for periodic timetabling are commonly based on the Periodic Event Scheduling
Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended
by only two features, namely a linear objective function and a symmetry requirement.
These extensions of the PESP do not really impose new types of constraints, because practitioners
have already required them even when only planning timetables autonomously without
interaction with other planning steps.
We derive a link between the short rate and a new index constructed in a multiasset
economy. This uses two structural assumptions: The volatility structure
of the assets is rigidly spherical , and the short rate function is homogeneous of
degree 0. We give clear motivations for the assumptions, and our main result is
economically intuitive and testable from observed data. A preliminary empirical
study illustrates how one can test such results.
In the case of the equidistant discretization of the Airy differential equation (\discrete
Airy equation") the exact solution can be found explicitly. This fact is used
to derive a discrete transparent boundary condition (TBC) for a Schroedinger
equation with linear varying potential, which can be used in \parabolic equation"
simulations in (underwater) acoustics and for radar propagation in the troposphere.
We propose different strategies for the discrete TBC and show an efficient implementation.
Finally a stability proof for the resulting scheme is given. A numerical
example in the application to underwater acoustics shows the superiority of the new
discrete TBC.
We investigate the numerical solution of large-scale Lyapunov equations
with the sign function method. Replacing the usual matrix inversion,
addition, and multiplication by formatted arithmetic for hierarchical
matrices, we obtain an implementation that has linear-polylogarithmic
complexity and memory requirements. The method is well suited for Lyapunov
operators arising from FEM and BEM approximations to elliptic
differential operators. With the sign function method it is possible to
obtain a low-rank approximation to a full-rank factor of the solution directly.
The task of computing such a factored solution arises, e.g., in
model reduction based on balanced truncation. The basis of our method
is a partitioned Newton iteration for computing the sign function of a
suitable matrix, where one part of the iteration uses formatted arithmetic
while the other part directly yields approximations to the full-rank factor
of the solution. We discuss some variations of our method and its application
to generalized Lyapunov equations. Numerical experiments show
that the method can be applied to problems of order up to O(105) on
desktop computers.
Branching Rules Revisited
(2004)
Mixed integer programs are commonly solved with linear programming
based branch-and-bound algorithms. The success of the algorithm
strongly depends on the strategy used to select the variable to
branch on.
We present a new generalization called reliability branching of today's
state-of-the-art strong branching and pseudocost branching branching
strategies for linear programming based branch-and-bound algorithms.
After reviewing commonly used branching strategies and performing
extensive computational studies we compare different parameter
settings and show the superiority of our proposed new strategy.
Effects of nonlocal feedback on traveling fronts in neural fields subject to transmission delay
(2004)
The work introduces a model for reciprocal connections in neural fields by a nonlocal feedback
mechanism, while the neural field exhibits nonlocal interactions and intra-areal transmission delays.
We study the speed of traveling fronts with respect to the transmission delay, the spatial feedback
range and the feedback delay for general axonal and feedback connectivity kernels. In addition, we
find a novel shape of traveling fronts due to the applied feedback and criteria for its occurence are
derived.
We develop a behavioural approach to linear, time-varying, differential algebraic systems.
The analysis is \almost everywhere" in the sense that the statements hold on R T, where
T is a discrete set. Controllability, observability and autonomy is introduced and related to
the behaviour of the system. Classical results on the behaviour of time-invariant systems are
studied in the context of time-varying systems.
Under high load, the automated dispatching of service vehicles for
the German Automobile Association (ADAC) must reoptimize a dispatch for
100{150 vehicles and 400 requests in about ten seconds to near optimality. In
the presence of service contractors, this can be achieved by the column generation
algorithm ZIBDIP. In metropolitan areas, however, service contractors
cannot be dispatched automatically because they may decline. The problem:
a model without contractors yields larger optimality gaps within ten seconds.
One way out are simplified reoptimization models. These compute a shortterm
dispatch containing only some of the requests: unknown future requests
will in
uence future service anyway. The simpler the models the better the
gaps, but also the larger the model error. What is more significant: reoptimization
gap or reoptimization model error? We answer this question in
simulations on real-world ADAC data: only the new models ShadowPrice and
ZIBDIPdummy can keep up with ZIBDIP.
We introduce a behavioural approach to linear, time-varying, differential algebraic
(descriptor) systems. The analysis is \almost global" in the sense that the analysis is
not restricted to an interval I R but is allowed for the \time axis" RnT, where T is
a discrete set of critical points, at which the solution may exhibit a finite escape time.
Controllable, observable, autonomous, and adjoint behaviour for linear time-varying
descriptor systems is introduced and characterized.
O&D revenue management (RM)
– either leg-based or PNR-based – has become
a standard in the airline industry. In this paper,
we present a new approach to O&D RM which
does not make any assumptions on demand distributions
or on the correlations of the booking
process. Protection levels are determined for all
origin destination itineraries, fare classes, points
of sale and data collection points (DCPs). This
approach to the seat inventory problem is modelled
as a multistage stochastic program, where
its stages correspond to the DCPs of the booking
horizon. The stochastic passenger demand
process is approximated by a scenario tree generated
from historical data by a recursive scenario
reduction procedure. The stochastic program
represents a specially structured large scale
LP that may be solved by standard LP software
(e.g. CPLEX). Preliminary numerical experience
is reported.
UMTS radio network evaluation and design are currently important issues for telecommunication operators.
We present a novel view on network evaluation. The recent dimension reduction approach is
generalized to an analytical approximation of the network's general performance based on average traffic.
The pivot is an average coupling matrix that captures the essential coverage and cell coupling properties of
the radio network. Based on this new evaluation method, we present new optimization methods, namely
a new optimization model based on designing the generalized average coupling matrix and an efficient
1-opt local search. We give preliminary computational results that show the potential of our methods on
realistic data.
We discuss solvers for Sylvester, Lyapunov, and Stein equations that are available in the SLICOT
Library (Subroutine Library In COntrol Theory). These solvers offer improved efficiency, reliability,
and functionality compared to corresponding solvers in other computer-aided control system
design packages. The performance of the SLICOT solvers is compared with the corresponding
Matlab solvers. This note can also serve as a guide to the SLICOT and SLICOT-based Matlab
solvers for Linear Matrix Equations.
We shortly review the uncoupling-coupling method, a Markov chain
Monte Carlo based approach to compute statistical properties of systems like
medium-sized biomolecules. This technique has recently been proposed for the efficient computation of biomolecular conformations. One crucial step of UC is the
decomposition of reversible nearly uncoupled Markov chains into rapidly mixing
subchains. We show how the underlying scheme of uncoupling-coupling can also be
applied to stochastic differential equations where it can be translated into a domain
decomposition technique for partial differential equations.
This paper discusses some relationships between ILU factorization techniques and factored sparse approximate inverse techniques. While ILU factorizations compute approximate LU factors of the coefficient matrix A, approximate inverse techniques aim at building triangular matrices Z and W such that $W^\top AZ$ is approximately diagonal. The paper shows that certain forms of approximate inverse techniques amount to approximately inverting the triangular factors obtained from some variants of ILU factorization of the original matrix. A few useful applications of these relationships will be discussed.
Quality of Service (QoS) mechanisms in networks
supporting mobile Internet communications give
rise to new threats: these mechanisms could be abused
by malicious entities launching so-called Denial of Service
(DoS) attacks. If the network can not efficiently check the
credibility of a QoS-request during a handover process,
malicious entities could flood the network with bogus QoSrequests;
if the authentication check is performed by means
of an AAA protocol before the access network commits its
resources to the request, the authentication process may
not only introduce a notable latency to the handover process,
but also generate an extensive traffic which degrades
the signaling capacity in the network when there are a considerable
amount of malicious requests. In order to defend
against these kinds of attacks and meet the low-latency
micro-mobility handover requirement, we 1propose to have
a preliminary authentication check with a cookie-based
mechanism before processing the requests and performing
authentication and authorization. The performance evaluation
shows that the cookie-based mechanism is efficient in
dealing with the identified issues.
In this paper we present a new incomplete LU decomposition which is based on
an existing sparse direct solver. In contrast to many incomplete LU decompositions
this ILU incorporates information about the inverse factors L-1 and U-1 which
have direct in
uence on the dropping strategy. We demonstrate in several large scale
examples that this implementation constructs a robust preconditioner.
This article is concerned with the averaging principle and its extensions
for stochastic dynamical systems with fast and slow degrees of
freedom. It is demonstrated how the \conventional" averaging principle
results from asymptotic multiscale analysis, how one can construct
an indicator for its (in-)appropriateness, and how, if inappropriate, it
may be extended into an improved approximation. The conventional
scheme contains averages over the entire accessible state space of the
fast degrees of freedom and may thus fail if these fast degrees of freedom
exhibit long-term (auto-)correlations. In contrast, the improved
scheme combines several conditional averages with a Markov jump process
that is designed to represent the
ipping process between the
conditional averages and thus incorporates the important long-term
correlations. All important steps of the derivation are illustrated by
numerical experiments. Application to problems from molecular dynamics
is discussed.
We study the instability arising at the moving ridge of holes appearing
upon dewetting of thin polymer films on hydrophobized substrates, giving
special attention to the role of slippage at the liquid/solid for the appear-
ance of the instability. We compare here numerical results for a lubrication
model of the dewetting film assuming either a no-slip or a free slip condition
at the liquid/solid interface. Linear stability analysis reveals that in both
cases, perturbations of the ridge are amplied, but by orders of magnitude
more in the free slip case. Furthermore, the perturbations become much
more asymmetrical in the free slip case, while they develop symmetrical
patterns without slip. Additional computations that solve the lubrication
model for the full three-dimensional
ow confirm that these findings carry
over into the nonlinear regime.
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 a
hierarchical network? We propose a solution approach that is based on mixed-integer programming and
Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but
also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved
within 30 minutes to less than 1% off optimality.
This paper introduces arithmetic-like operations on matrix pencils. The pencil-arithmetic
operations extend elementary formulas for sums and products of rational numbers and
include the algebra of linear transformations as a special case. These operation give an
unusual perspective on a variety of pencil related computations. We derive generalizations of
monodromy matrices and the matrix exponential. A new algorithm for computing a pencilarithmetic
generalization of the matrix sign function does not use matrix inverses and gives
an empirically forward numerically stable algorithm for extracting deflating subspaces.
Motivation: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches.
Results: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search.
We consider a one–dimensional coupled stationary Schrödinger drift–diffusion model for quantum
semiconductor device simulations. The device domain is decomposed into a part with large quantum
effects (quantum zone) and a part where quantum effects are negligible (classical zone). We give
boundary conditions at the classic–quantum interface which are current preserving. Collisions within
the quantum zone are introduced via a Pauli master equation. To illustrate the validity we apply the
model to three resonant tunneling diodes
The present work introduces an analysis framework for the de-
tection of metastable signal segments in multivariate time series. It
is shown that in case of linear data these segments represent tran-
sient generalized synchronization, while metastable segments in circu-
lar data reflect transient mutual phase synchronization. We propose
a single segmentation approach for both types of data considering the
space-time structure of the data. Applications to both event-related
potentials and single evoked potentials obtained from an auditory odd-
ball experiment reveal the lack of the component P300 in an experi-
mental condition, indicates attention effects in component N100 and
shows dramatic latency jitters in single trials. A comparison of the
proposed method to a conventional index of mutual phase synchro-
nization demonstrates the superiority of considering space-time data
structures.
The line planning problem is one of the fundamental problems in strategic
planning of public and rail transport. It consists of finding lines
and corresponding frequencies in a public transport network such that
a given travel demand can be satisfied. There are (at least) two objectives.
The transport company wishes to minimize its operating cost;
the passengers request short travel times. We propose two new multicommodity
ow models for line planning. Their main features, in comparison
to existing models, are that the passenger paths can be freely
routed and that the lines are generated dynamically.
The weighted matching problem is to find a matching in a weighted graph
that has maximum weight. The fastest known algorithm for this problem has running time
O(nm +n2 log n). Many real world problems require graphs of such large size that this running
time is too costly. We present a linear time approximation algorithm for the weighted
matching problem with a performance ratio of 2
3 ???? ". This improves the previously best
performance ratio of 1
2 .
Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested [5][17]. Both these algorithms have a performance ratio of 1/2. In this paper we present a set of local improvement operations and prove that it guarantees a performance ratio of 2/3. We show that a maximal set of these local improvements can be found in linear time.
To see how these local improvements behave in practice we conduct an experimental comparison of four different approximation algorithms for calculating maximum weight matchings in weighted graphs. One of these algorithms is the commonly used Greedy algorithm which achieves a performance ratio of 1/2 but has O(m log n) runtime. The other three algorithms all have linear runtime. Two of them are the above mentioned 1/2 approximation algorithms. The third algorithm may have an arbitrarily bad performance ratio but in practice produces reasonably good results. We compare the quality of the algorithms on a test set of weighted graphs and study the improvement achieved by our local improvement operations. We also do a comparison of the runtimes of all algorithms.
We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259–269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.
We investigate the problem of colouring random graphs G ? G(n; p)
in polynomial expected time. For the case p ? 1.01/n, we present an algorithm
that finds an optimal colouring in linear expected time. For
p ?? ln6(n)/n, we give algorithms which approximate the chromatic
number within a factor of O(? np). We also obtain an O(?
np/ ln(np))-
approximation algorithm for the independence number. As an application,
we propose an algorithm for deciding satisfiability of random 2k-
SAT formulas (with sufficiently many clauses) in
polynomial expected time.
We investigate the problem of colouring random graphs G ? G(n, p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n.
We introduce a systematic approach to the problem of maximizing the robust
utility of the terminal wealth of an admissible strategy in a general complete market
model, where the robust utility functional is defined by a set Q of probability measures.
Our main result shows that this problem can be reduced to determining a “least favorable”
measure Q0 2 Q, which is universal in the sense that it does not depend on the
particular utility function. The robust problem is thus equivalent to a standard utility
maximization problem with respect to the “subjective” probability measure Q0. By using
the Huber-Strassen theorem from robust statistics, it is shown that Q0 always exists if Q
is the core of a 2-alternating upper probability. We also discuss the problem of robust
utility maximization with uncertain drift in a Black-Scholes market and the case of “weak
information” as studied by Baudoin (2002).
We discuss an efficient algorithm for optimal Hankel norm approximation of large-scale
systems and an implementation which allows to reduce models of order up to O(104) using
parallel computing techniques. The major computational tasks in this approach are the
computation of a minimal balanced realization, involving the solution of two Lyapunov
equations, and the additive decomposition of a transfer function via block diagonalization.
We will illustrate that these computational tasks can all be performed using iterative
schemes for the matrix sign function. Numerical experiments on a cluster of Linux PCs
show the efficiency of our methods.
A new method for noise removal of arbitrary surfaces
meshes is presented which focuses on the preservation
and sharpening of non-linear geometric features such
as curved surface regions and feature lines. Our method
uses a prescribed mean curvature flow (PMC) for simplicial
surfaces which is based on three new contributions:
1. the definition and efficient calculation of a
discrete shape operator and principal curvature properties
on simplicial surfaces that is fully consistent with
the well-known discrete mean curvature formula, 2. an
anisotropic discrete mean curvature vector that combines
the advantages of the mean curvature normal with
the special anisotropic behaviour along feature lines of
a surface, and 3. an anisotropic prescribed mean curvature
flow which converges to surfaces with an estimated
mean curvature distribution and with preserved nonlinear
features. Additionally, the PMC flow prevents
boundary shrinkage at constrained and free boundary
segments.
We study perturbations of a stochastic program with a probabilistic constraint and r-concave original probability distribution. First we improve our earlier results substantially and provide conditions implying Hölder continuity properties of the solution sets w.r.t. the Kolmogorov distance of probability distributions. Secondly, we derive an upper Lipschitz continuity property for solution sets under more restrictive conditions on the original program and on the perturbed probability measures. The latter analysis applies to linear-quadratic models and is based on work by Bonnans and Shapiro. The stability results are illustrated by numerical tests showing the different asymptotic behaviour of parametric and nonparametric estimates in a program with a normal probabilistic constraint.
We consider stochastic programs with risk measures in the objective and study
stability properties as well as decomposition structures. Thereby we place emphasis on dynamic
models, i.e., multistage stochastic programs with multiperiod risk measures. In this context, we
define the class of polyhedral risk measures such that stochastic programs with risk measures taken
from this class have favorable properties. Polyhedral risk measures are defined as optimal values of
certain linear stochastic programs where the arguments of the risk measure appear on the right-hand
side of the dynamic constraints. Dual representations for polyhedral risk measures are derived and
used to deduce criteria for convexity and coherence. As examples of polyhedral risk measures we
propose multiperiod extensions of the Conditional-Value-at-Risk.
We consider multistage stochastic optimization models containing nonconvex constraints, e.g.,
due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding
decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on
convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes.
The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal
decomposition. The second group of results concerns large stochastic optimization models with loosely coupled
components. The results provide conditions implying relations between the duality gaps of geographical
decomposition and the duality gaps for scenario and nodal decomposition, respectively.
Portfolio and risk management problems of power
utilities may be modeled by multistage stochastic programs. These
models use a set of scenarios and corresponding probabilities
to model the multivariate random data process (electrical load,
stream flows to hydro units, and fuel and electricity prices). For
most practical problems the optimization problem that contains
all possible scenarios is too large. Due to computational complexity
and to time limitations this program is often approximated by
a model involving a (much) smaller number of scenarios. The proposed
reduction algorithms determine a subset of the initial scenario
set and assign new probabilities to the preserved scenarios.
The scenario tree construction algorithms successively reduce the
number of nodes of a fan of individual scenarios by modifying the
tree structure and by bundling similar scenarios. Numerical experience
is reported for constructing scenario trees for the load
and spot market prices entering a stochastic portfolio management
model of a German utility
We present a mixed-integer multistage stochastic programming model for the short term unit commitment of a hydro-thermal power system under uncertainty in load, inflow to reservoirs, and prices for fuel and delivery contracts. The model is implemented for uncertain load and tested on realistic data from a German power utility. Load scenario trees are generated by a procedure consisting of two steps: (i) Simulation of load scenarios using an explicit respresentation of the load distribution and (ii) construction of a tree out of these scenarios. The dimension of the corresponding mixed-integer programs ranges up to 200,000 binary and 350,000 continuous variables. The model is solved by a Lagrangian-based decomposition strategy exploiting the loose coupling structure. Solving the Lagrangian dual by a proximal bundle method leads to a successive decomposition into single unit subproblems, which are solved by specific algorithms. Finally, Lagrangian heuristics are used to construct nearly optimal first stage decisions.
Mathematical models for the electricity portfolio
management of a utility that owns a hydro-thermal generation system
and trades on the power market often lead to complex stochastic
optimization problems. We present a new approach to solving
stochastic hydro-storage subproblems that occur when stochastic
Lagrangian relaxation is applied to solving such models. The special
structure of such hydro-storage subproblems allows the design
of a stochastic network flow algorithm. The algorithm represents
a stochastic extension of a relaxation method, that algorithmically
solves the linear minimum cost flow problem. It is based on the
iterative improvement of dual costs. Numerical experience of the
new algorithm is reported and its performance is compared with
that of standard LP software .
This work is concerned with transparent boundary conditions (TBCs) for systems of Schrödinger type equations, namely the time-dependent kp-Schrödinger equations. These TBCs
have to be constructed for the discrete scheme, in order to maintain stability and to avoid
numerical re
ections. The discrete transparent boundary conditions (DTBCs) are constructed
using the solution of the exterior problem with Laplace and Z-transformation respectively.
Hence we will analyse the numerical error caused by the inverse Z-transformation. Since
these DTBCs are non-local in time and thus very costly, we present approximate DTBCs,
that allow a fast calculation of the boundary terms.
It is known that for each combinatorial type of convex 3-dimensional
polyhedra, there is a representative with edges tangent to the unit sphere.
This representative is unique up to projective transformations that fix the unit
sphere. We show that there is a unique representative (up to congruence) with
edges tangent to the unit sphere such that the origin is the barycenter of the
points where the edges touch the sphere.
Given a set of service requests (events), a set of guided servers (units),
and a set of unguided service contractors (conts), the vehicle dispatching problem
VDP is the task to find an assignment of events to units and conts as well as tours
for all units starting at their current positions and ending at their home positions
(dispatch) such that the total cost of the dispatch is minimized.
The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit
costs consist of driving costs, service costs and overtime costs; cont costs consist of
a fixed cost per service; event costs consist of late costs linear in the late time, which
occur whenever the service of the event starts later than its deadline.
The program ZIBDIP based on dynamic column generation and set partitioning
yields solutions on heavy-load real-world instances (215 events, 95 units) in less
than a minute that are no worse than 1% from optimum on state-of-the-art personal
computers.
We consider a particle constrained to a submanifold ? of the configuration space
Rm. Using that the notion of holonomic constraints coincides with integrability of the corresponding
vector field, we show how this property naturally determines local coordinates on ? . We give a
rigorous justification for the calculation of the mean force along the constrained coordinates, and
we provide a concise geometrical interpretation of the different contributions to the mean force.
Our approach gives rise to a generalisation of the Fixman Theorem which is well known and widely
used in molecular dynamics applications. It further allows for working out a Hybrid Monte-Carlo
based algorithm that can be used to compute arbitrary statistical quantities from constrained
simulations such as the mean force in the context of thermodynamic free energy statistics.
Models for physical systems often take the form of implicit or behavioral models. One important problem is the
identification of which combinations of variables are good candidtates for control variables. This paper first provides one
solution to this problem for linear time varying systems. The solution is shown to be related to a general optimization
problem. It is then shown how these same algorithms can be extended to a large and important class of nonlinear systems.
In this paper the numerical approximation of solutions of Itô stochastic differential
equations is considered, in particular for equations with a small parameter ? in the noise coex-
cient. We construct stochastic linear multi-step methods and develop the fundamental numerical
analysis concerning their mean-square consistency, numerical stability in the mean-square sense and
mean-square convergence. For the special case of two-step Maruyama schemes we derive conditions
guaranteeing their mean-square consistency. Further, for the small noise case we obtain expansions
of the local error in terms of the stepsize and the small parameter ?. Simulation results using several
explicit and implicit stochastic linear k-step schemes, k = 1; 2, illustrate the theoretical findings.