@misc{Steinbach2000, author = {Steinbach, Marc}, title = {Hierarchical Sparsity in Multistage Convex Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5837}, number = {00-15}, year = {2000}, abstract = {Interior point methods for multistage stochastic programs involve KKT systems with a characteristic global block structure induced by dynamic equations on the scenario tree. We generalize the recursive solution algorithm proposed in an earlier paper so that its linear complexity extends to a refined tree-sparse KKT structure. Then we analyze how the block operations can be specialized to take advantage of problem-specific sparse substructures. Savings of memory and operations for a financial engineering application are discussed in detail.}, language = {en} } @misc{MeyerSteinkeBrandletal.2000, author = {Meyer, Michael and Steinke, Thomas and Brandl, Maria and S{\"u}hnel, J{\"u}rgen}, title = {Density functional study of guanine and uracil quartets and of guanine quartet metal/ion complexes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5842}, number = {00-16}, year = {2000}, abstract = {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.}, language = {en} } @misc{OevermannKleinBergeretal.2000, author = {Oevermann, Michael and Klein, Rupert and Berger, Marsha and Goodman, Jonathan}, title = {A Projection Method for Two-Phase Incompressible Flow with Surface Tension and Sharp Interface Resolution}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5851}, number = {00-17}, year = {2000}, abstract = {We present a fully second order projection method for the simulation of two-phase incompressible flow with surface tension. The Navier-Stokes equations are solved with a projection method on a fixed Cartesian grid. The free interface between the two fluids is tracked with a level set approach. The conditions at the interface for the pressure, the pressure gradient, and the velocity are explicitly incorporated into the scheme leading to a sharp representation of the pressure discontinuity and the interfacial force. The scheme in the presented form does not introduce additional points in the standard finite difference stencils. Computational results are compared with analytic solutions for a static round bubble, damped surface waves, and Rayleigh-Taylor instabilities.}, language = {en} } @misc{Koster2000, author = {Koster, Arie M.C.A.}, title = {Re-Optimization of Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5863}, number = {00-18}, year = {2000}, abstract = {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.}, language = {en} } @misc{KrumkeNoltemeierWirth2000, author = {Krumke, Sven and Noltemeier, Hartmut and Wirth, Hans-Christoph}, title = {Graphentheoretische Konzepte und Algorithmen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5873}, number = {00-19}, year = {2000}, abstract = {Das vorliegende Skript bietet eine Einf{{\"u}}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{{\"a}}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{{\"o}}suung des ber{{\"u}}hmten K{{\"o}}nigsberger Br{{\"u}}ckenproblems aufgezeigt und der Satz von Euler bewiesen. Im vierten Kapitel wird gezeigt, wie man auf einfache Weise die Zusammenhangskomponenten eines Graphen bestimmen kann. Im Kapitel sechs wird dann sp{{\"a}}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {{\"u}}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{{\"a}}ume, k{{\"u}}rzeste Wege und maximale Fl{{\"u}}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.}, language = {de} } @misc{MeyerSchnurreReissbrodtetal.2000, author = {Meyer, Michael and Schnurre, R{\"u}diger and Reissbrodt, Rolf and Trowitzsch-Kienast, Wolfram}, title = {Computer-aided design of novel siderophores: Pyridinochelin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5887}, number = {00-20}, year = {2000}, abstract = {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.}, language = {en} } @misc{LangErdmann2000, author = {Lang, Jens and Erdmann, Bodo}, title = {Adaptive Linearly Implicit Methods for Heat and Mass Transfer Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5892}, number = {00-21}, year = {2000}, abstract = {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.}, language = {en} } @misc{HoeselKosterLeenseletal.2000, author = {Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Leensel, Robert L.M.J. van de and Savelsbergh, Martin W.P.}, title = {Polyhedral Results for the Edge Capacity Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5907}, number = {00-22}, year = {2000}, abstract = {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.}, language = {en} } @misc{KrumkeRambauWeider2000, author = {Krumke, Sven and Rambau, J{\"o}rg and Weider, Steffen}, title = {An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6217}, number = {00-53}, year = {2000}, abstract = {In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most \$C\$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.}, language = {en} } @misc{SchmidtFrieseZschiedrichetal.2000, author = {Schmidt, Frank and Friese, Tilmann and Zschiedrich, Lin and Deuflhard, Peter}, title = {Adaptive Multigrid Methods for the Vectorial Maxwell Eigenvalue Problem for Optical Waveguide Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6228}, number = {00-54}, year = {2000}, abstract = {This paper has been motivated by the need for a fast robust adaptive multigrid method to solve the vectorial Maxwell eigenvalue problem arising from the design of optical chips. Our nonlinear multigrid methods are based on a previous method for the scalar Helmholtz equation, which must be modified to cope with the null space of the Maxwell operator due to the divergence condition. We present two different approaches. First, we present a multigrid algorithm based on an edge element discretization of time-harmonic Maxwell's equations, including the divergence condition. Second, an explicit elimination of longitudinal magnetic components leads to a nodal discretization known to avoid discrete \emph{spurious modes} also and a vectorial eigenvalue problem, for which we present a multigrid solver. Numerical examples show that the edge element discretization clearly outperforms the nodal element approach.}, language = {en} } @misc{KrumkeRambau2000, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6238}, number = {00-55}, year = {2000}, abstract = {Wie soll man einen Aufzug steuern, wenn man keine Informationen {\"u}ber zuk{\"u}nftige Fahrauftr{\"a}ge besitzt? Soll man eine Bahncard kaufen, wenn die n{\"a}chsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollst{\"a}ndig gegeben sind. In vielen F{\"a}llen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungen{\"u}gend. Zahlreiche Problemstellungen in der Praxis sind in nat{\"u}rlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zuk{\"u}nftiger Ereignisse getroffen werden m{\"u}ssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten L{\"o}sung mit dem Wert einer optimalen Offline-L{\"o}sung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schw{\"a}chen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine F{\"u}lle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So m{\"u}ssen Entscheidungen unter strikten Zeitbeschr{\"a}nkungen gef{\"a}llt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgew{\"a}hlte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universit{\"a}t Berlin entstanden.}, language = {de} }