TY - GEN A1 - Gamrath, Gerald A1 - Anderson, Daniel A1 - Bestuzheva, Ksenia A1 - Chen, Wei-Kun A1 - Eifler, Leon A1 - Gasse, Maxime A1 - Gemander, Patrick A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Halbig, Katrin A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Le Bodic, Pierre A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Miltenberger, Matthias A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Tawfik, Christine A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 7.0 N2 - 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. T3 - ZIB-Report - 20-10 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78023 SN - 1438-0064 ER - TY - GEN A1 - Serrano, Felipe T1 - Visible points, the separation problem, and applications to MINLP N2 - In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{visible points} of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide. T3 - ZIB-Report - 19-38 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74016 SN - 1438-0064 ER - TY - JOUR A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Gleixner, Ambros T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms JF - SIAM Journal on Optimization 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. Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72767 VL - 30 IS - 2 SP - 1339 EP - 1365 ER - 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 - Serrano, Felipe A1 - Schwarz, Robert A1 - Gleixner, Ambros T1 - On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm N2 - 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. T3 - ZIB-Report - 19-18 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73253 SN - 1438-0064 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 - CHAP A1 - Serrano, Felipe T1 - Intersection cuts for factorable MINLP T2 - A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019 N2 - Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-17953-3_29 VL - 11480 SP - 385 EP - 398 ER - TY - GEN A1 - Serrano, Felipe T1 - Intersection cuts for factorable MINLP N2 - Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables. T3 - ZIB-Report - 18-59 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71105 SN - 1438-0064 ER - TY - CHAP A1 - Serrano, Felipe A1 - Muñoz, Gonzalo T1 - Maximal Quadratic-Free Sets T2 - Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020 N2 - The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we show how to construct maximal S-free sets when S is defined as a general quadratic inequality. Our maximal S-free sets are such that efficient separation of a vertex in LP-based approaches to quadratically constrained problems is guaranteed. To the best of our knowledge, this work is the first to provide maximal quadratic-free sets. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-45771-6_24 SP - 307 EP - 321 ER - TY - GEN 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 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. T3 - ZIB-Report - 19-55 KW - surrogate relaxation KW - MINLP KW - nonconvex optimization Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75179 SN - 1438-0064 ER -