TY - BOOK A1 - Koch, Thorsten A1 - Hiller, Benjamin A1 - Pfetsch, Marc A1 - Schewe, Lars T1 - Evaluating Gas Network Capacities Y1 - 2015 SN - 978-1-611973-68-6 PB - SIAM ER - TY - GEN A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers N2 - Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use. T3 - ZIB-Report - 07-26 KW - Aufzugsgruppensteuerung KW - Zielrufsteuerung KW - Echzeitoptimierung KW - Online-Optimierung KW - elevator group control KW - destination call system KW - real time optimation KW - online optimization Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10108 SN - 1438-0064 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, Rene A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Mirkov, Radoslava A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Mathematical Optimization for Challenging Network Planning Problems in Unbundled Liberalized Gas Markets N2 - The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor where united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We show that these new paradigms lead to new and challenging mathematical optimization problems. In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed. With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined. T3 - ZIB-Report - 13-13 KW - Gas Market Liberalization KW - Entry-Exit Model KW - Gas Network Access Regulation KW - Mixed-Integer Nonlinear Nonconvex Stochastic Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17821 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Witzig, Jakob T1 - Reoptimization in branch-and-bound algorithms with an application to elevator control N2 - We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm. We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm. T3 - ZIB-Report - 13-15 KW - reoptimization KW - branch-and-bound KW - column generation KW - elevator control Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17876 SN - 1438-0064 ER - TY - GEN A1 - Pfetsch, Marc A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Geißler, Nina A1 - Gollmer, Ralf A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Vigerske, Stefan A1 - Willert, Bernhard T1 - Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions N2 - In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously. T3 - ZIB-Report - 12-41 Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16531 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups N2 - The task of an elevator control is to schedule the elevators of a group such that small waiting and travel times for the passengers are obtained. We present an exact reoptimization algorithm for this problem. A reoptimization algorithm computes a new schedule for the elevator group each time a new passenger arrives. Our algorithm uses column generation techniques and is, to the best of our knowledge, the first exact reoptimization algorithms for a group of passenger elevators. To solve the column generation problem, we propose a Branch & Bound method. T3 - ZIB-Report - 12-43 KW - elevator control, online optimization, reoptimization algorithms, column generation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16485 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Stochastic dominance analysis of Online Bin Coloring algorithms N2 - 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. T3 - ZIB-Report - 12-42 KW - online algorithms, stochastic dominance, algorithm analysis, Markov chains Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16502 SN - 1438-0064 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Witzig, Jakob T1 - Reoptimization in branch-and-bound algorithms with an application to elevator control T2 - Proceedings of the 12th International Symposium on Experimental Algorithms Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38527-8_33 VL - 7933 SP - 378 EP - 389 ER - TY - CHAP A1 - Gotzes, Uwe A1 - Heinecke, Nina A1 - Hiller, Benjamin A1 - Rövekamp, Jessica A1 - Koch, Thorsten T1 - Regulatory rules for gas markets in Germany and other European countries T2 - Evaluating gas network capacities Y1 - 2015 SN - 978-1-611973-68-6 SP - 45 EP - 64 PB - Society for Industrial and Applied Mathematics ER - TY - GEN A1 - Walther, Tom A1 - Hiller, Benjamin A1 - Saitenmacher, René T1 - Polyhedral 3D Models for compressors in gas networks N2 - Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure. T3 - ZIB-Report - 17-66 KW - gas compressor modeling, polyhedral model, accuracy, z factor Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65864 SN - 1438-0064 ER -