TY - CHAP A1 - Hiller, Benjamin A1 - Krumke, Sven A1 - Rambau, Jörg ED - Liebling, T. ED - Duran, G. ED - Matamala, M. T1 - Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC T2 - Latin-American Conference on Combinatorics, Graphs and Applications, Santiago de Chile 2004 Y1 - 2004 VL - 18 SP - 157 EP - 163 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers T2 - Operations Research Proceedings 2007 Y1 - 2008 SP - 357 EP - 362 PB - Springer ER - TY - CHAP A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison T2 - Proceedings of the 16th esa Y1 - 2008 VL - 5193 SP - 528 EP - 539 PB - Springer ER - TY - JOUR A1 - Hiller, Benjamin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC JF - DISAM Y1 - 2006 VL - 154 IS - 13 SP - 1897 EP - 1907 ER - TY - JOUR A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Improved models for operation modes of complex compressor stations JF - Mathematical Methods of Operations Research N2 - We study combinatorial structures in large-scale mixed-integer (nonlinear) programming problems arising in gas network optimization. We propose a preprocessing strategy exploiting the observation that a large part of the combinatorial complexity arises in certain subnetworks. Our approach analyzes these subnetworks and the combinatorial structure of the flows within these subnetworks in order to provide alternative models with a stronger combinatorial structure that can be exploited by off-the-shelve solvers. In particular, we consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. We propose a refined model that allows to precompute tighter bounds for each operation mode and a number of model variants based on the refined model exploiting these tighter bounds. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode. We evaluate our model variants on reference benchmark data, showing that they reduce the average running time between 10% for easy instances and 46% for hard instances. Moreover, for three of four considered networks, the average number of search tree nodes is at least halved, showing the effectivity of our model variants to guide the solver’s search. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00186-021-00745-x VL - 94 SP - 171 EP - 195 ER - TY - CHAP A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas ED - Lucas, Klaus ED - Roosen, Peter T1 - Structuring a Dynamic Environment T2 - Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines Y1 - 2009 UR - http://www.springer.com/engineering/book/978-3-642-00869-6 U6 - https://doi.org/10.1007/978-3-642-00870-2 SP - 199 EP - 214 PB - Springer ER - TY - GEN A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Combinatorial Online Optimization: Elevators & Yellow Angels N2 - In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon. T3 - ZIB-Report - 07-36 KW - Online-Optimierung KW - Aufzugssteuerung KW - Dispatching von Fahrzeugen KW - online optimization KW - elevator control KW - vehicle dispatching Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10360 SN - 1438-0064 ER - TY - GEN A1 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited N2 - In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested. T3 - ZIB-Report - 20-05 KW - acyclic orientations KW - enumeration algorithm KW - multiple sources and sinks KW - bipolar orientations Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-77684 SN - 1438-0064 ER - TY - JOUR A1 - Koch, Thorsten A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger T1 - Capacity Evaluation for Large-Scale Gas Networks JF - German Success Stories in Industrial Mathematics Y1 - 2020 SN - 978-3-030-81454-0 U6 - https://doi.org/10.1007/978-3-030-81455-7 VL - 35 SP - 23 EP - 28 ER - TY - GEN A1 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - Improved optimization models for potential-driven network flow problems via ASTS orientations N2 - The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks. T3 - ZIB-Report - 19-58 KW - potential-driven network flows KW - mixed-integer nonlinear programming KW - ASTS orientations KW - bipolar orientations Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75347 SN - 1438-0064 ER -