@misc{Hiller2005, author = {Hiller, Benjamin}, title = {Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8896}, number = {05-56}, year = {2005}, abstract = {In this paper we consider a simple variant of the Online Dial-a-Ride Problem from a probabilistic point of view. To this end, we look at a probabilistic version of this online Dial-a-Ride problem and introduce a probabilistic notion of the competitive ratio which states that an algorithm performs well on the vast majority of the instances. Our main result is that under the assumption of high load a certain online algorithm is probabilistically \$(1+o(1))\$-competitive if the underlying graph is a tree. This result can be extended to general graphs by using well-known approximation techniques at the expense of a distortion factor~\$O(\log\|V\|)\$.}, language = {en} } @misc{GroetschelHillerTuchscherer2007, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Combinatorial Online Optimization: Elevators \& Yellow Angels}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10360}, number = {07-36}, year = {2007}, abstract = {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.}, language = {en} } @misc{BeckerHiller2020, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77684}, year = {2020}, abstract = {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.}, language = {en} } @misc{BeckerHiller2019, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Improved optimization models for potential-driven network flow problems via ASTS orientations}, issn = {1438-0064}, doi = {10.12752/7534}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75347}, year = {2019}, abstract = {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.}, language = {en} } @misc{BeckerHiller2018, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {ASTS Orientations on Undirected Graphs: Structural analysis and enumeration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69632}, year = {2018}, abstract = {All feasible flows in potential-driven networks induce an orientation on the undirected graph underlying the network. Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations.}, language = {en} } @misc{HillerBecker2018, author = {Hiller, Benjamin and Becker, Kai-Helge}, title = {Improving relaxations for potential-driven network flow problems via acyclic flow orientations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69622}, year = {2018}, abstract = {The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network. We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage.}, language = {en} } @misc{AndersonHiller2018, author = {Anderson, Lovis and Hiller, Benjamin}, title = {A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69489}, year = {2018}, 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. Naively, this can be done via inclusion/exclusion and leveraging the existing code for the volume of polytopes. However, this is often inefficient. 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} } @misc{HillerSaitenmacherWalther2018, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68179}, year = {2018}, 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. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode.}, language = {en} } @misc{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}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7928}, number = {04-17}, year = {2004}, abstract = {Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.}, language = {en} } @misc{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 Szab{\´o}, J{\´a}cint}, title = {Gas Network Topology Optimization for Upcoming Market Requirements}, doi = {10.1109/EEM.2011.5953035}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12348}, number = {11-09}, 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} }