@misc{Shinano2017, author = {Shinano, Yuji}, title = {The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65545}, year = {2017}, abstract = {Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.}, language = {en} } @misc{OrlowskiWernerWessaely2012, author = {Orlowski, Sebastian and Werner, Axel and Wess{\"a}ly, Roland}, title = {Estimating trenching costs in FTTx network planning}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_15}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14884}, year = {2012}, abstract = {In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".}, language = {en} } @misc{HillerVredeveld2012, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Stochastic dominance analysis of Online Bin Coloring algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16502}, year = {2012}, abstract = {This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.}, language = {en} } @misc{PfeufferWerner2015, author = {Pfeuffer, Frank and Werner, Axel}, title = {Adaptive telecommunication network operation with a limited number of reconfigurations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55547}, year = {2015}, abstract = {Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators' concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch \& Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.}, language = {en} } @misc{GriewankStreubelLehmannetal.2016, author = {Griewank, Andreas and Streubel, Tom and Lehmann, Lutz and Hasenfelder, Richard and Radons, Manuel}, title = {Piecewise linear secant approximation via Algorithmic Piecewise Differentiation}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1387256}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61642}, year = {2016}, abstract = {It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - x̌|| ||x - x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods.}, language = {en} }