TY - CHAP A1 - Berthold, Timo A1 - Gleixner, Ambros ED - Bonami, Pierre ED - Liberti, Leo ED - Miller, Andrew J. ED - Sartenaer, Annick T1 - Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering T2 - Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, April 12-16, 2010, Marseilles, France N2 - 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. Y1 - 2010 SP - 103 EP - 112 ER - TY - CHAP A1 - Bley, Andreas A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Vigerske, Stefan T1 - Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling T2 - Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam N2 - 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. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-25707-0_3 SP - 25 EP - 39 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Völker, Helena A1 - Gleixner, Ambros T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds N2 - 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. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89510 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering N2 - 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. T3 - ZIB-Report - 09-40 KW - MINLP KW - MIQCP KW - Primalheuristik KW - Nachbarschaftssuche KW - Mengenüberdeckung KW - mixed-integer nonlinear programming KW - MIQCP KW - primal heuristic KW - large neighborhood search KW - set covering Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11632 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Weltge, Stefan T1 - Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming N2 - Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times. T3 - ZIB-Report - 13-04 KW - MINLP KW - optimization-based bound tightening KW - optimality-based bound tightening KW - OBBT KW - propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17631 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components N2 - 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. T3 - ZIB-Report - 13-08 KW - mixed-integer quadratically constrained programming KW - mixed-integer programming KW - branch-and-cut KW - nonconvex KW - global optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17754 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Improving the Accuracy of Linear Programming Solvers with Iterative Refinement N2 - 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. T3 - ZIB-Report - 12-19 KW - Linear programming KW - Iterative refinement KW - Exact linear programming Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15451 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Vigerske, Stefan T1 - Comparing MIQCP solvers to a specialised algorithm for mine production scheduling N2 - 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. T3 - ZIB-Report - 09-32 Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11507 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover Branching N2 - 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. T3 - ZIB-Report - 13-14 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18030 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros T1 - Factorization and update of a reduced basis matrix for the revised simplex method N2 - 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. T3 - ZIB-Report - 12-36 Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16349 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - On the computational impact of MIQCP solver components N2 - 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. T3 - ZIB-Report - 11-01 KW - MIQCP KW - MIP KW - mixed-integer quadratically constrained programming KW - computational KW - nonconvex Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11998 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Völker, Helena T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds N2 - 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. T3 - ZIB-Report - 22-23 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88306 SN - 1438-0064 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Hoen, Alexander T1 - PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support JF - INFORMS Journal on Computing N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1287/ijoc.2022.0171 VL - 35 IS - 6 SP - 1329 EP - 1341 ER - TY - CHAP A1 - Müller, Benjamin A1 - Muñoz, Gonzalo A1 - Gasse, Maxime A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Serrano, Felipe T1 - On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming T2 - Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020 N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-45771-6_25 SP - 322 EP - 337 ER - TY - JOUR A1 - Serrano, Felipe A1 - Schwarz, Robert A1 - Gleixner, Ambros T1 - On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm JF - Journal of Global Optimization N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-020-00906-y VL - 78 SP - 161 EP - 179 ER - TY - GEN A1 - Witzig, Jakob A1 - Gleixner, Ambros T1 - Conflict-Driven Heuristics for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 19-08 KW - mixed integer programming; primal heuristics; conflict analysis; branch-and-bound Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72204 SN - 1438-0064 ER - TY - CHAP A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Völker, Helena T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds T2 - Proceedings of the Hungarian Global Optimization Workshop HUGO 2022 N2 - 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. Y1 - 2022 SP - 41 EP - 44 ER - TY - GEN A1 - Gleixner, Ambros A1 - Maher, Stephen J. A1 - Müller, Benjamin A1 - Pedroso, João Pedro T1 - Exact Methods for Recursive Circle Packing N2 - 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. T3 - ZIB-Report - 17-07 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62039 ER - TY - GEN A1 - Cheung, Kevin K. H. A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Verifying Integer Programming Results N2 - 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. T3 - ZIB-Report - 16-58 KW - correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61044 SN - 1438-0064 ER - TY - CHAP A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Cao, Karl-Kien A1 - Cebulla, Felix A1 - Fiand, Frederik A1 - Gils, Hans Christian A1 - Gleixner, Ambros A1 - Khabi, Dmitry A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Wetzel, Manuel T1 - Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods T2 - Operations Research Proceedings 2017 N2 - 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. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_85 SP - 641 EP - 647 PB - Springer International Publishing ER - TY - JOUR A1 - Furini, Fabio A1 - Traversi, Emiliano A1 - Belotti, Pietro A1 - Frangioni, Antonio A1 - Gleixner, Ambros A1 - Gould, Nick A1 - Liberti, Leo A1 - Lodi, Andrea A1 - Misener, Ruth A1 - Mittelmann, Hans A1 - Sahinidis, Nikolaos V. A1 - Vigerske, Stefan A1 - Wiegele, Angelika T1 - QPLIB: A Library of Quadratic Programming Instances JF - Mathematical Programming Computation N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1007/s12532-018-0147-4 VL - 11 IS - 2 SP - 237 EP - 265 ER -