Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen OPUS4-1138 Masterarbeit / Diplomarbeit Gleixner, Ambros Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of Möhring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05% gap of the optimum. 2009 urn:nbn:de:0297-zib-11389 Mathematical Optimization OPUS4-1150 misc Bley, Andreas; Gleixner, Ambros; Koch, Thorsten; Vigerske, Stefan Comparing MIQCP solvers to a specialised algorithm for mine production scheduling In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm. 2009 urn:nbn:de:0297-zib-11507 10.1007/978-3-642-25707-0 Mathematical Optimization OPUS4-1295 misc Koch, Thorsten; Achterberg, Tobias; Andersen, Erling; Bastert, Oliver; Berthold, Timo; Bixby, Robert E.; Danna, Emilie; Gamrath, Gerald; Gleixner, Ambros; Heinz, Stefan; Lodi, Andrea; Mittelmann, Hans; Ralphs, Ted; Salvagnin, Domenico; Steffy, Daniel; Wolter, Kati MIPLIB 2010 This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic. 2010 urn:nbn:de:0297-zib-12953 10.1007/s12532-011-0025-9 Mathematical Optimization OPUS4-1803 misc Berthold, Timo; Gleixner, Ambros Undercover Branching In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved. 2013 urn:nbn:de:0297-zib-18030 10.1007/978-3-642-38527-8_20 Mathematical Optimization OPUS4-1463 misc Berthold, Timo; Gleixner, Ambros Undercover: a primal MINLP heuristic exploring a largest sub-MIP We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. 2012 urn:nbn:de:0297-zib-14631 10.1007/s10107-013-0635-2 Mathematical Optimization OPUS4-1634 misc Gleixner, Ambros Factorization and update of a reduced basis matrix for the revised simplex method In this paper, we describe a method to enhance the FTRAN and BTRAN operations in the revised simplex algorithm by using a reduced basis matrix defined by basic columns and nonbasic rows. This submatrix of the standard basis matrix is potentially much smaller, but may change its dimension dynamically from iteration to iteration. For the classical product form update ("eta update"), the idea has been noted already by Zoutendijk, but only preliminarily tested by Powell in the early 1970s. We extend these ideas to Forrest-Tomlin type update formulas for an LU factorization of the reduced basis matrix, which are suited for efficient implementation within a state-of-the-art simplex solver. The computational advantages of the proposed method apply to pure LP solving as well as to LP-based branch-and-cut algorithms. It can easily be integrated into existing simplex codes. 2012 urn:nbn:de:0297-zib-16349 Mathematical Optimization OPUS4-1763 misc Gleixner, Ambros; Weltge, Stefan Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming 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. 2013 urn:nbn:de:0297-zib-17631 10.1007/978-3-642-38171-3_26 Mathematical Optimization OPUS4-1775 misc Berthold, Timo; Gleixner, Ambros; Heinz, Stefan; Vigerske, Stefan Analyzing the computational impact of MIQCP solver components We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. 2013 urn:nbn:de:0297-zib-17754 10.3934/naco.2012.2.739 Mathematical Optimization OPUS4-2993 Wissenschaftlicher Artikel Boland, Natashia; Dumitrescu, Irina; Froyland, Gary; Gleixner, Ambros LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity 2009 25 Computers & Operations Research 36 1064 1089 Mathematical Optimization OPUS4-2994 Masterarbeit / Diplomarbeit Gleixner, Ambros Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming 2008 Mathematical Optimization OPUS4-4749 Wissenschaftlicher Artikel Berthold, Timo; Gleixner, Ambros Undercover: a primal MINLP heuristic exploring a largest sub-MIP We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. 2014 31 Mathematical Programming 144 1-2 315 346 10.1007/s10107-013-0635-2 Mathematical Optimization OPUS4-5750 Konferenzveröffentlichung Gamrath, Gerald; Melchiori, Anna; Berthold, Timo; Gleixner, Ambros; Salvagnin, Domenico Branching on Multi-aggregated Variables In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. 2015 15 Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015 9075 141 156 10.1007/978-3-319-18008-3_10 Mathematical Optimization OPUS4-5771 Konferenzveröffentlichung Cao, Karl-Kiên; Gleixner, Ambros; Miltenberger, Matthias Methoden zur Reduktion der Rechenzeit linearer Optimierungsmodelle in der Energiewirtschaft - Eine Performance-Analyse Dieser Beitrag stellt mögliche Ansätze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ansätze bilden im Allgemeinen die Grundlage für konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien zählt die Verkleinerung der Modelldimensionen, was beispielsweise durch Ändern der zeitlichen, räumlichen oder technologischen Auflösung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar häufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivität werden jedoch meist nicht durchgeführt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Größenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verkürzte Betrachtungszeiträume das größte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-Lösungsverfahrens mit multiplen Threads unter Vernachlässigung des Cross-Over. 2016 EnInnov 2016: 14. Symposium Energieinnovation 2016 Mathematical Optimization OPUS4-6104 misc Cheung, Kevin K. H.; Gleixner, Ambros; Steffy, Daniel Verifying Integer Programming Results Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates. 2016 urn:nbn:de:0297-zib-61044 10.1007/978-3-319-59250-3_13 Mathematical Optimization OPUS4-6110 misc Gamrath, Gerald; Gleixner, Ambros; Koch, Thorsten; Miltenberger, Matthias; Kniasew, Dimitri; Schlögel, Dominik; Martin, Alexander; Weninger, Dieter Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. 2016 urn:nbn:de:0297-zib-61107 10.4208/jcm.1905-m2019-0055 Mathematical Optimization OPUS4-5969 Wissenschaftlicher Artikel Gleixner, Ambros; Berthold, Timo; Müller, Benjamin; Weltge, Stefan Three Enhancements for Optimization-Based Bound Tightening Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT. 2017 26 Journal of Global Optimization 67 4 731 757 10.1007/s10898-016-0450-4 Mathematical Optimization OPUS4-6408 Wissenschaftlicher Artikel Vigerske, Stefan; Gleixner, Ambros SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. 2018 30 Optimization Methods & Software 33 3 563 593 10.1080/10556788.2017.1335312 Mathematical Optimization OPUS4-4818 Wissenschaftlicher Artikel Berthold, Timo; Gleixner, Ambros; Heinz, Stefan; Vigerske, Stefan Analyzing the computational impact of MIQCP solver components We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. 2012 9 Numerical Algebra, Control and Optimization 2 4 739 748 10.3934/naco.2012.2.739 Mathematical Optimization OPUS4-4819 Konferenzveröffentlichung Gleixner, Ambros; Weltge, Stefan Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming 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. 2013 6 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 7874 355 361 10.1007/978-3-642-38171-3_26 Mathematical Optimization OPUS4-4820 Konferenzveröffentlichung Berthold, Timo; Gleixner, Ambros Bonifaci, Vincenzo; Demetrescu, Camil; Marchetti-Spaccamela, Alberto Undercover Branching In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved. 2013 11 Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013, Proceedings 7933 212 223 10.1007/978-3-642-38527-8_20 Mathematical Optimization OPUS4-4821 Konferenzveröffentlichung Berthold, Timo; Gleixner, Ambros; Heinz, Stefan; Koch, Thorsten; Shinano, Yuji SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる. 2012 27 Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming 165 192 Mathematical Optimization OPUS4-4760 Konferenzveröffentlichung Bley, Andreas; Gleixner, Ambros; Koch, Thorsten; Vigerske, Stefan Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm. 2012 14 Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam 25 39 10.1007/978-3-642-25707-0_3 Mathematical Optimization OPUS4-4840 Konferenzveröffentlichung Gleixner, Ambros; Steffy, Daniel; Wolter, Kati Improving the Accuracy of Linear Programming Solvers with Iterative Refinement 2012 7 ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation 187 194 10.1145/2442829.2442858 Mathematical Optimization OPUS4-4845 Konferenzveröffentlichung Berthold, Timo; Gleixner, Ambros Bonami, Pierre; Liberti, Leo; Miller, Andrew J.; Sartenaer, Annick Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib. 2010 9 Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, April 12-16, 2010, Marseilles, France 103 112 Mathematical Optimization OPUS4-4891 Wissenschaftlicher Artikel Gleixner, Ambros; Held, Harald; Huang, Wei; Vigerske, Stefan Towards globally optimal operation of water supply networks This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms. In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem. 2012 16 Numerical Algebra, Control and Optimization 2 4 695 711 10.3934/naco.2012.2.695 Mathematical Optimization OPUS4-3264 Wissenschaftlicher Artikel Koch, Thorsten; Achterberg, Tobias; Andersen, Erling; Bastert, Oliver; Berthold, Timo; Bixby, Robert E.; Danna, Emilie; Gamrath, Gerald; Gleixner, Ambros; Heinz, Stefan; Lodi, Andrea; Mittelmann, Hans; Ralphs, Ted; Salvagnin, Domenico; Steffy, Daniel; Wolter, Kati MIPLIB 2010 2011 60 Mathematical Programming Computation 3 2 103 163 10.1007/s12532-011-0025-9 Mathematical Optimization OPUS4-1559 misc Berthold, Timo; Gleixner, Ambros; Heinz, Stefan; Koch, Thorsten; Shinano, Yuji SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる. 2012 urn:nbn:de:0297-zib-15598 Mathematical Optimization OPUS4-1560 misc Gleixner, Ambros; Held, Harald; Huang, Wei; Vigerske, Stefan Towards globally optimal operation of water supply networks This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms. In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem. 2012 urn:nbn:de:0297-zib-15603 10.3934/naco.2012.2.695 Mathematical Optimization OPUS4-1565 misc Berthold, Timo; Gamrath, Gerald; Gleixner, Ambros; Heinz, Stefan; Koch, Thorsten; Shinano, Yuji Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development. 2012 urn:nbn:de:0297-zib-15654 Mathematical Optimization OPUS4-5937 misc Vigerske, Stefan; Gleixner, Ambros SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. 2016 urn:nbn:de:0297-zib-59377 10.1080/10556788.2017.1335312 Mathematical Optimization OPUS4-5911 Konferenzveröffentlichung D'Andreagiovanni, Fabio; Gleixner, Ambros Towards an accurate solution of wireless network design problems The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models. 2016 12 Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016 135 147 10.1007/978-3-319-45587-7_12 Mathematical Optimization OPUS4-5887 Dissertation Gleixner, Ambros Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming Mixed-integer nonlinear programming (MINLP) comprises the broad class of finite-dimensional mathematical optimization problems from mixed-integer linear programming and global optimization. The combination of the two disciplines allows us to construct more accurate models of real-world systems, while at the same time it increases the algorithmic challenges that come with solving them. This thesis presents new methods that improve the numerical reliability and the computational performance of global MINLP solvers. Since state-of-the-art algorithms for nonconvex MINLP fundamentally rely on solving linear programming (LP) relaxations, we address numerical accuracy directly for LP by means of LP iterative refinement: a new algorithm to solve linear programs to arbitrarily high levels of precision. The thesis is supplemented by an exact extension of the LP solver SoPlex, which proves on average 1.85 to 3 times faster than current state-of-the-art software for solving general linear programs exactly over the rational numbers. These methods can be generalized to quadratic programming. We study their application to numerically difficult multiscale LP models for metabolic networks in systems biology. To improve the computational performance of LP-based MINLP solvers, we show how the expensive, but effective, bound-tightening technique called optimization-based bound tightening can be approximated more efficiently via feasibility-based bound tightening. The resulting implementation increases the number of instances that can be solved and reduces the average running time of the MINLP solver SCIP by 17-19% on hard mixed-integer nonlinear programs. Last, we present branching rules that exploit the presence of nonlinear integer variables, i.e., variables both contained in nonlinear terms and required to be integral. The new branching rules prefer integer variables when performing spatial branching, and favor variables in nonlinear terms when resolving integer infeasibility. They reduce the average running time of SCIP by 17% on affected instances. Most importantly, all of the new methods enable us to solve problems which could not be solved before, either due to their numerical complexity or because of limited computing resources. Logos Verlag Berlin 2015 341 978-3-8325-4190-3 Mathematical Optimization OPUS4-5889 Wissenschaftlicher Artikel Gleixner, Ambros; Steffy, Daniel; Wolter, Kati Iterative Refinement for Linear Programming We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. 2016 15 INFORMS Journal on Computing 28 3 449 464 10.1287/ijoc.2016.0692 Mathematical Optimization OPUS4-5382 misc Gamrath, Gerald; Melchiori, Anna; Berthold, Timo; Gleixner, Ambros; Salvagnin, Domenico Branching on multi-aggregated variables In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. 2015 urn:nbn:de:0297-zib-53829 10.1007/978-3-319-18008-3_10 Mathematical Optimization OPUS4-5511 misc Gleixner, Ambros; Steffy, Daniel; Wolter, Kati Iterative Refinement for Linear Programming We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. 2015 urn:nbn:de:0297-zib-55118 10.1287/ijoc.2016.0692 Mathematical Optimization OPUS4-6836 misc Georges, Alexander; Gleixner, Ambros; Gojic, Gorana; Gottwald, Robert Lion; Haley, David; Hendel, Gregor; Matejczyk, Bartlomiej Feature-Based Algorithm Selection for Mixed Integer Programming Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented. 2018 urn:nbn:de:0297-zib-68362 Mathematical Optimization OPUS4-7432 misc Rehfeldt, Daniel; Hobbie, Hannes; Schönheit, David; Gleixner, Ambros; Koch, Thorsten; Möst, Dominik A massively parallel interior-point solver for linear energy system models with block structure Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market clearing. It has been widely applied in the literature on energy system analyses during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models. 2019 urn:nbn:de:0297-zib-74321 Mathematical Optimization OPUS4-7407 Konferenzveröffentlichung Gleixner, Ambros; Kempke, Nils-Christian; Koch, Thorsten; Rehfeldt, Daniel; Uslu, Svenja First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix. 1 Springer International Publishing 2020 XV, 819 Operations Research Proceedings 2019 105 111 10.1007/978-3-030-48439-2_13 Mathematical Optimization OPUS4-7408 misc Gleixner, Ambros; Kempke, Nils-Christian; Koch, Thorsten; Rehfeldt, Daniel; Uslu, Svenja First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix. 2019 urn:nbn:de:0297-zib-74084 10.1007/978-3-030-48439-2_13 Mathematical Optimization OPUS4-7459 Wissenschaftlicher Artikel Breuer, Thomas; Bussieck, Michael; Fiand, Frederik; Cao, Karl-Kiên; Gils, Hans Christian; Wetzel, Manuel; Gleixner, Ambros; Koch, Thorsten; Rehfeldt, Daniel; Khabi, Dmitry BEAM-ME: Ein interdisziplinärer Beitrag zur Erreichung der Klimaziele 2019 2 OR-News : das Magazin der GOR 66 6 8 Mathematical Optimization OPUS4-7840 Wissenschaftlicher Artikel Serrano, Felipe; Schwarz, Robert; Gleixner, Ambros On the relation between the extended supporting hyperplane algorithm and Kelley's cutting plane algorithm Recently, Kronqvist et al. (J Global Optim 64(2):249-272, 2016) rediscovered the supporting hyperplane algorithm of Veinott (Oper Res 15(1):147-152, 1967) and demonstrated its computational benefits for solving convex mixed integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm (J Soc Ind Appl Math 8(4):703-712, 1960) applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by a class of general, not necessarily convex nor differentiable, functions. 2020 18 Journal of Global Optimization 78 161 179 10.1007/s10898-020-00906-y Mathematical Optimization OPUS4-7804 Wissenschaftlicher Artikel Gleixner, Ambros; Hendel, Gregor; Gamrath, Gerald; Achterberg, Tobias; Bastubbe, Michael; Berthold, Timo; Christophel, Philipp M.; Jarck, Kati; Koch, Thorsten; Linderoth, Jeff; Lübbecke, Marco; Mittelmann, Hans; Ozyurt, Derya; Ralphs, Ted; Salvagnin, Domenico; Shinano, Yuji MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data. 2021 47 Mathematical Programming Computation 13 3 443 490 10.1007/s12532-020-00194-3 Mathematical Optimization OPUS4-7806 Wissenschaftlicher Artikel Gamrath, Gerald; Gleixner, Ambros; Koch, Thorsten; Miltenberger, Matthias; Kniasew, Dimitri; Schlögel, Dominik; Martin, Alexander; Weninger, Dieter Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP. 2019 22 Journal of Computational Mathematics 37 866 888 10.4208/jcm.1905-m2019-0055 Mathematical Optimization OPUS4-7531 misc Gleixner, Ambros; Steffy, Daniel Linear Programming using Limited-Precision Oracles 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. 2019 urn:nbn:de:0297-zib-75316 10.1007/s10107-019-01444-6 Mathematical Optimization OPUS4-7532 Wissenschaftlicher Artikel Gleixner, Ambros; Steffy, Daniel Linear Programming using Limited-Precision Oracles 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. 2020 29 Mathematical Programming 183 1-2 525 554 10.1007/s10107-019-01444-6 Mathematical Optimization OPUS4-7592 Konferenzveröffentlichung Devriendt, Jo; Gleixner, Ambros; Nordström, Jakob Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search Conflict-driven Pseudo-Boolean (PB) solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though PB solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear program (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven PB search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis over linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best of two worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut. Springer 2020 NaN Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020 12296 xxiv xxvi Mathematical Optimization OPUS4-7594 Konferenzveröffentlichung Müller, Benjamin; Muñoz, Gonzalo; Gasse, Maxime; Gleixner, Ambros; Lodi, Andrea; Serrano, Felipe On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments. 2020 15 Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020 322 337 10.1007/978-3-030-45771-6_25 Mathematical Optimization OPUS4-7325 misc Serrano, Felipe; Schwarz, Robert; Gleixner, Ambros On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley's Cutting Plane Algorithm Recently, Kronqvist et al. (2016) rediscovered the supporting hyperplane algorithm of Veinott (1967) and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by general, not necessarily convex, differentiable functions that satisfy a mild condition. 2019 urn:nbn:de:0297-zib-73253 Mathematical Optimization OPUS4-7212 Konferenzveröffentlichung Gleixner, Ambros; Steffy, Daniel Linear Programming using Limited-Precision Oracles Linear programming is a foundational tool for many aspects of integer and combinatorial optimization. This work studies the complexity of solving linear programs exactly over the rational numbers through use of an oracle capable of returning limited-precision LP solutions. 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. Previous work has often considered oracles that provide solutions of an arbitrary specified precision. While this leads to polynomial-time algorithms, the level of precision required is often unrealistic for practical computation. In contrast, our work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly. 2019 13 A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019 399 412 10.1007/978-3-030-17953-3_30 Mathematical Optimization OPUS4-7276 Wissenschaftlicher Artikel Müller, Benjamin; Serrano, Felipe; Gleixner, Ambros Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly. 2020 27 SIAM Journal on Optimization 30 2 1339 1365 urn:nbn:de:0297-zib-72767 10.1137/19M1249825 Mathematical Optimization OPUS4-6752 Konferenzveröffentlichung Breuer, Thomas; Bussieck, Michael; Cao, Karl-Kien; Cebulla, Felix; Fiand, Frederik; Gils, Hans Christian; Gleixner, Ambros; Khabi, Dmitry; Koch, Thorsten; Rehfeldt, Daniel; Wetzel, Manuel Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described. Springer International Publishing 2018 6 Operations Research Proceedings 2017 641 647 10.1007/978-3-319-89920-6_85 Mathematical Optimization OPUS4-6754 Konferenzveröffentlichung Cheung, Kevin K. H.; Gleixner, Ambros; Steffy, Daniel Verifying Integer Programming Results Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates. 2017 12 F. Eisenbrand and J. Koenemann, eds., Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017 10328 148 160 10.1007/978-3-319-59250-3_13 Mathematical Optimization OPUS4-7024 misc Eifler, Leon; Gleixner, Ambros; Pulaj, Jonad Chvátal's Conjecture Holds for Ground Sets of Seven Elements 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. 2018 urn:nbn:de:0297-zib-70240 Mathematical Optimization OPUS4-6814 Wissenschaftlicher Artikel Weber, Tobias; Sager, Sebastian; Gleixner, Ambros Solving Quadratic Programs to High Precision using Scaled Iterative Refinement Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library. Springer Berlin Heidelberg 2019 34 Mathematical Programming Computation 11 421 455 10.1007/s12532-019-00154-6 Mathematical Optimization OPUS4-6815 misc Weber, Tobias; Sager, Sebastian; Gleixner, Ambros Solving Quadratic Programs to High Precision using Scaled Iterative Refinement Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library. 2018 urn:nbn:de:0297-zib-68152 10.1007/s12532-019-00154-6 Mathematical Optimization OPUS4-6755 Wissenschaftlicher Artikel Furini, Fabio; Traversi, Emiliano; Belotti, Pietro; Frangioni, Antonio; Gleixner, Ambros; Gould, Nick; Liberti, Leo; Lodi, Andrea; Misener, Ruth; Mittelmann, Hans; Sahinidis, Nikolaos V.; Vigerske, Stefan; Wiegele, Angelika QPLIB: A Library of Quadratic Programming Instances This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very diverse class of problems, comprising sub-classes of problems ranging from trivial to undecidable. This diversity is reflected in the variety of solution methods for QP, ranging from entirely combinatorial ones to completely continuous ones, including many for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the many different interested communities is therefore important. We propose a simple taxonomy for QP instances that leads to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents. 2019 28 Mathematical Programming Computation 11 2 237 265 10.1007/s12532-018-0147-4 Mathematical Optimization OPUS4-7517 misc Müller, Benjamin; Muñoz, Gonzalo; Gasse, Maxime; Gleixner, Ambros; Lodi, Andrea; Serrano, Felipe On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments. 2019 urn:nbn:de:0297-zib-75179 Mathematical Optimization OPUS4-7275 misc Müller, Benjamin; Serrano, Felipe; Gleixner, Ambros Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly. 2019 urn:nbn:de:0297-zib-72759 Mathematical Optimization OPUS4-8182 misc Bestuzheva, Ksenia; Gleixner, Ambros; Vigerske, Stefan A Computational Study of Perspective Cuts The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. 2021 urn:nbn:de:0297-zib-81821 Mathematical Algorithmic Intelligence OPUS4-6618 misc Breuer, Thomas; Bussieck, Michael; Cao, Karl-Kien; Cebulla, Felix; Fiand, Frederik; Gils, Hans Christian; Gleixner, Ambros; Khabi, Dmitry; Koch, Thorsten; Rehfeldt, Daniel; Wetzel, Manuel Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described. 2017 urn:nbn:de:0297-zib-66183 10.1007/978-3-319-89920-6_85 Mathematical Optimization OPUS4-6449 Wissenschaftlicher Artikel Gleixner, Ambros; Maher, Stephen; Müller, Benjamin; Pedroso, João Pedro Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature. Springer US 2020 28 Annals of Operations Research 284 2 527 555 10.1007/s10479-018-3115-5 Mathematical Optimization OPUS4-5780 misc Gleixner, Ambros; Berthold, Timo; Müller, Benjamin; Weltge, Stefan Three Enhancements for Optimization-Based Bound Tightening Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT. 2016 urn:nbn:de:0297-zib-57803 10.1007/s10898-016-0450-4 Mathematical Optimization OPUS4-1545 misc Gleixner, Ambros; Steffy, Daniel; Wolter, Kati Improving the Accuracy of Linear Programming Solvers with Iterative Refinement We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We demonstrate that this algorithm is effective in practice for computing extended precision solutions and that this leads to direct improvement of the best known methods for solving LPs exactly over the rational numbers. 2012 urn:nbn:de:0297-zib-15451 10.1145/2442829.2442858 Mathematical Optimization OPUS4-1163 misc Berthold, Timo; Gleixner, Ambros Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib. 2009 urn:nbn:de:0297-zib-11632 Mathematical Optimization OPUS4-1199 misc Berthold, Timo; Gleixner, Ambros; Heinz, Stefan; Vigerske, Stefan On the computational impact of MIQCP solver components We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. 2011 urn:nbn:de:0297-zib-11998 Mathematical Optimization OPUS4-8795 Konferenzveröffentlichung Bestuzheva, Ksenia; Gleixner, Ambros; Völker, Helena Strengthening SONC Relaxations with Constraints Derived from Variable Bounds Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches. 2022 3 Proceedings of the Hungarian Global Optimization Workshop HUGO 2022 41 44 Mathematical Optimization OPUS4-6203 misc Gleixner, Ambros; Maher, Stephen J.; Müller, Benjamin; Pedroso, João Pedro Exact Methods for Recursive Circle Packing Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature. 2017 urn:nbn:de:0297-zib-62039 10.1007/s10479-018-3115-5 Mathematical Optimization OPUS4-7220 misc Witzig, Jakob; Gleixner, Ambros Conflict-Driven Heuristics for Mixed Integer Programming Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l. 2019 urn:nbn:de:0297-zib-72204 10.1287/ijoc.2020.0973 Mathematical Optimization OPUS4-6035 misc Witzig, Jakob; Beckenbach, Isabel; Eifler, Leon; Fackeldey, Konstantin; Gleixner, Ambros; Grever, Andreas; Weber, Marcus Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. 2016 urn:nbn:de:0297-zib-60353 10.1137/16M1091162 Numerical Mathematics OPUS4-6029 Wissenschaftlicher Artikel Witzig, Jakob; Beckenbach, Isabel; Eifler, Leon; Fackeldey, Konstantin; Gleixner, Ambros; Grever, Andreas; Weber, Marcus Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. 2018 17 Multiscale Modeling and Simulation 16 1 248 265 10.1137/16M1091162 Numerical Mathematics OPUS4-9015 misc Eifler, Leon; Gleixner, Ambros Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. 2023 urn:nbn:de:0297-zib-90159 AI in Society, Science, and Technology OPUS4-9143 Wissenschaftlicher Artikel Bestuzheva, Ksenia; Gleixner, Ambros; Vigerske, Stefan A Computational Study of Perspective Cuts The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. 2023 28 Mathematical Programming Computation 15 703 731 10.1007/s12532-023-00246-4 AI in Society, Science, and Technology OPUS4-9133 Konferenzveröffentlichung Bestuzheva, Ksenia; Gleixner, Ambros; Achterberg, Tobias Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods. Springer, Cham 2023 14 Integer Programming and Combinatorial Optimization. IPCO 2023. 13904 14 28 10.1007/978-3-031-32726-1_2 AI in Society, Science, and Technology OPUS4-8444 misc Eifler, Leon; Gleixner, Ambros; Pulaj, Jonad A Safe Computational Framework for Integer Programming applied to Chvátal's Conjecture We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chvátal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result we are able to provide a first machine-assisted proof that Chvátal's conjecture holds for all downsets whose union of sets contains seven elements or less. 2021 urn:nbn:de:0297-zib-84444 AI in Society, Science, and Technology OPUS4-8445 Konferenzveröffentlichung Sofranac, Boro; Gleixner, Ambros; Pokutta, Sebastian An Algorithm-Independent Measure of Progress for Linear Constraint Propagation 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. 2021 NaN 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) 210 52:1 52:17 10.4230/LIPIcs.CP.2021.52 Mathematical Optimization OPUS4-8439 Wissenschaftlicher Artikel Eifler, Leon; Gleixner, Ambros; Pulaj, Jonad A Safe Computational Framework for Integer Programming applied to Chvátal's Conjecture We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs.The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chvátal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result we are able to provide a first machine-assisted proof that Chvátal's conjecture holds for all downsets whose union of sets contains seven elements or less. 2022 ACM Transactions on Mathematical Software 48 2 10.1145/3485630 AI in Society, Science, and Technology OPUS4-8191 Wissenschaftlicher Artikel Rehfeldt, Daniel; Hobbie, Hannes; Schönheit, David; Koch, Thorsten; Möst, Dominik; Gleixner, Ambros A massively parallel interior-point solver for LPs with generalized arrowhead structure, and applications to energy system models Linear energy system models are a crucial component of energy system design and operations, as well as energy policy consulting. If detailed enough, such models lead to large-scale linear programs, which can be intractable even for the best state-of-the-art solvers. This article introduces an interior-point solver that exploits common structures of energy system models to efficiently run in parallel on distributed-memory systems. The solver is designed for linear programs with doubly-bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. In order to handle the large number of linking constraints and variables commonly observed in energy system models, a distributed Schur complement preconditioner is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the solver PIPS-IPM. We evaluate the computational performance on energy system models with up to four billion nonzero entries in the constraint matrix—and up to one billion columns and one billion rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market-clearing. It has been widely applied in the literature on energy system analyses in recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models. 2022 11 European Journal of Operational Research 296 1 60 71 10.1016/j.ejor.2021.06.063 Applied Algorithmic Intelligence Methods OPUS4-8622 Konferenzveröffentlichung Breuer, Thomas; Bussieck, Michael; Cao, Karl-Kien; Fiand, Fred; Gils, Hans-Christian; Gleixner, Ambros; Khabi, Dmitry; Kempke, Nils; Koch, Thorsten; Rehfeldt, Daniel; Wetzel, Manuel BEAM-ME: Accelerating Linear Energy Systems Models by a Massively Parallel Interior Point Method 2020 7 NIC Symposium 2020 50 345 352 AI in Society, Science, and Technology OPUS4-8960 Konferenzveröffentlichung Chmiela, Antonia; Gleixner, Ambros; Lichocki, Pawel; Pokutta, Sebastian Online Learning for Scheduling MIP Heuristics Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4%. Springer, Cham 2023 9 Integration of Constraint Programming, Artificial Intelligence, and Operations Research 13884 114 123 10.1007/978-3-031-33271-5_8 Mathematical Optimization OPUS4-8894 Wissenschaftlicher Artikel Šofranac, Boro; Gleixner, Ambros; Pokutta, Sebastian An Algorithm-independent Measure of Progress for Linear Constraint Propagation 2022 23 Constraints 27 432 455 10.1007/s10601-022-09338-9 Mathematical Algorithmic Intelligence OPUS4-9014 Wissenschaftlicher Artikel Eifler, Leon; Gleixner, Ambros Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. 2023 SIAM Journal on Optimization AI in Society, Science, and Technology OPUS4-8128 Wissenschaftlicher Artikel Eifler, Leon; Gleixner, Ambros A Computational Status Update for Exact Rational Mixed Integer Programming The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours. 2021 Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021 10.1007/978-3-030-73879-2_12 AI in Society, Science, and Technology OPUS4-8547 Wissenschaftlicher Artikel Eifler, Leon; Gleixner, Ambros A computational status update for exact rational mixed integer programming The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours. Springer 2022 Mathematical Programming 10.1007/s10107-021-01749-5 AI in Society, Science, and Technology OPUS4-8452 Konferenzveröffentlichung Chmiela, Antonia; Khalil, Elias B.; Gleixner, Ambros; Lodi, Andrea; Pokutta, Sebastian Learning to Schedule Heuristics in Branch and Bound Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances. 2021 Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021 AI in Society, Science, and Technology OPUS4-8549 Wissenschaftlicher Artikel Šofranac, Boro; Gleixner, Ambros; Pokutta, Sebastian Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices • Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances. 2022 Parallel Computing 109 102874 10.1016/j.parco.2021.102874 Mathematical Optimization OPUS4-8056 Konferenzveröffentlichung Sofranac, Boro; Gleixner, Ambros; Pokutta, Sebastian Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances. 2020 10 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3) 1 11 10.1109/IA351965.2020.00007 Mathematical Optimization OPUS4-8620 Wissenschaftlicher Artikel Bonami, Pierre; Gleixner, Ambros; Linderoth, Jeff; Misener, Ruth Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081) Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms. 2018 23 Dagstuhl Reports 8 2 64 87 10.4230/DagRep.8.2.64 AI in Society, Science, and Technology OPUS4-7805 Wissenschaftlicher Artikel Witzig, Jakob; Gleixner, Ambros Conflict-Driven Heuristics for Mixed Integer Programming Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l. 2020 14 INFORMS Journal on Computing 33 2 706 720 10.1287/ijoc.2020.0973 Mathematical Optimization OPUS4-8129 misc Eifler, Leon; Gleixner, Ambros A Computational Status Update for Exact Rational Mixed Integer Programming The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours. 2021 urn:nbn:de:0297-zib-81298 AI in Society, Science, and Technology OPUS4-8830 misc Bestuzheva, Ksenia; Gleixner, Ambros; Völker, Helena Strengthening SONC Relaxations with Constraints Derived from Variable Bounds Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches. 2022 urn:nbn:de:0297-zib-88306 Mathematical Optimization OPUS4-8625 Wissenschaftlicher Artikel Müller, Benjamin; Muñoz, Gonzalo; Gasse, Maxime; Gleixner, Ambros; Lodi, Andrea; Serrano, Felipe On generalized surrogate duality in mixed-integer nonlinear programming The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global ϵ-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments. 2022 29 Mathematical Programming 192 1 89 118 10.1007/s10107-021-01691-6 AI in Society, Science, and Technology OPUS4-8951 misc Bestuzheva, Ksenia; Völker, Helena; Gleixner, Ambros Strengthening SONC Relaxations with Constraints Derived from Variable Bounds Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set. 2023 urn:nbn:de:0297-zib-89510 Mathematical Optimization OPUS4-8153 Wissenschaftlicher Artikel Gemander, Patrick; Chen, Wei-Kun; Weninger, Dieter; Gottwald, Leona; Gleixner, Ambros Two-row and two-column mixed-integer presolve using hashing-based pairing methods In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP. 2020 35 EURO Journal on Computational Optimization 8 3-4 205 240 10.1007/s13675-020-00129-6 AI in Society, Science, and Technology OPUS4-8064 Wissenschaftlicher Artikel Devriendt, Jo; Gleixner, Ambros; Nordström, Jakob Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best-of-both-worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut. 2021 29 Constraints 26 26 55 10.1007/s10601-020-09318-x Mathematical Algorithmic Intelligence OPUS4-9135 Konferenzveröffentlichung Mexi, Gioni; Berthold, Timo; Gleixner, Ambros; Nordström, Jakob Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities. In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving. We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming. Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2023 NaN 29th International Conference on Principles and Practice of Constraint Programming (CP 2023) 280 27:1 27:19 10.4230/LIPIcs.CP.2023.27 AI in Society, Science, and Technology OPUS4-9257 misc Eifler, Leon; Nicolas-Thouvenin, Jules; Gleixner, Ambros Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary. We compare the practical performance of the resulting algorithm with both puremethods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach, while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero, while maintaining the speed of the pure LP iterative refinement approach. 2023 urn:nbn:de:0297-zib-92573 AI in Society, Science, and Technology OPUS4-9256 Wissenschaftlicher Artikel Eifler, Leon; Nicolas-Thouvenin, Jules; Gleixner, Ambros Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary. We compare the practical performance of the resulting algorithm with both puremethods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach, while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero, while maintaining the speed of the pure LP iterative refinement approach. 2023 AI in Society, Science, and Technology OPUS4-6217 misc Maher, Stephen J.; Fischer, Tobias; Gally, Tristan; Gamrath, Gerald; Gleixner, Ambros; Gottwald, Robert Lion; Hendel, Gregor; Koch, Thorsten; Lübbecke, Marco; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schenker, Sebastian; Schwarz, Robert; Serrano, Felipe; Shinano, Yuji; Weninger, Dieter; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 4.0 The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences. 2017 urn:nbn:de:0297-zib-62170 Mathematical Optimization OPUS4-5767 misc Gamrath, Gerald; Fischer, Tobias; Gally, Tristan; Gleixner, Ambros; Hendel, Gregor; Koch, Thorsten; Maher, Stephen J.; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schenker, Sebastian; Schwarz, Robert; Serrano, Felipe; Shinano, Yuji; Vigerske, Stefan; Weninger, Dieter; Winkler, Michael; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 3.2 The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs. 2016 urn:nbn:de:0297-zib-57675 Mathematical Optimization OPUS4-8530 misc Bestuzheva, Ksenia; Besançon, Mathieu; Chen, Wei-Kun; Chmiela, Antonia; Donkiewicz, Tim; van Doornmalen, Jasper; Eifler, Leon; Gaul, Oliver; Gamrath, Gerald; Gleixner, Ambros; Gottwald, Leona; Graczyk, Christoph; Halbig, Katrin; Hoen, Alexander; Hojny, Christopher; van der Hulst, Rolf; Koch, Thorsten; Lübbecke, Marco; Maher, Stephen J.; Matter, Frederic; Mühmer, Erik; Müller, Benjamin; Pfetsch, Marc E.; Rehfeldt, Daniel; Schlein, Steffan; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Sofranac, Boro; Turner, Mark; Vigerske, Stefan; Wegscheider, Fabian; Wellner, Philipp; Weninger, Dieter; Witzig, Jakob The SCIP Optimization Suite 8.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack. 2021 urn:nbn:de:0297-zib-85309 AI in Society, Science, and Technology OPUS4-7802 misc Gamrath, Gerald; Anderson, Daniel; Bestuzheva, Ksenia; Chen, Wei-Kun; Eifler, Leon; Gasse, Maxime; Gemander, Patrick; Gleixner, Ambros; Gottwald, Leona; Halbig, Katrin; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Le Bodic, Pierre; Maher, Stephen J.; Matter, Frederic; Miltenberger, Matthias; Mühmer, Erik; Müller, Benjamin; Pfetsch, Marc; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Tawfik, Christine; Vigerske, Stefan; Wegscheider, Fabian; Weninger, Dieter; Witzig, Jakob The SCIP Optimization Suite 7.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders' decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders' decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP. 2020 urn:nbn:de:0297-zib-78023 Mathematical Optimization OPUS4-6629 misc Gleixner, Ambros; Eifler, Leon; Gally, Tristan; Gamrath, Gerald; Gemander, Patrick; Gottwald, Robert Lion; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Viernickel, Jan Merlin; Vigerske, Stefan; Weninger, Dieter; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 5.0 This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG. 2017 urn:nbn:de:0297-zib-66297 Mathematical Optimization OPUS4-6936 misc Gleixner, Ambros; Bastubbe, Michael; Eifler, Leon; Gally, Tristan; Gamrath, Gerald; Gottwald, Robert Lion; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Lübbecke, Marco; Maher, Stephen J.; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schlösser, Franziska; Schubert, Christoph; Serrano, Felipe; Shinano, Yuji; Viernickel, Jan Merlin; Walter, Matthias; Wegscheider, Fabian; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 6.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP. 2018 urn:nbn:de:0297-zib-69361 Mathematical Optimization OPUS4-8838 Wissenschaftlicher Artikel Gleixner, Ambros; Gottwald, Leona; Hoen, Alexander PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support Presolving has become an essential component of modern mixed integer program (MIP) solvers, both in terms of computational performance and numerical robustness. In this paper, we present PaPILO, a new C++ header-only library that provides a large set of presolving routines for MIP and linear programming problems from the literature. The creation of PaPILO was motivated by the current lack of (a) solver-independent implementations that (b) exploit parallel hardware and (c) support multiprecision arithmetic. Traditionally, presolving is designed to be fast. Whenever necessary, its low computational overhead is usually achieved by strict working limits. PaPILO's parallelization framework aims at reducing the computational overhead also when presolving is executed more aggressively or is applied to large-scale problems. To rule out conflicts between parallel presolve reductions, PaPILO uses a transaction-based design. This helps to avoid both the memory-intensive allocation of multiple copies of the problem and special synchronization between presolvers. Additionally, the use of Intel's Threading Building Blocks library aids PaPILO in efficiently exploiting recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. We provide an overview of PaPILO's capabilities and insights into important design choices. 2023 12 INFORMS Journal on Computing 35 6 1329 1341 10.1287/ijoc.2022.0171 Mathematical Optimization OPUS4-5901 misc D'Andreagiovanni, Fabio; Gleixner, Ambros Towards an accurate solution of wireless network design problems The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models. 2016 urn:nbn:de:0297-zib-59010 Mathematical Optimization OPUS4-9271 Konferenzveröffentlichung Mexi, Gioni; Besançon, Mathieu; Bolusani, Suresh; Chmiela, Antonia; Hoen, Alexander; Gleixner, Ambros Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization 2023 Proceedings of Conference of the Society for Operations Research in Germany AI in Society, Science, and Technology OPUS4-9405 Wissenschaftlicher Artikel Bestuzheva, Ksenia; Besançon, Mathieu; Chen, Wei-Kun; Chmiela, Antonia; Donkiewicz, Tim; Doornmalen, Jasper; Eifler, Leon; Gaul, Oliver; Gamrath, Gerald; Gleixner, Ambros; Gottwald, Leona; Graczyk, Christoph; Halbig, Katrin; Hoen, Alexander; Hojny, Christopher; Hulst, Rolf; Koch, Thorsten; Lübbecke, Marco; Maher, Stephen J.; Matter, Frederic; Mühmer, Erik; Müller, Benjamin; Pfetsch, Marc; Rehfeldt, Daniel; Schlein, Steffan; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Sofranac, Boro; Turner, Mark; Vigerske, Stefan; Wegscheider, Fabian; Wellner, Philipp; Weninger, Dieter; Witzig, Jakob Enabling research through the SCIP optimization suite 8.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP. 2023 20 ACM Transactions on Mathematical Software 49 2 1 21 10.1145/3585516 AI in Society, Science, and Technology OPUS4-9407 Wissenschaftlicher Artikel Eifler, Leon; Gleixner, Ambros A computational status update for exact rational mixed integer programming The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours. 2023 19 Mathematical Programming 197 793 812 10.1007/s10107-021-01749-5 AI in Society, Science, and Technology OPUS4-9434 Konferenzveröffentlichung Gasse, Maxime; Bowly, Simon; Cappart, Quentin; Charfreitag, Jonas; Charlin, Laurent; Chételat, Didier; Chmiela, Antonia; Dumouchelle, Justin; Gleixner, Ambros; Kazachkov, Aleksandr M.; Khalil, Elias; Lichocki, Pawel; Lodi, Andrea; Lubin, Miles; Maddison, Chris J.; Christopher, Morris; Papageorgiou, Dimitri J.; Parjadis, Augustin; Pokutta, Sebastian; Prouvost, Antoine; Scavuzzo, Lara; Zarpellon, Giulia; Yang, Linxin; Lai, Sha; Wang, Akang; Luo, Xiaodong; Zhou, Xiang; Huang, Haohan; Shao, Shengcheng; Zhu, Yuanming; Zhang, Dong; Quan, Tao; Cao, Zixuan; Xu, Yang; Huang, Zhewei; Zhou, Shuchang; Binbin, Chen; Minggui, He; Hao, Hao; Zhiyu, Zhang; Zhiwu, An; Kun, Mao The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights 2022 Proceedings of Conference on Neural Information Processing Systems AI in Society, Science, and Technology OPUS4-9552 misc Bolusani, Suresh; Besançon, Mathieu; Bestuzheva, Ksenia; Chmiela, Antonia; Dionísio, João; Donkiewicz, Tim; van Doornmalen, Jasper; Eifler, Leon; Ghannam, Mohammed; Gleixner, Ambros; Graczyk, Christoph; Halbig, Katrin; Hedtke, Ivo; Hoen, Alexander; Hojny, Christopher; van der Hulst, Rolf; Kamp, Dominik; Koch, Thorsten; Kofler, Kevin; Lentz, Jurgen; Manns, Julian; Mexi, Gioni; Mühmer, Erik; E. Pfetsch, Marc; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Turner, Mark; Vigerske, Stefan; Weninger, Dieter; Xu, Liding The SCIP Optimization Suite 9.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver. 2024 urn:nbn:de:0297-zib-95528 AI in Society, Science, and Technology OPUS4-9485 Konferenzveröffentlichung Ghannam, Mohammed; Gleixner, Ambros Hybrid genetic search for dynamic vehicle routing with time windows 2023 Proceedings of Conference of the Society for Operations Research in Germany AI in Society, Science, and Technology OPUS4-9486 Konferenzveröffentlichung Hoen, Alexander; Oertel, Andy; Gleixner, Ambros; Nordström, Jakob Certifying MIP-based presolve reductions for 0-1 integer linear programs 2024 Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research AI in Society, Science, and Technology OPUS4-9484 Wissenschaftlicher Artikel Eifler, Leon; Gleixner, Ambros Safe and verified Gomory mixed integer cuts in a rational MIP framework 2024 SIAM Journal on Optimization AI in Society, Science, and Technology