TY - GEN A1 - Fackeldey, Konstantin A1 - Röblitz, Susanna A1 - Scharkoi, Olga A1 - Weber, Marcus T1 - Soft Versus Hard Metastable Conformations in Molecular Simulations N2 - Particle methods have become indispensible in conformation dynamics to compute transition rates in protein folding, binding processes and molecular design, to mention a few. Conformation dynamics requires at a decomposition of a molecule's position space into metastable conformations. In this paper, we show how this decomposition can be obtained via the design of either ``soft'' or ``hard'' molecular conformations. We show, that the soft approach results in a larger metastabilitiy of the decomposition and is thus more advantegous. This is illustrated by a simulation of Alanine Dipeptide. T3 - ZIB-Report - 11-27 KW - Proteins, Conformation Space, Meshfree Methods Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13189 ER - TY - GEN A1 - Tunga, Burcu A1 - Weber, Marcus T1 - Free Energy Calculation Using Mayer Cluster Expansion and Fluctuation Free Integration N2 - This work aims to develop a new algorithm to calculate the free energy of water molecules by using a deterministic way. For this purpose, we assume a closed system confined to a physical volume, having water molecules in gas phase. To calculate the free energy of this sytem we utilized Mayer cluster expansion and the fluctuation free integration method. T3 - ZIB-Report - 12-35 Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16031 SN - 1438-0064 ER - TY - GEN A1 - Lie, Han Cheng A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - A square root approximation of transition rates for a Markov State Model N2 - Trajectory- or mesh-based methods for analyzing the dynamical behavior of large molecules tend to be impractical due to the curse of dimensionality - their computational cost increases exponentially with the size of the molecule. We propose a method to break the curse by a novel square root approximation of transition rates, Monte Carlo quadrature and a discretization approach based on solving linear programs. With randomly sampled points on the molecular energy landscape and randomly generated discretizations of the molecular configuration space as our initial data, we construct a matrix describing the transition rates between adjacent discretization regions. This transition rate matrix yields a Markov State Model of the molecular dynamics. We use Perron cluster analysis and coarse-graining techniques in order to identify metastable sets in configuration space and approximate the transition rates between the metastable sets. Application of our method to a simple energy landscape on a two-dimensional configuration space provides proof of concept and an example for which we compare the performance of different discretizations. We show that the computational cost of our method grows only polynomially with the size of the molecule. However, finding discretizations of higher-dimensional configuration spaces in which metastable sets can be identified remains a challenge. T3 - ZIB-Report - 13-43 KW - Markov State Models KW - Markov chains KW - meshfree methods KW - metastability KW - Voronoi KW - linear programming Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42195 SN - 1438-0064 ER - TY - GEN A1 - Lehmann, Felix T1 - Inexaktheit in Newton-Lagrange-Verfahren für Optimierungsprobleme mit Elliptischen PDGL-Nebenbedingungen N2 - Bei der numerischen Lösung von Optimalsteuerungsproblemen mit elliptischen partiellen Differentialgleichungen als Nebenbedingung treten unvermeidlich Diskretisierungs- und Iterationsfehler auf. Man ist aus Aufwandsgründen daran interessiert die dabei entstehenden Fehler nicht sehr klein wählen zu müssen. In der Folge werden die linearisierten Nebenbedingungen in einem Composite-Step-Verfahren nicht exakt erfüllt. In dieser Arbeit wird der Einfluss dieser Ungenauigkeit auf das Konvergenzverhalten von Newton-Lagrange-Verfahren untersucht. Dabei sollen mehrere einschlägige lokale Konvergenzresultate diskutiert werden. Anschließend wird ein konkretes Composite-Step-Verfahren formuliert, in dem die Genauigkeit der inneren Iterationsverfahren adaptiv gesteuert werden kann. Am Ende der Arbeit wird an zwei Musterproblemen die hohe Übereinstimmung der analytischen Voraussagen und der tatsächlichen Performanz der dargestellten Methoden demonstriert. T3 - ZIB-Report - 13-37 KW - optimal control KW - PDE KW - inexact Newton Lagrange KW - adaptive Newton Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41972 SN - 1438-0064 ER - TY - GEN A1 - Winkelmann, Stefanie T1 - Markov Control with Rare State Observation: Average Optimality N2 - This paper investigates the criterion of long-term average costs for a Markov decision process (MDP) which is not permanently observable. Each observation of the process produces a fixed amount of \textit{information costs} which enter the considered performance criterion and preclude from arbitrarily frequent state testing. Choosing the \textit{rare} observation times is part of the control procedure. In contrast to the theory of partially observable Markov decision processes, we consider an arbitrary continuous-time Markov process on a finite state space without further restrictions on the dynamics or the type of interaction. Based on the original Markov control theory, we redefine the control model and the average cost criterion for the setting of information costs. We analyze the constant of average costs for the case of ergodic dynamics and present an optimality equation which characterizes the optimal choice of control actions and observation times. For this purpose, we construct an equivalent freely observable MDP and translate the well-known results from the original theory to the new setting. T3 - ZIB-Report - 16-59 KW - Markov decision process KW - partial observability KW - average optimality KW - information costs Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60981 SN - 1438-0064 ER - TY - THES A1 - Lubkoll, Lars T1 - Optimal Control in Implant Shape Design KW - optimal control Y1 - 2011 ER - TY - THES A1 - Lehmann, Felix T1 - Inexaktheit in Newton-Lagrange-Verfahren für Optimierungsprobleme mit Elliptischen PDGL-Nebenbedingungen N2 - Bei der numerischen Lösung von Optimalsteuerungsproblemen mit elliptischen partiellen Differentialgleichungen als Nebenbedingung treten unvermeidlich Diskretisierungs- und Iterationsfehler auf. Man ist aus Aufwandsgründen daran interessiert die dabei entstehenden Fehler nicht sehr klein wählen zu müssen. In der Folge werden die linearisierten Nebenbedingungen in einem Composite-Step-Verfahren nicht exakt erfüllt. In dieser Arbeit wird der Einfluss dieser Ungenauigkeit auf das Konvergenzverhalten von Newton-Lagrange-Verfahren untersucht. Dabei sollen mehrere einschlägige lokale Konvergenzresultate diskutiert werden. Anschließend wird ein konkretes Composite-Step-Verfahren formuliert, in dem die Genauigkeit der inneren Iterationsverfahren adaptiv gesteuert werden kann. Am Ende der Arbeit wird an zwei Musterproblemen die hohe Übereinstimmung der analytischen Voraussagen und der tatsächlichen Performanz der dargestellten Methoden demonstriert. KW - PDE KW - adaptive Newton KW - inexact Newton-Lagrange Y1 - 2013 UR - urn:nbn:de:0297-zib-41972 ER - TY - GEN A1 - Tateiwa, Nariaki A1 - Shinano, Yuji A1 - Yasuda, Masaya A1 - Kaji, Shizuo A1 - Yamamura, Keiichiro A1 - Fujisawa, Katsuki T1 - Massively parallel sharing lattice basis reduction N2 - For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments. T3 - ZIB-Report - 21-38 KW - Discrete optimization KW - Lattice problem KW - Lattice-based cryptography KW - Shortest vector problem KW - Parallel algorithms KW - Ubiquity Generator Framework Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85209 SN - 1438-0064 N1 - under review ER - TY - GEN A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult. T3 - ZIB-Report - 23-27 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93072 SN - 1438-0064 ER - TY - GEN A1 - Fujii, Koichi A1 - Ito, Naoki A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Shinano, Yuji A1 - Toh, Kim-Chuan T1 - 大規模二次割当問題への挑戦 T2 - 統計数理研究所共同研究リポート 453 最適化:モデリングとアルゴリズム33 2022年3月 「大規模二次割当問題への挑戦」 p.84-p.92 N2 - 二次割当問題は線形緩和が弱いことが知られ,強化のため多様な緩和手法が考案されているが,その一つである二重非負値計画緩和( DNN 緩和)及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し,それらに基づく分枝限定法の実装及び数値実験結果について報告する. T2 - Solving Large Scale QAPs with DNN-based Branch-and-bound : a progress report T3 - ZIB-Report - 22-11 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86779 SN - 1438-0064 ER - TY - GEN A1 - Kempke, Nils-Christian A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs N2 - In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints’ locality to decouple the factorization process. Our approach is motivated by large-scale unit-commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix. T3 - ZIB-Report - 24-13 KW - direct methods for linear systems KW - mathematical programming KW - parallel computation KW - linear programming KW - large-scale problems KW - interior-point methods Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98829 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin T1 - Einblicke in die Diskrete Mathematik N2 - „Diskrete Mathematik, was ist das?“, ist eine typische Frage von Lehrern mit traditioneller Mathematikausbildung, denn dort kam und kommt diskrete Mathematik kaum vor. Die etwas Aufgeschlosseneren fragen: „Wenn (schon wieder) etwas Neues unterrichtet werden soll, was soll denn dann im Lehrplan gestrichen werden?“ Auf die zweite Frage wird hier nicht eingegangen. Das Ziel dieses Aufsatzes ist es, in diskrete Mathematik einzuführen, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu berücksichtigen. Die Schüler und Schülerinnen werden dafür dankbar sein – eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde. T3 - ZIB-Report - 12-01 KW - diskrete Mathematik Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14399 SN - 1438-0064 ER - TY - GEN A1 - Rössig, Ansgar T1 - Verification of Neural Networks T3 - ZIB-Report - 19-40 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74174 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - New Perspectives on PESP: T-Partitions and Separators N2 - In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time. T3 - ZIB-Report - 19-35 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Graph Partitioning KW - Graph Separators KW - Balanced Cuts Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73853 SN - 1438-0064 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 - 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 - THES A1 - Anderson, Lovis T1 - The Computation of the Volume of the Union of Polytopes via a Sweep-Plane Algorithm N2 - Das Thema dieser Arbeit ist ein Volumen-Algorithmus für die Vereinigung von Polytopen. Der Algorithmus basiert auf der Arbeit von Bieri und Nef. Er berechnet das Volumen der Vereinigung von Polytopen mit einem Sweep-Verfahren. Dabei wird eine Hyperebene im Raum verschoben und das Volumen auf der einen Seite der Hyperebene berechnet. Umso weiter die Hyperebene verschobe wird, desto größer ist auch der Halbraum. Unser Algorithmus berechnet das Volumen einer Vereinigung von Polytopen geschnitten mit dem Halbraum der Sweep-Ebene als eine Funktion abhängig von der Veschiebung. Ab einem gewissen Punkt liegt der Körper dabei komplett im Halbraum der Sweep-Ebene und das Volumen bleibt konstant. Unser Algorithmus unterscheidet sich in zwei Punkten von dem Algorithmus von Bieri und Nef. Erstens funktioniert er nur auf der Vereinigung von Polytopen, wohingegen der Algorithmus von Bieri und Nef für Nef-Polyeder funktioniert. Diese sind eine Verallgemeinerung von Polyedern, die auch die Klasse der Vereinigung von Polytopen umfasst. Für uns ist das allerdings kein Nachteil, da unsere Datensätze zu Vereinigungen von Polytopen führen. Zweitens ist unser Algorithmus in zwei Teile aufgeteilt. Im ersten Teil wird eine Datenstruktur entwickelt, aus der im zweiten Teil zusammen mit einer Richtung die Sweep-Ebenen-Volumenfunktion berechnet wird. Der Großteil der Komplexität liegt im ersten Teil des Algorithmus. Das hat den Vorteil, dass wir die Volumenfunktionen für viele verschiedene Richtungen berechnen können. So können Einblicke in die Struktur des Körpers gewonnen werden. Der Algorithmus beruht auf zwei verschiedenen Zerlegungsansätzen. Zuerst können wir mit Hilfe von Anordnungen von Hyperebenen eine Vereinigung von Polytopen in ihre Zellen zerlegen. Dabei berufen wir uns auf die Arbeit von Gerstner und Holtz, in der das Konzept der Positionsvektoren eingeführt wird. Diese nutzen wir um die Ecken und ihre benachbarten Zellen zu bestimmen. So erhalten wir eine Zerlegung unserer Vereinigung in Zellen, deren paarweise Schnitte kein Volumen haben. Das zweite Zerlegungskonzept ist die konische Zerlegung, wie sie von Lawrence eingeführt wurde. Mit Hilfe dieser können wir die Indikatorfunktion eines Polytops als die Summe der Indikatorfunktionen seiner Vorwärtskegel schreiben. Die Sweep-Ebenen Volumenfunktionen können dann leicht mit Hilfe einer altbekannten Formel für das Volumen von Simplices berechnet werden. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71829 ER - TY - GEN A1 - Munguia, Lluis-Miquel A1 - Oxberry, Geoffrey A1 - Rajan, Deepak A1 - Shinano, Yuji T1 - Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs N2 - PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores. T3 - ZIB-Report - 17-58 KW - PIPS-SBB, UG, Parallel Branch and Bound Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65517 SN - 1438-0064 IS - ZIB-Report 17-58 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Egerer, Ascan A1 - Karbstein, Marika A1 - Messerschmidt, Ralf A1 - Perez, Marc A1 - Pfisterer, Steven A1 - Strauß, Petra T1 - Kombilösung: Optimierung des Liniennetzes in Karlsruhe N2 - Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung. T3 - ZIB-Report - 18-45 KW - ÖPNV KW - Linienplanung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69677 SN - 1438-0064 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 -