TY - CHAP A1 - Turner, Mark A1 - Berthold, Timo A1 - Besançon, Mathieu A1 - Koch, Thorsten T1 - Cutting Plane Selection with Analytic Centers and Multiregression T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023. N2 - Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method. Y1 - 2023 U6 - https://doi.org/10.1007/978-3-031-33271-5_4 VL - 13884 SP - 52 EP - 68 PB - Springer ER - TY - CHAP A1 - Anderson, Lovis A1 - Hiller, Benjamin T1 - A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes T2 - Operations Research Proceedings 2018 N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-18500-8_12 VL - Operations Research Proceedings ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Szabo, Jacint T1 - Gas Network Topology Optimization for Upcoming Market Requirements T2 - International Conference on the European Energy Market (EEM) N2 - 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. Y1 - 2011 U6 - https://doi.org/10.1109/EEM.2011.5953035 SP - 346 EP - 351 ER - TY - CHAP A1 - Martin, Alexander A1 - Geißler, Björn A1 - Heyn, Christine A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Optimierung Technischer Kapazitäten in Gasnetzen T2 - Optimierung in der Energiewirtschaft Y1 - 2011 SP - 105 EP - 114 PB - VDI-Verlag, Düsseldorf ER - TY - CHAP A1 - Streubel, Tom A1 - Strohm, Christian A1 - Trunschke, Philipp A1 - Tischendorf, Caren T1 - Generic Construction and Efficient Evaluation of Network DAEs and Their Derivatives in the Context of Gas Networks T2 - Operations Research Proceedings 2017 N2 - We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function f and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of f can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF). KW - compressed sparse row format KW - algorithmic differentiation KW - abs-normal form KW - piecewise linear tangent approximation KW - piecewise smooth Y1 - 2018 SN - 978-3-319-89920-6 U6 - https://doi.org/10.1007/978-3-319-89920-6_83 SP - 627 EP - 632 PB - Springer International Publishing ER - TY - CHAP A1 - Hoppmann, Kai A1 - Schwarz, Robert T1 - Finding Maximum Minimum Cost Flows to Evaluate Gas Network Capacities T2 - Operations Research Proceedings 2017 N2 - In this article we consider the following problem arising in the context of scenario generation to evaluate the transport capacity of gas networks: In the Uncapacitated Maximum Minimum Cost Flow Problem (UMMCF) we are given a flow network where each arc has an associated nonnegative length and infinite capacity. Additionally, for each source and each sink a lower and an upper bound on its supply and demand are known, respectively. The goal is to find values for the supplies and demands respecting these bounds, such that the optimal value of the induced Minimum Cost Flow Problem is maximized, i.e., to determine a scenario with maximum transportmoment. In this article we propose two linear bilevel optimization models for UMMCF, introduce a greedy-style heuristic, and report on our first computational experiment. Y1 - 2018 SN - 978-3-319-89919-0 U6 - https://doi.org/10.1007/978-3-319-89920-6_46 SP - 339 EP - 346 ER - TY - CHAP A1 - Hennings, Felix T1 - Benefits and Limitations of Simplified Transient Gas Flow Formulations T2 - Operations Research Proceedings 2017 N2 - Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification. Y1 - 2018 UR - https://link.springer.com/chapter/10.1007/978-3-319-89920-6_32 U6 - https://doi.org/10.1007/978-3-319-89920-6_32 VL - Operations Research Proceedings SP - 231 EP - 237 PB - Springer, Cham ER - TY - CHAP A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite T2 - Mathematical Software – ICMS 2016 N2 - SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42432-3_37 VL - 9725 SP - 301 EP - 307 PB - Springer ER - TY - CHAP A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations T2 - Proceedings of Operations Research 2016 N2 - 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. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_34 SP - 251 EP - 257 ER -