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)
Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.
We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.
MIPLIB 2010
(2012)
This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
In this paper we formulate a boundary layer approximation
for an Allen--Cahn-type equation involving a small parameter $\eps$. Here, $\eps$ is related to the thickness of the boundary layer and we are interested in the limit when $\eps$ tends to $0$ in order to derive nontrivial boundary conditions. The evolution of the system is written as an energy balance formulation of the L^2-gradient flow with the corresponding Allen--Cahn energy functional. By transforming the boundary layer to a fixed domain we show the convergence of the solutions to a solution of a limit system. This is done by using concepts related to Gamma- and Mosco convergence. By considering different scalings in the boundary layer we obtain different boundary conditions.
A theorem on error estimates for smooth nonlinear programming
problems in Banach spaces is proved that can be used to derive
optimal error estimates for optimal control problems. This theorem is applied
to a class of optimal control problems for quasilinear elliptic equations.
The state equation is approximated by a finite element scheme, while different
discretization methods are used for the control functions. The distance of
locally optimal controls to their discrete approximations is estimated.
Our model of the bovine estrous cycle is a set of ordinary differential equations which generates hormone profiles of successive estrous cycles with several follicular waves per cycle. It describes the growth and decay of the follicles and the corpus luteum, as well as the change of the key substances over time. In this work we describe recent improvements of this model, including the introduction of new components, and elimination of time delays. We validate our model by showing that the simulations agree with observations from synchronization studies and with measured progesterone data after a single dose administration of synthetic prostaglandin F2alpha.
Modelling, parameter identification, and simulation play an important rôle in Systems Biology. In recent years, various software packages have been established for scientific use in both licencing types, open source as well as commercial. Many of these codes are based on inefficient and mathematically outdated algorithms. By introducing the package BioPARKIN recently developed at ZIB, we want to improve this situation significantly. The development of the software BioPARKIN involves long standing mathematical ideas that, however, have not yet entered the field of Systems Biology, as well as new ideas and tools that are particularly important for the analysis of the dynamics of biological networks. BioPARKIN originates from the package PARKIN, written by P.Deuflhard and U.Nowak, that has been applied successfully for parameter identification in physical chemistry for many years.
This study presents a differential equation model for the feedback mechanisms between
Gonadotropin-releasing Hormone (GnRH), Follicle-Stimulating Hormone (FSH), Luteinizing
Hormone (LH), development of follicles and corpus luteum, and the production of estradiol
(E2), progesterone (P4), inhibin A (IhA), and inhibin B (IhB) during the female menstrual
cycle. In contrast to other models, this model does not involve delay differential equations
and is based on deterministic modelling of the GnRH pulse pattern, which allows for faster
simulation times and efficient parameter identification. These steps were essential to tackle
the task of developing a mathematical model for the administration of GnRH analogues. The
focus of this paper is on model development for GnRH receptor binding and the integration of
a pharmacokinetic/pharmacodynamic model for the GnRH agonist Nafarelin and the GnRH
antagonist Cetrorelix into the menstrual cycle model. The final mathematical model describes
the hormone profiles (LH, FSH, P4, E2) throughout the menstrual cycle in 12 healthy women.
Moreover, it correctly predicts the changes in the cycle following single and multiple dose
administration of Nafarelin or Cetrorelix at different stages in the cycle.
We propose a new approach to competitive analysis by introducing the novel concept of online approximation schemes. Such scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our method can also be applied to many other problems and yields a completely new and interesting view on online algorithms.
Some optimal control problems for linear and nonlinear ordinary differential equations related to the optimal switching between
different magnetic fields are considered. The main aim is to move an electrical initial current by a controllable
voltage in shortest time to a desired terminal current and to hold it afterwards. Necessary optimality conditions are derived by
Pontryagin's principle and a Lagrange technique. In the case of a linear system, the principal structure of time-optimal controls is
discussed. The associated optimality systems are solved by a one-shot strategy
using a multigrid software package. Various numerical examples are discussed.
Global higher integrability of minimizers of variational problems with mixed boundary conditions
(2012)
We consider integral functionals with densities of p-growth, with respect to gradients, on a Lipschitz domain with mixed boundary conditions. The aim of this paper is to prove that, under uniform estimates within certain classes of p-growth and coercivity assumptions on the density, the minimizers are of higher integrability order, meaning that they belong to the space of first order Sobolev functions with an integrability of order $p+\epsilon$ for a uniform $\epsilon >0$. The results are applied to a model describing damage evolution in a nonlinear elastic body and to a model for shape memory alloys.
Global spatial regularity for elasticity models with cracks, contact and other nonsmooth constraints
(2012)
A global higher differentiability result in Besov
spaces is proved for the displacement fields of linear elastic models
with self contact.
Domains with cracks are studied, where nonpenetration
conditions/Signorini conditions are imposed on the crack faces.
It is shown that
in a neighborhood of crack tips (in 2D) or
crack fronts (3D) the displacement fields are
$B^{3/2}_{2,\infty}$ regular.
The proof relies on a difference
quotient argument for the directions tangential to the crack. In order
to obtain the regularity estimates also in the normal direction, an
argument due to
Ebmeyer/Frehse/Kassmann is modified.
The methods are then applied to further examples like
contact problems with nonsmooth rigid foundations, to a model with
Tresca friction and
to minimization problems with
nonsmooth energies and constraints as they occur for instance in the modeling of
shape memory alloys.
Based on Falk's approximation Theorem for variational
inequalities, convergence rates for FE-discretizations of contact
problems are derived relying on the proven regularity properties.
Several numerical examples illustrate the theoretical results.
Existence result for a class of generalized standard materials with thermomechanical coupling
(2012)
This paper deals with the study of a three-dimensional model of thermomechanical coupling for viscous solids exhibiting hysteresis effects. This model is written in accordance with the formalism of generalized standard materials. It is composed by the momentum equilibrium equation combined with the flow rule, which describes some stress-strain dependance, and the heat-transfer equation. An existence result for this thermodynamically consistent problem is obtained by using a fixed-point argument and some qualitative properties of the solutions are established.
In this paper we revisit models for the description of the evolution of crystalline films with anisotropic surface energies.
We prove equivalences of symmetry properties of anisotropic surface energy models commonly used in the literature.
Then we systematically develop a framework for the derivation of surface diffusion models for the self-assembly of quantum dots during Stranski-Krastanov
growth that include surface energies also with large anisotropy as well as the effect of wetting energy,
elastic energy and a randomly perturbed atomic deposition flux.
A linear stability analysis for the resulting sixth-order semilinear evolution equation for the thin film surface shows that that the new model allows
for large anisotropy and gives rise to the formation of anisotropic quantum dots. The nonlinear three-dimensional evolution is investigated via numerical solutions.
These suggest that increasing anisotropy stabilizes the faceted surfaces and may lead to a dramatic slow-down of the coarsening of the dots.
A typical phase field approach for describing phase separation and
coarsening phenomena in alloys is the Cahn-Hilliard model. This
model has been generalized to the so-called Cahn-Larche system
by combining it with elasticity to capture non-neglecting deformation
phenomena,
which occur during phase separation and coarsening processes in the material.
In order to account for damage effects,
we extend the existing framework of Cahn-Hilliard and Cahn-Larche
systems by incorporating an internal damage variable of local character. This
damage variable allows to model the effect that damage of a material point is influenced by its local surrounding.
The damage process is described by a unidirectional rate-dependent evolution inclusion
for the internal variable.
For the introduced Cahn-Larche systems
coupled with rate-dependent
damage processes, we
establish a suitable notion of weak solutions and prove existence of weak solutions.
An electronic model for solar cells including active interfaces and energy resolved defect densities
(2011)
We introduce an electronic model for solar cells taking into account
heterostructures with active
interfaces and energy resolved volume and interface trap densities.
The model consists of continuity equations for electrons and holes with thermionic
emission transfer conditions at the interface and of ODEs for the trap
densities with energy level and spatial position as parameters,
where the right hand sides contain generation-recombination as well as
ionization reactions. This system is coupled with a Poisson
equation for the electrostatic potential.
We show the thermodynamic correctness of the model and prove a priori estimates
for the solutions to the evolution system. Moreover, existence and uniqueness
of weak solutions of the problem are proven. For this purpose we solve a
regularized problem and verify bounds of the corresponding solution
not depending on the regularization level.
Dissipativity is an important property of individual systems
that guarantees a stable interconnected system.
However, due to errors in the modeling process weakly non-dissipative
models may be constructed.
In this paper we introduce a method to perturb a non-dissipative LTI system in order to enforce dissipativity using spectral perturbation results for
para-Hermitian pencils.
Compared to earlier algorithms the new method
is applicable to a wider class of problems,
it utilizes a simpler framework, and
employs a larger class of allowable perturbations
resulting in smaller perturbations. Moreover, system stability can be enforced as well.
Numerical examples are provided to show the effectiveness of the new approach.
Time-stepping procedures for the solution of evolution equations can be performed on parallel architecture by parallelizing the space computation at each time step. This, however, requires heavy communication between processors and becomes inefficient when many time-steps are to be computed and many processors are available. In such
cases parallelization in time is advantageous.
In this paper we present a method for parallelization in time of linear multistep discretizations of linear evolution problems; we consider a model parabolic and a model hyperbolic problem, and their, respectively, A(theta)-stable and A-stable linear multistep discretizations. The method consists of a discrete decoupling procedure, whereby N+1 decoupled Helmholtz problems with complex frequencies are obtained; N being the number of time steps computed in parallel. The usefulness of the method rests on our ability to solve these Helmholtz problems efficiently. We discuss the theory and give numerical examples for multigrid preconditioned iterative solvers of relevant
complex frequency Helmholtz problems. The parallel
approach can easily be combined with a time-stepping procedure, thereby obtaining a block time-stepping method where each block of steps is computed in parallel. In this way we are able to optimize the algorithm with respect to the number of processors available, the difficulty of solving the Helmholtz problems, and the possibility of both time and space adaptivity. Extensions to other linear evolution problems and to Runge-Kutta time discretization
are briefly mentioned.
Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.