TY - JOUR A1 - 藤澤, 克樹 A1 - 品野, 勇治 T1 - 最適化と計算の今後 ―大規模問題をどこまで解決できるのか?― JF - 機関誌「オペレーションズ・リサーチ」 N2 - 近年,大規模かつ複雑な最適化問題を高速に解く需要はさまざまな産業界や学術分野において急速に高まりつつある.これからの研究においては最先端理論 (Theory)+超大規模実データ (Practice)+最新計算技術(Computation) の三つを有機的に組み合わせることによって,実用に耐えうる解決策の提示と大規模最適化問題を扱う際の先例となることが求められている.本稿では最適化と計算に関する最新の傾向に触れるとともに,最適化の計算の今後についても考えていきたい. Y1 - 2014 UR - https://orsj.org/wp-content/corsj/or59-1/or59_1_11.pdf VL - 59 IS - 1 SP - 11 EP - 19 ER - TY - JOUR A1 - 品野, 勇治 T1 - 最適化研究における数値実験を中心とした アプリケーション駆動研究サイクル JF - 機関誌「オペレーションズ・リサーチ」 N2 - 最適化研究におけるアプリケーション駆動研究サイクルを紹介する.アプリケーション駆動研究サイクルは,学術機関での研究と企業における研究成果の利用とのつながりを良くする点では優れている.一方で,ソフトウェア開発・維持に多大な労力を要するため,日本の大学や研究機関における実施には困難さが伴う.ZIBにおいてアプリケーション駆動研究サイクルが,比較的うまく機能している背景を説明する.また,日本においてアプリケーション駆動研究サイクルを活性化するための第一歩として,論文投稿時に,論文中の数値実験に利用した全データ提出の義務化を提案したい. Y1 - 2014 UR - https://orsj.org/wp-content/corsj/or59-5/or59_5_247.pdf VL - 59 IS - 5 SP - 247 EP - 253 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - エネルギー供給システムの設計および運用の階層的関係を考慮した最適化(手法の提案) T1 - Optimization of Energy Supply Systems in Consideration of Hierarchical Relationship Between Design and Operation (Proposal of Optimization Method) JF - 第33回エネルギー・資源学会研究発表会講演論文要旨集・講演論文集 N2 - A mixed-integer linear programming (MILP) method utilizing the hierarchical relationship between design and op- eration variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified. Y1 - 2014 SP - 183 EP - 188 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - エネルギー供給システムの設計および運用階層的関係を考慮した最適化(K-ベスト解の探索) T1 - Optimization ofEnergy Supply Systems in Consideration of Hierarchical Relationship Between Design and Operation (Search for K-Best Solutions) JF - 日本機械学会第11回最適化シンポジウム2014講演論文集 N2 - A mixed-integer linear programming methodutilizing the hierarchical relationship between design and operation variables proposed ot solve the optimal design problem of energy supply systems efficiently is extended ot search K-best solutions: At the upper level, the optimal values ofdesign variables are searched with operation variables relaxed to continuous ones; At the lower level, the values of operation variables are optimized with the values of design variables given tentatively; The obtained solution is used to renew K-best incumbent solutions, and the upper bound for the value of the objective function for K-best solutions is replaced correspondingly. A practical case study is conducted, and the validity and effectiveness of the proposed method are clarified. Y1 - 2014 SP - 1 EP - 4 ER - TY - CHAP A1 - Braun, Gábor A1 - Fiorini, Samuel A1 - Pokutta, Sebastian T1 - Average case polyhedral complexity of the maximum stable set problem T2 - Proceedings of RANDOM Y1 - 2014 N1 - Additional Note: http://www.dagstuhl.de/dagpub/978-3-939897-74-3 N1 - URL of the PDF: http://www.dagstuhl.de/dagpub/978-3-939897-74-3 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Xie, Y. T1 - Info-Greedy Sequential Adaptive Compressed Sensing T2 - Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing Y1 - 2014 ER - TY - JOUR A1 - Schmaltz, Christian A1 - Pokutta, Sebastian A1 - Heidorn, Thomas A1 - Andrae, Silvio T1 - How to make regulators and shareholders happy under Basel III JF - Journal of Banking and Finance Y1 - 2014 UR - http://ssrn.com/abstract=2179490 N1 - Additional Note: 10.1016/j.jbankfin.2014.05.031 N1 - URL of the PDF: http://dx.doi.org/10.1016/j.jbankfin.2014.05.031 SP - 311 EP - 325 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set JF - Operations Research Letters Y1 - 2014 N1 - Additional Note: 10.1016/j.orl.2014.05.004 VL - 42 SP - 307 EP - 310 ER - TY - JOUR A1 - Dey, Santanu Sabush A1 - Pokutta, Sebastian T1 - Design and verify: a new scheme for generating cutting-planes JF - Mathematical Programming A Y1 - 2014 UR - http://www.optimization-online.org/DB_HTML/2011/04/3002.html N1 - Additional Note: DOI: 10.1007/978-3-642-20807-2_12 VL - 145 SP - 199 EP - 222 ER - TY - JOUR A1 - Drewes, S. A1 - Pokutta, Sebastian T1 - Computing discrete expected utility maximizing portfolios JF - Journal of Investing Y1 - 2014 UR - http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1662729 VL - 23 IS - 4 SP - 121 EP - 132 ER - TY - JOUR A1 - Drewes, S. A1 - Pokutta, Sebastian T1 - Symmetry-exploiting cuts for a class of mixed-0/1 second order cone programs JF - Discrete Optimization Y1 - 2014 UR - http://www.optimization-online.org/DB_HTML/2010/06/2652.html N1 - Additional Note: doi:10.1016/j.disopt.2014.04.002 VL - 13 SP - 23 EP - 35 ER - TY - JOUR A1 - Martin, Alexander A1 - Müller, J. A1 - Pokutta, Sebastian T1 - Strict linear prices in non-convex European day-ahead electricity markets JF - Optimization Methods and Software Y1 - 2014 UR - http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1660528 N1 - Additional Note: 10.1080/10556788.2013.823544 N1 - URL of the PDF: http://dx.doi.org/10.1080/10556788.2013.823544 VL - 29 IS - 1 SP - 189 EP - 221 ER - TY - CHAP A1 - Hiremath, Kirankumar A1 - Zschiedrich, Lin A1 - Burger, Sven A1 - Schmidt, Frank T1 - Finite elements based numerical solution of nonlocal hydrodynamic Drude model of nano-plasmonic scatterers T2 - 12th International Conference on Fiber Optics and Photonics Y1 - 2014 U6 - https://doi.org/10.1364/PHOTONICS.2014.M3D.4 SP - M3D.4 ER - TY - JOUR A1 - Banisch, Ralf A1 - Djurdjevac Conrad, Natasa T1 - Cycle-flow-based module detection in directed recurrence networks JF - EPL (Europhysics Letters) Y1 - 2014 U6 - https://doi.org/10.1209/0295-5075/108/68008 VL - 108 IS - 6 ER - TY - THES A1 - Frech, Ralf T1 - Das Konzept der Flussdichte und sein Bezug zur Bohmschen Mechanik Y1 - 2014 ER - TY - THES A1 - Tumescheit, Charlotte T1 - Using Birkhoff-von Neumann und Sinkhorn Algorithm to Find Dominating Cycles Y1 - 2014 ER - TY - CHAP A1 - Fackeldey, Konstantin A1 - Bujotzek, Alexander T1 - Local Quantum-Like Updates in Classical Molecular Simulation Realized Within an Uncoupling-Coupling Approach T2 - Progress in Industrial Mathematics at ECMI 2012 N2 - In this article a method to improve the precision of the classical molecular dynamics force field by solving an approximation problem with scattered quantum mechanical data is presented. This novel technique is based on two steps. In the first step a partition of unity scheme is used for partitioning the state space by meshfree basis functions. As a consequence the potential can be localized for each basis function. In a second step, for one state in each meshfree basis function, the precise QM-based charges are computed. These local QM-based charges are then used, to optimize the local potential function. The performance of this method is shown for the alanine tripeptide. Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-05365-3_42 VL - 19 SP - 309 EP - 313 ER - TY - CHAP A1 - Baum, Daniel A1 - Mahlow, Kristin A1 - Lamecker, Hans A1 - Zachow, Stefan A1 - Müller, Johannes A1 - Hege, Hans-Christian T1 - The Potential of Surface-based Geometric Morphometrics for Evolutionary Studies: An Example using Dwarf Snakes (Eirenis) T2 - Abstract in DigitalSpecimen 2014 N2 - Geometric morphometrics plays an important role in evolutionary studies. The state-of-the-art in this field are landmark-based methods. Since the landmarks usually need to be placed manually, only a limited number of landmarks are generally used to represent the shape of an anatomical structure. As a result, shape characteristics that cannot be properly represented by small sets of landmarks are disregarded. In this study, we present a method that is free of this limitation. The method takes into account the whole shape of an anatomical structure, which is represented as a surface, hence the term ‘surface-based morphometrics’. Correspondence between two surfaces is established by defining a partitioning of the surfaces into homologous surface patches. The first step for the generation of a surface partitioning is to place landmarks on the surface. Subsequently, the landmarks are connected by curves lying on the surface. The curves, called ‘surface paths’, might either follow specific anatomical features or they can be geodesics, that is, shortest paths on the surface. One important requirement, however, is that the resulting surface path networks are topologically equivalent across all surfaces. Once the surface path networks have been defined, the surfaces are decomposed into patches according to the path networks. This approach has several advantages. One of them is that we can discretize the surface by as many points as desired. Thus, even fine shape details can be resolved if this is of interest for the study. Since a point discretization is used, another advantage is that well-established analysis methods for landmark-based morphometrics can be utilized. Finally, the shapes can be easily morphed into one another, thereby greatly supporting the understanding of shape changes across all considered specimens. To show the potential of the described method for evolutionary studies of biological specimens, we applied the method to the para-basisphenoid complex of the snake genus Eirenis. By using this anatomical structure as example, we present all the steps that are necessary for surface-based morphometrics, including the segmentation of the para-basisphenoid complex from micro-CT data sets. We also show some first results using statistical analysis as well as classification methods based on the presented technique. Y1 - 2014 ER - TY - THES A1 - Günther, Matthias T1 - Implementation and verification of methods for the validation of knee joint kinematics KW - Biomechanics Y1 - 2014 ER - TY - CHAP A1 - Engelke, Wito A1 - Kuhn, Alexander A1 - Flatken, Markus A1 - Chen, Fang A1 - Hege, Hans-Christian A1 - Gerndt, Andreas A1 - Hotz, Ingrid T1 - Atmospheric Impact of Volcano Eruptions T2 - Proceedings IEEE SciVis 2014 N2 - The analysis of data that captures volcanic eruptions and their atmospheric aftermath plays an important role for domain experts to gain a deeper understanding of the volcanic eruption and their consequences for atmosphere, climate and air traffic. Thereby, one major challenge is to extract and combine the essential information, which is spread over various, mostly sparse data sources. This requires a careful integration of each data set with its strength and limitations. The sparse, but more reliable measurement data is mainly used to calibrate the more dense simulation data. This work combines a collection of visualization approaches into an exploitative framework. The goal is to support the domain experts to build a complete picture of the situation. But it is also important to understand the individual data sources, the wealth of their information and the quality of the simulation results. All presented methods are designed for direct interaction with the data from different perspectives rather than the sole generation of some final images. Y1 - 2014 ER - TY - GEN A1 - Seidel, Ronald A1 - Knötel, David A1 - Baum, Daniel A1 - Weaver, James C. A1 - Dean, Mason N. T1 - Material and structural characterization of mineralized elasmobranch cartilage – lessons in repeated tiling patterns in mechanically loaded 3D objects T2 - Poster, Tomography for Scientific Advancement symposium (ToScA), London, UK, September 1 - 3, 2014 N2 - Biological tissues achieve a wide range of properties and function, however with limited components. The organization of these constituent parts is a decisive factor in the impressive properties of biological materials, with tissues often exhibiting complex arrangements of hard and soft materials. The “tessellated” cartilage of the endoskeleton of sharks and rays, for example, is a natural composite of mineralized polygonal tiles (tesserae), collagen fiber bundles, and unmineralized cartilage, resulting in a material that is both flexible and strong, with optimal stiffness. The properties of the materials and the tiling geometry are vital to the growth and mechanics of the system, but had not been investigated due to the technical challenges involved. We use high-resolution materials characterization techniques (qBEI, µCT) to show that tesserae exhibit great variability in mineral density, supporting theories of accretive growth mechanisms. We present a developmental series of tesserae and outline the development of unique structural features that appear to function in load bearing and energy dissipation, with some structural features far exceeding cortical bone’s mineral content and tissue stiffness. To examine interactions among tesserae, we developed an advanced tiling-recognition-algorithm to semi-automatically detect and isolate individual tiles in microCT scans of tesseral mats. The method allows quantification of shape variation across a wide area, allowing localization of regions of high/low reinforcement or flexibility in the skeleton. The combination of our material characterization and visualization techniques allows the first quantitative 3d description of anatomy and material properties of tesserae and the organization of tesseral networks in elasmobranch mineralized cartilage, providing insight into form-function relationships of the repeating tiled pattern. We aim to combine detailed knowledge of intra-tesseral morphology and mineralization to model the relationships of tesseral shapes and skeletal surface curvature, to understand fundamental tiling laws important for complex, mechanically loaded 3d objects. Y1 - 2014 ER - TY - CHAP A1 - Gupta, Pooja A1 - Krause, Carola A1 - Rikeit, Paul A1 - Röblitz, Susanna A1 - Knaus, Petra A1 - Schütte, Christof T1 - Modeling of the BMP mediated co-regulation of the Smad and Non-Smad pathways in the context of cell density T2 - 10th International BMP conference, 2014, Berlin, Germany Y1 - 2014 ER - TY - GEN A1 - Titschack, Jürgen A1 - Baum, Daniel T1 - Advanced computed tomography analyses of cold-water coral mound cores: new insights into mound formation processes T2 - Poster, 19th International Sedimentological Congress, Geneva, Switzerland, 2014, August 18 - 22 Y1 - 2014 ER - TY - CHAP A1 - Grötschel, Martin A1 - Borndörfer, Ralf T1 - Mathematik im Verkehr T2 - HEUREKA '14. Vorträge der Tagung am 2./3. April 2014 in Stuttgart N2 - Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein. Y1 - 2014 SN - 978-3-86446-074-6 SP - 28 EP - 44 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-and-Propagate JF - Journal of Heuristics N2 - In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics. Y1 - 2014 U6 - https://doi.org/10.1007/s10732-014-9271-0 VL - 21 IS - 1 SP - 73 EP - 106 ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael ED - IEEE, T1 - Solving Hard MIPLIP2003 Problems with ParaSCIP on Supercomputers: An Update T2 - IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel & Distributed Processing Symposium Workshops Y1 - 2014 SN - 978-1-4799-4117-9 U6 - https://doi.org/10.1109/IPDPSW.2014.174 SP - 1552 EP - 1561 PB - IEEE Computer Society CY - Washington, DC, USA ER - TY - GEN A1 - Gutsche, Philipp A1 - Judd, Thomas A1 - Schmidt, Frank T1 - A convergence study of different Rigorous Coupled Wave Analysis (RCWA) approaches to time-harmonic electromagnetic scattering problems with applications to nanooptical structures T2 - Verhandlungen der Deutschen Physikalischen Gesellschaft (DPG-Frühjahrstagung Berlin 2014) N2 - Reliable numerical simulations of nano-optical structures are the key for design and pre-fabrication processes in diverse disciplines such as lithography in semiconductor industries, spectroscopy of biological molecules, optimization of quantum dot cavities for single-photon sources, and computation of atomic forces like the Casimir Effect. For these purposes a variety of different methods, e.g. FDTD, FEM and RCWA, are in use. On the one hand, FDTD and FEM are investigated intensively - both in mathematics and numerical experiments - and their approximations and convergence properties are well known. On the other hand, there is a lack of these insights in RCWA. In spite of this, RCWA is commonly used to simulate a wide range of systems. We review historical and modern contributions to convergence improvements with respect to RCWA from the early sugesstions to modern developments. We study the convergence rates of the open-source software S4 and analyze the algorithmic properties in detail. Furthermore, we compare RCWA and FEM simulations for different classes of problems including 1D-binary gratings and 2D-periodic photonic crystals. Y1 - 2014 ER - TY - THES A1 - Gutsche, Philipp T1 - Convergence Study of the Fourier Modal Method for Nano-optical Scattering Problems in Comparison with the Finite Element Method N2 - Nano-optical scattering problems play an important role in our modern, technologically driven society. Computers, smartphones and all kinds of electronic devices are manufactured by the semiconductor industry which relies on production using photomasks as well as optical process control. The digital world, e.g. the world wide web, is based on optical interconnects and so-called quantum computers based on optics are supposed to be next generation computers. Moreover, global economic progress demands new and sustainable energy resources and one option is to make use of the power stored in optical radiation from the sun. Additionally, understanding fundamental physics such as the optical properties of asymmetric, or chiral, structures could promote future innovations in engineering. In order to understand and manipulate these kinds of processes, physics provides a well established model: the so-called Maxwell’s equations. Stated by James Clerk Maxwell in 1862, this description of the interaction of light and matter still provides a profound basis for the analysis of electromagnetic phenomena. However, real world problems cannot be calculated using simple mathematics. Rather, computer simulations are needed to obtain solutions of the physical model. Finding suitable methods to solve these problems opens up a wide variety of possibilities. On the one hand, there are methods which require long computing times. On the other hand, some algorithms depend on high memory usage. That is why the field of numerics deals with the question which method is optimally suited for specific problems. The aim of this work is to investigate the applicability of the so-called Fourier Modal Method (FMM) to nano-optical scattering problems in general. Since simple analytical solutions are non-existent for most recent physical problems, we use the Finite Element Method (FEM) to double-check performance of the FMM. Mathematics provide reliable procedures to control the errors of numerics using the FEM. Yet up to now it has not been possible to rigorously classify the quality of the Fourier Modal Method’s results. It is not fully understood whether the process of investing more and more computing resources yields more accurate results. So, we have to ask ourselves: does the numerical method invariably converge? In spite of this uncertainty when using the FMM, it is a well established method dating back to the 1980s. This numerical method has recently been used to optimize performance of solar cells [19] as well as to improve the optical properties of so-called single-photon sources [41] which are essential for quantum cryptography. The latter is a promising candidate to increase digital security and revolutionise cryptography techniques. Furthermore, with the help of the Fourier Modal Method an important issue in optics has been partly resolved: angular filtering of light was made possible by using a mirror which becomes transparent at a certain viewing angle [77]. In addition, an improved numerical technique to design so-called Photonic Crystal waveguides based on the FMM was developed recently [15]. Photonic Crystals are used in the fields of optical bio-sensing and for the construction of novel semiconductor devices. Moreover, approaches to link the FMM and the FEM try to combine advantages of both methods to obtain fast and accurate results [81]. These ideas are closely linked to the well-known concept of Domain Decomposition within the FEM [88]. Here, one possibility to couple domains is to use the scattering matrix formalism as it is done in the FMM. In the scope of this convergence study, we state Maxwell’s equations, particularly for periodic geometries. We describe two physical phenomena of nano-optics, namely chirality and opto-electrical coupling, and define the errors of our simulations. Afterwards, the two investigated methods are analysed with respect to their general properties and a way to unify modelling physics when using both algorithms is presented. With the help of various numerical experiments, we explore convergence characteristics of the FMM and draw conclusions about the ability of this approach to provide accurate results and, consequently, its potential for research on technological innovations. KW - Nano-optics KW - Fourier Modal Method (FMM) KW - Rigorous Coupled Wave Analysis (RCWA) KW - Finite Element Method (FEM) Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56084 ER - TY - CHAP A1 - Gausemeier, Pia A1 - Seliger, Günther A1 - Schenker, Sebastian A1 - Borndörfer, Ralf T1 - Nachhaltige Technologiepfade für unterschiedliche Entwicklungsniveaus mithilfe mehrkriterieller Entscheidungsfindung T2 - Vorausschau und Technologieplanung Y1 - 2014 SN - 978-3-942647-53-3 VL - 334 SP - 65 EP - 94 ER - TY - CHAP A1 - Polthier, Konrad A1 - Bobenko, Alexander A1 - Hildebrandt, Klaus A1 - Kornhuber, Ralf A1 - Tycowicz, Christoph von A1 - Yserentant, Harry A1 - Ziegler, Günter M. T1 - Geometry processing T2 - MATHEON - Mathematics for Key Technologies Y1 - 2014 SN - 978-3-03719-137-8 U6 - https://doi.org/10.4171/137 VL - 1 SP - 341 EP - 355 PB - EMS Publishing House ER - TY - THES A1 - Tycowicz, Christoph von T1 - Concepts and Algorithms for the Deformation, Analysis, and Compression of Digital Shapes N2 - This thesis concerns model reduction techniques for the efficient numerical treatment of physical systems governing the deformation behavior of geometrically complex shapes. We present new strategies for the construction of simplified, low-dimensional models that capture the main features of the original complex system and are suitable for use in interactive computer graphics applications. To demonstrate the effectiveness of the new techniques we propose frameworks for real-time simulation and interactive deformation-based modeling of elastic solids and shells and compare them to alternative approaches. In addition, we investigate differential operators that are derived from the physical models and hence can serve as alternatives to the Laplace-Beltrami operator for applications in modal shape analysis. Furthermore, this thesis addresses the compression of digital shapes. In particular, we present a lossless compression scheme that is adapted to the special characteristics of adaptively refined, hierarchical meshes. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:188-fudissthesis000000096721-7 UR - http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000096721 ER - TY - JOUR A1 - Quitzsch, Nicole T1 - Vorbei die Zeiten von Gebrauchsanweisungen für Bibliotheksportale : Nutzerbeteiligung und Co-Design am Beispiel des neuen KOBV-Portals T1 - Gone are the times of operating instructions for library portals : User participation and co-design, exemplified by the new KOBV Portal JF - Bibliotheksdienst N2 - Bibliotheken stehen heute mehr denn je vor der Frage, wie sie ihre Dienste attraktiv gestalten können. Da liegt es nahe, Nutzerinnen und Nutzer aktiv in den Designprozess einzubinden. Die Neuentwicklung des KOBV-Portals (http://portal.kobv.de), einer regionalen Suche über die Bestände der Bibliotheken in Berlin und Brandenburg, geht konsequent den Weg des Co-Designs. Nutzerinnen und Nutzer werden als Entwicklungspartner verstanden. Als Projektpartner wurde das Institut für Bibliotheks- und Informationswissenschaft (IBI) der Humboldt-Universität zu Berlin gewonnen. N2 - More than ever, libraries today are faced with the question of how to make their services more attractive. Thus, it only seems logical to actively integrate users into the design process. The re-implementation of the KOBV Portal (http://portal.kobv.de), a regional search in the holdings of libraries in Berlin and Brandenburg, consistently follows the path of co-design. Users are regarded as development partners. The Berlin School of Library and Information Science acts as a project partner. Y1 - 2014 U6 - https://doi.org/10.1515/bd-2014-0097 VL - 48 IS - 10 SP - 795 EP - 806 ER - TY - GEN A1 - Weitzmann, John H. A1 - Klimpel, Paul ED - digiS - Servicestelle Digitalisierung Berlin, T1 - Rechtliche Rahmenbedingungen für Digitalisierungsprojekte von Gedächtnisinstitutionen N2 - Kulturerbe- und Gedächtnisinstitutionen sammeln, bewahren, dokumentieren und vermitteln Zeugnisse und Objekte des kulturellen Erbes. Die Digitalisierung eröffnet für alle diese Handlungsfelder neue Möglichkeiten, aber gleichzeitig auch neue Herausforderungen. Diese berühren sowohl organisatorische und technische als auch rechtliche Aspekte. Gerade letztere sind oft mit schwer kalkulierbaren Risiken für die Kultureinrichtungen behaftet. Die vorliegende Handreichung, die von iRights im Auftrag der Servicestelle Digitalisierung des Landes Berlin (digiS) erstellt wurde, soll eine Einführung für die Mitarbeiter der Kulturinstitutionen in die Themen Urheber- und Leistungsschutzrechte sein. Sie soll für rechtliche Risiken sensibilisieren und Handlungsspielräume aufzeigen. Die ursprüngliche Version 1.0 wurde im Nachgang des Workshops der Autoren am ZIB noch einmal überarbeitet. Neu hinzugekommen sind zwei Abschnitte zu den Themen Archivkopie und elektronischer Leseplatz. Y1 - 2014 U6 - https://doi.org/10.12752/2.0.002.1 ER - TY - GEN A1 - Müller, Anja A1 - Bartholmei, Stephan A1 - Fischer, Barbara A1 - Hahn, Helene T1 - Der GLAM-Hackathon "Coding da Vinci" N2 - Coding da Vinci, der erste deutsche Kultur-Hackathon, wurde gemeinsam von der Open Knowledge Foundation Deutschland, der Servicestelle Digitalisierung Berlin, Wikimedia Deutschland und der Deutschen Digitalen Bibliothek veranstaltet. Zwischen Ende April und Anfang Juli haben 150 Teilnehmer (Coder, Webdesigner, Kulturinteressierte u.a.) an Webseiten, mobilen Apps,Spielen, Hardwareprojekten und anderen Anwendungen offener Daten gearbeitet. Die Daten wurden von 16 Kultur-Einrichtungen bereitgestellt. Im Verlauf des Hackathons wurden daraus 17 funktionsfähige Prototypen entwickelt, öffentlich präsentiert und fünf davon auch prämiert.Doch was genau ist ein Hackathon? Wie kommen Kulturinstitutionen und Hacker zusammen? Wie gelangt eine Kulturinstitution zu offenen Daten? Welche Herausforderungen und Chancen bietet ein Hackathon für den Kulturbereich? Welche neue Qualität erwächst aus einem partizipativen Zugang zum digitalen Kulturerbe und der Möglichkeit mit Daten zu arbeiten? Was bleibt zu tun,um die Ergebnisse nachhaltig zu sichern? Diese Fragen sollen anhand der Ergebnisse von CdV diskutiert werden. Unter dem Motto „lessons learned“ wagen wir den Ausblick auf Coding da Vinci 2015. T3 - ZIB-Report - 15-23 KW - Hackathon KW - open data KW - GLAM KW - Kulturinstitutionen Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54566 SN - 1438-0064 ER - TY - JOUR A1 - Schulz, Christian A1 - Tycowicz, Christoph von A1 - Seidel, Hans-Peter A1 - Hildebrandt, Klaus T1 - Animating Deformable Objects Using Sparse Spacetime Constraints JF - ACM Transactions on Graphics N2 - We propose a scheme for animating deformable objects based on spacetime optimization. The main feature is that it robustly and quickly (within a few seconds) generates interesting motion from a sparse set of spacetime constraints. Providing only partial (as opposed to full) keyframes for positions and velocities is sufficient. The computed motion satisfies the constraints and the remaining degrees of freedom are determined by physical principles using elasticity and the spacetime constraints paradigm. Our modeling of the spacetime optimization problem combines dimensional reduction, modal coordinates, wiggly splines, and rotation strain warping. Controlling the warped motion requires the derivative of the warp map. We derive a representation of the derivative that can be efficiently and robustly evaluated. Our solver is based on a theorem that characterizes the solutions of the optimization problem and allows us to restrict the optimization to very low-dimensional search spaces. This treatment of the optimization problem avoids a time discretization and the resulting method can robustly deal with sparse input and wiggly motion. Y1 - 2014 U6 - https://doi.org/10.1145/2601097.2601156 VL - 33 IS - 4 SP - 109:1 EP - 109:10 ER - TY - THES A1 - Berthold, Timo T1 - Heuristic algorithms in global MINLP solvers N2 - In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are: - Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation, - a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP, - an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures, - RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution, - Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP, - Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs, - Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection. Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes. The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress. KW - mixed integer nonlinear programming KW - primal heuristic KW - mixed integer programming KW - branching rule KW - large neighborhood search KW - solver software Y1 - 2014 UR - http://www.zib.de/berthold/Berthold2014.pdf SN - 978-3-8439-1931-9 PB - Dr. Hut Verlag ER - TY - THES A1 - Knötel, David T1 - Segmentation of ray and shark tesserae N2 - Rays and sharks are cartilaginous fishes. Most of the cartilaginous skeleton is covered with calcified tiles to improve the stability of the skeleton. These tiles are called tesserae and enclose areas of uncalcified cartilage. Because of the special properties of the tesserae, biologists are interested to understand shape and structure of tessellated cartilage. This thesis presents a segmentation pipeline for the separation of tesserae on the cartilaginous skeleton of rays and sharks. The segmentation pipeline consists of an automatic initial segmentation step followed by manual error corrections by the user. The initial segmentation is based on the contour tree data structure that tracks the evolution of level sets in a dataset during iso-value changes. The presented segmentation concepts are not limited to the segmentation of tesserae but also viable for similar kinds of tiled structures. The input datasets are given as micro-CT scans. The contribution of this thesis is the development of a segmentation pipeline. The pipeline uses a newly developed fast version of the contour-tree-based segmentation algorithm that, after a preprocessing step, does not need to iterate over all voxels in the dataset. Visualizations and computations are done with the software system ZIBAmira. Used algorithms are either implemented as new ZIBAmira modules or they extend already existing ZIBAmira modules. KW - segmentation, contour tree, watershed, distance map Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54429 ER - TY - THES A1 - Hendel, Gregor T1 - Empirical Analysis of Solving Phases in Mixed Integer Programming N2 - Modern solving software for mixed-integer programming (MIP) incorporates numerous algorithmic components whose behavior is controlled by user parameter choices, and whose usefulness dramatically varies depending on the progress of the solving process. In this thesis, our aim is to construct a phase-based solver that dynamically reacts on phase transitions with an appropriate change of its component behavior. Therefore, we decompose the branch-and-bound solving process into three distinct phases: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps: First, we identify promising components for every solving phase individually and show that their combination is beneficial on a test bed of practical MIP instances. We then present and evaluate three heuristic criteria to make use of the phase-based solver in practice, where it is infeasible to distinguish between the last two phases before the termination of the solving process. KW - mixed-integer programming KW - branch-and-cut Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54270 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio T1 - Revisiting wireless network jamming by SIR-based considerations and Multiband Robust Optimization JF - Optimization Letters N2 - We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model based on the explicit use of signal-to-interference quantities. Moreover, to address the uncertain nature of the jamming problem and tackle the peculiar right-hand-side uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from multiband robust optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances. Y1 - 2014 U6 - https://doi.org/10.1007/s11590-014-0839-2 VL - 9 SP - 1495 EP - 1510 PB - Springer ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Di Lullo, Michela A1 - Felici, Giovanni A1 - Lacalandra, Fabrizio T1 - A Unified View on Tight Formulations for the Unit Commitment Problem with Optimal Transmission Switching T2 - Gaspard Monge Program for Optimization - Conference on Optimization & Practices in Industry : PGMO-COPI '14 N2 - The classical Unit Commitment Problem (UC) consists in determining the production of a set of thermal and hydro power generation units over a given time horizon, in order to meet a forecast energy demand and minimize a cost function. In the last years, in connection with the UC, increasingly attention has been given to active switching, namely the possibility of changing the topology of the transmission network by tripping some of the lines. Active switching has been indeed recognized as an important way to improve capacity and reliability of the network. Modifying the network topology is also very useful in modern electricity systems, where the penetration of on-programmable renewable energy sources is high and tends to be very concentrated in some zones of the network. As a consequence, the interest for automatic and optimized switching procedures is currently spreading. In this paper, we address the UC when complemented by active switching, thus leading to so-called Unit Commitment with Optimal Transmission Switching (UCOTS). We formulate the UCOTS as a mixed integer linear program, where we unify tight formulations recently proposed in literature for relevant subfamilies of constraints of the problem. Concerning the cost function, in our formulation we approximate the quadratic thermal cost objective function by a piecewise linear function based on perspective cuts and we propose a new simple and effective way to perturb it, with the aim of breaking symmetries induced by optimal transmission switching decision variables. Our original solution approach also exploits specialized branching priorities. Computational experiments on realistic UCOTS instances highlight that our new framework is able to find optimal and near-optimal solutions in reasonable amount of time by direct use of a state-of-the-art commercial MIP solver. Y1 - 2014 ER - TY - JOUR A1 - Moualeu-Ngangue, Dany Pascal A1 - Bowong, Samuel A1 - Kurths, Jürgen T1 - Parameter Estimation of a Tuberculosis Model in a Patchy Environment: Case of Cameroon JF - BIOMAT - Proceedings of the 12th International Symposium on Mathematical and Computational Biology, Toronto, 2013 Y1 - 2014 U6 - https://doi.org/10.1142/9789814602228_0021 ER - TY - JOUR A1 - Mücklich, Frank A1 - Webel, Johannes A1 - Aboulfadl, Hisham A1 - Lindow, Norbert A1 - Hege, Hans-Christian T1 - Correlative Tomography – Extraction of Reliable Information with Adequate Resolution from mm Scale Down to Sub-nm Scale JF - Microsc. Microanal. Y1 - 2014 U6 - https://doi.org/10.1017/S1431927614005911 VL - 20 IS - Suppl 3 SP - 838 EP - 839 ER - TY - JOUR A1 - Karbstein, Marika T1 - Ohne Umsteigen ans Ziel JF - OR News N2 - Die Anforderungen an das Liniennetz eines Verkehrsunternehmens sind vielfältig: kurze Fahrzeiten, viele Direktverbindungen und geringe Kosten. Mathematische Optimierungsmethoden können die Planung von Liniennetzen unterstützen und beste Kompromisse bzgl. aller Anforderungen berechnen. Y1 - 2014 VL - 52 SP - 12 EP - 14 ER - TY - JOUR A1 - Weber, Marcus A1 - Zoschke, Christian A1 - Sedighi, Amir A1 - Fleige, Emanuel A1 - Haag, Rainer A1 - Schäfer-Korting, Monika T1 - Free Energy Simulations of Drug loading for Core-Multishell Nanotransporters JF - J Nanomed Nanotechnol Y1 - 2014 U6 - https://doi.org/10.4172/2157-7439.1000234 VL - 5 IS - 5 SP - 234 ER - TY - THES A1 - Witzig, Jakob T1 - Reoptimization Techniques in MIP Solvers N2 - Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems. In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence. At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this thesis, 2013. Since most of the state-of-the-art MIP solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54067 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A Fast Hybrid Primal Heuristic for Multiband Robust Capacitated Network Design with Multiple Time Periods N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps. T3 - ZIB-Report - 14-40 KW - Capacitated Network Design KW - Multiperiod Design KW - Multiband Robust Optimization KW - Traffic Uncertainty KW - Metaheuristic KW - Ant Colony Optimization KW - Exact Large Neighborhood Search Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52862 SN - 1438-0064 ER - TY - BOOK ED - Ciccotti, Giovanni ED - Ferrario, Mauro ED - Schütte, Christof T1 - Molecular Dynamics Simulation T3 - Entropy (special issue) Y1 - 2014 PB - Multidisciplinary Digital Publishing Institute (MDPI) ER - TY - GEN A1 - Bertelmann, Roland A1 - Gebauer, Petra A1 - Hasler, Tim A1 - Kirchner, Ingo A1 - Peters-Kottig, Wolfgang A1 - Razum, Matthias A1 - Recker, Astrid A1 - Ulbricht, Damian A1 - van Gasselt, Stephan T1 - Einstieg ins Forschungsdatenmanagement in den Geowissenschaften N2 - Nur wenn eine Kultur der Nachnutzung und des freien Teilens von Wissen entsteht, werden Wissenschaftler auch die eigenen Forschungsdaten für die Langzeitverfügbarkeit aufbereiten und freigeben. Zu diesem Zweck ist diese Handreichung als Einstieg in das Thema Forschungsdatenmanagement entstanden. Y1 - 2014 U6 - https://doi.org/10.2312/lis.14.01 ER - TY - GEN A1 - Nielsen, Adam A1 - Weber, Marcus T1 - Computing the nearest reversible Markov chain N2 - Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem. T3 - ZIB-Report - 14-48 KW - Reversible Markov Chain KW - Convex Optimization KW - MSM Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53292 SN - 1438-0064 ER - TY - THES A1 - Humpola, Jesco T1 - Gas Network Optimization by MINLP N2 - One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. The challenging question is how to expand and operate the network in order to facilitate the transportation of specified gas quantities at minimum cost. This task can be formulated as a mathematical optimization problem that reflects to real-world instances of enormous size and complexity. The aim of this thesis is the development of novel theory and optimization algorithms which make it possible to solve these problems. Gas network topology optimization problems can be modeled as nonlinear mixed-integer programs (MINLPs). Such an MINLP gives rise to a so-called active transmission problem (ATP), a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. The key to solving the ATP as well as the overall gas network topology optimization problem and the main contribution of this thesis is a novel domain relaxation of the variable bounds and constraints in combination with a penalization in the objective function. In case the domain relaxation does not yield a primal feasible solution for the ATP we offer novel sufficient conditions for proving the infeasibility of the ATP. These conditions can be expressed in the form of an MILP, i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. If the gas network consists only of pipes and valves, the ATP turns into a passive transmission problem (PTP). Although its constraints are non-convex, its domain relaxation can be proven to be convex. Consequently, the feasibility of the PTP can be checked directly in an efficient way. Another advantage of the passive case is that the solution of the domain relaxation gives rise to a cutting plane for the overall topology optimization problem that expresses the infeasibility of the PTP. This cut is obtained by a Benders argument from the Lagrange function of the domain relaxation augmented by a specially tailored pc-regularization. These cuts provide tight lower bounds for the passive gas network topology optimization problem. The domain relaxation does not only provide certificates of infeasibility and cutting planes, it can also be used to construct feasible primal solutions. We make use of parametric sensitivity analysis in order to identify binary variables to be switched based on dual information. This approach allows for the first time to compute directly MINLP solutions for large-scale gas network topology optimization problems. All the research in this thesis has been realized within the collaborative research project "Forschungskooperation Netzoptimierung (ForNe)". The developed software is in use by the cooperation partner Open Grid Europe GmbH. Parts of this thesis have been published in book chapters, journal articles and technical reports. An overview of the topics and solution approaches within the research project is given by Martin et al. (2011) and Fügenschuh et al. (2013). Gas network operation approaches and solution methods are described in detail by Pfetsch et al. (2014) and with a special focus on topology optimization in Fügenschuh et al. (2011). The primal heuristic presented in this thesis is published by Humpola et al. (2014b). The method for pruning nodes of the branch-and-bound tree for an approximation of the original problem is described in Fügenschuh and Humpola (2013) and Humpola et al. (2014a). The Benders like inequality is introduced by Humpola and Fügenschuh (2013). N2 - Ein Viertel des europäischen Energiebedarfs wird durch Gas gedeckt, das durch ein europaweites Pipelinesystem verteilt wird. Aufgrund von Ausbaukosten von 1 Mio. Euro pro Kilometer ist der Netzausbau ein Milliardenunterfangen. Die größte Herausforderung besteht darin zu entscheiden, wie das Netzwerk kostengünstig ausgebaut und genutzt werden kann, um notwendige Gasmengen zu transportieren. Diese Aufgabe kann mit Hilfe eines mathematischen Optimierungsproblems formuliert werden, wobei anwendungsnahe Instanzen eine enorme Größe und Komplexität aufweisen. Ziel der vorliegenden Arbeit ist die Entwicklung neuer mathematischer Theorien und damit einhergehender Optimierungsalgorithmen, die es ermöglichen, derartige Probleme zu lösen. Die Optimierung der Topologie eines Gasnetzwerks kann mit Hilfe eines nichtlinearen gemischt-ganzzahligen Programms (MINLP) modelliert werden. Durch Fixierung aller ganzzahligen Variablen ergibt sich ein kontinuierliches Zulässigkeitsproblem, das als aktives Transmissionsproblem (ATP) bezeichnet wird. Die zentrale Methode um dieses ATP zu lösen, ist eine neuartige Relaxierung, welche Variablenschranken und einige Nebenbedingungen relaxiert und in der Zielfunktion bestraft. Diese Relaxierung bildet den Kern der in dieser Arbeit vorgestellten Theorie und ermöglicht so die effiziente Lösung der Topologieoptimierung eines Gasnetzwerkes. Für den Fall, dass die Relaxierung keine Primallösung für das ATP liefert, ist es uns gelungen, hinreichende Bedingungen für die Unzulässigkeit des ATP zu formulieren, die durch ein MILP dargestellt werden. Kurz gefasst kann die Unzulässigkeit eines nicht-konvexen NLP durch Lösung eines MILP bewiesen werden. Beide Methoden liefern effiziente Schranken in einem branch-and-bound Lösungsverfahren. Besteht ein Gasnetzwerk nur aus Rohren und Schiebern, dann wird das ATP als passives Transmissionsproblem (PTP) bezeichnet. Obwohl die Nebenbedingungen des PTP nicht konvex sind, konnten wir zeigen, dass seine Relaxierung konvex ist. Daher kann die Unzulässigkeit des PTP direkt auf effiziente Weise geprüft werden. Außerdem können mit Hilfe der Relaxierung in diesem speziellen Fall Schnittebenen für das Topologieoptimierungsproblem aufgestellt werden. Diese repräsentieren die Unzulässigkeit des PTP und folgen aus der Lagrange Funktion der Relaxierung zusammen mit einer speziellen Erweiterung, der sogenannten pc-Regularisierung. Abgesehen von den genannten Klassifizierungen kann die Relaxierung auch genutzt werden, um primale Lösungen zu konstruieren. Hier nutzen wir die parametrische Sensitivitätsanalyse, um mit Hilfe dualer Informationen Binärvariablen des ATP zu identifizieren, deren Werte angepasst werden müssen. Dieser Ansatz erlaubt es zum ersten Mal, direkt MINLP Lösungen für das Topologieoptimierungsproblem realer Gasnetzwerke zu berechnen. Die Resultate dieser Arbeit wurden im Rahmen des Forschungsprojekts "Forschungskooperation Netzoptimierung (ForNe)" erarbeitet. Die entwickelte Software wird vom Kooperationspartner Open Grid Europe GmbH aktiv genutzt. Teile dieser Arbeit sind in Buchkapiteln, Journalen und technischen Berichten publiziert. Eine Übersicht über die Themen und Lösungsansätze im ForNe-Projekt veröffentlichten Martin u. a. (2011) und Fügenschuh u. a. (2013). Für Lösungsmethoden für die operative Nutzung von Gasnetzwerken verweisen wir auf Pfetsch u. a. (2014). Ansätze für eine Topologieoptimierung wurden von Fügenschuh u. a. (2011) beschrieben. Die in dieser Arbeit präsentierte primale Heuristik ist publiziert von Humpola u. a. (2014b). Die genannte Methode, um Knoten innerhalb des branch-and-bound Baums abzuschneiden, wurde für eine Approximation des Topologieproblems von Fügenschuh und Humpola (2013) und Humpola u. a. (2014a) beschrieben. Ein Bericht über die Ungleichungen nach Benders ist in Humpola und Fügenschuh (2013) nachzulesen. T2 - Gas Netzwerk Optimierung mittels MINLP Y1 - 2014 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/5904 ER - TY - CHAP A1 - Wiesendanger, Samuel A1 - Bischoff, Thomas A1 - Jovanov, Vladislav A1 - Knipp, Dietmar A1 - Burger, Sven A1 - Lederer, Falk A1 - Rockstuhl, Carsten T1 - Numerical investigations on the effects of film growth modes on light trapping in silicon thin film solar cells T2 - Light, Energy and the Environment Y1 - 2014 U6 - https://doi.org/10.1364/PV.2014.PF4C.4 SP - PF4C.4 PB - OSA ER - TY - JOUR A1 - Schmid, Martina A1 - Manley, Phillip T1 - Nano- and microlenses as concepts for enhanced performance of solar cells JF - J. Photon. Energy Y1 - 2014 U6 - https://doi.org/10.1117/1.JPE.5.057003 VL - 5 SP - 057003 ER - TY - CHAP A1 - Wohlfeil, Benjamin A1 - Stamatiadis, Christos A1 - Jäger, Matthias A1 - Zimmermann, Lars A1 - Burger, Sven A1 - Petermann, Klaus T1 - Integrated optical fiber grating coupler on SOI for the excitation of several higher order fiber modes T2 - Optical Communication (ECOC), 2014 European Conference on Y1 - 2014 U6 - https://doi.org/10.1109/ECOC.2014.6963980 SP - 1 EP - 3 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Dittbrenner, Bastian A1 - Langenhan, Andreas A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integrierte Dienst- und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit JF - Straßenverkehrstechnik Y1 - 2014 IS - 9 SP - 583 EP - 591 ER - TY - JOUR A1 - Schäfer, Patrick T1 - Experiencing the Shotgun Distance for Time Series Analysis JF - Transactions on Machine Learning and Data Mining Y1 - 2014 SN - 1864-9734 VL - 7 IS - 1 SP - 3 EP - 25 ER - TY - GEN A1 - Wang, Han A1 - Schütte, Christof T1 - Building Markov State Models for Periodically Driven Non-Equilibrium Systems N2 - Recent years have seen an increased interest in non-equilibrium molecular dynamics (NEMD) simulations, especially for molecular systems with periodic forcing by external fields, e.g., in the context of studying effects of electromagnetic radiation on the human body tissue. Lately, an NEMD methods with local thermostating has been proposed that allows for studying non-equilibrium processes in a statistically reliable and thermodynamically consistent way. In this article, we demonstrate how to construct Markov State Models (MSMs) for such NEMD simulations. MSM building has been well-established for systems in equilibrium where MSMs with just a few (macro-)states allow for accurate reproduction of the essential kinetics of the molecular system under consideration. Non-equilibrium MSMs have been lacking so far. The article presents how to construct such MSMs and illustrates their validity and usefulness for the case of conformation dynamics of alanine dipeptide in an external electric field. T3 - ZIB-Report - 14-46 KW - Non-equilibrium KW - Markov states model KW - Alanine dipeptide KW - Electric field KW - Floquet theory Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53167 SN - 1438-0064 N1 - To appear in: Journal of Chemical Theory and Computation ER - TY - GEN A1 - Egger, Robert A1 - Dercksen, Vincent J. A1 - Udvary, Daniel A1 - Hege, Hans-Christian A1 - Oberlaender, Marcel T1 - Generation of dense statistical connectomes from sparse morphological data N2 - Sensory-evoked signal flow, at cellular and network levels, is primarily determined by the synaptic wiring of the underlying neuronal circuitry. Measurements of synaptic innervation, connection probabilities and sub-cellular organization of synaptic inputs are thus among the most active fields of research in contemporary neuroscience. Methods to measure these quantities range from electrophysiological recordings over reconstructions of dendrite-axon overlap at light-microscopic levels to dense circuit reconstructions of small volumes at electron-microscopic resolution. However, quantitative and complete measurements at subcellular resolution and mesoscopic scales to obtain all local and long-range synaptic in/outputs for any neuron within an entire brain region are beyond present methodological limits. Here, we present a novel concept, implemented within an interactive software environment called NeuroNet, which allows (i) integration of sparsely sampled (sub)cellular morphological data into an accurate anatomical reference frame of the brain region(s) of interest, (ii) up-scaling to generate an average dense model of the neuronal circuitry within the respective brain region(s) and (iii) statistical measurements of synaptic innervation between all neurons within the model. We illustrate our approach by generating a dense average model of the entire rat vibrissal cortex, providing the required anatomical data, and illustrate how to measure synaptic innervation statistically. Comparing our results with data from paired recordings in vitro and in vivo, as well as with reconstructions of synaptic contact sites at light- and electron-microscopic levels, we find that our in silico measurements are in line with previous results. T3 - ZIB-Report - 14-43 KW - 3D neural network KW - Dense connectome KW - Reconstruction Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53075 SN - 1438-0064 ER - TY - THES A1 - Dovica, Ivan T1 - Robust tail assignment N2 - The first part of this thesis is devoted to the general problem of stochastic shortest path problem. It is about searching for the shortest path in a graph in which arc lengths are uncertain and specified by continuous random variables. This problem is at the core of various applications, especially in robust transportation planning where paths correspond to aircraft, train, or bus rotations, crew duties or rosters, etc. We propose a novel solution method based on a discretisation of random variables which is applicable to any class of continuous random variables. We also give bounds on the approximation error of the discretised path lengths compared to the continuous path lengths. In addition, we provide theoretical results for the computational complexity of this method. In the second part we apply this method to a real world airline transportation problem: the so-called tail assignment problem. The goal of the tail assignment problem is to construct aircraft rotations, routes consisting of flight segments, for a set of individual aircraft in order to cover a set of flight segments (legs) while considering operational constraints of each individual aircraft as well as short- to long-term individual maintenance requirements. We state a stochastic programming formulation of this problem and we show how to solve it efficiently by using our method within a column generation framework. We show the gain of our stochastic approach in comparison to standard KPI in terms of less propagated delay and thus less operational costs without growth of computational complexity. A key point of our complex approach to robust optimisation problem is the fit of the underlying stochastic model with reality. We propose a delay propagation model that is realistic, not overfitted, and can therefore be used for forecasting purposes. We benchmark our results using extensive simulation. We show a significant decrease of arrival delays and thus monetary savings on average as well as in the majority of our disruption scenarios. We confirm these benefits in even more life-like benchmarks as simulation where recovery actions are taken and in scenarios which use historical delays directly instead of the stochastic model. KW - Flugzeug-Umlaufplanung KW - Spaltenerzeugung KW - Verspätungspropagation KW - column generation KW - delay propagation KW - stochastic shortest path problem KW - tail assignment Y1 - 2014 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/5664 ER - TY - CHAP A1 - Vierhaus, Ingmar A1 - Fügenschuh, Armin A1 - Gottwald, Robert Lion A1 - Grösser, Stefan T1 - Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models T2 - Proceedings of the 32nd International Conference of the System Dynamics Society N2 - We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems. Y1 - 2014 ER - TY - CHAP A1 - Gschrey, Manuel A1 - Seifried, Marc A1 - Krüger, Luzy A1 - Schmidt, Ronny A1 - Schulze, Jan-Hindrick A1 - Heindel, Tobias A1 - Burger, Sven A1 - Rodt, Sven A1 - Schmidt, Frank A1 - Strittmatter, Andre A1 - Reitzenstein, Stephan T1 - Advanced Quantum Light Sources: Modelling and Realization by Deterministic Nanofabrication Technologies T2 - Integrated Photonics Research, Silicon and Nanophotonics Y1 - 2014 U6 - https://doi.org/10.1364/IPRSN.2014.IW1A.3 VL - IPRSN SP - IW1A.3 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods JF - Applied Soft Computing N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps. Y1 - 2014 U6 - https://doi.org/10.1016/j.asoc.2014.10.016 VL - 26 SP - 497 EP - 507 ER - TY - GEN A1 - Karbstein, Marika T1 - Integrated Line Planning and Passenger Routing: Connectivity and Transfers N2 - The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem. T3 - ZIB-Report - 14-42 KW - line planning, transfers,Steiner connectivity problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52986 SN - 1438-0064 ER - TY - GEN A1 - Weber, Britta A1 - Tranfield, Erin M. A1 - Höög, Johanna L. A1 - Baum, Daniel A1 - Antony, Claude A1 - Hyman, Tony A1 - Verbavatz, Jean-Marc A1 - Prohaska, Steffen T1 - Automated stitching of microtubule centerlines across serial electron tomograms N2 - Tracing microtubule centerlines in serial section electron tomography requires microtubules to be stitched across sections, that is lines from different sections need to be aligned, endpoints need to be matched at section boundaries to establish a correspondence between neighboring sections, and corresponding lines need to be connected across multiple sections. We present computational methods for these tasks: 1) An initial alignment is computed using a distance compatibility graph. 2) A fine alignment is then computed with a probabilistic variant of the iterative closest points algorithm, which we extended to handle the orientation of lines by introducing a periodic random variable to the probabilistic formulation. 3) Endpoint correspondence is established by formulating a matching problem in terms of a Markov random field and computing the best matching with belief propagation. Belief propagation is not generally guaranteed to converge to a minimum. We show how convergence can be achieved, nonetheless, with minimal manual input. In addition to stitching microtubule centerlines, the correspondence is also applied to transform and merge the electron tomograms. We applied the proposed methods to samples from the mitotic spindle in C. elegans, the meiotic spindle in X. laevis, and sub-pellicular microtubule arrays in T. brucei. The methods were able to stitch microtubules across section boundaries in good agreement with experts’ opinions for the spindle samples. Results, however, were not satisfactory for the microtubule arrays. For certain experiments, such as an analysis of the spindle, the proposed methods can replace manual expert tracing and thus enable the analysis of microtubules over long distances with reasonable manual effort. T3 - ZIB-Report - 14-41 KW - electron tomography KW - microtubules KW - serial sectioning KW - image analysis KW - geometry reconstruction KW - image and geometry alignment KW - point correspondence Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52958 SN - 1438-0064 ER - TY - CHAP A1 - Hege, Hans-Christian T1 - Visual analysis of molecular dynamics data using geometric and topological methods T2 - Forum "Math for Industry" 2014 Y1 - 2014 VL - 57 SP - 45 EP - 46 PB - Institute of Mathematics for Industry, Kyushu University CY - Fukuoka, Japan ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem T2 - 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. Y1 - 2014 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2014.79 VL - 42 SP - 79 EP - 91 ER - TY - THES A1 - Sniegula, Erik T1 - Histogram-based Visualization and Analysis of Vector Fields using Stream Line Projection Plots N2 - Field lines in vector fields, e.g. stream lines, path lines, streak lines or time lines, play an important role in the analysis of vector fields. They improve the classification of flow features and its characteristics in particular. Because of the variety of structural information in field lines the effective processing, analysis and visualization play an important role. More effective techniques may contribute to an improved understanding of struc- tural phenomena in a wide range of applications of vector field visualization, such as gaseous flow (e.g. development of cars and aircrafts), design of machines (e.g. turbines), chemistry (e.g. simulation of molecules) and fluid flow in technical or medical applications (e.g. bloodvessel and ocean simulations). This master thesis focuses on the histogram-based visualization and analysis of vec- tor fields using field line projection plots, stream lines in particular. The goal of this work is to develop a hand full of selection criteria to answer specific applica- tion relevant questions about the characteristics and structures of their vector fields. Therefore we present a powerful analysis tool for vector fields or more precisely for their field lines. KW - Vector Field Visualization, Trajectory Visualization Y1 - 2014 ER - TY - JOUR A1 - Betker, Andreas A1 - Gamrath, Inken A1 - Kosiankowski, Dirk A1 - Lange, Christoph A1 - Lehmann, Heiko A1 - Pfeuffer, Frank A1 - Simon, Felix A1 - Werner, Axel T1 - Comprehensive Topology and Traffic Model of a Nationwide Telecommunication Network JF - Journal of Optical Communications and Networking N2 - As a basis for meaningful simulation and optimization efforts with regard to traffic engineering or energy consumption in telecommunication networks, suitable models are indispensable. This concerns not only realistic network topologies but also models for the geographical distribution and the temporal dynamics of traffic, as well as the assumptions on network components and technology. This paper derives such a model from the practice of a large national carrier. Applying the network and traffic model, we demonstrate its use by presenting various optimization cases related to energy-efficient telecommunication. Here, we focus on load adaptivity by employing sleep modes to the network hardware, where several constraints on the reconfigurability of the network over time are considered. Y1 - 2014 U6 - https://doi.org/10.1364/JOCN.6.001038 VL - 6 IS - 11 SP - 1038 EP - 1047 ER - TY - CHAP A1 - Reuther, Markus T1 - Local Search for the Resource Constrained Assignment Problem T2 - 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature. Y1 - 2014 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2014.62 VL - 42 SP - 62 EP - 78 ER - TY - GEN T1 - Annual Report 2013 T3 - Jahresbericht - 2013 KW - Jahresbericht Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52848 SN - 0934-5892 VL - 2013 ER - TY - JOUR A1 - Schöneich, Marc A1 - Stommel, Markus A1 - Kratz, Andrea A1 - Zobel, Valentin A1 - Scheuermann, Gerik A1 - Hotz, Ingrid A1 - Burgeth, Bernhard T1 - Optimization strategy for the design of ribbed plastic components JF - International Journal of Plastics Technology Y1 - 2014 IS - 10 SP - 160 EP - 175 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Harman, Radoslav T1 - Optimal Designs for Steady-state Kalman filters N2 - We consider a stationary discrete-time linear process that can be observed by a finite number of sensors. The experimental design for the observations consists of an allocation of available resources to these sensors. We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter, with respect to a standard optimality criterion, such as $D-$ or $A-$optimality. This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors. Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming. T3 - ZIB-Report - 14-39 KW - Optimal Design KW - Kalman Filter KW - Semidefinite programming Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52808 SN - 1438-0064 ER - TY - CHAP A1 - Kratz, Andrea A1 - Schöneich, Marc A1 - Zobel, Valentin A1 - Burgeth, Bernhard A1 - Scheuermann, Gerik A1 - Hotz, Ingrid A1 - Stommel, Markus T1 - Tensor Visualization Driven Mechanical Component Design T2 - Proc. IEEE Pacific Visualization Symposium 2014 Y1 - 2014 U6 - https://doi.org/10.1109/PacificVis.2014.51 SP - 145 EP - 152 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Mehrgardt, Julika A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - The Cycle Embedding Problem N2 - Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach. T3 - ZIB-Report - 14-37 KW - cycle embedding problem KW - railway vehicle rotation scheduling KW - sequential coarse-first-fine-second planning approach Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52788 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - The Price of Spite in Spot-checking games N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. T3 - ZIB-Report - 14-38 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52775 SN - 1438-0064 ER - TY - CHAP A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar ED - Lavi, Ron T1 - The Price of Spite in Spot-checking games T2 - 7th International Symposium on Algorithmic Game Theory (SAGT'2014) N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. Y1 - 2014 SN - 978-3-662-44802-1 U6 - https://doi.org/10.1007/978-3-662-44803-8 N1 - Brief Announcement included in Back Matter p. 293 following VL - 8768 SP - 293 PB - Springer ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung T1 - Fair ticket pricing in public transport as a constrained cost allocation game JF - Annals of Operations Research N2 - Ticket pricing in public transport usually takes a welfare maximization point of view. Such an approach, however, does not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and linear and integer programming. The ticket pricing problem is considered to be a constrained cost allocation game, which is a generalization of cost allocation games that allows to deal with constraints on output prices and on the formation of coalitions. An application to pricing railway tickets for the intercity network of the Netherlands is presented. The results demonstrate that the fairness of prices can be improved substantially in this way. A preliminary version of this paper appeared in the Proceedings of HPSC 2009 (Borndörfer and Hoang 2012). This journal article introduces better model and algorithms. Y1 - 2014 U6 - https://doi.org/10.1007/s10479-014-1698-z VL - 226 SP - 51 EP - 68 ER - TY - CHAP A1 - Kruber, Nico A1 - Schintke, Florian A1 - Berlin, Michael T1 - A Relational Database Schema on the Transactional Key-Value Store Scalaris T2 - Proceedings of 2nd Workshop on Scalable Cloud Data Management Y1 - 2014 U6 - https://doi.org/10.1109/BigData.2014.7004441 ER - TY - JOUR A1 - Froyland, Gary A1 - Maher, Stephen J. A1 - Wu, Cheng-Lung T1 - The recoverable robust tail assignment problem JF - Transportation Science N2 - Schedule disruptions are commonplace in the airline industry with many flight-delaying events occurring each day. Recently there has been a focus on introducing robustness into airline planning stages to reduce the effect of these disruptions. We propose a recoverable robustness technique as an alternative to robust optimisation to reduce the effect of disruptions and the cost of recovery. We formulate the recoverable robust tail assignment problem (RRTAP) as a stochastic program, solved using column generation in the master and subproblems of the Benders' decomposition. We implement a two-phase algorithm for the Benders' decomposition and identify pareto-optimal cuts. The RRTAP includes costs due to flight delays, cancellation, and passenger rerouting, and the recovery stage includes cancellation, delay, and swapping options. To highlight the benefits of simultaneously solving planning and recovery problems in the RRTAP we compare our tail assignment solution against current approaches from the literature. Using airline data we demonstrate that by developing a better tail assignment plan via the RRTAP framework, one can reduce recovery costs in the event of a disruption. Y1 - 2014 U6 - https://doi.org/10.1287/trsc.2013.0463 VL - 48 IS - 3 SP - 351 EP - 372 ER - TY - GEN A1 - Betker, Andreas A1 - Gamrath, Inken A1 - Kosiankowski, Dirk A1 - Lange, Christoph A1 - Lehmann, Heiko A1 - Pfeuffer, Frank A1 - Simon, Felix A1 - Werner, Axel T1 - Comprehensive Topology and Traffic Model of a Nation-wide Telecommunication Network N2 - As a basis for meaningful simulation and optimization efforts with regard to traffic engineering or energy consumption in telecommunication networks, suitable models are indispensable. This concerns not only realistic network topologies, but also models for the geographical distribution and the temporal dynamics of traffic, as well as the assumptions on network components and technology. This paper derives such a model from the practice of a large national carrier. Applying the network and traffic model, we demonstrate its use by presenting various optimization cases related to energy-efficient telecommunication. Here, we focus on load-adaptivity by employing sleep modes to the network hardware, where several constraints on the reconfigurability of the network over time are considered. T3 - ZIB-Report - 14-36 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52670 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. T3 - ZIB-Report - 14-26 KW - column generation KW - coarse-to-fine approach KW - multi-layer approach KW - rolling stock rotation problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51009 SN - 1438-0064 ER - TY - JOUR A1 - Weber, Britta A1 - Tranfield, Erin M. A1 - Höög, Johanna L. A1 - Baum, Daniel A1 - Antony, Claude A1 - Hyman, Tony A1 - Verbavatz, Jean-Marc A1 - Prohaska, Steffen T1 - Automated stitching of microtubule centerlines across serial electron tomograms JF - PLoS ONE Y1 - 2014 U6 - https://doi.org/10.1371/journal.pone.0113222 SP - e113222 ER - TY - JOUR A1 - Shchukin, Vitaly A1 - Ledentsov, Jr., Nikolay A1 - Kropp, Jörg-R. A1 - Steinle, Gunther A1 - Ledentsov, Jr., Nikolay A1 - Burger, Sven A1 - Schmidt, Frank T1 - Single-Mode Vertical Cavity Surface Emitting Laser via Oxide-Aperture-Engineering of Leakage of High Order Transverse Modes JF - IEEE J. Quant. Electron. Y1 - 2014 U6 - https://doi.org/10.1109/JQE.2014.2364544 VL - 50 IS - 12 SP - 990 EP - 995 ER - TY - THES A1 - von Hafe Pérez Ferreira da Silva, Maria Isabel T1 - Computational Left-Ventricle Reconstruction from MRI Data for Patient-specific Cardiac Simulations Y1 - 2014 ER - TY - THES A1 - Kulagina, Svetlana T1 - Distributed Multi-Stage Time Series Similarity Search Y1 - 2014 ER - TY - THES A1 - Fajerski, Jan T1 - Map Reduce on Distributed Hash Tables Y1 - 2014 ER - TY - GEN A1 - Sarich, Marco A1 - Schütte, Christof ED - Bowman, Gregory R. ED - Pande, Vijay S. ED - Noé, Frank T1 - Markov Model Theory T2 - An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation N2 - This section reviews the relation between the continuous dynamics of a molecular system in thermal equilibrium and the kinetics given by a Markov State Model (MSM). We will introduce the dynamical propagator, an error-less, alternative description of the continuous dynamics, and show how MSMs result from its discretization. This allows for an precise understanding of the approximation quality of MSMs in comparison to the continuous dynamics. The results on the approximation quality are key for the design of good MSMs. While this section is important for understanding the theory of discretization and related systematic errors, practitioners wishing only to learn how to construct MSMs may skip directly to the discussion of Markov model estimation. Y1 - 2014 U6 - https://doi.org/10.1007/978-94-007-7606-7 VL - 797 SP - 23 EP - 44 PB - Springer ER - TY - GEN A1 - Deuflhard, Peter A1 - Weber, Marcus ED - Deuflhard, Peter ED - Grötschel, Martin ED - Hömberg, Dietmar ED - Horst, Ulrich ED - Kramer, Jürg ED - Mehrmann, Volker ED - Polthier, Konrad ED - Schmidt, Frank ED - Skutella, Martin ED - Sprekels, Jürgen T1 - Mathematics without pain T2 - MATHEON-Mathematics for Key Technologies Y1 - 2014 U6 - https://doi.org/10.4171/137 VL - 1 SP - 26 EP - 28 PB - European Mathematical Society ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A massively parallel STP solver N2 - In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research. T3 - ZIB-Report - 14-35 KW - Steiner Tree Problem KW - Mixed-Integer Programming KW - Branch-and-Cut KW - DIMACS Challenge Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52293 SN - 1438-0064 ER - TY - CHAP A1 - Bonneau, Georges-Pierre A1 - Hege, Hans-Christian A1 - Johnson, Chris R. A1 - Oliveira, Manuel M. A1 - Potter, Kristin A1 - Rheingans, Penny A1 - Schultz, Thomas T1 - Overview and State-of-the-Art of Uncertainty Visualization T2 - Scientific Visualization - Uncertainty, Multifield, Biomedical, and Scalable Visualization N2 - The goal of visualization is to effectively and accurately communicate data. Visualization research has often overlooked the errors and uncertainty which accompany the scientific process and describe key characteristics used to fully understand the data. The lack of these representations can be attributed, in part, to the inherent difficulty in defining, characterizing, and controlling this uncertainty, and in part, to the difficulty in including additional visual metaphors in a well designed, potent display. However, the exclusion of this information cripples the use of visualization as a decision making tool due to the fact that the display is no longer a true representation of the data. This systematic omission of uncertainty commands fundamental research within the visualization community to address, integrate, and expect uncertainty information. In this chapter, we outline sources and models of uncertainty, give an overview of the state-of-the-art, provide general guidelines, outline small exemplary applications, and finally, discuss open problems in uncertainty visualization. Y1 - 2014 SN - 978-1-4471-6496-8 U6 - https://doi.org/10.1007/978-1-4471-6497-5_1 SP - 3 EP - 27 PB - Springer ER - TY - JOUR A1 - Winkelmann, Stefanie A1 - Schütte, Christof A1 - von Kleist, Max T1 - Markov Control Processes with Rare State Observation: Theory and Application to Treatment Scheduling in HIV-1 JF - Communications in Mathematical Sciences N2 - Markov Decision Processes (MDP) or Partially Observable MDPs (POMDP) are used for modelling situations in which the evolution of a process is partly random and partly controllable. These MDP theories allow for computing the optimal control policy for processes that can continuously or frequently be observed, even if only partially. However, they cannot be applied if state observation is very costly and therefore rare (in time). We present a novel MDP theory for rare, costly observations and derive the corresponding Bellman equation. In the new theory, state information can be derived for a particular cost after certain, rather long time intervals. The resulting information costs enter into the total cost and thus into the optimization criterion. This approach applies to many real world problems, particularly in the medical context, where the medical condition is examined rather rarely because examination costs are high. At the same time, the approach allows for efficient numerical realization. We demonstrate the usefulness of the novel theory by determining, from the national economic perspective, optimal therapeutic policies for the treatment of the human immunodeficiency virus (HIV) in resource-rich and resource-poor settings. Based on the developed theory and models, we discover that available drugs may not be utilized efficiently in resource-poor settings due to exorbitant diagnostic costs. Y1 - 2014 U6 - https://doi.org/10.4310/CMS.2014.v12.n5.a4 VL - 12 IS - 5 SP - 859 EP - 877 ER - TY - JOUR A1 - Wang, Han A1 - Schütte, Christof A1 - Ciccotti, Giovanni A1 - von Kleist, Max T1 - Exploring the conformational dynamics of alanine dipeptide in solution subjected to an external electric field: A nonequilibrium molecular dynamics simulation JF - Journal of Chemical Theory and Computation N2 - In this paper, we investigate the conformational dynamics of alanine dipeptide under an external electric field by nonequilibrium molecular dynamics simulation. We consider the case of a constant and of an oscillatory field. In this context, we propose a procedure to implement the temperature control, which removes the irrelevant thermal effects of the field. For the constant field different time-scales are identified in the conformational, dipole moment, and orientational dynamics. Moreover, we prove that the solvent structure only marginally changes when the external field is switched on. In the case of oscillatory field, the conformational changes are shown to be as strong as in the previous case, and nontrivial nonequilibrium circular paths in the conformation space are revealed by calculating the integrated net probability fluxes. Y1 - 2014 U6 - https://doi.org/10.1021/ct400993e VL - 10 IS - 4 SP - 1376 EP - 1386 ER - TY - CHAP A1 - Pfister, Hanspeter A1 - Kaynig, Verena A1 - Botha, Charl P. A1 - Bruckner, Stefan A1 - Dercksen, Vincent J. A1 - Hege, Hans-Christian A1 - Roerdink, Jos B.T.M. ED - Hansen, Charles D. ED - Chen, Min ED - Johnson, Christopher R. ED - Kaufman, Arie E. ED - Hagen, Hans T1 - Visualization in Connectomics T2 - Scientific Visualization - Uncertainty, Multifield, Biomedical, and Scalable Visualization N2 - Connectomics is a branch of neuroscience that attempts to create a connectome, i.e., a complete map of the neuronal system and all connections between neuronal structures. This representation can be used to understand how functional brain states emerge from their underlying anatomical structures and how dysfunction and neuronal diseases arise. We review the current state-of-the-art of visualization and image processing techniques in the field of connectomics and describe a number of challenges. After a brief summary of the biological background and an overview of relevant imaging modalities, we review current techniques to extract connectivity information from image data at macro-, meso- and microscales. We also discuss data integration and neural network modeling, as well as the visualization, analysis and comparison of brain networks. Y1 - 2014 SN - 978-1-4471-6496-8 U6 - https://doi.org/10.1007/978-1-4471-6497-5_21 SP - 221 EP - 245 PB - Springer ER - TY - CHAP A1 - Stoppel, Sergej A1 - Hege, Hans-Christian A1 - Wiebel, Alexander T1 - Visibility-driven depth determination of surface patches in direct volume rendering T2 - EuroVis - Short Papers 2014 N2 - This paper presents an algorithm called surfseek for selecting surfaces on the most visible features in direct volume rendering (DVR). The algorithm is based on a previously published technique (WYSIWYP) for picking 3D locations in DVR. The new algorithm projects a surface patch on the DVR image, consisting of multiple rays. For each ray the algorithm uses WYSIWYP or a variant of it to find the candidates for the most visible locations along the ray. Using these candidates the algorithm constructs a graph and computes a minimum cut on this graph. The minimum cut represents a visible and typically rather smooth surface. In the last step the selected surface is displayed. We provide examples for results using artificially generated and real-world data sets. Y1 - 2014 U6 - https://doi.org/10.2312/eurovisshort.20141164 SP - 97 EP - 101 ER - TY - JOUR A1 - Goubergrits, Leonid A1 - Spuler, Andreas A1 - Schaller, Jens A1 - Wiegmann, Nils A1 - Berthe, Andre A1 - Hege, Hans-Christian A1 - Affeld, Klaus A1 - Kertzscher, Ulrich T1 - In vitro study of hemodynamic treatment improvement: Hunterian ligation of a fenestrated basilar artery aneurysm after coiling JF - The International Journal of Artificial Organs N2 - Hunterian ligation affecting hemodynamics in vessels was proposed to avoid rebleeding in a case of a fenestrated basilar artery aneurysm after incomplete coil occlusion. We studied the hemodynamics in vitro to predict the hemodynamic changes near the aneurysm remnant caused by Hunterian ligation. A transparent model was fabricated based on three-dimensional rotational angiography imaging. Arteries were segmented and reconstructed. Pulsatile flow in the artery segments near the partially occluded (coiled) aneurysm was investigated by means of particle image velocimetry. The hemodynamic situation was investigated before and after Hunterian ligation of either the left or the right vertebral artery (LVA/RVA). Since post-ligation flow rate in the basilar artery was unknown, reduced and retained flow rates were simulated for both ligation options. Flow in the RVA and in the corresponding fenestra vessel is characterized by a vortex at the vertebrobasilar junction, whereas the LVA exhibits undisturbed laminar flow. Both options (RVA or LVA ligation) cause a significant flow reduction near the aneurysm remnant with a retained flow rate. The impact of RVA ligation is, however, significantly higher. This in vitro case study shows that flow reduction near the aneurysm remnant can be achieved by Hunterian ligation and that this effect depends largely on the selection of the ligated vessel. Thus the ability of the proposed in vitro pipe-line to improve hemodynamic impact of the proposed therapy was successfully proved. Y1 - 2014 U6 - https://doi.org/10.5301/ijao.5000314 VL - 37 IS - 4 SP - 325 EP - 335 ER - TY - CHAP A1 - Soltwisch, Victor A1 - Wernecke, Jan A1 - Haase, Anton A1 - Probst, Jürgen A1 - Schoengen, Max A1 - Scholze, Frank A1 - Pomplun, Jan A1 - Burger, Sven T1 - Determination of line profile on nanostructured surfaces using EUV and x-ray scattering T2 - Proc. SPIE Y1 - 2014 U6 - https://doi.org/10.1117/12.2066165 VL - 9235 SP - 92351D ER - TY - JOUR A1 - Hochfeld, Mascha A1 - Lamecker, Hans A1 - Thomale, Ulrich W. A1 - Schulz, Matthias A1 - Zachow, Stefan A1 - Haberl, Hannes T1 - Frame-based cranial reconstruction JF - Journal of Neurosurgery: Pediatrics N2 - The authors report on the first experiences with the prototype of a surgical tool for cranial remodeling. The device enables the surgeon to transfer statistical information, represented in a model, into the disfigured bone. The model is derived from a currently evolving databank of normal head shapes. Ultimately, the databank will provide a set of standard models covering the statistical range of normal head shapes, thus providing the required template for any standard remodeling procedure as well as customized models for intended overcorrection. To date, this technique has been used in the surgical treatment of 14 infants (age range 6-12 months) with craniosynostosis. In all 14 cases, the designated esthetic result, embodied by the selected model, has been achieved, without morbidity or mortality. Frame-based reconstruction provides the required tools to precisely realize the surgical reproduction of the model shape. It enables the establishment of a self-referring system, feeding back postoperative growth patterns, recorded by 3D follow-up, into the model design. Y1 - 2014 U6 - https://doi.org/10.3171/2013.11.PEDS1369 VL - 13 IS - 3 SP - 319 EP - 323 ER - TY - THES A1 - Amiranashvili, Tamaz T1 - Fitting Smooth Strips to Rough Surfaces Y1 - 2014 ER - TY - THES A1 - Solleder, Marthe T1 - Bewertung von Transformationsprodukten im Wasserkreislauf durch Computersimulationen Y1 - 2014 ER - TY - JOUR A1 - Weber, Marcus A1 - Fackeldey, Konstantin T1 - Computing the Minimal Rebinding Effect Included in a Given Kinetics JF - Multiscale Model. Simul. N2 - The rebinding effect is a phenomenon which occurs when observing a ligand-receptor binding process. On the macro scale this process comprises the Markov property. This Makovian view is spoiled when switching to the atomistic scale of a binding process. We therefore suggest a model which accurately describes the rebinding effect on the atomistic scale by allowing ''intermediate'' bound states. This allows us to define an indicator for the magnitude of rebinding and to formulate an optimization problem. The results form our examples show good agreement with data form laboratory. Y1 - 2014 U6 - https://doi.org/10.1137/13091124X VL - 12 IS - 1 SP - 318 EP - 334 ER - TY - JOUR A1 - Andrae, Karsten A1 - Merkel, Stefan A1 - Durmaz, Vedat A1 - Fackeldey, Konstantin A1 - Köppen, Robert A1 - Weber, Marcus A1 - Koch, Matthias T1 - Investigation of the Ergopeptide Epimerization Process JF - Computation N2 - Ergopeptides, like ergocornine and a-ergocryptine, exist in an S- and in an R-configuration. Kinetic experiments imply that certain configurations are preferred depending on the solvent. The experimental methods are explained in this article. Furthermore, computational methods are used to understand this configurational preference. Standard quantum chemical methods can predict the favored configurations by using minimum energy calculations on the potential energy landscape. However, the explicit role of the solvent is not revealed by this type of methods. In order to better understand its influence, classical mechanical molecular simulations are applied. It appears from our research that “folding” the ergopeptide molecules into an intermediate state (between the S- and the R-configuration) is mechanically hindered for the preferred configurations. Y1 - 2014 U6 - https://doi.org/10.3390/computation2030102 VL - 2 IS - 3 SP - 102 EP - 111 ER -