TY - GEN A1 - Chmiela, Antonia A1 - Muñoz, Gonzalo A1 - Serrano, Felipe T1 - On the implementation and strengthening of intersection cuts for QCQPs N2 - The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments. KW - Intersection cuts KW - QCQPs KW - Quadratic-free sets Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79994 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 - GEN A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Dionísio, João A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Ghannam, Mohammed A1 - Gleixner, Ambros A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hedtke, Ivo A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Kamp, Dominik A1 - Koch, Thorsten A1 - Kofler, Kevin A1 - Lentz, Jurgen A1 - Manns, Julian A1 - Mexi, Gioni A1 - Mühmer, Erik A1 - E. Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Xu, Liding T1 - The SCIP Optimization Suite 9.0 N2 - 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. T3 - ZIB-Report - 24-02-29 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 KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-95528 SN - 1438-0064 ER - TY - GEN A1 - Vu, Thi Huong A1 - Litzel, Ida A1 - Koch, Thorsten T1 - Similarity-based fuzzy clustering scientific articles: potentials and challenges from mathematical and computational perspectives N2 - Fuzzy clustering, which allows an article to belong to multiple clusters with soft membership degrees, plays a vital role in analyzing publication data. This problem can be formulated as a constrained optimization model, where the goal is to minimize the discrepancy between the similarity observed from data and the similarity derived from a predicted distribution. While this approach benefits from leveraging state-of-the-art optimization algorithms, tailoring them to work with real, massive databases like OpenAlex or Web of Science -- containing about 70 million articles and a billion citations -- poses significant challenges. We analyze potentials and challenges of the approach from both mathematical and computational perspectives. Among other things, second-order optimality conditions are established, providing new theoretical insights, and practical solution methods are proposed by exploiting the problem’s structure. Specifically, we accelerate the gradient projection method using GPU-based parallel computing to efficiently handle large-scale data. T3 - ZIB-Report - 25-09 KW - bibliometrics KW - fuzzy clustering KW - large-scale publication data KW - non-convex optimization KW - second-order optimality KW - gradient projection methods KW - Nesterov acceleration KW - GPU-based parallel computing Y1 - 2025 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/10036 ER -