Refine
Year of publication
- 2014 (53) (remove)
Document Type
- ZIB-Report (44)
- Master's Thesis (7)
- ZIB-Annual (1)
- Bachelor's Thesis (1)
Has Fulltext
- yes (53) (remove)
Keywords
- directed networks (2)
- finite element method (2)
- metastability (2)
- 3D neural network (1)
- 3D reconstruction (1)
- Active message (1)
- Alanine dipeptide (1)
- Ant Colony Optimization (1)
- Benders' decomposition (1)
- Beton (1)
Institute
- Mathematical Optimization (22)
- Numerical Mathematics (15)
- Visual Data Analysis (10)
- Visual and Data-centric Computing (10)
- Mathematics of Transportation and Logistics (9)
- Distributed Algorithms and Supercomputing (4)
- Computational Nano Optics (3)
- Computational Molecular Design (2)
- Computational Systems Biology (2)
- Digital Data and Information for Society, Science, and Culture (2)
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.
In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems.
The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented.
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.
The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate.
Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems.
The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de
This work deals with the reduction of a previously developed ODE model for the bovine estrous cycle. After applying a method for exploring the parameter space by Apri et al. (2012), we perform structure-based reduction steps and several system specific adaptations. Overall, the original model consisting of 15 ODEs and 60 parameters is reduced to a model of 10 odes and 38 parameters. The reduced model qualitatively reproduces the state trajectories of the original model.
In this thesis, we study different modelling approaches for piecewise linear functions, in particular with respect to their occurrence in mathematical optimization problems. Reviewing the quality of the classical MIP models from the literature, we will see that all but the disaggregated convex combination method yield both sharp and locally ideal formulations. In the main part, we will present an alternative approach for modelling constraints involving piecewise linear functions, based on ideas of constraint programming and using a convex hull relaxation. For the purpose of developing a branch-and-bound procedure specifically adapted to our constraint formulation within SCIP, all required components such as propagation, branching and separation will be discussed. In particular, we will focus on adapting well-known MIP strategies for the selection of branching variables to our type of piecewise linear constraints.
Adaptive sampling strategies for efficient parameter scans in nano-photonic device simulations
(2014)
Rigorous optical simulations are an important tool in optimizing scattering properties of nano-photonic devices and are used, for example, in solar cell optimization. The finite element method (FEM) yields rigorous, time-harmonic, high accuracy solutions of the full 3D vectorial Maxwell's equations [1] and furthermore allows for great flexibility and accuracy in the geometrical modeling of these often complex shaped 3D nano-structures. A major drawback of frequency domain methods is the limitation of single frequency evaluations. For example the accurate computation of the short circuit current density of an amorphous silicon / micro-crystalline multi-junction thin film solar cell may require the solution of Maxwell's equations for over a hundred different wavelengths if an equidistant sampling strategy is employed. Also in optical metrology, wavelength scans are frequently used to reconstruct unknown geometrical and material properties of optical systems numerically from measured
scatterometric data.
In our contribution we present several adaptive numerical integration and sampling routines and study their efficiency in the context of the determination of generation rate profiles of solar cells. We show that these strategies lead to a reduction in the computational effort without loss of accuracy. We discuss the employment of tangential information in a Hermite interpolation scheme to achieve similar accuracy on coarser grids. We explore the usability of these strategies for scatterometry and solar cell simulations.
We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$.