@inproceedings{HillerKrumkeRambau2004, author = {Hiller, Benjamin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC}, volume = {18}, booktitle = {Latin-American Conference on Combinatorics, Graphs and Applications, Santiago de Chile 2004}, editor = {Liebling, T. and Duran, G. and Matamala, M.}, pages = {157 -- 163}, year = {2004}, language = {en} } @inproceedings{HillerTuchscherer2008, author = {Hiller, Benjamin and Tuchscherer, Andreas}, title = {Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers}, booktitle = {Operations Research Proceedings 2007}, publisher = {Springer}, pages = {357 -- 362}, year = {2008}, language = {en} } @inproceedings{HillerVredeveld2008, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison}, volume = {5193}, booktitle = {Proceedings of the 16th esa}, publisher = {Springer}, pages = {528 -- 539}, year = {2008}, language = {en} } @article{HillerKrumkeRambau2006, author = {Hiller, Benjamin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC}, volume = {154}, journal = {DISAM}, number = {13}, pages = {1897 -- 1907}, year = {2006}, language = {en} } @article{HillerSaitenmacherWalther2021, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Improved models for operation modes of complex compressor stations}, volume = {94}, journal = {Mathematical Methods of Operations Research}, doi = {https://doi.org/10.1007/s00186-021-00745-x}, pages = {171 -- 195}, year = {2021}, abstract = {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.}, language = {en} } @incollection{GroetschelHillerTuchscherer2009, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Structuring a Dynamic Environment}, booktitle = {Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines}, editor = {Lucas, Klaus and Roosen, Peter}, publisher = {Springer}, doi = {10.1007/978-3-642-00870-2}, pages = {199 -- 214}, year = {2009}, language = {en} } @article{KochSchmidtHilleretal.2020, author = {Koch, Thorsten and Schmidt, Martin and Hiller, Benjamin and Pfetsch, Marc and Geißler, Bj{\"o}rn and Henrion, Ren{\´e} and Joormann, Imke and Martin, Alexander and Morsi, Antonio and R{\"o}misch, Werner and Schewe, Lars and Schultz, R{\"u}diger}, title = {Capacity Evaluation for Large-Scale Gas Networks}, volume = {35}, journal = {German Success Stories in Industrial Mathematics}, isbn = {978-3-030-81454-0}, doi = {10.1007/978-3-030-81455-7}, pages = {23 -- 28}, year = {2020}, language = {en} } @inproceedings{AndersonHiller2019, author = {Anderson, Lovis and Hiller, Benjamin}, title = {A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes}, volume = {Operations Research Proceedings}, booktitle = {Operations Research Proceedings 2018}, doi = {10.1007/978-3-030-18500-8_12}, year = {2019}, abstract = {Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set. We propose a revised variant of an old algorithm by Bieri and Nef (1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane.}, language = {en} } @inproceedings{HillerVredeveld2009, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Stochastic dominance analysis of online bin coloring algorithms}, booktitle = {9th Workshop on Models and Algorithms for Planning and Scheduling Problems}, year = {2009}, language = {en} } @misc{Hiller2004, type = {Master Thesis}, author = {Hiller, Benjamin}, title = {Bad Guys are Rare}, year = {2004}, language = {en} } @phdthesis{Hiller2009, author = {Hiller, Benjamin}, title = {Online Optimization}, year = {2009}, language = {en} } @incollection{BerberichHagenHilleretal.2010, author = {Berberich, Eric and Hagen, Matthias and Hiller, Benjamin and Moser, Hannes}, title = {Experiments}, volume = {5971}, booktitle = {Algorithm Engineering}, editor = {M{\"u}ller-Hannemann, Matthias and Schirra, Stefan}, publisher = {Springer}, pages = {325 -- 388}, year = {2010}, language = {en} } @article{HillerVredeveld2012, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Probabilistic alternatives for competitive analysis}, volume = {27}, journal = {Computer Science - Research and Development}, number = {3}, publisher = {Springer}, doi = {10.1007/s00450-011-0149-1}, pages = {189 -- 196}, year = {2012}, language = {en} } @incollection{GeyerHillerMeinert2010, author = {Geyer, Markus and Hiller, Benjamin and Meinert, Sascha}, title = {Modeling}, volume = {5971}, booktitle = {Algorithm Engineering}, editor = {M{\"u}ller-Hannemann, Matthias and Schirra, Stefan}, publisher = {Springer}, pages = {16 -- 57}, year = {2010}, language = {en} } @misc{Hiller2003, author = {Hiller, Benjamin}, title = {Hochlastvarianten des Algorithmus ZIBDIP f{\"u}r die automatische Disposition von ADAC-Einsatzfahrzeugen}, publisher = {Studienarbeit TU Ilmenau\,/\,Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin}, year = {2003}, language = {en} } @article{PfetschFuegenschuhGeissleretal.2014, author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2014.888426}, year = {2014}, abstract = {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 feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.}, language = {en} } @inproceedings{FuegenschuhHillerHumpolaetal.2011, author = {F{\"u}genschuh, Armin and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Schwarz, Robert and Schweiger, Jonas and Szabo, Jacint}, title = {Gas Network Topology Optimization for Upcoming Market Requirements}, booktitle = {International Conference on the European Energy Market (EEM)}, doi = {10.1109/EEM.2011.5953035}, pages = {346 -- 351}, year = {2011}, abstract = {Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed.}, language = {en} } @article{HillerKlugTuchscherer2013, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups}, journal = {Flexible Services and Manufacturing Journal}, doi = {10.1007/s10696-013-9175-6}, pages = {1 -- 24}, year = {2013}, language = {en} } @article{FuegenschuhGeisslerGollmeretal.2013, author = {F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Gollmer, Ralf and Hayn, Christine and Henrion, Ren{\´e} and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Mirkov, Radoslava and Morsi, Antonio and R{\"o}misch, Werner and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Willert, Bernhard}, title = {Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets}, volume = {5}, journal = {Energy Systems}, number = {3}, publisher = {Springer Berlin Heidelberg}, address = {Berlin}, doi = {10.1007/s12667-013-0099-8}, pages = {449 -- 473}, year = {2013}, abstract = {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 were 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 discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network's capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations.}, language = {en} } @article{DomschkeGrossHanteetal.2015, author = {Domschke, Pia and Groß, Martin and Hante, Falk M. and Hiller, Benjamin and Schewe, Lars and Schmidt, Martin}, title = {Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken}, volume = {156}, journal = {gwf - Gas+Energie}, number = {11}, pages = {880 -- 885}, year = {2015}, language = {de} } @inproceedings{HillerKlugTuchscherer2009, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improving the performance of elevator systems using exact reoptimization algorithms}, booktitle = {Proceedings of MAPSP}, pages = {224 -- 226}, year = {2009}, language = {en} } @inproceedings{HillerKlugTuchscherer2010, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improved destination call elevator control algorithms for up peak traffic}, booktitle = {Operations Research Proceedings 2010}, publisher = {Springer}, year = {2010}, language = {en} } @inproceedings{HillerTuchscherer2008, author = {Hiller, Benjamin and Tuchscherer, Andreas}, title = {Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers}, booktitle = {Operations Research Proceedings}, editor = {Kalcsics, J{\"o}rg and Nickel, Stefan}, publisher = {Springer}, pages = {357 -- 362}, year = {2008}, language = {en} } @inproceedings{HillerKrumkeSalibaetal.2009, author = {Hiller, Benjamin and Krumke, Sven and Saliba, Sleman and Tuchscherer, Andreas}, title = {Randomized Online Algorithms for Dynamic Multi-Period Routing Problems}, booktitle = {Proceedings of MAPSP}, pages = {71 -- 73}, year = {2009}, language = {en} } @inproceedings{MartinGeisslerHeynetal.2011, author = {Martin, Alexander and Geißler, Bj{\"o}rn and Heyn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, booktitle = {Optimierung in der Energiewirtschaft}, publisher = {VDI-Verlag, D{\"u}sseldorf}, pages = {105 -- 114}, year = {2011}, language = {en} } @article{HillerKochScheweetal.2018, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, volume = {270}, journal = {European Journal of Operational Research}, number = {3}, pages = {797 -- 808}, year = {2018}, abstract = {In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now trans- ported by independent so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.}, language = {en} } @incollection{HillerHumpolaLehmannetal.2015, author = {Hiller, Benjamin and Humpola, Jesco and Lehmann, Thomas and Lenz, Ralf and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Willert, Bernhard}, title = {Computational results for validation of nominations}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, year = {2015}, abstract = {The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.}, language = {en} } @incollection{HumpolaFuegenschuhHilleretal.2015, author = {Humpola, Jesco and F{\"u}genschuh, Armin and Hiller, Benjamin and Koch, Thorsten and Lehmann, Thomas and Lenz, Ralf and Schwarz, Robert and Schweiger, Jonas}, title = {The Specialized MINLP Approach}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, year = {2015}, abstract = {We propose an approach to solve the validation of nominations problem using mixed-integer nonlinear programming (MINLP) methods. Our approach handles both the discrete settings and the nonlinear aspects of gas physics. Our main contribution is an innovative coupling of mixed-integer (linear) programming (MILP) methods with nonlinear programming (NLP) that exploits the special structure of a suitable approximation of gas physics, resulting in a global optimization method for this type of problem.}, language = {en} } @book{KochHillerPfetschetal.2015, author = {Koch, Thorsten and Hiller, Benjamin and Pfetsch, Marc and Schewe, Lars}, title = {Evaluating Gas Network Capacities}, publisher = {SIAM}, isbn = {978-1-611973-68-6}, pages = {xvi + 376 pages}, year = {2015}, language = {en} } @inproceedings{HillerKlugWitzig2013, author = {Hiller, Benjamin and Klug, Torsten and Witzig, Jakob}, title = {Reoptimization in branch-and-bound algorithms with an application to elevator control}, volume = {7933}, booktitle = {Proceedings of the 12th International Symposium on Experimental Algorithms}, doi = {10.1007/978-3-642-38527-8_33}, pages = {378 -- 389}, year = {2013}, language = {en} } @incollection{GotzesHeineckeHilleretal.2015, author = {Gotzes, Uwe and Heinecke, Nina and Hiller, Benjamin and R{\"o}vekamp, Jessica and Koch, Thorsten}, title = {Regulatory rules for gas markets in Germany and other European countries}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {978-1-611973-68-6}, pages = {45 -- 64}, year = {2015}, language = {en} } @inproceedings{HillerSaitenmacherWalther2017, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, booktitle = {Proceedings of Operations Research 2016}, doi = {10.1007/978-3-319-55702-1_34}, pages = {251 -- 257}, year = {2017}, abstract = {We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model.}, language = {en} } @inproceedings{GamrathHillerWitzig2015, author = {Gamrath, Gerald and Hiller, Benjamin and Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, volume = {9125}, edition = {Experimental Algorithms, Lecture Notes in Computer Science}, publisher = {Springer}, isbn = {978-3-319-20086-6}, doi = {10.1007/978-3-319-20086-6_14}, pages = {181 -- 192}, year = {2015}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @incollection{HillerHaynHeitschetal.2015, author = {Hiller, Benjamin and Hayn, Christine and Heitsch, Holger and Henrion, Ren{\´e} and Le{\"o}vey, Hernan and M{\"o}ller, Andris and R{\"o}misch, Werner}, title = {Methods for verifying booked capacities}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, pages = {291 -- 315}, year = {2015}, language = {en} }