Clash of MINLP Relaxations: Piecewise Linear vs. Global Parabolic
Adrian Gö β \beta · 2026
Read Clash of MINLP Relaxations: Piecewise Linear vs. Global Parabolic by Adrian Gö β \beta (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16505.txt.
Introduction
Göß compares two ways to relax mixed-integer nonlinear programs. Relaxations swap a hard problem for an easier bound problem. Global parabolic relaxations use paraboloids as global bounds. Their one-shot computation can explode into an intractable model. Göß gives an iterative method that works where the old one failed. Tests then face PARA against piecewise linear relaxations. Piecewise wins when tolerance is loose. PARA wins as tolerance tightens. Sine constraints widen the PARA edge.
Catalog record
| CREATOR | Adrian Gö β \beta |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72223 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.16505
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Clash of MINLP Relaxations: Piecewise Linear vs. Global Parabolic Adrian Gö β \beta Abstract . Solving mixed-integer nonlinear programs (MINLPs) typically relies on constructing relaxations that are easier to tackle than the original problem. Recently, global parabolic (PARA) relaxations were introduced, featuring separable quadratic functions – paraboloids – as global under- or overestimators of general nonlinear constraint functions. So far, the paraboloids are all computed at once by solving a mixed-integer linear program (MIP). For small tolerances or wide function domains, the corresponding MIP grows in size and is eventually intractable, preventing a meaningful comparison with established relaxation techniques. We therefore propose a novel iterative method to compute PARA approximations that succeeds on all tolerance-domain combinations where the original one has failed. The computational study is preceded by a thorough theoretical explanation and analysis. Finally, the improved method enables a computational comparison with piecewise linear (PWL) relaxations in terms of runtime on general MINLP instances. The results show that the modern solver SCIP can solve PWL relaxations faster when the tolerance is high, shifting strongly in favor of PARA for tighter tolerances. We attribute the effect to the difference in the corresponding problem size: PWL relaxations introduce binary variables to identify the active linear piece and their number grows with decreasing tolerance. PARA, on the other hand, does not require additional variables such that the dimension is maintained. For problems with at least one (co)sine constraint, the effect significantly amplifies. Thereby, for medium tolerances, PARA relaxations outperform SCIP stand-alone. Applied problems like alternating current optimal power flow (AC-OPF) feature such constraint types, leaving PARA a viable relaxation strategy. 2010 Mathematics Subject Classification 90C11, 90C20, 90C26, 90C30 1. Introduction The modeling power of minlp ( minlp ) is undisputed. The combination of integral components and nonlinear interconnection allows for the resemblance of a great variety of applications. These range from gas network control [ 30 ] over chemical processes [ 2 ] up to the design of water networks [ 8 ] . Along with this power comes a certain (computational) cost, which makes it hard to solve general minlpps ( minlpps ) at scale and necessitates a retreat to simplified models, at least as an intermediate step. For instance, in modern optimization software for minlp like BARON [ 37 ] , COUENNE [ 6 ] , Gurobi [ 27 ] , SCIP [ 28 ] , or XPRESS [ 22 ] relaxations of the original problem are constructed and then solved. A popular technique to construct relaxations of problems with general nonlinear constraints is their piecewise handling. With the advances in mip ( mip ) throughout the last decades, constructing relaxations based on linear functions appears as a potentially successful option. In fact, pwl ( pwl ) relaxations have been originally introduced in [ 31 ] – to the best of our knowledge – and are further developed and adjusted every since, e.g., see [ 3 , 12 , 16 , 29 , 36 ] . Also refer to [ 41 ] for an extensive survey and to [ 9 ] for a recent computational comparison. As fas as we are aware, all of the aforementioned solvers include such relaxations. There also exist piecewise techniques beyond the linear realm. For instance, the SC- minlp approach [ 20 , 18 ] can be seen as an extension of pwl . For a nonlinear and twice continuously differentiable function f , it divides the function domain into intervals on which f is either convex or concave, respectively. Then, the concave parts are relaxed by pwl , whereas the convex parts remain. This renders the resulting relaxed problem a convex minlpp , which is considered (more) tractable. Even more general approaches feature piecewise quadratic [ 40 ] or piecewise polynomial approximates [ 17 ] . The resulting problems fall into the class of miqcp ( miqcp ), at least after reformulation. Though miqcp is still a subclass of minlp , there exist tailored approaches to solve such problems [ 4 , 3 , 10 , 11 , 21 , 34 , 33 , 42 ] . All those piecewise approaches have the benefit to construct relaxations that can fulfill a prespecified tolerance. That is, given a tolerance \varepsilon>0 , one can compute approximates, i.e., pieces of linear/quadratic functions, that fulfill the \varepsilon -accuracy with respect to the original problem. Thus any solution to the relaxed problem constitutes an \varepsilon -approximate solution which often suffice in practice. As an additional advantage, the character of the relaxed problem as a mip or miqcp problem allows to leverage tailored solvers. Naturally, those benefits are not without cost. Depending on the modeling technique, they come with the introduction of binary variables whose number grows with the number of pieces. The approximates – e.g., linear pieces – lack a global validity, i.e., they do not constitute global under-/overestimators of the constraint function, and thus need to be “disabled” outside their corresponding interval. Hence, the resulting relaxation grows in (variable) size, which may impose computational challenges for large problems or tight tolerances. In a first attempt to circumvent additional integer variables, the authors of [ 26 ] introduced a framework to compute para ( para ) approximations of functions. The approximates are paraboloids , i.e., separable quadratic functions, globally under-/overestimating a constraint function. Although not necessarily being convex, the global validity allows to incorporate the paraboloids as constraints without the necessity of additional binary variables. That is, the problem size grows in the number of constraints only, but some solvers like SCIP seem to handle those similar-shaped constraints quite well, compare [ 26 ] . Although the para approach seems to be a viable relaxation technique, the method to compute respective para approximations in [ 26 ] is computationally limited. It computes all approximating paraboloids at once by repetitively solving mip problems. Thereby, their size grows with domain width and decreasing tolerance, leaving them eventually not solvable under limited resources. Consequently, [ 26 ] reports valid parabolic approximations only on artificial domains and with respect to moderate tolerances, preventing a meaningful comparison with established techniques like pwl . We thus introduce a novel iterative method that leverages differentiability of the constraint functions in combination with a factorable problem structure to compute para approximations for tight tolerances and wide domains. In Section 3 , we introduce our method formally, give proof of its correctness, and showcase that it is indeed able to succeed on tolerance-domain combinations that are left as unsolved by the approach in [ 26 ] . Furthermore, our method then allows for a comparison against pwl relaxations in terms of numbers of approximates – linear pieces versus parabolas – ( Section 3.2.2 ) and computational efficacy ( Section 4 ). The remainder is dedicated to establish common ground in Section 2 by a presentation of the notation and the optimization problem. Further, it gives a short introduction into pwl ( Section 2.3 ) and the original para approach ( Section 2.4 ). We close the article with some concluding remarks in Section 5 . Proofs and additional results can be found in Appendix A and Appendix B , respectively. 2. Preliminaries Before diving into the main topic