Bibliothek

Beschreibung: The mathematical modeling of a special modular catalytic reactor kit leads to a system of partial differential equation in two space dimensions. As customary, this model contains unconfident physical parameters, which may be adapted to fit experimental data. To solve this nonlinear least squares problem we apply a damped Gauss-Newton method. A method of lines approach is used to evaluate the associated model equations. By an a priori spatial discretization a large DAE system is derived and integrated with an adaptive, linearly-implicit extrapolation method. For sensitivity evaluation we apply an internal numerical differentiation technique, which reuses linear algebra information from the model integration. In order not to interfere the control of the Gauss-Newton iteration these computations are done usually very accurately and, therefore, very costly. To overcome this difficulty, we discuss several accuracy adaptation strategies, e.g., a master-slave mode. Finally, we present some numerical experiments.

Beschreibung: Many real world problems can be mapped onto graphs and solved with well-established efficient algorithms studied in graph theory. One such problem is to find large sets of points satisfying some mutual relationship. This problem can be transformed to the problem of finding all cliques of an undirected graph by mapping each point onto a vertex of the graph and connecting any two vertices by an edge whose corresponding points satisfy our desired relationship. Clique detection has been widely studied and there exist efficient algorithms. In this paper we study a related problem, where all points have a set of binary attributes, each of which is either 0 or 1. This is only a small limitation, since all discrete properties can be mapped onto binary attributes. In our case, we want to find large sets of points not only satisfying some mutual relationship; but, in addition, all points of a set also need to have at least one common attribute with value 1. The problem we described can be mapped onto a set of induced subgraphs, where each subgraph represents a single attribute. For attribute $i$, its associated subgraph contains those vertices corresponding to the points with attribute $i$ set to 1. We introduce the notion of a maximal clique of a family, $\mathcal{G}$, of induced subgraphs of an undirected graph, and show that determining all maximal cliques of $\mathcal{G}$ solves our problem. Furthermore, we present an efficient algorithm to compute all maximal cliques of $\mathcal{G}$. The algorithm we propose is an extension of the widely used Bron-Kerbosch algorithm.

Beschreibung: We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols.

Beschreibung: We introduce FreeLence, a lossless single-rate connectivity compression algorithm for triangle surface meshes. Based upon a geometry-driven traversal scheme we present two novel and simple concepts: free-valence connectivity encoding and entropy coding based on geometric context. Together these techniques yield significantly smaller rates for connectivity compression than current state of the art approaches - valence-based algorithms and Angle- Analyzer, with an average of $36\%$ improvement over the former and an average of $18\%$ over the latter on benchmark 3D models, combined with the ability to well adapt to the regularity of meshes. We also prove that our algorithm exhibits a smaller worst case entropy for a class of "'well-behaved"' triangle meshes than valence-driven connectivity encoding approaches.

Beschreibung: 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.

Beschreibung: This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization.

Beschreibung: Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.

Beschreibung: In this paper we describe the semantic analysis of differential equations given in the ubiquitous semi-structured formats MathML and OpenMath. The analysis is integrated in a deployed Web indexing framework. Starting from basic classifications for differential equations the proposed system architecture is amenable to extensions for further reconstruction of mathematical content on the Web. The syntactic analysis of mathematical formulae given in the considered formats must overcome ambiguities that stem from the fact that formula particles may have different encodings, which are in principle completely arbitrary. However, it turns out that the syntactic analysis can be done straightforward given some natural heuristic assumptions.

Beschreibung: 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 non-linear features. Additionally, the PMC flow prevents boundary shrinkage at constrained and free boundary segments.

Beschreibung: A primal-dual interior point method for optimal control problems with PDE constraints is considered. The algorithm is directly applied to the infinite dimensional problem. Existence and convergence of the central path are analyzed. Numerical results from an inexact continuation method applied to a model problem are shown.

Beschreibung: In this paper, we present a novel approach to the congestion control and resource allocation problem of elastic and real-time traffic in telecommunication networks. With the concept of utility functions, where each source uses a utility function to evaluate the benefit from achieving a transmission rate, we interpret the resource allocation problem as a global optimization problem. The solution to this problem is characterized by a new fairness criterion, \e{utility proportional fairness}. We argue that it is an application level performance measure, i.e. the utility that should be shared fairly among users. As a result of our analysis, we obtain congestion control laws at links and sources that are globally stable and provide a utility proportional fair resource allocation in equilibrium. We show that a utility proportional fair resource allocation also ensures utility max-min fairness for all users sharing a single path in the network. As a special case of our framework, we incorporate utility max-min fairness for the entire network. To implement our approach, neither per-flow state at the routers nor explicit feedback beside ECN (Explicit Congestion Notification) from the routers to the end-systems is required.

Beschreibung: The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types.

Beschreibung: In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.

Beschreibung: Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions---or as relaxation in a branch and bound framework, addressing in particular the KKT systems arising in primal-dual interior methods. We propose a custom solution algorithm using sparse local projections, based on the KKT systems' structual properties induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a control space method and with the multifrontal solver MA27 are provided.

Beschreibung: The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe.

Beschreibung: Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results.

Beschreibung: In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.

Beschreibung: The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in (Bodlaender, Koster, Wolle, 2004). In experiments it was shown that this lower bound improves upon other treewidth lower bounds. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, block s of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy and another lower bound for treewidth. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described.

Beschreibung: The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex $v$ in an MCS-ordering is the number of neighbors of $v$ that are before $v$ in the ordering. The visited degree of an MCS-ordering $\psi$ of $G$ is the maximum visited degree over all vertices $v$ in $\psi$. The maximum visited degree over all MCS-orderings of graph $G$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph $G$ is at least its maximum visited degree. We show that the maximum visited degree is of size $O(\log n)$ for planar graphs, and give examples of planar graphs $G$ with maximum visited degree $k$ with $O(k!)$ vertices, for all $k\in \Bbb{N}$. Given a graph $G$, it is NP-complete to determine if its maximum visited degree is at least $k$, for any fixed $k\geq 7$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.

Beschreibung: A new and time efficient model to evaluate the free energy of solvation has been developed. The solvation free energy is separated into an electrostatic term, a hydrogen bond term, and a rest-term, combining both entropic and van der Waals effects. The electrostatic contribution is evaluated with a simplified boundary element method using the partial charges of the MMFF94 force field. The number of hydrogen bonds and the solvent excluded surface area over the surface atoms are used in a linear model to estimate the non-electrostatic contribution. This model is applied to a set of 213 small and mostly organic molecules, yielding an rmsd of 0.87kcal/mol and a correlation with experimental data of r=0.951. The model is applied as a supplementary component of the free energy of binding to estimate binding constants of protein ligand complexes. The intermolecular interaction energy is evaluated by using the MMFF94 force field.

Beschreibung: In this paper we describe a new algorithm for multiple semi-flexible superpositioning of drug-sized molecules. The algorithm identifies structural similarities of two or more molecules. When comparing a set of molecules on the basis of their three-dimensional structures, one is faced with two main problems. (1) Molecular structures are not fixed but flexible, i.e., a molecule adopts different forms. To address this problem, we consider a set of conformers per molecule. As conformers we use representatives of conformational ensembles, generated by the program ZIBMol. (2) The degree of similarity may vary considerably among the molecules. This problem is addressed by searching for similar substructures present in arbitrary subsets of the given set of molecules. The algorithm requires to preselect a reference molecule. All molecules are compared to this reference molecule. For this pairwise comparison we use a two-step approach. Clique detection on the correspondence graph of the molecular structures is used to generate start transformations, which are then iteratively improved to compute large common substructures. The results of the pairwise comparisons are efficiently merged using binary matching trees. All common substructures that were found, whether they are common to all or only a few molecules, are ranked according to different criteria, such as number of molecules containing the substructure, size of substructure, and geometric fit. For evaluating the geometric fit, we extend a known scoring function by introducing weights which allow to favor potential pharmacophore points. Despite considering the full atomic information for identifying multiple structural similarities, our algorithm is quite fast. Thus it is well suited as an interactive tool for the exploration of structural similarities of drug-sized molecules.

Beschreibung: Molecular dynamics simulations of possible ligands for proteins yield large amounts of data in the form of trajectories which are further processed in order to find metastable conformations. These conformations can then be used for docking between ligand and protein. Around this core computation procedure lots of other data have to be managed. It should also be possible for external users not involved in program development to perform computations. As a paradigm for other fields where a similar constitution of program usage and data processing is found we present a software architecture for data generation, access and management. Requirements for this system include: Ease of use, graphical user interface, persistent storage of data concerning molecules, users, programs, program parameters, metadata, and results. A mere storage in the file system would render a quick overview of data more or less impossible. On the other hand, storing large amounts of binary data in a database doesn't yield any advantage concerning speed of access. Therefore, a hybrid approach combining file system and database is appropriate. The system should be easily extensible by inserting new applications which can be controlled and whose results can be collected and stored. The software system described here consists of different components, the presentation layer (graphical user interface), the business logic, the persistence layer (relational database plus file system), and an interface to the compute cluster (batch system for parallel processing). We will discuss the alternatives and take a closer look at the components.

Beschreibung: We propose an approach for transforming the sampling of a molecular conformation distribution into an analytical model based on Hidden Markov Models. The model describes the sampled shape density as a mixture of multivariate unimodal densities. Thus, it delivers an interpretation of the sampled density as a set of typical shapes that appear with different probabilities and are characterized by their geometry, their variability and transition probabilities between the shapes. The gained model is used to identify atom groups of constant shape that are connected by metastable torsion angles. Based on this description an alignment for the original sampling is computed. As it takes into account the different shapes contained in the sampled set, this alignment allows to compute reasonable average shapes and meaningful shape density plots. Furthermore, it enables us to visualize typical conformations.

Beschreibung: We present publicly available data sets related to research on wireless networks. The scenarios contain a wide range of data and are detailed in all aspects. To our knowledge, this is the most realistic, comprehensive, and detailed \emph{public} data collection on mobile networking. We indicate example uses of this data collection in applications related tu UMTS.

Beschreibung: The \emph{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 multi-commodity flow 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.

Beschreibung: The aim of this paper is to give a survey of the known results concerning centrally symmetric polytopes, spheres, and manifolds. We further enumerate nearly neighborly centrally symmetric spheres and centrally symmetric products of spheres with dihedral or cyclic symmetry on few vertices, and we present an infinite series of vertex-transitive nearly neighborly centrally symmetric 3-spheres.

Beschreibung: We focus on the role of anisotropic elasticity in the simulation of the load distribution in a human mandible due to a lateral bite on the leftmost premolar. Based on experimental evidence, we adopt ``local''" orthotropy of the elastic properties of the bone tissue. Since the trajectories of anisotropic elasticity are not accessible from Computer Tomographic (CT) data, they will be reconstructed from (i) the organ's geometry and (ii) from coherent structures which can be recognized from the spatial distribution of the CT values. A sensitivity analysis comprising various 3D FE simulations reveals the relevance of elastic anisotropy for the load carrying behavior of a human mandible: Comparison of the load distributions in isotropic and anisotropic simulations indicates that anisotropy seems to ``spare''" the mandible from loading. Moreover, a maximum degree of anisotropy leads to kind of an load minimization of the mandible, expressed by a minimum of different norms of local strain, evaluated throughout the organ. Thus, we may suggest that anisotropy is not only relevant, but also in some sense ``optimal''.

Beschreibung: The paper extends affine conjugate Newton methods from convex to nonconvex minimization, with particular emphasis on PDE problems originating from compressible hyperelasticity. Based on well-known schemes from finite dimensional nonlinear optimization, three different algorithmic variants are worked out in a function space setting, which permits an adaptive multilevel finite element implementation. These algorithms are tested on two well-known 3D test problems and a real-life example from surgical operation planning.

Beschreibung: We present formulae for the corner points of the multidimensional Hausdorff and Dale Polytopes and show how these results can be used to improve linear programming models for computing e.\,g.\ moments of exit distribution of diffusion processes. Specifically, we compute the mean exit time of twodimensional Brownian motion from the unit square and the unit triangle, as well as higher moments of the exit time of time space Brownian motion from a triangle.

Beschreibung: Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover $\cal Q$ and a stable set cover $\cal S$ s.t.~every clique in $\cal Q$ intersects every stable set in $\cal S$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (Körner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). Körner and de Simone observed that $C_5$, $C_7$, and $\overline C_7$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every $C_5$, $C_7$, $\overline C_7$- free graph is normal (Normal Graph Conjecture, Körner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants.

Beschreibung: It is known that the suspension of a simplicial complex can be realized with only one additional point. Suitable iterations of this construction generate highly symmetric simplicial complexes with a various interesting combinatorial and topological properties. In particular, infinitely many non-PL spheres as well as contactible simplicial complexes with a vertex-transitive group of automorphisms cab be contained in this way.

Beschreibung: This paper presents an automatic approach for segmentation of the liver from computer tomography (CT) images based on a 3D statistical shape model. Segmentation of the liver is an important prerequisite in liver surgery planning. One of the major challenges in building a 3D shape model from a training set of segmented instances of an object is the determination of the correspondence between different surfaces. We propose to use a geometric approach that is based on minimizing the distortion of the correspondence mapping between two different surfaces. For the adaption of the shape model to the image data a profile model based on the grey value appearance of the liver and its surrounding tissues in contrast enhanced CT data was developed. The robustness of this method results from a previous nonlinear diffusion filtering of the image data. Special focus is turned to the quantitative evaluation of the segmentation process. Several different error measures are discussed and implemented in a study involving more than 30 livers.

Beschreibung: 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 {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost 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 newstrategy.

Beschreibung: This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.

Beschreibung: Structural mechanics simulation of bony organs is of general medical and biomechanical interest, because of the interdependence of the inner architecture of bone and its functional loading already stated by Wolff in 1892. This work is part of a detailed research project concerning the human mandible. By adaptive finite element techniques, stress/strain profiles occurring in the bony structure under biting were simulated. Estimates of the discretization errors, local grid refinement, and multilevel techniques guarantee the reliability and efficiency of the method. In general, our simulation requires a representation of the organ's geometry, an appropriate material description, and the load case due to teeth, muscle, or joint forces. In this paper, we want to focus on the influence of the masticatory system. Our goal is to capture the physiological situation as far as possible. By means of visualization techniques developed by the group, we are able to extract individual muscle fibres from computed tomography data. By a special algorithm, the fibres are expanded to fanlike (esp. for the musc. temporalis) coherent vector fields similar to the anatomical reality. The activity of the fibres can be adapted according to compartmentalisation of the muscles as measured by electromyological experiments. A refined sensitivity analysis proved remarkable impact of the presented approach on the simulation results.

Beschreibung: Operative planning in gas networks with prescribed binary decisions yields large scale nonlinear programs defined on graphs. We study the structure of the KKT systems arising in interior methods and present a customized direct solution algorithm. Computational results indicate that the algorithm is suitable for optimization in small and medium-sized gas networks.

Beschreibung: We investigate a special class of quadratic Hamiltonians on $so(4)$ and $so(3,1)$ and describe Hamiltonians that have additional polynomial integrals. One of the main results is a new integrable case with an integral of sixth degree.

Beschreibung: We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph $\Gneu$ by joining two nodes if the corresponding departures are in conflict. This graph $\Gneu$ has no odd antiholes and no $k$-holes for any integer $k\geq 5$. In particular, any finite, node induced subgraph of $\Gneu$ is perfect. For any integer $r\geq 2$ we construct minimal headways for $r$ train types so that the resulting graph $\Gneu$ has $2r$-antiholes and $4$-holes at the same time. Hence, $\Gneu$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in $G$.

Beschreibung: Unnecessarily conservative behavior of standard process control techniques can be avoided by stochastic programming models when the distribution of random disturbances is known. In an earlier study we have investigated such an approach for tank level constraints of a distillation process. Here we address techniques that have accelerated the numerical solution of the large and expensive stochastic programs by a factor of six, and then present a refined optimization model for the same application.

Beschreibung: We investigate the impact of hop-limited routing paths on the total cost of a telecommunication network. For different survivability settings (dedicated protection, link and path restoration), the optimal network cost without restrictions on the admissible path set is compared to the results obtained with two strategies to impose hop limits on routing paths. In a thorough computational study on optimal solutions for nine real-world based problem instances, we show that hop limits should be avoided if the technology allows it and network cost is a major planning issue. In this case, column generation should be employed to deal with all routing paths. If hop-limits are required, these should be defined for each demand individually and as large as possible.

Beschreibung: 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 short-term dispatch containing only some of the requests: unknown future requests will influence 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 model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.

Beschreibung: Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed $k$, it is polynomial time decidable if a given graph $G$ has contraction degeneracy at least $k$. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search (Lucena, 2003). Finally, heuristics for the treewidth are proposed and! evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al (2003).

Beschreibung: A primal interior point method for control constrained optimal control problems with PDE constraints is considered. Pointwise elimination of the control leads to a homotopy in the remaining state and dual variables, which is addressed by a short step pathfollowing method. The algorithm is applied to the continuous, infinite dimensional problem, where discretization is performed only in the innermost loop when solving linear equations. The a priori elimination of the least regular control permits to obtain the required accuracy with comparable coarse meshes. Convergence of the method and discretization errors are studied, and the method is illustrated at two numerical examples.

Beschreibung: In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur Förderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods.

Beschreibung: Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.

Beschreibung: 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.

Beschreibung: In [7,8,12] homogenization techniques are applied to derive an anisotropic variant of the bio-heat transfer equation as asymptotic result of boundary value problems providing a microscopic description for microvascular tissue. In view of a future application on treatment planning in hyperthermia, we investigate here the homogenization limit for a coupling model, which takes additionally into account the influence of convective heat transfer in medium size blood vessels. This leads to second order elliptic boundary value problems with nonlocal boundary conditions on parts of the boundary. Moreover, we present asymptotic estimates for first order correctors.

Beschreibung: 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.

Beschreibung: An edge of a perfect graph $G$ is critical if $G-e$ is imperfect. We would like to decide whether $G - e$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.

Beschreibung: Collection of abstracts of the first SIAM-EMS conference Applied Mathematics in our Changing World'' in Berlin, September 2-6, 2001.

Beschreibung: {\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.

Beschreibung: 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 {\sl 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 \textsf{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.

Beschreibung: Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.

Beschreibung: In this paper we present an algorithm that accelerates 3D texture-based volume rendering of large and sparse data sets. A hierarchical data structure (known as AMR tree) consisting of nested uniform grids is employed in order to efficiently encode regions of interest. The hierarchies resulting from this kind of space partitioning yield a good balance between the amount of volume to render and the number of texture bricks -- a prerequisite for fast rendering. Comparing our approach to an octree based algorithm we show that our algorithm increases rendering performance significantly for sparse data. A further advantage is that less parameter tuning is necessary.

Beschreibung: Mathematical optimization techniques are on their way to becoming a standard tool in chemical process engineering. While such approaches are usually based on deterministic models, uncertainties such as external disturbances play a significant role in many real-life applications. The present article gives an introduction to practical issues of process operation and to basic mathematical concepts required for the explicit treatment of uncertainties by stochastic optimization.

Beschreibung: Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the $n$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario.

Beschreibung: Standard model predictive control for real-time operation of industrial production processes may be inefficient in the presence of substantial uncertainties. To avoid overly conservative disturbance corrections while ensuring safe operation, random influences should be taken into account explicitly. We propose a multistage stochastic programming approach within the model predictive control framework and apply it to a distillation process with a feed tank buffering external sources. A preliminary comparison to a probabilistic constraints approach is given and first computational results for the distillation process are presented.

Beschreibung: Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.

Beschreibung: We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~$B\in\mathbb{N}$. The packing process is subject to the constraint that at any moment in time at most $q\in\mathbb{N}$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of $3q$ - 1 and a lower bound of $2q$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of $2q$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio $\Omega (q)$ and that randomization does not improve this lower bound even when the adversary is oblivious.

Beschreibung: In circuit switching networks call streams are characterized by their mean and peakedness (two-moment method). The $GI/M/C/0$ system is used to model a single link, where the $GI$-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a $GI/M/C/0$ system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d.\ holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used rigorously. The main result of this paper is an efficient algorithm for computing the moments of the freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.

Beschreibung: In this work we concentrate on developing methods which determine good lower bounds for set partitioning problems (SPP) in an appropriate amount of time. We found out that it makes sense to use the Lagrangian relaxation method for this task. The Lagrangian relaxed problem of SPP has a simple structure, which leads to algorithms and heuristics, whose total complexity per iteration depends linearly on the number of non-zeros of the problem matrix of SPP. In contrast, other methods like simplex methods or interior point methods have a complexity of higher order. Because the problem matrices of our tested instances are sparse, the linear dependence becomes an advantage for the algorithms and heuristics mentioned above. As a reference for the state-of-the-art we have applied the dual simplex method and the barrier function method, implemented in CPLEX. The methods, which we have developed and compared with those of CPLEX, are SBM, CAM, CCBM, and CBM. SBM is a subgradient bundle method derived from the basic subgradient method, which is a global convergent method for determining the maximum of concave functions. CAM is a coordinate ascent method, where the convex coordinate bundle method CCBM and the coordinate bundle method CBM are derivatives from CAM. We observed that the basic subgradient and the coordinate ascent method are improved if bundling techniques can be used. But the motivation for bundling differs for both approaches. In the former case bundling helps to approximate a minimum norm subgradient, which provides a steepest ascent direction, in order to speed up the performance. In the latter case bundling enables proceeding along directions, which are not restricted on the coordinate directions. By this the performance is accelerated. Among all used techniques stabilization is worth mentioning. Stabilization improves the performance especially at the beginning by avoiding too big steps during the proceeding. This leads to a more stabilized progression. Stabilization was successfully applied to SBM, CAM, CCBM, and CBM. As an overall result we conclude the following: \begin{enumerate} \item CPLEX computes the optimal objective values, whereas SBM and CBM has on average a gap of under $1.5\%$. \item In comparison to CPLEX baropt, SBM, CAM, and CBM the algorithm CCBM has a slow convergence because of the convex combination of ascent coordinate directions. An alternative is to relax the convex combination to a simple sum of the corresponding directions. This idea is realized in CBM. \item If we focus on the running time rather than on optimality then CBM is on average the fastest algorithm. \end{enumerate} Note that methods like SBM or CBM are applied on static SPP instances in order to determine a good lower bound. For solving SPP we need dynamical methods. Due to the complex topic of dynamical methods we will not discuss them, but a certain technique is worth mentioning. It is called column generation. We have indicated that this technique needs good Lagrangian multipliers of the corresponding SPP instances in order to generate further columns (in our case duties), which are added to the current SPP instance. Those multipliers are by-products of methods like our six considered methods. Due to the large number of such generation steps the running time depends on the computation time of these methods. Therefore, CBM fits more to this technique than CPLEX baropt or SBM. To sum it up it can be said that applications such as a duty scheduling can be described as set partitioning problems, whose lower bound can be solved by simplex, interior points, subgradient, or coordinate ascent methods. It turns out that the interior points method CPLEX baropt and the heuristic CBM have good performances. Furthermore, good Lagrangian multipliers, which are by-products of these methods, can be used by techniques like column generation. For this particular technique it also turns out that among our tested algorithms CBM is the most efficient one. In general we can state that real-world applications, which have to solve a large number of Lagrangian relaxed SPP instances can improve their performance by using CBM.

Beschreibung: The success of large-scale multi-national projects like the forthcoming analysis of the LHC particle collision data at CERN relies to a great extent on the ability to efficiently utilize computing a management software (Datagrid, Globus, etc.), while the effective integration of computing nodes has been largely neglected up to now. This is the focus of our work. We present a framework for a high-performance cluster that can be used as a reliable computing node in the Grid. We outline the cluster architecture, the management of distributed data and the seamless intergration of the cluster into the Grid environment.

Beschreibung: A new approach to the numerical solution of optimal control problems including control and state constraints is presented. Like hybrid methods, the approach aims at combining the advantages of direct and indirect methods. Unlike hybrid methods, however, our method is directly based on interior-point concepts in function space --- realized via an adaptive multilevel scheme applied to the complementarity formulation and numerical continuation along the central path. Existence of the central path and its continuation towards the solution point is analyzed in some theoretical detail. An adaptive stepsize control with respect to the duality gap parameter is worked out in the framework of affine invariant inexact Newton methods. Finally, the performance of a first version of our new type of algorithm is documented by the successful treatment of the well-known intricate windshear problem.

Beschreibung: By computed tomography data (CT), the individual geometry of the mandible is quite well reproduced, also the separation between cortical and trabecular bone. Using anatomical knowledge about the architecture and the functional potential of the masticatory muscles, realistic situations were approximated. The solution of the underlying partial differential equations describing linear elastic material behaviour is provided by an adaptive finite element method. Estimations of the discretization error, local grid refinement, and multilevel techniques guarantee the reliability and efficiency of the method.

Beschreibung: Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.

Beschreibung: This paper describes a new simulation tool for the prediction of aerosol formation and behavior in gas--liquid contact devices such as absorbers, scrubbers, quench coolers, and condensers as well as multistage gas cleaning processes, respectively. Aerosol formation can impact severely the separation efficiency of gas cleaning processes. Aerosol or fog formation can arise by spontaneous condensation or desublimation in supersaturated gas phases. The rigorous description of the mass and energy transfer between the gas phase, the liquid phase, and the growing aerosol droplets leads to a system of partial differential and algebraic equations. For the solution of these systems we have developed the plant simulation tool AerCoDe. This program bases upon the linearly--implicit Euler discretisation, which in combination with extrapolation permits an adaptive step size and order control. Typical simulation results of a multistage industrial flue gas scrubbing process are presented. It is shown, that experimental data can be confirmed if the number concentration of condensation nuclei as an input parameter is roughly known.

Beschreibung: This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.

Beschreibung: Mobile cellular communcication is a key technology in today's information age. Despite the continuing improvements in equipment design, interference is and will remain a limiting factor for the use of radio communication. This Ph. D. thesis investigates how to prevent interference to the largest possible extent when assigning the available frequencies to the base stations of a GSM cellular network. The topic is addressed from two directions: first, new algorithms are presented to compute "good" frequency assignments fast; second, a novel approach, based on semidef inite programming, is employed to provide lower bounds for the amount of unavoidable interference. The new methods proposed for automatic frequency planning are compared in terms of running times and effectiveness in computational experiments, where the planning instances are taken from practice. For most of the heuristics the running time behavior is adequate for inter active planning; at the same time, they provide reasonable assignments from a practical point of view (compared to the currently best known, but substantially slower planning methods). In fact, several of these methods are successfully applied by the German GSM network operator E-Plus. The currently best lower bounds on the amount of unavoidable (co-channel) interference are obtained from solving semidefinite programs These programs arise as nonpolyhedral relaxation of a minimum /c-parti tion problem on complete graphs. The success of this approach is made plausible by revealing structural relations between the feasible set of the semidefinite program and a polytope associated with an integer linear programming formulation of the minimum ^-partition problem. Comparable relations are not known to hold for any polynomial time solvable polyhedral relaxation of the minimum ^-partition problem. The appli cation described is one of the first of semidefinite programming for large industrial problems in combinatorial optimization.

Beschreibung: Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.

Beschreibung: This paper is a summary of the Round Table: ``The Impact of Mathematical Research on Industry and Vice Versa'' held at 3ecm in Barcelona on July 11, 2000. The round table started with contributions of the three panelists. Irene Fonseca, the panel chair, opened the discussion by stating six questions addressing the main issues of the round table topic. She presented the panel's answers to these questions, drawing on many examples from her own academic experience. In the following additional presentations, the other two panel members added further points of view based on their personal involvement with industry. The round table ended with a lively discussion with members from the audience. This written summary of the oral presentations follows the structure of the round table indicated above.

Beschreibung: This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.

Beschreibung: The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.

Beschreibung: Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data.

Beschreibung: By combining techniques of preparation, histology, confocal microscopy, data visualization and data processing, we have created and recently published a standard brain model for drosophila and honey bee brains. This report describes the algorithms and implementation of the corresponding software modules. At the same time it serves as a user's guide for scientist who want to reproduce the results for differerent species or mutants.

Beschreibung: Several classes of systems of evolution equations with one or two vector unknowns are considered. We investigate also systems with one vector and one scalar unknown. For these classes all equations having the simplest higher symmetry are listed.

Beschreibung: Two traffic streams $\Phi_1$, $\Phi_2$ are offered a link. The calls of $\Phi_i$ require exponential holding times with parameter $\mu$ and are accepted if less than $C_i$ trunks are occupied. Approximating the $\Phi_i$ by appropriate renewal processes meeting their first two moments, defined as the moments of the numbers of calls in virtual links of infinite capacity to which the traffic streams as freed traffics are virtually directed and where the calls get fresh exponential i.i.d.\ holding times with parameter $\mu$, stable recursive algorithms of complexity $O(\max(C_1,C_2))$ are derived for the first two defined as above moments of the individual overflow and freed carried traffics. The results offer a unified handling of both overflow and carried traffics in circuit switching networks with trunk reservation, providing a basis for new two-moment network dimensioning algorithms.

Beschreibung: We study the performance of QCD simulations with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering on $10^4$ and $12^4$ lattices. In order to compare tempered with standard simulations, covariance matrices between sub-ensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter $\kappa$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD.

Beschreibung: We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7$^{th}$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.

Beschreibung: Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.

Beschreibung: The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.

Beschreibung: {\begin{rawhtml} 〈a href="http://dx.doi.org/10.1007/s10479-007-0178-0"〉 Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0〈/a〉 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

Beschreibung: The pole condition is a general concept for the theoretical analysis and the numerical solution of a variety of wave propagation problems. It says that the Laplace transform of the physical solution in radial direction has no poles in the lower complex half-plane. In the present paper we show that for the Helmholtz equation with a radially symmetric potential the pole condition is equivalent to Sommerfeld's radiation condition. Moreover, a new representation formula based on the pole condition is derived and used to prove existence, uniqueness and asymptotic properties of solutions. This lays the foundations of a promising new algorithm to solve time-harmonic scattering problems numerically and provides a new approach for analyzing existing algorithms such as the Perfectly Matched Layer (PML) method and the Bayliss-Gunzburger-Turkel (BGT) algorithm.

Beschreibung: In this paper we study the PML method for Helmholtz-type scattering problems with radially symmetric potential. The PML method consists in surrounding the computational domain by a \textbf{P}erfectly \textbf{M}atched sponge \textbf{L}ayer. We prove that the approximate solution obtained by the PML method converges exponentially fast to the true solution in the computational domain as the thickness of the sponge layer tends to infinity. This is a generalization of results by Lassas and Somersalo based on boundary integral eqaution techniques. Here we use techniques based on the pole condition instead. This makes it possible to treat problems without an explicitly known fundamental solution.

Beschreibung: One important step in the fabrication of silicon-based integrated circuits is the creation of semiconducting areas by diffusion of dopant impurities into silicon. Complex models have been developed to investigate the redistribution of dopants and point defects. In general, numerical analysis of the resulting PDEs is the central tool to assess the modelling process. We present an adaptive approach which is able to judge the quality of the numerical approximation and which provides an automatic mesh improvement. Using linearly implicit methods in time and multilevel finite elements in space, we are able to integrate efficiently the arising reaction-drift-diffusion equations with high accuracy. Two different diffusion processes of practical interest are simulated.

Beschreibung: Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. By determining almost invariant sets of the associated Markov operator, the Monte Carlo sampling splits by a hierarchical annealing process into the essential regions of the state space; therefore UCMC aims at avoiding the typical metastable behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. The correct weighting factors for the various Markov chains are obtained via a coupling matrix, that connects the samplings from the different almost invariant sets. The underlying mathematical structure of this approach is given by a general examination of the uncoupling-coupling procedure. Furthermore, the overall algorithmic scheme of UCMC is applied to the $n$-pentane molecule, a well-known example from molecular dynamics.

Beschreibung: The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie presented a $9$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an $8$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of $\frac{4}{\ln 2}\approx 5.7708$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.

Beschreibung: In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~$3/2$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.

Beschreibung: Regional hyperthermia, a clinical cancer therapy, is the main topic of the Sonderforschungsbereich Hyperthermia: Scientific Methods and Clinical Applications'' at Berlin. In recent years, technological improvements towards a better concentration of heat to the desired target region have been achieved. These include a rather sophisticated integrated software environment for therapy planning and a new hyperthermia applicator. In a next step, a detailed closed loop monitoring of the actual treatment is to be developed. For this purpose the hyperthermia applicator is combined with an MRI system, which will allow to check the positioning of the patients and to measure individual blood perfusion as well as the 3D temperature distribution. The measurements will then be employed for an on-line control of the whole treatment. In this intended setting, new fast feedback control algorithms will come into play.

Beschreibung: In this paper for the $M(n)/M(n)/s+GI$ system, i.e.\ for a $s$-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general $M(n)/M/s+GI$ system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.

Beschreibung: Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph $G = (V,E)$ with two different edge-weight functions $c$ (modeling the construction or communication cost) and $d$ (modeling the service distance), and a bound~$B$ on the total service distance. The goal is to find a subtree~$T$ of $G$ with minimum $c$-cost $c(T)$ subject to the constraint that the sum of the service distances of all the remaining nodes $v \in V\setminus T$ to their closest neighbor in~$T$ does not exceed the specified budget~$B$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible

Beschreibung: Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.

Beschreibung: The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied on $10^4$ and $12^4$ lattices. As an indicator for decorrelation the topological charge is used.

Beschreibung: In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.

Beschreibung: The structures and interaction energies of guanine and uracil quartets have been determined by B3LYP hybrid density functional calculations. The total interaction energy $\Delta$E$^{T}$ of the $\it{C}$$_{4h}$-symmetric guanine quartet consisting of Hoogsteen type base pairs with two hydrogen bonds between two neighbour bases is -66.07 kcal/mol at the highest level. The uracil quartet with C6-H6...O4 interactions between the individual bases has only a small interaction energy of -20.92 kcal/mol and the interaction energy of -24.63 kcal/mol for the alternative structure with N3-H3...O4 hydrogen bonds is only slightly more negative. Cooperative effects contribute between 10 and 25 \% to all interaction energies. Complexes of metal ions with G-quartets can be classified into different structure types. The one with Ca$^{2+}$ in the central cavity adopts a $\it{C}$$_{4h}$-symmetric structure with coplanar bases, whereas the energies of the planar and non-planar Na$^{+}$ complexes are almost identical. The small ions Li$^{+}$, Be$^{2+}$, Cu$^{+}$ and Zn$^{2+}$ prefer a non-planar $\it{S}$$_{4}$-symmetric structure. The lack of co-planarity prevents probably a stacking of these base quartets. The central cavity is too small for K$^{+}$ ions and therefore this ion favours in contrast to all other investigated ions a $\it{C}$$_{4}$-symmetric complex, which is 4.73 kcal/mol more stable than the $\it{C}$$_{4h}$-symmetric one. The distance 1.665 {\AA} between K$^{+}$ and the root mean squares plane of the guanine bases is approximately half of the distance between two stacked G-quartets. The total interaction energy of alkaline earth ion complexes exceeds the ones with alkali ions. Within both groups of ions the interaction energy decreases with an increasing row position in the periodic table. The B3LYP and BLYP methods lead to similar structures and energies. Both methods are suitable for hydrogen-bonded biological systems. Compared with the before mentioned methods the HCTH functional leads to longer hydrogen bonds and different relative energies for two U-quartets. Finally we calculated also structures and relative energies with the MMFF94 forcefield. Contrary to all DFT methods, MMFF94 predicts bifurcated C-H...O contacts in the uracil quartet. In the G-quartet the MMFF94 hydrogen bond distances N2-H22...N7 are shorter than the DFT distances, whereas the N1-H1...O6 distances are longer.

Beschreibung: Pyridinochelin, a novel catecholate type siderophore, has been designed on the basis of the active analog enterobactin. Growth promotion tests indicate that this synthetic siderophore feeds various pathogenic bacteria effectively with iron even though it lacks one catecholate group compared to enterobactin. The superposition of the siderophore structures suggests that the structure of the skeleton connecting the catecholate groups might be an important factor for the iron transport.

Beschreibung: Dynamical process simulation of complex real-life problems often requires the use of modern algorithms, which automatically adapt both the time and space discretization in order to get error-controlled approximations of the solution. In this paper, a combination of linearly implicit time integrators of Rosenbrock type and adaptive multilevel finite elements based on a posteriori error estimates is presented. This approach has proven to work quite satisfactorily for a wide range of challenging practical problems. We show the performance of our adaptive method for two applications that arise in the study of flame balls and brine transport in porous media.

Beschreibung: The statistical behavior of deterministic and stochastic dynamical systems may be described using transfer operators, which generalize the notion of Frobenius Perron and Koopman operators. Since numerical techniques to analyze dynamical systems based on eigenvalues problems for the corresponding transfer operator have emerged, bounds on its essential spectral radius became of interest. This article shows that they are also of great theoretical interest. We give an analytical representation of the essential spectral radius in $L^{1}\!(\mu)$, which then is exploited to analyze the asymptotical properties of transfer operators by combining results from functional analysis, Markov operators and Markov chain theory. In particular, it is shown, that an essential spectral radius less than $1$, constrictiveness and some weak form'' of the so--called Doeblin condition are equivalent. Finally, we apply the results to study three main problem classes: deterministic systems, stochastically perturbed deterministic systems and stochastic systems.

Beschreibung: We focus on two new types of extremal graphs with respect to perfectness: critically and anticritically perfect graphs that lose their perfectness by simply deleting and adding an arbitrary edge, respectively. We present examples and study properties in order to compare critically and anticritically perfect graphs with minimally imperfect graphs, another type of extremal graphs with respect to perfectness. We discuss two attempts to characterize the classes of all critically and anticritically perfect graphs and give a brief overview on classes of perfect graphs which contain critically or anticritically perfect graphs.

Beschreibung: A path following algorithm for linear complementarity problems is presented. Given a point $z$ that approximates a point $z(\tau)$ on the central path with complementarity gap $\tau$, one determines a parameter $\theta\in (0,1)$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining $z((1-\theta)\tau)$. It is shown that $\theta$ is bounded below by a multiple of $n^{-1/2}$, where $n$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to $z((1-\theta)\tau)$. We show that the number of steps required to obtain an acceptable approximation of $z((1-\theta)\tau)$ is bounded above by a number independent of $n$. Therefore the algorithm has $O(\sqrt{n}L)$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased.

Beschreibung: The polynomial differential system modelling the behavior of a chemical reaction is given by graphtheoretic structures. The concepts from toric geometry are applied to study the steady states and stable steady states. Deformed toric varieties give some insight and enable graph theoretic interpretations. The importance of the circuits in the directed graph are emphazised. The counting of positive solutions of a sparse polynomial system by B.\ Sturmfels is generalized to the counting of stable positive solutions in case of a polynomial differential equation. The generalization is based on a method by sparse resultants to detect whether a system may have a Hopf bifurcation. Special examples from chemistry are used to illustrate the theoretical results.