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)
Large-scale maintenance in industrial plants requires the entire shutdown of production
units for disassembly, comprehensive inspection and renewal. It is an important process but causes high out-of-service cost. Therefore a good schedule for a shutdown and and an analysis of possible associated risks are crucial for the manufacturer.
We derive models and algorithms for shutdown scheduling that include different features
such as time-cost tradeoff, precedence constraints, hiring external resources, resource leveling, different working shifts, and risk analysis. Our experimental results show that our methods solve large real-world instances very fast and yield an excellent resource utilization. A comparison with solutions of a mixed integer program on smaller instances proves the high quality
of the schedules that our algorithms produce within a few minutes.
Our algorithms work in two phases. The first phase supports the manager in finding a
good makespan for the shutdown. It computes an approximate project time cost tradeoff
curve together with a stochastic evaluation of the risk for meeting a particular makespan t. Our risk measures are the expected tardiness at time t and the probability of completing the shutdown within time t. In the second, detailed planning phase, we solve the actual scheduling optimization problem for the makespan chosen in the first phase heuristically and compute a detailed schedule that respects all side constraints. Again, we complement this by computing
upper bounds for the same two risk measures, but now for the detailed schedule. The shutdown problem has many relationships with well established areas of scheduling, and we also give an overview on the large variety of scheduling problems involved.
We introduce a new technique for solving several sequencing problems. We consider Gilmore and Gomory's variant of the Traveling Salesman Problem and two variants of no-wait flowshop scheduling, the classical makespan minimization problem and a new problem arising in the multistage production process in steel manufacturing.
Our technique is based on an intuitive interpretation of sequencing problems as Eulerian Extension Problems. This view reveals new structural insights and leads to elegant and simple algorithms and proofs for this ancient type of problems. As a major effect, we compute not only a single solution; instead, we represent the entire space of optimal solutions. For the new flowshop scheduling problem we give a full complexity classification for any machine configuration.
We consider backward stochastic differential equations (BSDE) with nonlinear generators typically of quadratic growth in the control variable. A measure solution of such a BSDE will be understood as a probability measure under which the generator is seen as vanishing, so that the classical solution can be reconstructed by a combination of the operations of conditioning and using martingale representations. In case the terminal condition ist bounded and the generator fulfills the usual continuity and boundedness conditions, we show the measure solutions with equivalent measures just reinterpret classical ones. In case of terminal conditions that have only exponentially bounded moments, we discuss a series of examples which show that in cas of non-uniqueness classical solutions that fail to be measure solutions can coexists with different measure solution.
We solve Skorokhod's embedding problem for Brownian mostion with linear drift $(W_t + \kappa t)_{t\ge 0}$ by means of techniques of stochastic control theory. The search for a stopping time $T$ such that the law of $W_T + \kappa T$ coincides with a prescribed law $\mu$ processing the first moment is based on solutions of backward stochastic differential equations of quadratic type. Theis new approach generalizes an approach by Bass [BAS] of the classical version of Skorokhod's embedding problem using martingale representation techniques.
Financial markets with asymmetric information: information drift, additional utility and entropy
(2009)
We review a general mathematical link between utility and information theory appearing in a simple financial market model with two kinds of small investors: insiders, whose extra information is stored in an enlargement of the less informed agents' filtration. The insider's expected logarithmic utility increment is described in terms of the information drift, i.e. the drift one has to eliminate in order to perceive the price dynamics as a martingale from his perspective. We describe the information drift in a very general setting by natural quantities expressing the conditional laws of the better informed view of the world. This on th other hand allows to identify the additional utility by entropy related quantities known from information theory.
We deal with backward stochastic differential equations with time delayed generators. In this new type of equations, a generator at time t can depend on the values of a solution in the past, weighted with a time delay function for instance of the moving average type. We prove existence and uniqueness of a solution for a sufficiently small time horizon or for a sufficiently small Lipschitz constant of a generator. We give examples of BSDE with time delayed generators that have multiple solutions or that have no solutions. We show for some special class of generators that existence and uniqueness may still hold for an arbitrary time horizon and for arbitrary Lipschitz constant. This class includes linear time delayed generators, which we study in more detail. We are concerned with different properties of a solution of a BSDE with time delayed generator, including the inheritance of boundedness from the terminal condition, the comparison principle, the existence of a measure solution and the BMO martingale property. We give examples in which they may fail.
In this paper we consider a class of BSDE with drivers of quadratic growth, on a stochastic basis generated by continuous local martingales. We first derive the Markov property of a forward-backward system (FBSDE) if the generating martingale is a strong Markov process. Then we establish the differentiability of a FBSDE with respect to the initial value of its forward component. This enables us to obtain the main result of this article which from the perspective of a utility optimization interpretation of the underlying control problem on a financial market takes the following form. The control process of the BSDE steers the system into a random liability depending on a market external uncertainty and this way describes the optimal derivative hedge of the liability by investment in a capital market the dynamics of which is described by the forward component. This delta hedge is described in a key formula in terms of a derivative functional of the solution process and the correlation structure of the internal uncertainty captured by the forward process and the external uncertainty responsible for the market incompleteness. The formula largely extends the scope of validity of the results obtained by several authors in the Brownian setting, designed to give a genuinely stochastic representation of the optimal delta hedge in the context of cross hedging insurance derivatives generalizing the derivative hedge in the Black-Scholes model. Of course, Malliavin’s calculus needed in the Brownian setting is not available in the general local martingale framework. We replace it by new tools based on stochastic calculus techniques.
We investigate solutions of backward stochastic differential equations (BSDE) with time delayed generators driven by Brownian motions and Poisson random measures that constitute the two components of a Lévy process. In this new type of equations, the generator can depend on the past values of a solution, by feeding them back into the dynamics with a time lag. For such time delayed BSDE, we prove existence and uniqueness of solutions provided we restrict on a sufficiently small time horizon or the generator possesses a sufficiently small Lipschitz constant. We study differentiability in the variational or Malliavin sense and derive equations that are satisfied by the Malliavin gradient processes. On the chosen stochastic basis this addresses smoothness both with respect to the continuous part of our Lévy process in terms of the classical Malliavin derivative for Hilbert space valued random variables, as well as with respect to the pure jump component for which it takes the form of an increment quotient operator related to the Picard difference operator.
Good-deal bounds have been introduced as a way to obtain valuation bounds
for derivative assets which are tighter than the arbitrage bounds. This is achieved by ruling out not only those prices that violate no-arbitrage restrictions but also
trading opportunities that are `too good'.
We study dynamic good-deal valuation bounds that are derived from bounds on optimal
expected growth rates. This leads naturally to restrictions on the set of pricing measure which are local in time, thereby inducing good dynamic properties for the good-deal valuation bounds.
We study good-deal bounds by duality arguments in a general semimartingale setting.
In a Wiener space setting where asset prices evolve as It\^o-processes,
good-deal bounds are then conveniently described by backward SDEs.
We show how the good-deal bounds arise as the value function for an
optimal control problem, where a dynamic coherent a priori risk measure is minimized by the choice of a suitable hedging strategy.
This demonstrates how the theory of no-good-deal valuations can be associated to an established concept of dynamic hedging in continuous time.
Zonotopes With Large 2D Cuts
(2009)
Durhuus and Jonsson (1995) introduced the class of “locally constructible” (LC) 3-spheres and showed that there are only exponentially-many combinatorial types of simplicial LC 3-spheres. Such upper bounds are crucial for the convergence of models for 3D quantum gravity.
We characterize the LC property for d-spheres ("the sphere minus a facet collapses to a (d-2)-complex") and for d-balls. In particular, we link it to the classical notions of collapsibility, shellability and constructibility, and obtain hierarchies of such properties for
simplicial balls and spheres. The main corollaries from this study are: (1.) Not all simplicial 3-spheres are locally constructible. (This solves a problem by Durhuus and Jonsson.)
(2.) There are only exponentially many shellable simplicial 3-spheres with given number of facets. (This answers a question by Kalai.)
(3.) All simplicial constructible 3-balls are collapsible. (This answers a question by Hachimori.)
(4.) Not every collapsible 3-ball collapses onto its boundary minus a facet. (This property appears in papers by Chillingworth and Lickorish.)
Modelling incompressible ideal fluids as a finite collection of
vortex filaments is important in physics (super-fluidity, models for the
onset of turbulence) as well as for numerical algorithms used in computer
graphics for the real time simulation of smoke. Here we introduce
a time-discrete evolution equation for arbitrary closed polygons in 3-
space that is a discretisation of the localised induction approximation of
filament motion. This discretisation shares with its continuum limit the
property that it is a completely integrable system. We apply this polygon
evolution to a significant improvement of the numerical algorithms
used in Computer Graphics.
We develop a generic method for constructing a weak static minimum
variance hedge for a wide range of derivatives that may involve optimal exercise features or contingent cash flow streams, to provide a hedge along a
sequence of future hedging dates. The optimal hedge is constructed using
a portfolio of preselected hedge instruments which could be derivatives
with different maturities. The hedge portfolio is weakly static in that
it is initiated at time zero, does not involve intermediate re-balancing,
but hedges may be gradually unwound over time. We study the static
hedging of a convertible bond to demonstrate the method by an example
that involves equity and credit risk. We investigate the robustness of the
hedge performance with respect to parameter and model risk by numerical
experiments.
We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported.
The optimization of fare systems in public transit allows to pursue
objectives such as the maximization of demand, revenue, profit, or
social welfare. We propose a non-linear optimization approach to fare
planning that is based on a detailed discrete choice model of user
behavior. The approach allows to analyze different fare structures,
optimization objectives, and operational scenarios involving, e.g.,
subsidies. We use the resulting models to compute optimized fare
systems for the city of Potsdam, Germany.
A biological regulatory network can be modeled as a discrete function f that contains all available information on network component interactions. From f we can derive a graph representation of the network structure as well as of the dynamics of the system. In this paper we introduce a method to identify modules of the network that allow us to construct the behavior of f from the dynamics of the modules. Here, it proves useful to distinguish between dynamical and structural modules, and to define network modules combining aspects of both.
As a key concept we establish the notion of symbolic steady state, which basically represents a set of states where the behavior of f is in some sense predictable, and which gives rise to suitable network modules.
We apply the method to a regulatory network involved in T helper cell differentiation.
The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.
In this paper we investigate the fare planning model for public
transport, which consists in designing a system of fares maximizing
the revenue. We discuss a discrete choice model in which passengers
choose between different travel alternatives to express the demand as
a function of fares. Furthermore, we give a computational example for
the city of Potsdam and discuss some theoretical aspects.
This paper introduces the line connectivity
problem, a generalization of the Steiner tree problem and a
special case of the line planning problem. We study its complexity and
give an IP formulation in terms of an exponential number of
constraints associated with "line cut constraints". These inequalities
can be separated in polynomial time. We also generalize the Steiner
partition inequalities.
Every day, millions of people are transported by buses, trains, and airplanes
in Germany. Public transit (PT) is of major importance for the quality of
life of individuals as well as the productivity of entire regions. Quality and
efficiency of PT systems depend on the political framework (state-run, market
oriented) and the suitability of the infrastructure (railway tracks, airport
locations), the existing level of service (timetable, flight schedule), the use
of adequate technologies (information, control, and booking systems), and
the best possible deployment of equipment and resources (energy, vehicles,
crews). The decision, planning, and optimization problems arising in this
context are often gigantic and “scream” for mathematical support because of
their complexity.
This article sketches the state and the relevance of mathematics in planning
and operating public transit, describes today’s challenges, and suggests a
number of innovative actions.
The current contribution of mathematics to public transit is — depending
on the transportation mode — of varying depth. Air traffic is already well
supported by mathematics. Bus traffic made significant advances in recent
years, while rail traffic still bears significant opportunities for improvements.
In all areas of public transit, the existing potentials are far from being exhausted.
For some PT problems, such as vehicle and crew scheduling in bus and
air traffic, excellent mathematical tools are not only available, but used in
many places. In other areas, such as rolling stock rostering in rail traffic,
the performance of the existing mathematical algorithms is not yet sufficient.
Some topics are essentially untouched from a mathematical point
of view; e.g., there are (except for air traffic) no network design or fare
planning models of practical relevance. PT infrastructure construction is
essentially devoid of mathematics, even though enormous capital investments
are made in this area. These problems lead to questions that can only be
tackled by engineers, economists, politicians, and mathematicians in a joint
effort.
Among other things, the authors propose to investigate two specific topics,
which can be addressed at short notice, are of fundamental importance not
only for the area of traffic planning, should lead to a significant improvement
in the collaboration of all involved parties, and, if successful, will be of real
value for companies and customers:
• discrete optimal control: real-time re-planning of traffic systems in case
of disruptions,
• model integration: service design in bus and rail traffic.
Work on these topics in interdisciplinary research projects could be funded
by the German ministry of research and education (BMBF), the German
ministry of economics (BMWi), or the German science foundation (DFG).