Refine
Year of publication
Language
- English (1103)
- German (10)
- Multiple languages (1)
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)
Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.
We investigate a nonstandard phase field
model of Cahn-Hilliard type. The model, which was introduced in
[16], describes two-species phase segregation and consists of a
system of two highly nonlinearly coupled PDEs. It has been studied
recently in
[5], [6] for the case of homogeneous Neumann
boundary conditions. In this paper, we investigate the case that the
boundary condition for one of the unknowns of the system is of third
kind and nonhomogeneous. For the resulting system, we show
well-posedness, and we study optimal boundary control
problems. Existence of optimal controls is shown, and the first-order
necessary optimality conditions are derived. Owing to the strong
nonlinear couplings in the PDE system, standard arguments of optimal
control theory do not apply directly, although the control constraints
and the cost functional will be of standard type.
This paper is concerned with a diffusion model of phase-field type, consisting
of a {parabolic} system of two partial differential equations{,} interpreted as balances
of microforces and microenergy{, for two unknowns: the problem's order parameter $\rho$}
and the chemical potential $\mu$; each equation includes a viscosity term -- respectively, $\varepsilon \,\partial_t\mu$ and $\delta\,\partial_t\rho$ -- with $\varepsilon$ and $\delta$ two positive parameters; the field equations are complemented by Neumann homogeneous boundary conditions and suitable initial conditions. In a recent paper \cite{CGPS3}, we proved that this problem is \wepo\ and investigated the \loti\ \bhv\ of its $(\varepsilon,\delta)-$solutions. Here we discuss the asymptotic limit of the system as $\eps$
tends to $0$. We prove convergence of
$(\varepsilon,\delta)-$solutions to the corresponding solutions for
the case $\eps =0$, whose long-time behavior we characterize; in the
proofs, we employ compactness and monotonicity arguments.
We study the expansion of the eigenfunctions of Schrödinger operators with smooth confinement potentials in Hermite functions; confinement potentials are potentials that become unbounded at infinity. The key result is that such eigenfunctions and all their derivatives decay more rapidly than any exponential function under some mild growth
conditions to the potential and its derivatives. Their expansion in Hermite functions converges therefore very fast, super-algebraically.
The mixed regularity of electronic wave functions in fractional order and weighted Sobolev spaces
(2012)
The paper continues the study of the regularity of electronic wave functions in Hilbert spaces of mixed derivatives. It is shown that the eigenfunctions of electronic Schr\"odinger operators and their
exponentially weighted counterparts possess, roughly speaking, square integrable mixed weak derivatives of fractional order $\vartheta$ for $\vartheta<3/4$. The bound $3/4$ is best possible and can neither be reached nor surpassed. Such results are important for the study
of sparse grid-like expansions of the wave functions and show that their asymptotic convergence rate measured in terms of the number of ansatz functions involved does not deteriorate with the number of electrons.
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.
Im Zuge der Übernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans für das Jahr 2010. Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen bestätigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verkürzung der Reisezeit um 1%, eine als um 6% verkürzt empfundene Reisezeit, 10% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5% möglich sind
The slow processes of metastable stochastic dynamical systems are difficult to access by direct numerical simulation due the sampling problem. Here, we suggest an approach for modeling the slow parts of Markov processes by approximating the dominant eigenfunctions and eigenvalues of the propagator. To this end, a variational principle is derived that is based on the maximization of a Raleigh coefficient. It is shown that this Raleigh coefficient can be estimated from statistical observables that can be obtained from short distributed simulations starting from different parts of state space. The approach forms a basis for the development of adaptive and efficient computational algorithms for simulating and analyzing metastable Markov processes while avoiding the sampling problem. Since any stochastic process with finite memory can be transformed into a Markov process, the approach is applicable to a wide range of processes relevant for modeling complex real-world phenomena.
Folding and conformational changes of macromolecules often require the generation of large amounts of simulation data that are difficult to ana- lyze. Markov state models (MSMs) address this challenge by providing a systematic way to decompose the state space of the molecular system into substates and to estimate a transition matrix containing the transi- tion probabilities between these substates. This transition matrix can be analyzed to reveal the metastable, i.e. long-living, states of the system, its slowest relaxation timescales and transition pathways and rates e.g. from unfolded to folded, or from dissociated to bound states. To reduce the technical burden of constructing such MSMs we provide the software framework EMMA (available at https://simtk.org/home/emma) to con- struct, validate and analyse such Markov State Models.
While seemingly straightforward in principle, the reliable estimation of rate constants is seldom easy in practice. Numerous issues, such as the complication of poor reaction coordinates, cause obvious approaches to yield unreliable estimates. When a reliable order parameter is available, the reactive flux theory of Chandler allows the rate constant to be extracted from the plateau region of an appropriate reactive flux correlation function. However, when applied to real data from single- molecule experiments or molecular dynamics simulations, the reactive flux correlation function requires the numerical differentiation of a noisy empirical correlation function, which can result in an unacceptably poor estimate of the rate and pathological dependence on the sampling interval. We present a modified version of this theory which does not require numerical derivatives, allowing rate constants to be robustly estimated from the time-correlation function directly. We illustrate the approach using single-molecule passive force spectroscopy measurements of an RNA hairpin.
Single-molecule force spectroscopy has proven to be a powerful tool for studying the kinetic be- havior of biomolecules. Through application of an external force, conformational states with small or transient populations can be stabilized, allowing them to be characterized and the statistics of in- dividual trajectories studied to provide insight into biomolecular folding and function. Because the observed quantity (force or extension) is not necessarily an ideal reaction coordinate, individual ob- servations cannot be uniquely associated with kinetically distinct conformations. While maximum- likelihood schemes such as hidden Markov models have solved this problem for other classes of single-molecule experiments by using temporal information to aid in the inference of a sequence of distinct conformational states, these methods do not give a clear picture of how precisely the model parameters are determined by the data due to instrument noise and finite-sample statistics, both sig- nificant problems in force spectroscopy. We solve this problem through a Bayesian extension that allows the experimental uncertainties to be directly quantified, and build in detailed balance to fur- ther reduce uncertainty through physical constraints. We illustrate the utility of this approach in characterizing the three-state kinetic behavior of an RNA hairpin in a stationary optical trap.
In multicriteria optimization, a compromise solution is a feasible solution whose
cost vector minimizes the distance to the ideal point w.r.t. a given norm. The coor-
dinates of the ideal point are given by the optimal values for the single optimization
problem for each criterion.
We show that the concept of compromise solutions ts nicely into the existing
notion of Pareto optimality: For a huge class of norms, every compromise solution
is Pareto optimal, and under certain conditions on the norm all Pareto optimal so-
lution are also a compromise solution, for an appropriate weighting of the criteria.
Furthermore, under similar conditions on the norm, the existence of an FPTAS for
compromise solutions guarantees the approximability of the Pareto set.
These general results are completed by applications to classical combinatorial
optimization problems. In particular, we study approximation algorithms for the
multicriteria shortest path problem and the multicriteria minimum spanning tree
problem. On the one hand, we derive approximation schemes for both problems, on
the other hand we show that for the latter problem simple approaches like local search
and greedy techniques do not guarantee good approximation factors.
We solve Skorokhod's embedding problem for Brownian motion with linear drift $(W_t+ \kappa t)_{t\geq 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$ possessing the first
moment is based on solutions of backward stochastic differential equations of quadratic
type. This new approach generalizes an approach by Bass [Bas] of the classical version of
Skorokhod's embedding problem using martingale representation techniques.
We consider a dynamical system described by the differential equation $\dot{Y}_t = -U^'(Y_t)$
with a unique stable point at the origin. We perturb the system by L\'evy noise of
intensity $\varepsilon$, to obtain the stochastic differential equation $dX^\varepsilon_t = -U^'(X^\varepsilon_{t-})dt + \varepsilon dL_t}.
The process $L$ is a symmetric L\'evy process whose jump measure $\nu$ has exponentially
light tails, $\nu([u, \infty))\sim exp(-u^\alpha), \alpha > 0, u \to\infty$. We study the first exit problem for
the trajectories of the solutions of the stochastic differential equation from the interval
$[-1, 1]$. In the small noise limit $\varepsilon\to 0$ we determine the law and the mean value of the
first exit time, to discover an intriguing phase transition at the critical index $\alpha = 1$.
In a strong constant electric field, a dielectric particle immersed in a weakly conducting fluid exhibits spontaneous rotations. This phenomenon is known under the name of the Quincke effect. In the original setup the particle was suspended on a silk thread and performed torsional oscillations of remarkably high amplitude. We derive the governing equations for this experiment, and ascertain
that onset of oscillations from the quiescent state corresponds to the supercritical Hopf bifurcation.
For the case of a soft thread, we characterize the regime of large-scale torsional relaxation oscillations:
explicit estimates are derived for their period and amplitude, effects of bifurcation delay are described. In a stronger electric field, these relaxation oscillations yield to small-scale erratic rotations of the pendulum.
Markov state models have become very popular for the description of conformation dynamics of molecules over
long timescales. The construction of such models requires a partitioning of the configuration space such that the discretization
can serve as an approximation of metastable conformations. Since the computational complexity for the construction of a
Markov state model increases quadratically with the number of sets, it is desirable to obtain as few sets as necessary. In this
paper we propose an algorithm for the adaptive refinement of an initial coarse partitioning. A spectral clustering method is
applied to the final partitioning to detect the metastable conformations. We apply this method to the conformation analysis of
a model tri-peptide molecule, where metastable beta- and gamma-turn conformations can be identified.
Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern.