TY - CHAP A1 - Gleixner, Ambros A1 - Weltge, Stefan T1 - Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013 N2 - Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38171-3_26 VL - 7874 SP - 355 EP - 361 ER - TY - CHAP A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Improving the Accuracy of Linear Programming Solvers with Iterative Refinement T2 - ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation Y1 - 2012 U6 - https://doi.org/10.1145/2442829.2442858 SP - 187 EP - 194 ER - TY - JOUR A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - On cut-based inequalities for capacitated network design polyhedra JF - Networks Y1 - 2011 UR - http://onlinelibrary.wiley.com/doi/10.1002/net.20395/abstract VL - 57 IS - 2 SP - 141 EP - 156 ER - TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - An Algorithm-Independent Measure of Progress for Linear Constraint Propagation T2 - 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) N2 - Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported. Y1 - 2021 U6 - https://doi.org/10.4230/LIPIcs.CP.2021.52 VL - 210 SP - 52:1 EP - 52:17 ER - TY - JOUR A1 - Frank, A. A1 - Chi Lau, L. A1 - Szabó, Jácint T1 - A note on degree-constrained subgraphs JF - Discrete Mathematics Y1 - 2008 VL - 308 IS - 12 SP - 2647 EP - 2648 PB - Elsevier ER - TY - THES A1 - Eifler, Leon T1 - Mixed-Integer Programming for Clustering in Non-reversible Markov Processes N2 - The topic of this thesis is the examination of an optimization model which stems from the clustering process of non-reversible markov processes. We introduce the cycle clustering problem und formulate it as a mixed integer program (MIP). We prove that this problem is N P-hard and discuss polytopal aspects such as facets and dimension. The focus of this thesis is the development of solving methods for this clustering problem. We develop problem specific primal heuristics, as well as separation methods and an approximation algorithm. These techniques are implemented in practice as an application for the MIP solver SCIP. Our computational experiments show that these solving methods result in an average speedup of ×4 compared to generic solvers and that our application is able to solve more instances to optimality within the given time limit of one hour. KW - Markov State Models KW - NESS KW - Non-reversible Markov Processes KW - Mixed-Integer Programming Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66486 ER - TY - GEN A1 - Eifler, Leon A1 - Gleixner, Ambros A1 - Pulaj, Jonad T1 - Chvátal’s Conjecture Holds for Ground Sets of Seven Elements N2 - We establish a general computational framework for Chvátal’s conjecture based on exact rational integer programming. As a result we prove Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer programming solver used. T3 - ZIB-Report - 18-49 KW - extremal combinatorics KW - exact rational integer programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70240 SN - 1438-0064 ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Der junge Albring und Schwelm T2 - Der Forscher und der Zweifler - Werner Albring zum 90. Geburtstag Y1 - 2005 SP - 11 EP - 35 PB - Berlin-Brandenburgische Akademie der Wissenschaften 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 - CHAP A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Hoang, Nam-Dung ED - Biermann, Katja ED - Grötschel, Martin ED - Lutz-Westphal, Brigitte T1 - Lagenwechsel minimieren – oder das Bohren von Löchern in Leiterplatten T2 - Besser als Mathe Y1 - 2010 U6 - https://doi.org/10.1007/978-3-658-01004-1_19 SP - 161 EP - 174 PB - Vieweg+Teubner ER - TY - CHAP A1 - Grötschel, Martin ED - Hecht, Hartmut ED - Mikosch, Regina ED - Schwarz, Ingo ED - Siebert, Harald ED - Werther, Romy T1 - Tiefensuche T2 - Kosmos und Zahl - Beiträge zur Mathematik- und Astronomiegeschichte, zu Alexander von Humboldt und Leibniz Y1 - 2008 UR - http://www.steiner-verlag.de/titel/56734.html VL - 58 SP - 331 EP - 346 PB - Franz Steiner Verlag ER - TY - CHAP A1 - Grötschel, Martin A1 - Lügger, Joachim ED - Keil, Reinhard ED - Kerres, Michael ED - Schulmeister, Rolf T1 - Die Wissenschaftsgalaxis T2 - eUniversity - Update Bologna Y1 - 2007 UR - http://opus.kobv.de/zib/volltexte/2007/1014/ SP - 335 EP - 354 PB - Waxmann Verlag ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Geistiges Eigentum – Eine Zusammenfassung der vorgetragenen Standpunkte T2 - Geistiges Eigentum – Streitgespräche in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften Y1 - 2008 VL - Heft 7 SP - 89 EP - 95 PB - Berlin-Brandenburgische Akademie der Wissenschaften ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Geistiges Eigentum – Einführung in das Thema T2 - Geistiges Eigentum – Streitgespräche in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften Y1 - 2008 VL - Heft 7 SP - 9 EP - 14 PB - Berlin-Brandenburgische Akademie der Wissenschaften ER - TY - CHAP A1 - Grötschel, Martin ED - Hußmann, Stephan ED - Lutz-Westphal, Brigitte T1 - Schnelle Rundreisen T2 - Kombinatorische Optimierung erleben – In Studium und Unterricht Y1 - 2007 UR - http://www.viewegteubner.de/index.php;do=show/site=v/book_id=6158 SP - 95 EP - 128 PB - Vieweg CY - Wiesbaden ER - TY - GEN A1 - Grötschel, Martin ED - Hußmann, Stephan ED - Lutz-Westphal, Brigitte T1 - Das Problem mit der Komplexität T2 - Kombinatorische Optimierung erleben – In Studium und Unterricht Y1 - 2007 U6 - https://doi.org/10.1007/978-3-8348-9120-4_9 SP - 265 EP - 274 PB - Vieweg CY - Wiesbaden ER - TY - CHAP A1 - Grötschel, Martin ED - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes T2 - The Sharpest Cut Y1 - 2004 SP - 99 EP - 120 PB - MPS-SIAM ER - TY - CHAP A1 - Grötschel, Martin T1 - In der Mathematik sind sich alle einig und die Gesellschaft hat von ihr nichts zu befürchten T2 - Wissenschaft Kontrovers Y1 - 2005 VL - 2 PB - Chronos, Edition Collegium Helveticum CY - Zürich ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Ohne x is nix T2 - Berichte und Abhandlungen Y1 - 2008 VL - 14 SP - 195 EP - 219 PB - Akademie-Verlag CY - Berlin ER - TY - GEN A1 - Grötschel, Martin T1 - Tiefensuche: Bemerkungen zur Algorithmengeschichte T1 - Depth-first search: Remarks on the history of algorithms N2 - Dieser kurze Aufsatz zur Algorithmengeschichte ist Eberhard Knobloch, meinem Lieblings-Mathematikhistoriker, zum 65. Geburtstag gewidmet. Eberhard Knobloch hat immer, wenn ich ihm eine historische Frage zur Mathematik stellte, eine Antwort gewusst – fast immer auch sofort. Erst als ich mich selbst ein wenig und dazu amateurhaft mit Mathematikgeschichte beschäftigte, wurde mir bewusst, wie schwierig dieses „Geschäft“ ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in früheren Zeiten kennen. Man muss zusätzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen“ war, insbesondere, was seinerzeit gültige Beweisideen und -schritte waren, und daher damals keiner präzisen Definition oder Einführung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies möchte ich in diesem Artikel kurz darlegen in der Hoffnung, dass sich Wissenschaftshistoriker dieses Themas noch intensiver annehmen, als sie das bisher tun. Der Grund ist, dass heute Algorithmen viele Bereiche unserer Alltagswelt steuern und unser tägliches Leben oft von funktionierenden Algorithmen abhängt. Daher wäre eine bessere Kenntnis der Algorithmengeschichte von großem Interesse. T3 - ZIB-Report - 08-23 KW - Algorithmengeschichte KW - Algorithmus Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9628 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Lutz-Westphal, Brigitte T1 - Diskrete Mathematik und ihre Anwendungen: Auf dem Weg zu authentischem Mathematikunterricht N2 - Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. könnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale Bürger"' weiss davon nichts, der Schulunterricht könnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zugänglich. Solche Anwendungen, die zusätzlich noch der Lebensumwelt der Schüler zugehören, können dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die Lösung praktischer Fragen, anschaulich zu erläutern. Gerade in der diskreten Mathematik können hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenständiges Entdecken der Schüler entwickelt werden. Wir beginnen mit einigen Beispielen. T3 - ZIB-Report - 08-21 KW - Diskrete Mathematik KW - Mathematikunterricht in Schulen KW - authentischer Mathematikunterricht Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10758 SN - 1438-0064 ER - TY - JOUR A1 - Hoppmann-Baum, Kai T1 - On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows JF - Networks N2 - Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time. Y1 - 2021 U6 - https://doi.org/10.1002/net.22060 ER - TY - CHAP A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Winter, Thomas A1 - Zimmermann, Uwe ED - Grötschel, Martin ED - Krumke, Sven ED - Rambau, Jörg T1 - Combinatorial Online Optimization in Real Time T2 - Online Optimization of Large Scale Systems Y1 - 2001 SP - 679 EP - 704 PB - Springer ER - TY - CHAP A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg ED - Grötschel, Martin ED - Krumke, Sven ED - Rambau, Jörg T1 - Online Optimization of Complex Transportation Systems T2 - Online Optimization of Large Scale Systems Y1 - 2001 SP - 705 EP - 729 PB - Springer ER - TY - GEN A1 - Grötschel, Martin A1 - Raack, Christian A1 - Werner, Axel T1 - Towards optimizing the deployment of optical access networks N2 - In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a “unified” integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases. T3 - ZIB-Report - 13-11 KW - FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18627 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin T1 - Einblicke in die Diskrete Mathematik N2 - „Diskrete Mathematik, was ist das?“, ist eine typische Frage von Lehrern mit traditioneller Mathematikausbildung, denn dort kam und kommt diskrete Mathematik kaum vor. Die etwas Aufgeschlosseneren fragen: „Wenn (schon wieder) etwas Neues unterrichtet werden soll, was soll denn dann im Lehrplan gestrichen werden?“ Auf die zweite Frage wird hier nicht eingegangen. Das Ziel dieses Aufsatzes ist es, in diskrete Mathematik einzuführen, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu berücksichtigen. Die Schüler und Schülerinnen werden dafür dankbar sein – eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde. T3 - ZIB-Report - 12-01 KW - diskrete Mathematik Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14399 SN - 1438-0064 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 - Grötschel, Martin A1 - Neumann, Gerald T1 - 10 Jahre TELOTA N2 - Das TELOTA-Projekt - zunächst nur für zwei Jahre gestartet - feierte am 15. Juni 2011 sein 10-jähriges Bestehen im Rahmen eines Workshops mit einem abschließenden Festvortrag von Richard Stallmann zum Thema „Copyright versus community in the age of computer networks“. Diese Veranstaltung zeigte, wie aktuell die TELOTA-Themen weiterhin sind und dass diese eine große Resonanz in der allgemeinen Öffentlichkeit finden. Die TELOTA-Aktivitäten haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen, gehen aber weit über reinen Service hinaus. Sie beeinflussen die Forschung selbst und führen zu neuen interessanten wissenschaftlichen Fragestellungen. Der Rückblick auf die ersten zehn Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben, was bisher geleistet wurde. T3 - ZIB-Report - 12-13 KW - BBAW KW - Telota Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14799 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Nemhauser, George T1 - George Dantzig's contributions to integer programming N2 - This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem T3 - ZIB-Report - 07-39 KW - George Dantzig KW - integer programming KW - traveling salesman problem KW - TSP KW - mixed-integer programs Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10393 SN - 1438-0064 ER - TY - CHAP A1 - Grötschel, Martin A1 - Fonseca, Irene A1 - Davis, Mark ED - Casacuberta, Carles ED - Miró-Roig, Rosa ED - Ortega, Joaquín ED - Xambó-Descamps, Sebastià T1 - The Impact of Mathematical Research on Industry and Vice Versa T2 - Mathematical Glimpses into the 21st Century Y1 - 2001 SP - 35 EP - 53 PB - Societat Catalana de Matemàtiques and Centro Internacional de Métodos Numéricos en Ingeniería CY - Barcelona, Spain ET - First ER - TY - CHAP A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Völker, Manfred ED - Hoffmann, Karl-Heinz ED - Jäger, Willi ED - Lohmann, Thomas ED - Schunck (Hrsg.), Hermann T1 - Optimierung des Fahrzeugumlaufs im Öffentlichen Nahverkehr T2 - Mathematik Y1 - 1997 SP - 609 EP - 624 PB - Springer ER - TY - GEN A1 - Maher, Stephen J. A1 - Ralphs, Ted A1 - Shinano, Yuji T1 - Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms N2 - Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that resource consumption is at the heart of what we generally refer to as the “effectiveness” of an implementation. The proposed framework carefully distinguishes between an implementation’s baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment. T3 - ZIB-Report - 19-03 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74702 ER - TY - GEN A1 - Chen, Ying A1 - Koch, Thorsten A1 - Xu, Xiaofei T1 - Regularized partially functional autoregressive model with application to high-resolution natural gas forecasting in Germany N2 - We propose a partially functional autoregressive model with exogenous variables (pFAR) to describe the dynamic evolution of the serially correlated functional data. It provides a unit� ed framework to model both the temporal dependence on multiple lagged functional covariates and the causal relation with ultrahigh-dimensional exogenous scalar covariates. Estimation is conducted under a two-layer sparsity assumption, where only a few groups and elements are supposed to be active, yet without knowing their number and location in advance. We establish asymptotic properties of the estimator and investigate its unite sample performance along with simulation studies. We demonstrate the application of pFAR with the high-resolution natural gas flows in Germany, where the pFAR model provides insightful interpretation as well as good out-of-sample forecast accuracy. T3 - ZIB-Report - 19-34 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74880 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian ED - Cacchiani, Valentina ED - Marchetti-Spaccamela, Alberto T1 - New Perspectives on PESP: T-Partitions and Separators T2 - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time. Y1 - 2019 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2019.2 VL - 75 SP - 2:1 EP - 2:18 PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - JOUR A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann-Baum, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas JF - Optimization and Engineering N2 - Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s11081-020-09559-y VL - 22 SP - 687 EP - 734 PB - Springer Nature ET - 2 ER - TY - CHAP A1 - Euler, Ricardo A1 - Borndörfer, Ralf T1 - A Graph- and Monoid-based Framework for Price-Sensitive Routing in Local Public Transportation Networks T2 - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries. Y1 - 2019 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2019.12 VL - 75 SP - 12:1 EP - 12:15 ER - TY - JOUR A1 - Rössig, Ansgar A1 - Petkovic, Milena T1 - Advances in Verification of ReLU Neural Networks JF - Journal of Global Optimization N2 - We consider the problem of verifying linear properties of neural networks. Despite their success in many classification and prediction tasks, neural networks may return unexpected results for certain inputs. This is highly problematic with respect to the application of neural networks for safety-critical tasks, e.g. in autonomous driving. We provide an overview of algorithmic approaches that aim to provide formal guarantees on the behavior of neural networks. Moreover, we present new theoretical results with respect to the approximation of ReLU neural networks. On the other hand, we implement a solver for verification of ReLU neural networks which combines mixed integer programming (MIP) with specialized branching and approximation techniques. To evaluate its performance, we conduct an extensive computational study. For that we use test instances based on the ACAS Xu System and the MNIST handwritten digit data set. Our solver is publicly available and able to solve the verification problem for instances which do not have independent bounds for each input neuron. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-020-00949-1 PB - Springer ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Linear Programming using Limited-Precision Oracles JF - Mathematical Programming N2 - Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-019-01444-6 VL - 183 IS - 1-2 SP - 525 EP - 554 ER - TY - CHAP A1 - Beulertz, Daniel A1 - Charousset-Brignol, Sandrine A1 - Most, Dieter A1 - Giannelos, Spyros A1 - Yueksel-Erguen, Inci T1 - Development of a Modular Framework for Future Energy System Analysis T2 - 54th International Universities Power Engineering Conference (UPEC) N2 - This paper gives an overview of the modeling framework that is being developed within the Horizon2020 project plan4res. In the context of energy transition, integration of high shares of renewable energies will play a vital role for achieving the proposed climate targets. This brings new challenges to modeling tools, including data construction, implementation and solution techniques. In order to address these challenges, plan4res aims to create a well-structured and highly modular framework that will provide insights into the needs of future energy systems. An overview of the central modeling aspects is given in this paper. Finally, three case studies are presented that show the adequacy and relevance of the proposed optimization framework. Y1 - 2019 U6 - https://doi.org/10.1109/UPEC.2019.8893472 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of cycle inequalities in periodic timetabling JF - Discrete Optimization N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. Y1 - 2020 U6 - https://doi.org/10.1016/j.disopt.2019.100552 IS - 35 SP - 100552 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Lindner, Niels A1 - Roth, Sarah T1 - A Concurrent Approach to the Periodic Event Scheduling Problem JF - Journal of Rail Transport Planning & Management N2 - We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib. Y1 - 2020 U6 - https://doi.org/10.1016/j.jrtpm.2019.100175 SN - 2210-9706 IS - 15 SP - 100175 ER - TY - THES A1 - Rössig, Ansgar T1 - Verification of Neural Networks KW - Neural Network Verification Y1 - 2019 ER - TY - GEN A1 - Hoang, Nam-Dung A1 - Koch, Thorsten T1 - Steiner Tree Packing Revisited N2 - The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some “classical” STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality. T3 - ZIB-Report - 12-02 KW - Steiner tree packing KW - Integer Programming KW - grid graphs Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14625 SN - 1438-0064 ER - TY - GEN A1 - Breugem, Thomas A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Schulz, Christof T1 - A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements N2 - In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes. T3 - ZIB-Report - 19-43 KW - Crew Planning KW - Column Generation KW - Variable-Depth Neighborhood Search Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74297 SN - 1438-0064 ER - TY - GEN A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-Period Line Planning with Resource Transfers N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. T3 - ZIB-Report - 19-51 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74662 SN - 1438-0064 ER - TY - GEN A1 - Gotzes, Uwe A1 - Hoppmann, Kai T1 - Bounds for the final ranks during a round robin tournament T2 - Operational Research - An International Journal (ORIJ) N2 - This article answers two kinds of questions regarding the Bundesliga which is Germany's primary football (soccer) competition having the highest average stadium attendance worldwide. First "At any point of the season, what final rank will a certain team definitely reach?" and second "At any point of the season, what final rank can a certain team at most reach?". Although we focus especially on the Bundesliga, the models that we use to answer the two questions can easily be adopted to league systems that are similar to that of the Bundesliga. T3 - ZIB-Report - 19-50 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74638 ER - TY - THES A1 - Beckenbach, Isabel T1 - Matchings and Flows in Hypergraphs N2 - In this dissertation, we study matchings and flows in hypergraphs using combinatorial methods. These two problems are among the best studied in the field of combinatorial optimization. As hypergraphs are a very general concept, not many results on graphs can be generalized to arbitrary hypergraphs. Therefore, we consider special classes of hypergraphs, which admit more structure, to transfer results from graph theory to hypergraph theory. In Chapter 2, we investigate the perfect matching problem on different classes of hypergraphs generalizing bipartite graphs. First, we give a polynomial time approximation algorithm for the maximum weight matching problem on so-called partitioned hypergraphs, whose approximation factor is best possible up to a constant. Afterwards, we look at the theorems of König and Hall and their relation. Our main result is a condition for the existence of perfect matchings in normal hypergraphs that generalizes Hall’s condition for bipartite graphs. In Chapter 3, we consider perfect f-matchings, f-factors, and (g,f)-matchings. We prove conditions for the existence of (g,f)-matchings in unimodular hypergraphs, perfect f-matchings in uniform Mengerian hypergraphs, and f-factors in uniform balanced hypergraphs. In addition, we give an overview about the complexity of the (g,f)-matching problem on different classes of hypergraphs generalizing bipartite graphs. In Chapter 4, we study the structure of hypergraphs that admit a perfect matching. We show that these hypergraphs can be decomposed along special cuts. For graphs it is known that the resulting decomposition is unique, which does not hold for hypergraphs in general. However, we prove the uniqueness of this decomposition (up to parallel hyperedges) for uniform hypergraphs. In Chapter 5, we investigate flows on directed hypergraphs, where we focus on graph-based directed hypergraphs, which means that every hyperarc is the union of a set of pairwise disjoint ordinary arcs. We define a residual network, which can be used to decide whether a given flow is optimal or not. Our main result in this chapter is an algorithm that computes a minimum cost flow on a graph-based directed hypergraph. This algorithm is a generalization of the network simplex algorithm. N2 - Diese Arbeit untersucht Matchings und Flüsse in Hypergraphen mit Hilfe kombinatorischer Methoden. In Graphen gehören diese Probleme zu den grundlegendsten der kombinatorischen Optimierung. Viele Resultate lassen sich nicht von Graphen auf Hypergraphen verallgemeinern, da Hypergraphen ein sehr abstraktes Konzept bilden. Daher schauen wir uns bestimmte Klassen von Hypergraphen an, die mehr Struktur besitzen, und nutzen diese aus um Resultate aus der Graphentheorie zu übertragen. In Kapitel 2 betrachten wir das perfekte Matchingproblem auf Klassen von „bipartiten“ Hypergraphen, wobei es verschiedene Möglichkeiten gibt den Begriff „bipartit“ auf Hypergraphen zu definieren. Für sogenannte partitionierte Hypergraphen geben wir einen polynomiellen Approximationsalgorithmus an, dessen Gütegarantie bis auf eine Konstante bestmöglich ist. Danach betrachten wir die Sätze von Konig und Hall und untersuchen deren Zusammenhang. Unser Hauptresultat ist eine Bedingung für die Existenz von perfekten Matchings auf normalen Hypergraphen, die Halls Bedingung für bipartite Graphen verallgemeinert. Als Verallgemeinerung von perfekten Matchings betrachten wir in Kapitel 3 perfekte f-Matchings, f-Faktoren und (g, f)-Matchings. Wir beweisen Bedingungen für die Existenz von (g, f)-Matchings auf unimodularen Hypergraphen, perfekten f-Matchings auf uniformen Mengerschen Hypergraphen und f-Faktoren auf uniformen balancierten Hypergraphen. Außerdem geben wir eine Übersicht über die Komplexität des (g, f)-Matchingproblems auf verschiedenen Klassen von Hypergraphen an, die bipartite Graphen verallgemeinern. In Kapitel 4 untersuchen wir die Struktur von Hypergraphen, die ein perfektes Matching besitzen. Wir zeigen, dass diese Hypergraphen entlang spezieller Schnitte zerlegt werden können. Für Graphen weiß man, dass die so erhaltene Zerlegung eindeutig ist, was im Allgemeinen für Hypergraphen nicht zutrifft. Wenn man jedoch uniforme Hypergraphen betrachtet, dann liefert jede Zerlegung die gleichen unzerlegbaren Hypergraphen bis auf parallele Hyperkanten. Kapitel 5 beschäftigt sich mit Flüssen in gerichteten Hypergraphen, wobei wir Hypergraphen betrachten, die auf gerichteten Graphen basieren. Das bedeutet, dass eine Hyperkante die Vereinigung einer Menge von disjunkten Kanten ist. Wir definieren ein Residualnetzwerk, mit dessen Hilfe man entscheiden kann, ob ein gegebener Fluss optimal ist. Unser Hauptresultat in diesem Kapitel ist ein Algorithmus, um einen Fluss minimaler Kosten zu finden, der den Netzwerksimplex verallgemeinert. KW - Matchings KW - Balanced Hypergraphs KW - Normal Hypergraphs KW - Mengerian Hypergraphs KW - Factors KW - Tight Cuts KW - Network Flows Y1 - 2019 UR - http://nbn-resolving.de/urn:nbn:de:kobv:188-refubium-24385-6 ER - TY - JOUR A1 - Gotzes, Uwe T1 - Ein neuer Ansatz zur Optimierung des Bilanzausgleichs in einem Gasmarktgebiet JF - Zeitschrift für Energiewirtschaft N2 - Im BDEW/VKU/GEODE-Leitfaden Krisenvorsorge Gas ist zu lesen, dass als oberster Grundsatz zur Vermeidung von Versorgungsengpässen in Gasversorgungssystemen gilt, möglichst laufend einen Bilanzausgleich in allen Teilen des Netzes zu erreichen. Wir entwickeln Modelle zur Optimierung des laufenden Bilanzausgleichs. Als Gasversorgungssystem betrachten wir modellhaft die Fernleitungsnetze eines Marktgebiets. Als Teile des Gasversorgungssystems fassen wir vereinfachend die jeweiligen Netze der Fernleitungsnetzbetreiber auf. Die Optimierung erfolgt in zwei Schritten. Im ersten Schritt wird der optimale Einsatz netzbezogener Maßnahmen ermittelt. Beispiele für netzbezogene Maßnahmen sind die Nutzung von Netzpuffer und Mengenverlagerungen mit anderen Infrastrukturbetreibern. Falls sich die Bilanzen durch netzbezogene Maßnahmen nicht vollständig ausgleichen lassen, werden Fehlmengen angesetzt, die so gleichmäßig wie möglich auf die Teile des Netzes verteilt werden. Im zweiten Schritt werden die verbliebenen Fehlmengen, welche in der Regel durch marktbezogene Maßnahmen bereinigt werden, regulierungskonform auf möglichst große Teile des Gasversorgungssystems verteilt. Im Ergebnis erhalten wir ein transparentes, gerechtes, flexibel parametrier- und erweiterbares Verfahren, welches zyklisch im Dispatchingprozess eingesetzt werden kann, um die Integrität der Netze zu unterstützen. Dies wird an Beispielen verdeutlicht. Y1 - 2019 U6 - https://doi.org/10.1007/s12398-019-00257-6 ER - TY - JOUR A1 - Pulaj, Jonad T1 - Cutting planes for families implying Frankl's conjecture JF - Mathematics of Computation N2 - We find previously unknown families of sets which ensure Frankl's conjecture holds for all families that contain them using an algorithmic framework. The conjecture states that for any nonempty finite union-closed (UC) family there exists an element of the ground set in at least half the sets of the considered UC family. Poonen's Theorem characterizes the existence of weights which determine whether a given UC family implies the conjecture for all UC families which contain it. We design a cutting-plane method that computes the explicit weights which satisfy the existence conditions of Poonen's Theorem. This method enables us to answer several open questions regarding structural properties of UC families, including the construction of a counterexample to a conjecture of Morris from 2006. Y1 - 2019 U6 - https://doi.org/10.1090/mcom/3461 ER - TY - JOUR A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Fiand, Frederik A1 - Cao, Karl-Kiên A1 - Gils, Hans Christian A1 - Wetzel, Manuel A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Khabi, Dmitry T1 - BEAM-ME: Ein interdisziplinärer Beitrag zur Erreichung der Klimaziele JF - OR-News : das Magazin der GOR Y1 - 2019 IS - 66 SP - 6 EP - 8 ER -