@inproceedings{GleixnerWeltge2013, author = {Gleixner, Ambros and Weltge, Stefan}, title = {Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming}, volume = {7874}, booktitle = {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}, doi = {10.1007/978-3-642-38171-3_26}, pages = {355 -- 361}, year = {2013}, abstract = {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.}, language = {en} } @inproceedings{GleixnerSteffyWolter2012, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Improving the Accuracy of Linear Programming Solvers with Iterative Refinement}, booktitle = {ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation}, doi = {10.1145/2442829.2442858}, pages = {187 -- 194}, year = {2012}, language = {en} } @article{RaackKosterOrlowskietal.2011, author = {Raack, Christian and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {On cut-based inequalities for capacitated network design polyhedra}, volume = {57}, journal = {Networks}, number = {2}, pages = {141 -- 156}, year = {2011}, language = {en} } @inproceedings{SofranacGleixnerPokutta2021, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, volume = {210}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, doi = {10.4230/LIPIcs.CP.2021.52}, pages = {52:1 -- 52:17}, year = {2021}, abstract = {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.}, language = {en} } @article{FrankChiLauSzabo2008, author = {Frank, A. and Chi Lau, L. and Szab{\´o}, J{\´a}cint}, title = {A note on degree-constrained subgraphs}, volume = {308}, journal = {Discrete Mathematics}, number = {12}, publisher = {Elsevier}, pages = {2647 -- 2648}, year = {2008}, language = {en} } @misc{Eifler2017, type = {Master Thesis}, author = {Eifler, Leon}, title = {Mixed-Integer Programming for Clustering in Non-reversible Markov Processes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66486}, pages = {74}, year = {2017}, abstract = {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.}, language = {en} } @misc{EiflerGleixnerPulaj2018, author = {Eifler, Leon and Gleixner, Ambros and Pulaj, Jonad}, title = {Chv{\´a}tal's Conjecture Holds for Ground Sets of Seven Elements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70240}, year = {2018}, abstract = {We establish a general computational framework for Chv{\´a}tal's conjecture based on exact rational integer programming. As a result we prove Chv{\´a}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.}, language = {en} } @incollection{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Der junge Albring und Schwelm}, booktitle = {Der Forscher und der Zweifler - Werner Albring zum 90. Geburtstag}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {11 -- 35}, year = {2005}, 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} } @incollection{GroetschelKochHoang2010, author = {Gr{\"o}tschel, Martin and Koch, Thorsten and Hoang, Nam-Dung}, title = {Lagenwechsel minimieren - oder das Bohren von L{\"o}chern in Leiterplatten}, booktitle = {Besser als Mathe}, editor = {Biermann, Katja and Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, publisher = {Vieweg+Teubner}, doi = {10.1007/978-3-658-01004-1_19}, pages = {161 -- 174}, year = {2010}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche}, volume = {58}, booktitle = {Kosmos und Zahl - Beitr{\"a}ge zur Mathematik- und Astronomiegeschichte, zu Alexander von Humboldt und Leibniz}, editor = {Hecht, Hartmut and Mikosch, Regina and Schwarz, Ingo and Siebert, Harald and Werther, Romy}, publisher = {Franz Steiner Verlag}, pages = {331 -- 346}, year = {2008}, language = {en} } @incollection{GroetschelLuegger2007, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Die Wissenschaftsgalaxis}, booktitle = {eUniversity - Update Bologna}, editor = {Keil, Reinhard and Kerres, Michael and Schulmeister, Rolf}, publisher = {Waxmann Verlag}, pages = {335 -- 354}, year = {2007}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Geistiges Eigentum - Eine Zusammenfassung der vorgetragenen Standpunkte}, volume = {Heft 7}, booktitle = {Geistiges Eigentum - Streitgespr{\"a}che in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {89 -- 95}, year = {2008}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Geistiges Eigentum - Einf{\"u}hrung in das Thema}, volume = {Heft 7}, booktitle = {Geistiges Eigentum - Streitgespr{\"a}che in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {9 -- 14}, year = {2008}, language = {en} } @incollection{Groetschel2007, author = {Gr{\"o}tschel, Martin}, title = {Schnelle Rundreisen}, booktitle = {Kombinatorische Optimierung erleben - In Studium und Unterricht}, editor = {Hußmann, Stephan and Lutz-Westphal, Brigitte}, publisher = {Vieweg}, address = {Wiesbaden}, pages = {95 -- 128}, year = {2007}, language = {en} } @misc{Groetschel2007, author = {Gr{\"o}tschel, Martin}, title = {Das Problem mit der Komplexit{\"a}t}, journal = {Kombinatorische Optimierung erleben - In Studium und Unterricht}, editor = {Hußmann, Stephan and Lutz-Westphal, Brigitte}, publisher = {Vieweg}, address = {Wiesbaden}, doi = {10.1007/978-3-8348-9120-4_9}, pages = {265 -- 274}, year = {2007}, language = {en} } @incollection{Groetschel2004, author = {Gr{\"o}tschel, Martin}, title = {Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes}, booktitle = {The Sharpest Cut}, editor = {Gr{\"o}tschel, Martin}, publisher = {MPS-SIAM}, pages = {99 -- 120}, year = {2004}, language = {en} } @incollection{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {In der Mathematik sind sich alle einig und die Gesellschaft hat von ihr nichts zu bef{\"u}rchten}, volume = {2}, booktitle = {Wissenschaft Kontrovers}, publisher = {Chronos, Edition Collegium Helveticum}, address = {Z{\"u}rich}, year = {2005}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Ohne x is nix}, volume = {14}, booktitle = {Berichte und Abhandlungen}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Akademie-Verlag}, address = {Berlin}, pages = {195 -- 219}, year = {2008}, language = {en} } @misc{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche: Bemerkungen zur Algorithmengeschichte}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9628}, number = {08-23}, year = {2008}, abstract = {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{\"a}ftigte, wurde mir bewusst, wie schwierig dieses „Gesch{\"a}ft" ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in fr{\"u}heren Zeiten kennen. Man muss zus{\"a}tzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen" war, insbesondere, was seinerzeit g{\"u}ltige Beweisideen und -schritte waren, und daher damals keiner pr{\"a}zisen Definition oder Einf{\"u}hrung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies m{\"o}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{\"a}gliches Leben oft von funktionierenden Algorithmen abh{\"a}ngt. Daher w{\"a}re eine bessere Kenntnis der Algorithmengeschichte von großem Interesse.}, language = {de} } @misc{GroetschelLutzWestphal2008, author = {Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, title = {Diskrete Mathematik und ihre Anwendungen: Auf dem Weg zu authentischem Mathematikunterricht}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10758}, number = {08-21}, year = {2008}, abstract = {Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. k{\"o}nnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale B{\"u}rger"' weiss davon nichts, der Schulunterricht k{\"o}nnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zug{\"a}nglich. Solche Anwendungen, die zus{\"a}tzlich noch der Lebensumwelt der Sch{\"u}ler zugeh{\"o}ren, k{\"o}nnen dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die L{\"o}sung praktischer Fragen, anschaulich zu erl{\"a}utern. Gerade in der diskreten Mathematik k{\"o}nnen hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenst{\"a}ndiges Entdecken der Sch{\"u}ler entwickelt werden. Wir beginnen mit einigen Beispielen.}, language = {de} } @article{HoppmannBaum2021, author = {Hoppmann-Baum, Kai}, title = {On the Complexity of Computing Maximum and Minimum Min-Cost-Flows}, journal = {Networks}, doi = {10.1002/net.22060}, year = {2021}, abstract = {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.}, language = {en} } @incollection{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {679 -- 704}, year = {2001}, language = {en} } @incollection{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {705 -- 729}, year = {2001}, language = {en} } @misc{GroetschelRaackWerner2013, author = {Gr{\"o}tschel, Martin and Raack, Christian and Werner, Axel}, title = {Towards optimizing the deployment of optical access networks}, issn = {1438-0064}, doi = {10.1007/s13675-013-0016-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18627}, year = {2013}, abstract = {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.}, language = {en} } @misc{Groetschel2012, author = {Gr{\"o}tschel, Martin}, title = {Einblicke in die Diskrete Mathematik}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14399}, number = {12-01}, year = {2012}, abstract = {„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{\"u}hren, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu ber{\"u}cksichtigen. Die Sch{\"u}ler und Sch{\"u}lerinnen werden daf{\"u}r dankbar sein - eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde.}, language = {de} } @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{GroetschelNeumann2012, author = {Gr{\"o}tschel, Martin and Neumann, Gerald}, title = {10 Jahre TELOTA}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14799}, number = {12-13}, year = {2012}, abstract = {Das TELOTA-Projekt - zun{\"a}chst nur f{\"u}r zwei Jahre gestartet - feierte am 15. Juni 2011 sein 10-j{\"a}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 {\"O}ffentlichkeit finden. Die TELOTA-Aktivit{\"a}ten haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen, gehen aber weit {\"u}ber reinen Service hinaus. Sie beeinflussen die Forschung selbst und f{\"u}hren zu neuen interessanten wissenschaftlichen Fragestellungen. Der R{\"u}ckblick auf die ersten zehn Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben, was bisher geleistet wurde.}, language = {de} } @misc{GroetschelNemhauser2007, author = {Gr{\"o}tschel, Martin and Nemhauser, George}, title = {George Dantzig's contributions to integer programming}, issn = {1438-0064}, doi = {10.1016/j.disopt.2007.08.003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10393}, number = {07-39}, year = {2007}, abstract = {This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem}, language = {en} } @incollection{GroetschelFonsecaDavis2001, author = {Gr{\"o}tschel, Martin and Fonseca, Irene and Davis, Mark}, title = {The Impact of Mathematical Research on Industry and Vice Versa}, booktitle = {Mathematical Glimpses into the 21st Century}, editor = {Casacuberta, Carles and Mir{\´o}-Roig, Rosa and Ortega, Joaqu{\´i}n and Xamb{\´o}-Descamps, Sebasti{\`a}}, edition = {First}, publisher = {Societat Catalana de Matem{\`a}tiques and Centro Internacional de M{\´e}todos Num{\´e}ricos en Ingenier{\´i}a}, address = {Barcelona, Spain}, pages = {35 -- 53}, year = {2001}, language = {en} } @incollection{GroetschelLoebelVoelker1997, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, booktitle = {Mathematik}, editor = {Hoffmann, Karl-Heinz and J{\"a}ger, Willi and Lohmann, Thomas and Schunck (Hrsg.), Hermann}, publisher = {Springer}, pages = {609 -- 624}, year = {1997}, language = {en} } @misc{MaherRalphsShinano2019, author = {Maher, Stephen J. and Ralphs, Ted and Shinano, Yuji}, title = {Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74702}, year = {2019}, abstract = {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.}, language = {en} } @misc{ChenKochXu2019, author = {Chen, Ying and Koch, Thorsten and Xu, Xiaofei}, title = {Regularized partially functional autoregressive model with application to high-resolution natural gas forecasting in Germany}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74880}, year = {2019}, abstract = {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.}, language = {en} } @inproceedings{LindnerLiebchen2019, author = {Lindner, Niels and Liebchen, Christian}, title = {New Perspectives on PESP: T-Partitions and Separators}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2019.2}, pages = {2:1 -- 2:18}, year = {2019}, abstract = {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.}, language = {en} } @article{HenningsAndersonHoppmannBaumetal.2021, author = {Hennings, Felix and Anderson, Lovis and Hoppmann-Baum, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, volume = {22}, journal = {Optimization and Engineering}, edition = {2}, publisher = {Springer Nature}, doi = {https://doi.org/10.1007/s11081-020-09559-y}, pages = {687 -- 734}, year = {2021}, abstract = {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.}, language = {en} } @inproceedings{EulerBorndoerfer2019, author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf}, title = {A Graph- and Monoid-based Framework for Price-Sensitive Routing in Local Public Transportation Networks}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, doi = {10.4230/OASIcs.ATMOS.2019.12}, pages = {12:1 -- 12:15}, year = {2019}, abstract = {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.}, language = {en} } @article{RoessigPetkovic2020, author = {R{\"o}ssig, Ansgar and Petkovic, Milena}, title = {Advances in Verification of ReLU Neural Networks}, journal = {Journal of Global Optimization}, publisher = {Springer}, doi = {10.1007/s10898-020-00949-1}, year = {2020}, abstract = {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.}, language = {en} } @article{GleixnerSteffy2020, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, volume = {183}, journal = {Mathematical Programming}, number = {1-2}, doi = {10.1007/s10107-019-01444-6}, pages = {525 -- 554}, year = {2020}, abstract = {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.}, language = {en} } @inproceedings{BeulertzCharoussetBrignolMostetal.2019, author = {Beulertz, Daniel and Charousset-Brignol, Sandrine and Most, Dieter and Giannelos, Spyros and Yueksel-Erguen, Inci}, title = {Development of a Modular Framework for Future Energy System Analysis}, booktitle = {54th International Universities Power Engineering Conference (UPEC)}, doi = {10.1109/UPEC.2019.8893472}, year = {2019}, abstract = {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.}, language = {en} } @article{BorndoerferHoppmannKarbsteinetal.2020, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of cycle inequalities in periodic timetabling}, journal = {Discrete Optimization}, number = {35}, doi = {10.1016/j.disopt.2019.100552}, pages = {100552}, year = {2020}, abstract = {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.}, language = {en} } @article{BorndoerferLindnerRoth2020, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, journal = {Journal of Rail Transport Planning \& Management}, number = {15}, issn = {2210-9706}, doi = {10.1016/j.jrtpm.2019.100175}, pages = {100175}, year = {2020}, abstract = {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.}, language = {en} } @misc{Roessig2019, type = {Master Thesis}, author = {R{\"o}ssig, Ansgar}, title = {Verification of Neural Networks}, pages = {143}, year = {2019}, language = {en} } @misc{HoangKoch2012, author = {Hoang, Nam-Dung and Koch, Thorsten}, title = {Steiner Tree Packing Revisited}, issn = {1438-0064}, doi = {10.1007/s00186-012-0391-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14625}, number = {12-02}, year = {2012}, abstract = {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.}, language = {en} } @misc{BreugemBorndoerferSchlechteetal.2019, author = {Breugem, Thomas and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Schulz, Christof}, title = {A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74297}, year = {2019}, abstract = {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.}, language = {en} } @misc{SahinAhmadiBorndoerferetal.2019, author = {Sahin, Guvenc and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Multi-Period Line Planning with Resource Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74662}, year = {2019}, abstract = {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.}, language = {en} } @misc{GotzesHoppmann2019, author = {Gotzes, Uwe and Hoppmann, Kai}, title = {Bounds for the final ranks during a round robin tournament}, journal = {Operational Research - An International Journal (ORIJ)}, doi = {https://doi.org/10.1007/s12351-020-00546-w}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74638}, year = {2019}, abstract = {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.}, language = {en} } @phdthesis{Beckenbach2019, author = {Beckenbach, Isabel}, title = {Matchings and Flows in Hypergraphs}, year = {2019}, abstract = {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{\"o}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.}, language = {en} } @article{Gotzes2019, author = {Gotzes, Uwe}, title = {Ein neuer Ansatz zur Optimierung des Bilanzausgleichs in einem Gasmarktgebiet}, journal = {Zeitschrift f{\"u}r Energiewirtschaft}, doi = {10.1007/s12398-019-00257-6}, year = {2019}, abstract = {Im BDEW/VKU/GEODE-Leitfaden Krisenvorsorge Gas ist zu lesen, dass als oberster Grundsatz zur Vermeidung von Versorgungsengp{\"a}ssen in Gasversorgungssystemen gilt, m{\"o}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{\"u}r netzbezogene Maßnahmen sind die Nutzung von Netzpuffer und Mengenverlagerungen mit anderen Infrastrukturbetreibern. Falls sich die Bilanzen durch netzbezogene Maßnahmen nicht vollst{\"a}ndig ausgleichen lassen, werden Fehlmengen angesetzt, die so gleichm{\"a}ßig wie m{\"o}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{\"o}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{\"a}t der Netze zu unterst{\"u}tzen. Dies wird an Beispielen verdeutlicht.}, language = {de} } @article{Pulaj2019, author = {Pulaj, Jonad}, title = {Cutting planes for families implying Frankl's conjecture}, journal = {Mathematics of Computation}, doi = {10.1090/mcom/3461}, year = {2019}, abstract = {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.}, language = {en} } @article{BreuerBussieckFiandetal.2019, author = {Breuer, Thomas and Bussieck, Michael and Fiand, Frederik and Cao, Karl-Ki{\^e}n and Gils, Hans Christian and Wetzel, Manuel and Gleixner, Ambros and Koch, Thorsten and Rehfeldt, Daniel and Khabi, Dmitry}, title = {BEAM-ME: Ein interdisziplin{\"a}rer Beitrag zur Erreichung der Klimaziele}, journal = {OR-News : das Magazin der GOR}, number = {66}, pages = {6 -- 8}, year = {2019}, language = {de} }