TY - GEN ED - COMPASS '18, T1 - Two Approximate Dynamic Programming Algorithms for Managing Complete SIS Networks N2 - Inspired by the problem of best managing the invasive mosquito Aedes albopictus across the 17 Torres Straits islands of Australia, we aim at solving a Markov decision process on large Susceptible-Infected-Susceptible (SIS) networks that are highly connected. While dynamic programming approaches can solve sequential decision-making problems on sparsely connected networks, these approaches are intractable for highly connected networks. Inspired by our case study, we focus on problems where the probability of nodes changing state is low and propose two approximate dynamic programming approaches. The first approach is a modified version of value iteration where only those future states that are similar to the current state are accounted for. The second approach models the state space as continuous instead of binary, with an on-line algorithm that takes advantage of Bellman's adapted equation. We evaluate the resulting policies through simulations and provide a priority order to manage the 17 infested Torres Strait islands. Both algorithms show promise, with the continuous state approach being able to scale up to high dimensionality (50 nodes). This work provides a successful example of how AI algorithms can be designed to tackle challenging computational sustainability problems. Y1 - 2018 SN - 978-1-4503-5816-3 U6 - https://doi.org/10.1145/3209811.3209814 PB - ACM New York, NY, USA ER - 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 -