TY - GEN A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Gleixner, Ambros T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms N2 - 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. T3 - ZIB-Report - 19-15 KW - mixed-integer quadratically constrained programs KW - nonconvex KW - global optimization KW - separation KW - propagation KW - projection KW - bilinear terms Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72759 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gamrath, Gerald A1 - Salvagnin, Domenico T1 - Exploiting Dual Degeneracy in Branching N2 - Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average. T3 - ZIB-Report - 19-17 KW - mixed integer programming KW - branching rule KW - search strategy KW - dual degeneracy Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73028 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Computational Aspects of Infeasibility Analysis in Mixed Integer Programming N2 - The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress. T3 - ZIB-Report - 19-54 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74962 SN - 1438-0064 ER - TY - GEN A1 - Anderson, Daniel A1 - Hendel, Gregor A1 - Le Bodic, Pierre A1 - Viernickel, Jan Merlin T1 - Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation N2 - We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases. T3 - ZIB-Report - 19-11 KW - Mixed-Integer Programming solvers KW - Restart KW - Progress measures KW - tree-size estimates Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72653 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - Müller, Benjamin A1 - Weltge, Stefan T1 - Three Enhancements for Optimization-Based Bound Tightening N2 - 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. T3 - ZIB-Report - 15-16 KW - MINLP KW - optimization-based bound tightening KW - optimality-based bound tightening KW - OBBT KW - propagation KW - bound tightening Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57803 SN - 1438-0064 ER - TY - GEN A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework N2 - 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. T3 - ZIB-Report - 16-24 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59377 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP N2 - 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. T3 - ZIB-Report - 12-07 KW - Primal Heuristic KW - Mixed-Integer Nonlinear Programming KW - Large Neighborhood Search KW - Mixed-Integer Quadratically Constrained Programming KW - Nonconvex Optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14631 SN - 1438-0064 ER - TY - THES A1 - Gleixner, Ambros T1 - Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming N2 - 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. Y1 - 2015 UR - http://dx.doi.org/10.14279/depositonce-4938 SN - 978-3-8325-4190-3 PB - Logos Verlag Berlin ER - TY - GEN A1 - Gleixner, Ambros A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gemander, Patrick A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 5.0 N2 - 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. T3 - ZIB-Report - 17-61 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66297 SN - 1438-0064 ER - TY - JOUR A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming JF - Mathematical Programming Computation N2 - Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP. Y1 - 2018 ER -