On refinement strategies for solving MINLPs\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textsc {MINLP}\mathrm{s}}$$\end{document} by piecewise linear relaxations: a generalized red refinement

Burlacu, Robert Article — Published Version On refinement strategies for solving MINLPs\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin} {-69pt} \begin{document}$${\textsc {MINLP}\mathrm{s}}$$\end{document}by piecewise linear relaxations: a generalized red refinement Optimization Letters Provided in Cooperation with: Springer Nature Suggested Citation: Burlacu, Robert (2021) : On refinement strategies for solving MINLPs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textsc {MINLP}\mathrm{s}}$$\end{document}by piecewise linear relaxations: a generalized red refinement, Optimization Letters, ISSN 1862-4480, Springer, Berlin, Heidelberg, Vol. 16, Iss. 2, pp. 635-652, https://doi.org/10.1007/s11590-021-01740-1 This Version is available at: https://hdl.handle.net/10419/286958 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Optimization Letters (2022) 16:635–652 https://doi.org/10.1007/s11590-021-01740-1 ORIGINAL PAPER On refinement strategies for solving MINLPsby piecewise linear relaxations: a generalized red refinement Robert Burlacu1,2 Received: 27 July 2020 / Accepted: 13 April 2021 / Published online: 19 June 2021 © The Author(s) 2021 Abstract We investigate the generalized red refinement for n-dimensional simplices that dates back to Freudenthal (Ann Math 43(3):580–582, 1942) in a mixed-integer nonlinear program (MINLP) context. We show that the red refinement meets sufficient convergence conditions for a known MINLP solution framework that is essentially based on solving piecewise linear relaxations. In addition, we prove that applying this refinement procedure results in piecewise linear relaxations that can be modeled by the well-known incremental method established by Markowitz and Manne (Econometrica 25(1):84–110, 1957). Finally, numerical results from the field of alternating current optimal power flow demonstrate the applicability of the red refinement in such MIP- based MINLP solution frameworks. Keywords Mixed-integer nonlinear programming ·Red refinement ·Piecewise linear relaxation ·Incremental method 1 Introduction Solving general MINLPs is to this day a very challenging task. The backbone of most approaches in this context is still branch-and-bound. In the last two decades, however, various methods have been proposed that tackle non-convex MINLPsby piecewise convex relaxations without direct branching of the continuous variables, see The author thanks the Deutsche Forschungsgemeinschaft for their support within Project B07 of the Sonderforschungsbereich/Transregio 154 “Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks”. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. BRobert Burlacu [email protected] 1Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Discrete Optimization, Cauerstr. 11, 91058 Erlangen, Germany 2Energie Campus Nürnberg, Fürther Str. 250, 90429 Nuremberg, Germany 123 636 R. Burlacu for example [7,8,12,14,16]. Although these approaches are sometimes rather different, they all need to address the following two problems: the construction of reasonable relaxations of the nonlinear functions and the incorporation of these relaxations into a mixed-integer linear program (MIP) or convex nonlinear program (NLP). One way to obtain such relaxations is to compute an optimal linearization of a nonlinear function with respect to the number of breakpoints and an a priori given accuracy as in [17,18]. Complementary, optimal polynomial relaxations of one-dimensional functions are constructed in [16]. For up to three-dimensional functions, explicit approximation techniques for general nonlinear functions are proposed in [15]. The main drawback of all these methods, however, is that the number of simplices in the approximation grows exponentially with the dimension of the function. We refer to the approach from [19] that avoids this problem in that the piecewise linear approximation is not required to interpolate the original function at the vertices of the triangulation. There are many different ways to model piecewise linear functions as an MIP. A detailed overview of the various models is presented by [20]. Among the most important ones is the incremental method of Markowitz and Manne, see [13], which is originally developed for one-dimensional functions. A generalization to higher dimensions is described in [6,11,21]. Supplementary to this, an extension to relaxations is given in [7]. In this paper, we consider the MINLP solution method proposed in [3,6] and further developed in [2] that tackles an MINLP by solving a series of MIP relaxations that are based on piecewise linear functions and completely contain the graph of the function. The functions are defined on simplices, which in turn are defined by several vertices. The authors develop an iterative algorithm to find a global optimal solution of the MINLP by solving these MIP relaxations, which are adaptively refined. They present rather general convergence conditions for MINLP solution algorithms that rely on the adaptive refinement of piecewise linear relaxations. They show that the classical longest-edge bisection fulfills these conditions and therefore is suitable for such a solution framework. In addition, they prove that triangulations that are constructed by successively applying the longest-edge bisection lead to piecewise linear relaxations that can always be modeled by the already mentioned generalization of the incremental method. We extend this result by another refinement strategy for n-dimensional simplices: the generalized red refinement introduced by Freudenthal in [5]. This procedure is to some extent an n-dimensional generalization of the well-known red-green refinement, which is used for two-dimensional simplices. We show that the red refinement meets the convergence conditions from [3]. Moreover, we prove that the generalized incremental method is suitable to model piecewise linear relaxations that are obtained by iteratively applying the red refinement. Finally, numerical results from the field of alternating current optimal power flow demonstrate the applicability of the red refinement in an MINLP solution framework as presented in [3]. More precisely, we show that this refinement strategy yields tighter dual bounds for the MINLP problems. This article is structured as follows. We introduce all necessary definitions and theorems of previous works in Sect. 2. Section 3shows that the red refinement fulfills the convergence conditions from [3]. In Sect. 3, we prove that adaptively red refined piecewise linear relaxations can be modeled by the generalized incremental method. 123 On refinement strategies for solving MINLPs by piecewise… 637 Section 4presents some numerical results that illustrate the practicability of the red refinement procedure. We conclude this work in Sect. 5. 2 Preliminaries The aim of this article is to prove that the generalized red refinement procedure is suitable for an MINLP solution framework such as in [3]. We consider an MINLP problem as an optimization problem of the following type: minxcx s.t. Ax ≤b, fi(x)≤0 for all i∈{1,...,k},(P) l≤x≤u, x∈Rq×Zp, where k,q,p∈N.First,Ax ≤brepresents the linear constraints, while the nonlinear constraints are described by continuous nonlinear real-valued functions fi:Rq+p→R for i=1,...,k. The variables xare bounded from below and above by l,u∈Rq+p. Moreover, we denote by Fthe set of all nonlinear functions fi(x).LetDf⊂Rq+p be the domain of a nonlinear function f∈F. Since each variable in (P) has lower and upper bounds, the domain Dfis a compact set. We consider it to be a d-dimensional box with its edges parallel to the coordinate axes, while d≤q+p. Equality constraints, i.e., constraints of type fi(x)=0, are implicitly contained in (P) by simply adding the constraints fi(x)≤0 and −fi(x)≤0. Please note that we are not restricted to a linear objective function cx, because we can include any nonlinear objective function f:Rq+p→Rby substituting f(x)with a variable y∈Rand adding f(x)≤yas a constraint to the MINLP problem. Due to max cx=−min −cx, any maximization problem can be transformed to a minimization problem. Thus, (P) represents a general formal description of MINLP problems. The main idea of the MINLP solution approach from [3] is to use piecewise linear functions to construct MIP relaxations of the underlying MINLP. An iterative algorithm is developed to find a global optimal solution by solving these relaxations, which are adaptively refined. With the domain Dfof f∈F, the refinement is performed on a simplicial triangulation Tof Df. A more formal description of this method is given in Algorithm 2.1. In [3], the classical longest-edge bisection is used for the refinement procedure in Line 19 of Algorithm 2.1. In this paper, we consider the generalized red refinement instead. Please note that the theoretical results are part of the author’s Ph.D. thesis [2]. In order to be equipped with all the necessary ingredients for the following proofs, we first introduce the most relevant definitions and theorems from [3]. First, with a δ-precise refinement procedure, Algorithm 2.1 is both correct and convergent: Definition 2.1 The refinement procedure in Algorithm 2.1 is called δ-precise,iffor an arbitrary sequence (Si)∈Tiof simplices Sithat are refined by the refinement 123 638 R. Burlacu Algorithm 2.1 Global optimization of an MINLP by solving adaptively refined MIP relaxations Input: An MINLP problem Pof type (P), upper bounds 0 f>0 for the absolute linearization errors in the piecewise linear approximations used to construct the initial relaxation and the maximal absolute linearization errors f>0 for all f∈F. Output: If Pis feasible, the algorithm returns an optimal solution xof an MIP relaxation Πof Pwith |f(xf)−yf|≤ffor all f∈Fand cx≤cxfor any feasible point xof P.IfnosuchMIP relaxation Πof Pexists, this is reported by returning infeasible. 1: Set F←all nonlinear functions that are contained in P. 2: Set Df,0 f,f←the domain Dfand the error bounds 0 f,ffor all f∈F. 3: Compute an initial piecewise linear approximation φ0 fof f∈Fsatisfying the upper bound 0 ffor all f∈F. 4: Set i←0. 5: repeat 6: Construct an MIP relaxation Πiof Pfrom φi ffor all f∈F. 7: Solve Πi. 8: if Πiis feasible then 9: Set xi←optimal solution of Πi. 10: else 11: return infeasible. 12: end if 13: Set stop ←true. 14: for all f∈Fdo 15: Set xi f←projection of xion Df. 16: Set yi f←value of the variable for the relaxed function value of f. 17: if f(xi f)−yi f>fthen 18: Set Si f←simplex of triangulation Tφi fthat contains xi f. 19: Set Tφi+1 f←refinement of Tφi f(by refining Si f). 20: Set φi+1 f←piecewise linear approximation according to Tφi+1 f. 21: Set stop ←false. 22: else 23: Set φi+1 f←φi f. 24: end if 25: end for 26: Set i←i+1. 27: until stop. 28: return xi−1. procedure with initial triangulation T0of Dfand given δ>0, there exists an index N∈N, such that diam(SN)<δ (1) holds, where diam(SN):= supx,x∈SN{x−x}. Proposition 2.2 (Theorem 3.6, [3]) If the refinement procedure in Algorithm 2.1 is δ-precise for every δ>0, then Algorithm 2.1 is correct and terminates after a finite number of steps. It is therefore sufficient to prove that the generalized red refinement is δ-precise in order to show that its combination with Algorithm 2.1 yields a correct and convergent algorithm. 123 On refinement strategies for solving MINLPs by piecewise… 639 Moreover, we must prove that piecewise linear relaxations that are obtained by iteratively applying the red refinement can be described by an MIP model. In Algorithm 2.1, the piecewise linear relaxations are modeled by the generalized incremental method, see [6]. There are two main ideas of the generalized incremental model. At first, any point xSinside a simplex Swith its vertex set V(S)={¯xS 0,..., ¯xS d}can be expressed either as a convex combination of its vertices or equivalently as xS=¯xS 0+ d  j=1¯xS j−¯xS 0δS j(2) with d j=1δS j≤1 and δS j≥0for j=1,...,d. The other main idea is that all simplices of a triangulation are ordered in such a way that the last vertex of any simplex is equal to the first vertex of the next one. In this way, we can construct a Hamiltonian path and model the piecewise linear approximation along this path. It is known that modeling piecewise linear functions by the generalized incremental method is possible if an ordering of the simplices with the following properties is available: (O1) The simplices in T={S1,...,Sn}are ordered such that V(Si)∩V(Si+1)=∅ for i=1,...,n−1, and (O2) for each simplex Siits vertices ¯xSi 0,..., ¯xSi dcan be labeled such that ¯xSi d=¯xSi+1 0 for i=1,...,n−1. Hence, we only have to show that a red refined triangulation has properties (O1) and (O2) to utilize the generalized incremental method. 3 Convergence result In this article, we consider Algorithm 3.1 that is proposed in [1,5] as the refinement procedure in Algorithm 2.1. It is a generalization of the red refinement strategy, which originally was only developed for triangles. It is known that the generalized red refinement procedure always delivers a triangulation of a simplex (that has to be refined) by 2dsub-simplices. Moreover, the triangulation is consistent, i.e., the intersection of any two sub-simplices is either empty or a common lower-dimensional simplex with respect to the vertex sets. Consequently, a consistent triangulation does not allow for hanging nodes, i.e., nodes that are contained in the vertex set of a simplex S, but not in all vertex sets of the simplices that are adjacent to S. We again point out that the theoretical results in this and the subsequent section are part of the author’s Ph.D. thesis [2]. We first illustrate the refinement by Algorithm 3.1 using an example in dimension two. Example 3.2 We consider a simplex Slof some triangulation of a two-dimensional nonlinear function with vertex set V(Sl)={¯x0,¯x1,¯x2}that has to be refined. Let the scalar δbe sufficiently large such that a refinement is performed by Algorithm 3.1. Note that for k≤1 the condition τ−1(1)<···<τ −1(k)is considered to be fulfilled. The same applies for the condition τ−1(k+1)<···<τ −1(d)in case of k≥d−1. 123 640 R. Burlacu Algorithm 3.1 Generalized red refinement of a simplex S Input: AsimplexSwith V(S)={¯x0,..., ¯xd}and a scalar δ. Output: If the longest edge of Sis greater than δ,asetof2 dsimplices {S0,...,S2d−1}with S=∪ 2d−1 i=0Si and int(Si)∩int(Sj)=∅for all i= jis returned. Otherwise no refinement is performed. 1: Set e←longest edge of S. 2: if e≤δthen 3: return V(S). 4: else 5: Set i←−1. 6: for 0≤k≤ddo 7: Set v0←1 2(¯x0+¯xk). 8: for τ∈Symddo 9: if τ−1(1)<···<τ −1(k)and τ−1(k+1)<···<τ −1(d)then 10: for 1≤l≤ddo 11: Set vl←vl−1+1 2(¯xτ(l)−¯xτ(l)−1). 12: end for 13: Set i←i+1. 14: Set V(Si)←{v0,...,v d};Si←conv(V(Si)). 15: end if 16: end for 17: end for 18: return V(S0),...,V(S2d−1). 19: end if First, the symmetry group Sym2has two permutations: the identity τ1=id and the permutation τ2:{1,2}→{2,1}. The identity fulfills the condition in Line 9 for all 0≤k≤2. Since τ2does not satisfy Line 9 for k=0, we obtain the first corner sub-simplex S0 l for τ1. The vertices of S0 lare v0=¯x0,v 1=v0+1 2(¯x1−¯x0), v2=v1+1 2(¯x2−¯x1);(3) see Fig. 1for an illustration. For k=1 both permutations τ1and τ2comply with Line 9. Equivalent to k=0, with τ1we obtain the simplex S1 las in (3), while now v0=¯x0+1 2(¯x1−¯x0). We thus obtain the corner sub-simplex S1 lsimply by translating the corner sub-simplex S0 lby the vector 1 2(¯x1−¯x0).Forτ2, we compute the vertices of the simplex S2 las v0=1 2(¯x1−¯x0), v1=v0+1 2(¯x2−¯x1), v2=v1+1 2(¯x1−¯x0). (4) Finally, for k=1 again only the identity τ1fulfills the condition in Line 9. We obtain the simplex S3 las in (3) with v0=¯x0+1 2(¯x2−¯x0). The corner sub-simplex S3 l again corresponds to a translation of S0 lby the vector 1 2(¯x2−¯x0). We now prove the δ-preciseness of the refinement procedure and show how to model a refined triangulation by the generalized incremental method afterward. Let  Tkbe the refined triangulation of an initial triangulation T0of Dfobtained by applying Algorithm 3.1 such that in every iteration i≤kall simplices of  Ti−1are refined. 123 On refinement strategies for solving MINLPs by piecewise… 641 Fig. 1 A red refinement of a two-dimensional simplex with corresponding ordering and labeling of the four sub-simplices. The labeled vertices of the original simplex that is refined are marked in bold blue Lemma 3.3 Let S ∈Rdbe a simplex of T0and e the longest edge of S. Then, the longest edge of any simplex of  Tlcontained in (the set) S is bounded by 1 2lewith l ∈N. Proof The lemma follows directly from Line 11 of Algorithm 3.1, since  1 2(¯xτ(l)−¯xτ(l)−1)≤1 2e are the lengths of the edges of the sub-simplices that are constructed during the first refinement step. Applying this recursively finishes the proof.  Lemma 3.4 Let δ>0, then there is an ˜ N∈N, such that  T˜ Nis a refinement of every triangulation obtained by applying Algorithm 3.1 to T0with δas input parameter. Proof Let e0be the longest edge of all simplices of T0. With Lemma 3.3 and ˜ N:= max 0,ln e0 δ/ln(2), the proof works equivalently to the one of Theorem 3.4 from [3]: After at most ˜ Nrefinement steps the longest edge of any simplex of  T˜ Nis bounded by δ. Since Algorithm 3.1 only refines simplices with a longest edge larger than δand no simplex in  T˜ Nhas an edge longer than δ, it follows by the pigeonhole principle that  T˜ Nis the finest refinement of T0that is achievable.  Theorem 3.5 Algorithm 3.1 as refinement procedure in Algorithm 2.1 is δ-precise for every δ>0. With ˜ N as in Lemma 3.4, the number of refinement steps N as in Definition 2.1 is bounded from above by N:= m(2˜ Nd −1)+1, where m is the number of simplices contained in T0. Proof We count every single simplex that has to be refined to achieve  T˜ Nfrom Lemma 3.4 and obtain m(1+2d+22d+···+2˜ Nd−1)=m(2˜ Nd −1) 123 642 R. Burlacu refinements in total. The rest of the proof follows by the pigeonhole principle as in the proof of Theorem 3.5 from [3]: Every sequence (Si)∈Tiof simplices has an element Skwith index k≤m(2˜ Nd−1)+1, such that Sk∈ T˜ N, since  T˜ Nis a refinement of every triangulation obtained by Algorithm 3.1 with parameter δ. Therefore, simplex Skhas the δ-preciseness property (1), as no simplex in  T˜ Nhas an edge longer than δ. The next corollary follows directly from Proposition 2.2 and Theorem 3.5. Corollary 3.6 Algorithm 2.1 together with Algorithm 3.1 as refinement procedure is correct and terminates after a finite number of steps. 4 Incremental method for red refined piecewise linear relaxations We now show that a piecewise linear approximation that results from applying Algorithm 3.1 can also be modeled with the generalized incremental method. We first prove two lemmata that are used afterward to prove the main result of this section. Lemma 4.1 Let S={S0,...,S2d−1}be a refinement of a simplex S by Algorithm 3.1 with V(S)={¯x0,..., ¯xd}. Then, each simplex of the subset of the corner sub-simplices S={Si0,...,Sid}of Scontains a vertex of the simplex S, i.e., ¯xj∈V(Sij)for all j =0,...,d. Moreover, for each pair of simplices Sij,Sik∈Sthe midpoint m jk of the edge with endpoints ¯xjand ¯xkis contained in both vertex sets of the simplices. Proof First, the identity id ∈Symdalways fulfills the conditions from Line 9 of Algorithm 3.1.LetSijbe the simplex that is constructed using the starting vertex v0= 1 2(¯x0+¯xj)and τ=id, where j=0,...,d. Due to the telescoping sum in Line 11, it follows that vj=1 2(¯x0+¯xj)   v0 +1 2(¯x1−¯x0)   v1 +1 2(¯x2−¯x1)   . . . +···+ 1 2(¯xj−¯xj−1)=xj(5) is contained in the vertex set of Sij. Furthermore, due to the telescoping sum in (5), we can rewrite Line 11 as vl←1 2(¯x0+¯xj)+1 2(¯xl−¯x0)=1 2(¯xj+¯xl) for τ=id. Since mjk =1 2(¯xj+¯xk), we conclude that the vertices vkand vjthat occur during the construction of Sijand Sik, respectively, are equal to mjk. Lemma 4.2 Let S ={S0,...,S2d−1−(d+1)}be a refinement of a simplex S by Algorithm 3.1 without the d +1corner sub-simplices of Sas in Lemma 4.1. Then, the 123 On refinement strategies for solving MINLPs by piecewise… 649 Table 2 Results summary for the AC OPF MIP relaxations with 32 simplices for each nonlinearity Nesta_case_ Standard api sad dLEB dRR TLEB (s) TRR (s) dLEB dRR TLEB (s) TRR (s) dLEB dRR TLEB (s) TRR (s) 3_lmbd 55.74 55.79 5.44 0.10 3.61 3.62 0.10 0.10 57.02 56.84 0.10 0.10 4_gs 1.11 1.11 0.10 0.10 7.57 7.58 0.10 0.10 3.10 3.12 0.10 0.10 5_pjm 145.62 146.20 5.43 4.50 29.71 29.74 5.57 4.75 256.02 255.74 0.10 0.10 6_ww 31.05 31.06 0.10 4.12 31.10 31.11 2.05 17.65 6_c 0.21 0.22 9.84 8.13 8.05 8.06 1.51 2.70 0.23 0.23 38.55 21.17 9_wscc 52.38 52.53 15.54 13.72 6.52 6.53 1.11 0.10 54.32 54.09 2.06 0.10 14_ieee 2.37 2.38 1 974.83 1 855.49 3.17 3.17 578.62 314.10 2.37 2.38 4 727.75 6 592.35 24_ieee_rts 610.67 611.18 TL TL 51.67 52.21 391.57 312.74 739.56 717.78 8 574.45 1 590.11 29_edin 238.01 219.58 TL TL 2831.18 2836.86 TL TL 298.35 317.08 TL TL 30_fsr 3.42 3.54 TL TL 1.43 1.39 TL TL 3.21 3.43 TL TL 30_as 5.92 5.72 TL TL 5.11 4.99 TL TL 6.70 6.81 TL TL 30_ieee 1.18 1.14 TL TL 3.51 3.56 TL TL 1.27 1.20 TL TL 39_epri 937.39 939.92 TL TL 70.13 70.48 TL TL 949.65 942.87 TL TL 57_ieee 9.05 9.00 TL TL 12.08 12.11 TL TL 9.13 9.24 TL TL 73_ieee_rts 1771.64 1773.22 TL TL 167.33 167.44 TL TL 2117.09 2102.50 TL TL 89_pegase 34.90 35.53 TL TL 12.34 12.19 TL TL 36.57 36.12 TL TL 118_ieee 27.48 27.52 TL TL 46.34 46.38 TL TL 28.38 28.79 TL TL 162_ieee_dtc 33.39 33.59 TL TL 49.64 49.87 TL TL 33.40 33.71 TL TL 189_edin 0.30 0.43 TL TL 5.65 5.33 TL TL 0.27 0.50 TL TL 300_ieee 133.85 132.28 TL TL 169.75 170.46 TL TL 132.86 133.81 TL TL 123 650 R. Burlacu Table 3 Results summary for the AC OPF MIP relaxations with 128 triangles for each two-dimensional function and 2 segments for each one-dimensional function Nesta_case_ Standard api sad dLEB dRR TLEB (s) TRR (s) dLEB dRR TLEB (s) TRR (s) dLEB dRR TLEB (s) TRR (s) 3_lmbd 32.70 32.70 1.02 0.10 3.48 3.48 0.10 0.10 33.62 33.62 0.10 0.10 4_gs 0.85 0.85 0.10 0.10 5.67 5.67 0.10 0.10 2.28 2.28 1.43 0.10 5_pjm 104.00 104.00 0.10 0.10 26.84 26.84 0.10 0.10 229.00 229.14 0.10 4.69 6_ww 22.06 22.06 5.63 0.10 22.35 22.35 3.98 0.10 6_c 0.00 0.00 1.38 2.43 4.18 4.19 6.83 4.92 0.00 0.00 3.65 6.58 9_wscc 23.51 23.51 3.28 2.20 4.95 4.95 2.24 1.55 25.50 25.46 6.63 4.50 14_ieee 0.00 0.00 32.43 28.60 0.03 0.04 1 785.20 2 470.70 0.00 0.00 123.81 159.88 24_ieee_rts 487.42 487.43 1 124.07 551.03 39.55 39.54 819.27 374.45 531.29 529.03 TL 296.79 29_edin 122.83 122.79 TL TL 2468.70 2469.18 TL TL 190.88 197.72 TL TL 30_fsr 0.00 0.00 16.37 1.57 0.00 0.00 5.19 1.97 0.00 0.00 197.79 28.18 30_as 2.85 2.85 21.67 1.91 1.31 1.31 315.90 303.17 2.85 2.85 325.92 758.83 30_ieee 0.00 0.00 83.70 24.99 0.00 0.00 88.74 6.50 0.00 0.00 746.26 337.23 39_epri 692.08 692.07 111.55 137.20 57.96 57.96 173.01 81.29 700.63 700.64 2 065.10 967.07 57_ieee 0.00 0.00 1 651.80 1 770.00 0.00 0.00 432.73 652.38 0.15 0.16 TL TL 73_ieee_rts 1413.38 1413.50 TL TL 125.79 125.87 TL TL 1487.14 1522.29 TL TL 89_pegase 16.04 16.04 2 581.74 1 602.08 6.37 6.37 5 114.17 TL 16.04 16.04 11 324.58 TL 118_ieee 3.88 3.87 TL TL 9.89 9.94 TL TL 4.74 4.71 TL TL 162_ieee_dtc 11.02 11.04 TL TL 18.45 18.47 TL TL 11.31 11.26 TL TL 189_edin 0.00 0.00 12 633.28 481.34 0.00 0.00 12 633.28 3 402.69 0.00 0.00 12 633.28 3 317.47 300_ieee 22.65 23.36 TL TL 40.53 40.40 TL TL 24.46 24.66 TL TL 123 On refinement strategies for solving MINLPs by piecewise… 651 Table 3contains the results for all 59 NESTA instances. The geometric mean in Table 3is 23.36 for dLEB and 23.40 for dRR. Regarding the run times, we have 451.67 s for TLEB and 330.84 s for TRR. Hence, in the case of very fine initial relaxations the RR can be very advantageous. Although the dual bounds are of the same quality, the run time is significantly better. This suggests that with the RR, we are able to find tight dual bounds at shorter run times. The numerical results in this section demonstrate that red refinement can be applied advantageously for initial relaxations in Algorithm 2.1. In particular, when the red refinement is used to construct very fine MIP relaxations to obtain tight dual bounds it is more favorable than the longest-edge bisection for MINLP problems that arise in the field of AC OPF. 6 Conclusion In this paper, we showed that the generalized red refinement for n-dimensional simplices can be utilized for solving MINLP problems by piecewise linear relaxations. We proved that the red refinement meets sufficient convergence conditions for such an MINLP solution framework as proposed in [3]. Furthermore, we showed that applying this refinement procedure results in piecewise linear relaxations that can be modeled by the well-known incremental method established by Markowitz and Manne [13]. Numerical results from the field of alternating current optimal power flow illustrated that the application of the red refinement procedure as an alternative to the longestedge bisection can be advantageous in practice. Especially, if the MIP relaxation is primarily used to obtain tight dual bounds, the red refinement seems to be favorable. The most important subject of future research is to what extent the combination of the two refinement strategies provides further potential for improvement. One possibility is to implement a hybrid approach that starts with an initial relaxation constructed by the red refinement and subsequently refines it by applying the longest-edge bisection. Acknowledgements The author thanks the Deutsche Forschungsgemeinschaft for their support within Project B07 of the Sonderforschungsbereich/Transregio 154 “Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks”. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. Finally, the author is very grateful to Kevin-Martin Aigner for fruitful discussion regarding the numerical results and to Lena Hupp for the thorough reading of the paper. Fundings Open Access funding enabled and organized by Projekt DEAL. Data availability The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. 123 652 R. Burlacu References 1. Bey, J.: Simplicial grid refinement: on Freudenthal’s algorithm and the optimal number of congruence classes. Numer. Math. 85(1), 1–29 (2000) 2. Burlacu, R.: Adaptive mixed-integer refinements for solving nonlinear problems with discrete decisions. Ph.D. Thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) (2020) 3. Burlacu, R., Geißler, B., Schewe, L.: Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes. Optim. Methods Softw. 35, 37–64 (2019) 4. Coffrin, C., Gordon, D., Scott, P.: Nesta, the NICTA energy system test case archive. CoRR, arXiv:1411.0359 (2014) 5. Freudenthal, H.: Simplizialzerlegungen von beschränkter flachheit. Ann. Math. 43(3), 580–582 (1942) 6. Geißler, B.: Towards globally optimal solutions of MINLPs by discretization techniques with applications in gas network optimization. Ph.D. Thesis, FAU Erlangen-Nürnberg (2011) 7. Geißler, B., Martin, A., Morsi, A., Schewe, L.: Using piecewise linear functions for solving MINLPs. In: Lee, J., Leyffer, S (eds.) Mixed Integer Nonlinear Programming. Springer, New York, pp. 287–314 (2012) 8. Gugat, M., Leugering, G., Martin, A., Schmidt, M., Sirvent, M., Wintergerst, D.: Towards simulation based mixed-integer optimization with differential equations. Networks 72, 60–83 (2018) 9. Jabr, R.A.: Radial distribution load flow using conic programming. IEEE Trans. Power Syst. 21(3), 1458–1459 (2006) 10. LLC Gurobi Optimization: Gurobi optimizer reference manual (2020) 11. Lee, J., Wilson, D.: Polyhedral methods for piecewise-linear functions. I. The lambda method. Discrete Appl. Math 108(3), 269–285 (2001) 12. Lundell, A., Skjäl, A., Westerlund, T.: A reformulation framework for global optimization. J. Glob. Optim. 57(1), 115–141 (2013) 13. Markowitz, H.M., Manne, A.S.: On the solution of discrete programming problems. Econometrica 25(1), 84–110 (1957) 14. Martin, A., Möller, M., Moritz, S.: Mixed integer models for the stationary case of gas network optimization. Math. Program. 105(2), 563–582 (2006) 15. Misener, R., Floudas, C.A.: Piecewise-linear approximations of multidimensional functions. J. Optim. Theory Appl. 145(1), 120–147 (2010) 16. Morsi, A.: Solving MINLPs on loosely-coupled networks with applications in water and gas network optimization. Ph.D. Thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) (2013) 17. Rebennack, S., Kallrath, J.: Continuous piecewise linear delta-approximations for bivariate and multivariate functions. J. Optim. Theory Appl. 167(1), 102–117 (2015) 18. Rebennack, S., Kallrath, J.: Continuous piecewise linear delta-approximations for univariate functions: computing minimal breakpoint systems. J. Optim. Theory Appl. 167(2), 617–643 (2015) 19. Ricardo, R., Claudia, D., Andrea, L., Silvano, M.: Optimistic MILP modeling of non-linear optimization problems. European J. Oper. Res 239(1), 32–45 (2014) 20. Vielma, J.P., Ahmed, S., Nemhauser, G.L.: Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions. Oper. Res. 58(2), 303–315 (2010) 21. Wilson, D.: Polyhedral methods for piecewise-linear functions. Ph.D. Thesis, University of Kentucky (1998) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123