@misc{SteffyWolter2011, author = {Steffy, Daniel and Wolter, Kati}, title = {Valid Linear Programming Bounds for Exact Mixed-Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12332}, number = {11-08}, year = {2011}, abstract = {Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly feasible, giving a valid bound. Solutions are repaired by performing a projection and a shift to ensure all constraints are satisfied; bound computations are accelerated by reusing structural information through the branch-and-bound tree. We demonstrate this method to be widely applicable and faster than solving a sequence of exact LPs. Several variations of the algorithm are described and computationally evaluated in an exact branch-and-bound algorithm within the mixed-integer programming framework SCIP.}, language = {en} } @misc{CookKochSteffyetal.2011, author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {An Exact Rational Mixed-Integer Programming Solver}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12329}, number = {11-07}, year = {2011}, abstract = {We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann collections.}, language = {en} } @misc{EisenblaetterSchweiger2011, author = {Eisenbl{\"a}tter, Andreas and Schweiger, Jonas}, title = {Multistage Stochastic Programming in Strategic Telecommunication Network Planning}, doi = {10.1007/s10287-012-0143-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12232}, number = {11-06}, year = {2011}, abstract = {Mobile communication is nowadays taken for granted. Having started primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. Operators are facing the challenge to match the demand by continuously expanding and upgrading the network infrastructure. However, the evolution of the customer's demand is uncertain. We introduce a novel (long-term) network planning approach based on multistage stochastic programming, where demand evolution is considered as a stochastic process and the network is extended as to maximize the expected profit. The approach proves capable of designing large-scale realistic UMTS networks with a time-horizon of several years. Our mathematical optimization model, the solution approach, and computational results are presented in this paper.}, language = {en} } @misc{ReininghausKastenWeinkaufetal.2011, author = {Reininghaus, Jan and Kasten, Jens and Weinkauf, Tino and Hotz, Ingrid}, title = {Combinatorial Feature Flow Fields: Tracking Critical Points in Discrete Scalar Fields}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12151}, number = {11-02}, year = {2011}, abstract = {We propose a combinatorial algorithm to track critical points of 2D time-dependent scalar fields. Existing tracking algorithms such as Feature Flow Fields apply numerical schemes utilizing derivatives of the data, which makes them prone to noise and involve a large number of computational parameters. In contrast, our method is robust against noise since it does not require derivatives, interpolation, and numerical integration. Furthermore, we propose an importance measure that combines the spatial persistence of a critical point with its temporal evolution. This leads to a time-aware feature hierarchy, which allows us to discriminate important from spurious features. Our method requires only a single, easy-to-tune computational parameter and is naturally formulated in an out-of-core fashion, which enables the analysis of large data sets. We apply our method to a number of data sets and compare it to the stabilized continuous Feature Flow Field tracking algorithm.}, language = {en} } @misc{PossRaack2011, author = {Poss, Michael and Raack, Christian}, title = {Affine recourse for the robust network design problem: between static and dynamic routing}, doi = {10.1002/net.21482}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12122}, number = {11-03}, year = {2011}, abstract = {Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.}, language = {en} } @misc{BergRitterRoeblitz2011, author = {Berg, Mascha and Ritter, Julia and R{\"o}blitz, Susanna}, title = {A mathematical model for the Zinc response of young pigs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12191}, number = {11-05}, year = {2011}, abstract = {In a number of studies the feeding of pharmacological levels of Zinc to weanling pigs was examined. The publications agree in the fact that the achieved performance increase of the pigs depends on the amount of Zinc as well as on the type of mineral complex used as feed additive. The results are based on measurements of the animals' body weight and the Zinc concentration in the blood within the first two weeks of the experiments. From the measurement values, conclusions are drawn about adequate Zinc doses, but a deeper understanding of the physiological processes that influence the Zinc distribution in the organism is still missing. In this report, we want to close this gap by using a systems biology approach. We present a small mathematical model that describes the organic feedback mechanisms with the help of differential equations. The simulation results not only match with measurement values, but also give insight into non-measurable processes, which will hopefully contribute to animal experiments being organized in a more selective and reduced way.}, language = {en} } @misc{BertholdGleixnerHeinzetal.2011, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {On the computational impact of MIQCP solver components}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11998}, number = {11-01}, year = {2011}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} }