Amélie Lambert
email: amelie.lambert@cnam.fr

A tight compact quadratically constrained convex relaxation of the Optimal Power Flow problem

Keywords: Global optimization, Optimal Power Flow, Quadratic Convex Relaxation, Semidefinite programming, Quadratically constrained Quadratic Programming

In this paper, we consider the optimal power flow (OPF) problem which consists in determining the power production at each bus of an electric network by minimizing the production cost. Our contribution is an exact solution algorithm for the OPF problem. It consists in a spatial branch-and-bound algorithm based on a compact quadratically constrained convex relaxation. This compact relaxation is computed by solving the rank relaxation once at the beginning of the algorithm so that the lower bound at the root node of the tree is equal to the rank relaxation value. Then, at every sub-nodes of the branch-and-bound, the lower bound is obtained by solving a quadratic convex problem. To construct this compact relaxation, we add onlyO(n + m) variables that model the squares of the initial variables, where n is the number of buses in the power system, and m the number of transmission lines. Since the relations between the initial and auxiliary variables are non-convex, we relax them to get a quadratic convex relaxation. Finally, in our branch-and-bound algorithm, we have only O(n + m) equalities to force to prove global optimality. Our first experiments show that our new algorithm Compact OPF (COPF) is more efficient than other quadratic convex relaxation based methods we compare it with.

Introduction

The Optimal Power Flow (OPF) problem consists in the determination of the power production at different buses of an electric network that minimizes a production cost. The electrical transmission network is modeled by a mutli-digraph G = (B, L), where each network point belongs to the set B of nodes (i.e the set of buses), and their connections (i.e. the set of transmission lines) are modeled by the set of edges L. Every line is represented by two anti-parallel arcs, and L is partitioned in two sets L 0 , L 1 , with |L 0 | = |L 1 |. We denote by n = |B| the number of buses, and m = |L| the number of lines. We assume that there is an electric demand at each node also called load. We distinguish two classes of nodes: B = B g ∪ B d , where B g is the set of nodes that generates and flows the power (the generator nodes), and B d is the set of nodes that only flows the power (the consuming nodes). The aim of the OPF problem is to satisfy demand of all buses while minimizing the total production costs of the generators such that the solution obeys Ohm's law and Kirchhoff's law, and follows the physical limits of the electrical transmission network. This problem is naturally formulated with complex variables. Let Y ∈ C n×n be the admittance matrix, which has component Y ij = G ij + jB ij for each line (i, j) of the network, and

G ii = g ii - i̸ =j G ij , B ii = b ii - i̸ =j
B ij , where g ii (resp. b ii ) is the shunt conductance (resp. susceptance) at bus i, and j 2 = -1. Let p i , q i be the real and reactive power output of the generator node i, and p i , q i the given real and reactive power output of the load node i. For each line (i, j) ∈ L, we consider the complex power in the rectangular form: S ij = s r ij + js c ij , and for each bus i ∈ B, the complex voltage in the rectangular form: V i = e i + jf i where |V i | 2 = e 2 i + f 2 i is the voltage magnitude, and we denote by δ(i) the set of adjacent nodes of bus i. With the above notation, the OPF problem can be modeled by the well known rectangular formulation of [START_REF] Torres | An interior-point method for nonlinear optimal power flow using voltage rectangular coordinates[END_REF]:

(OP F )                                                                                            min h(p) = i∈Bg C ii p 2 i + c i p i s.t. p i -p i = g ii (e 2 i + f 2 i ) + j∈δ(i) s r ij i ∈ B g (1)
-p i = g ii (e 2 i + f 2 i ) +

j∈δ(i) s r ij i ∈ B d (2)
q i -q i = -b ii (e 2 i + f 2 i ) + j∈δ(i) s c ij i ∈ B g (3)
-

q i = -b ii (e 2 i + f 2 i ) + j∈δ(i) s c ij i ∈ B d (4) s r ij = -G ij (e 2 i + f 2 i ) + G ij (e i e j + f i f j ) -B ij (e i f j -e j f i ) (i, j) ∈ L (5)
s c ij = B ij (e 2 i + f 2 i ) -B ij (e i e j + f i f j ) -G ij (e i f j -e j f i ) (i, j) ∈ L (6) v i ≤ e 2 i + f 2 i ≤ v i i ∈ B (7) (s r ij ) 2 + (s c ij ) 2 ≤ S ij (i, j) ∈ L (8) p i ≤ p i ≤ p i i ∈ B g (9)
q i ≤ q i ≤ q i i ∈ B g (10) (p, q) ∈ (R |Bg| , R |Bg| ), (e, f ) ∈ (R n , R n ), (s r , s c ) ∈ (R m , R m ) (11)
where C ∈ S + |Bg| is a diagonal and semidefinite matrix, c ∈ R |Bg| is the vector of linear costs of the power injection at each generator node, (v, v) ∈ (R n , R n ) are the bounds on the voltage magnitude, S ij the thermal limit of line (i, j), and (p, p, q, q) ∈ (R |Bg| , R |Bg| , R |Bg| , R |Bg| ). This formulation has 2(n + |B g | + m) variables, 2n quadratic equalities (1)-(4) that enforces the active and reactive power balances at each node, 2m quadratic equalities (5)-( 6) that define the power at each line, 2n quadratic inequalities (7) that models the voltage magnitude, m quadratic inequalities (8) that ensure the thermal line limits, and 4|B g | box constraints (9)-(10).

The first results of the literature for solving the OPF problem were focused on optimal local solutions, mostly by adapting interior point methods, see, e.g., [START_REF] Wu | A direct nonlinear predictor-corrector primal-dual interior point algorithm for optimal power flows[END_REF]; [START_REF] Torres | An interior-point method for nonlinear optimal power flow using voltage rectangular coordinates[END_REF]; [START_REF] Jabr | A primal-dual interior point method for optimal power flow dispatching[END_REF]; [START_REF] Wang | On computational issues of marketbased optimal power flow[END_REF]. In the context of global optimization, one requires furthermore to determine lower bounds on the OPF problem. For this, the second-order cone programming (SOCP) and the semidefinite programming (SDP) relaxations were first used (see [START_REF] Bai | Semi-definite programming-based method for security-constrained unit commitment with operational and optimal power flow constraints[END_REF]; [START_REF] Bai | Semidefinite programming for optimal power flow problems[END_REF]; [START_REF] Jabr | Radial distribution load flow using conic programming[END_REF]; [START_REF] Lavaei | Zero duality gap in optimal power flow problem[END_REF]; [START_REF] Zohrizadeh | A survey on conic relaxations of optimal power flow problem[END_REF]). The most used SDP relaxation, also named the rank relaxation, leads to very tight lower bounds on the OPF problem. In particular, it was proven in [START_REF] Gan | Exact convex relaxation of optimal power flow in radial networks[END_REF] that this relaxation is exact for a restricted class of problems and under some assumptions. In other cases, where it is not exact, the rank relaxation can be used within a branch-and-cut algorithm as it is done with a complex formulation of the OPF in [START_REF] Chen | A spatial branch-and-cut method for nonconvex qcqp with bounded complex variables[END_REF]. The approach called SDP-BT [START_REF] Gopinath | Proving global optimality of acopf solutions[END_REF] tightened the rank relaxation with RLT inequalities, and then iterates with Bound Tightening techniques until reaching global optimality. Another approach is to strength it following the ideas of the hierarchy of moment relaxation problems [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF]; [START_REF] Parrilo | Semidefinite programming relaxations for semialgebraic problems[END_REF], that can be applied to any polynomial optimisation problem. This approach was specialized in the context of the OPF problem in [START_REF] Josz | Application of the moment-sos approach to global optimization of the opf problem[END_REF], and showed its efficiency to solve small-size problems. It was also used in [START_REF] Molzahn | Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem[END_REF] to strengthen the lower bounds for larger problems. Unfortunately, in practice, using interior point methods for solving several large SDP relaxations, with increasing sizes at each rank of the hierarchy, is intractable for large networks. Several specialized algorithms that exploit the sparsity of power networks were thus proposed as in [START_REF] Jabr | Radial distribution load flow using conic programming[END_REF][START_REF] Jabr | Exploiting sparsity in sdp relaxations of the opf problem[END_REF]; [START_REF] Madani | Convex relaxation for optimal power flow problem: Mesh networks[END_REF]; [START_REF] Molzahn | Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem[END_REF]; [START_REF] Molzahn | Implementation of a large-scale optimal power flow solver based on semidefinite programming[END_REF].

More recently, several cheaper computable convex relaxations were introduced for the OPF problem. For instance, linear and quadratic envelopes for trigonometric functions in the polar formulation of the OPF problem are constructed in [START_REF] Coffrin | The qc relaxation: A theoretical and computational study on optimal power flow[END_REF]; [START_REF] Coffrin | Convex quadratic relaxations for mixed-integer nonlinear programs in power systems[END_REF]; [START_REF] Coffrin | A linear-programming approximation of ac power flows[END_REF], and strong SOCP relaxations were introduced in [START_REF] Kocuk | Strong socp relaxations for the optimal power flow problem[END_REF][START_REF] Kocuk | Matrix minor reformulation and socp-based spatial branchand-cut method for the ac optimal power flow problem[END_REF]. These bounds, that can be computed in polynomial time, may then be used within a spatial branch-and-bound framework to solve the OPF problem to global optimality.

Exact algorithms have also been proposed for a variant of problem (OP F ) where the thermal line limits (Constraints (8)) are not considered. In this case, variables s r ij and s c ij can be replaced in Constraints ( 1)-( 4) by their expression given by Constraints ( 5)-( 6), which reduce the total number of variables and constraints of the formulation. In [START_REF] Phan | Lagrangian duality and branch-and-bound algorithms for optimal power flow[END_REF], a sub-gradient algorithm is proposed to solve the Lagrangian dual of (OP F ), which is used as a bound in a global solution approach. In [START_REF] Foster | Mixed-integer quadratically-constrained programming, piecewise-linear approximation and error analysis with applications in power flow[END_REF], the spatial branch-and-bound is based on a piece-wise linear approximation. Another exact solution approach called RC-OPF was proposed in [START_REF] Godard | Global optimality of optimal power flow using quadratic convex optimization[END_REF], that is a specialization of the Quadratic Convex Reformulation approach proposed in Elloumi & Lambert [2019] for generic quadratic problems. It consists in a branch-and-bound algorithm based on a quadratic convex relaxation of the OPF problem. This convex relaxation, whose value reaches that of the rank relaxation, is computed in a pre-processing step by solving the rank relaxation. Then, at each node of the branch-and-bound tree, the bound is obtained by solving a convex problem with a quadratic convex objective function and linear constraints. The size of the relaxation is a quadratic function of the number of initial variables, since it relies on the introduction of one additional variable for each possible product of the original variables. Unfortunately, and as illustrated in Section 4, in practice the spatial branch-and-bound can be very time consuming for the OPF problem.

Our contribution is an exact solution algorithm for problem (OP F ), called Compact Quadratic Convex Reformulation (COPF), that relies on a quadratic convex relaxation whose size is a linear function of the number of initial variables. This compact relaxation is a quadratically constrained quadratic problem that also reaches the optimal value of the rank relaxation. The key advantage of COPF over RC-OPF is that the spatial branch-and-bound has to enforce a significantly smaller number of equalities between the additional variables and the products that they model to prove global optimality, which speeds up the resolution. An additional contribution in comparison to method RC-OPF is to provide a quadratic relaxation based method that handles the thermal line limits.

The paper is organized as follows. In Section 2, we present a new family of compact quadratic convex relaxations to (OP F ). In Section 3, we show how to calculate the tightest quadratic convex relaxation within this family. Finally, in Section 4, after by a brief recall of method RC-OPF and of the variant it applies, we present a computational comparison of the two approaches. Then, we evaluate COPF on instances of problem (OP F ) and we compare it with the method SDP-BT of [START_REF] Gopinath | Proving global optimality of acopf solutions[END_REF]. Section 5 draws a conclusion.

Building a compact family of quadratic convex relaxations

We start by observing that the structure of the formulation (OP F ) is specific. First, only variables p are involved into the objective function. Moreover, the matrix C is diagonal and positive semidefinite, hence the objective function is convex and separable. It follows that the non convexities only come from the quadratic constraints (1)-( 7). Moreover, in the constraints, variables e and f are only involved into quadratic forms, while variables p and q only in linear forms, while variables s r and s c appear both in linear and quadratic forms.

Starting from the latter observations, our idea is to build an equivalent problem to (OP F ), where the original constraints are convexified thanks to 2(n + m) auxiliary variables z = (z e , z f ) ∈ R 2n , and w = (w s r , w s c ) ∈ R 2m , that model the squares of the initial variables e, f , s r , and s c , respectively:

               z e i = e 2 i i ∈ B (12)
z f i = f 2 i i ∈ B (13)
w s r ij = (s r ij ) 2 (i, j) ∈ L (14) w s c ij = (s c ij ) 2 (i, j) ∈ L (15)
Using these new variables it is easy to rewrite Constraints (1)-( 4), ( 7) and (8) into a linear form, and we get:

                                         p i -p i = g ii (z e i + z f i ) + j∈δ(i) s r ij i ∈ B g (16)
-

p i = g ii (z e i + z f i ) + j∈δ(i) s r ij i ∈ B d (17) q i -q i = -b ii (z e i + z f i ) + j∈δ(i) s c ij i ∈ B g (18)
-

q i = -b ii (z e i + z f i ) + j∈δ(i) s c ij i ∈ B d (19) v i ≤ z e i + z f i ≤ v i i ∈ B ( 20
)
w s r ij + w s c ij ≤ S ij (i, j) ∈ L (21)
We now focus on the convexification of the quadratic equality constraints (5)-(6). For this, our first step is to transform each equality into two inequalities. We thus introduce for all (i, j) ∈ L, Constraints ( 22)-( 25)

obviously equivalent to Constraints ( 5)-( 6):

               s r ij + G ij (e 2 i + f 2 i ) -G ij (e i e j + f i f j ) + B ij (e i f j -e j f i ) ≤ 0 (i, j) ∈ L (22) -s r ij -G ij (e 2 i + f 2 i ) + G ij (e i e j + f i f j ) -B ij (e i f j -e j f i ) ≤ 0 (i, j) ∈ L (23) s c ij -B ij (e 2 i + f 2 i ) + B ij (e i e j + f i f j ) + G ij (e i f j -e j f i ) ≤ 0 (i, j) ∈ L (24) -s c ij + B ij (e 2 i + f 2 i ) -B ij (e i e j + f i f j ) -G ij (e i f j -e j f i ) ≤ 0 (i, j) ∈ L (25)
Then, recall that Inequalities ( 22)-( 25) are only quadratic on variables e and f . To make them convex, we apply the smallest eigenvalue method introduced in Hammer & Rubin [1970]. Denote by A r ij (resp. A c ij ) the sub-matrix of the Hessian of the (i, j) th Constraints (5) (resp. ( 6)) that corresponds to the quadratic terms involving variables e and f only. Let λ(A r ij ) be the smallest eigenvalue of matrix A r ij , and d(λ(A r ij )) be the diagonal matrix where each diagonal term equals λ(A r ij ). To rewrite Inequality (22) (resp. ( 23)) as a convex function, we add to it the quadratic quantity -λ(A r ij )

k∈B

(e 2 k +f 2 k -z e k -z f k ) (resp. -λ(-A r ij ) k∈B (e 2 k +f 2 k -z e k - z f k )). As a consequence the Hessian matrix of the new function is A r ij -d(λ(A r ij )) (resp. -A r ij -d(λ(-A r ij ))
) that is obviously a positive semidefinite matrix. Moreover, the value of the convexified function remains the same as soon as for all k ∈ B, e 2 k + f 2 k -z e k -z f k = 0, or equivalently when Equalities ( 12)-( 13) are satisfied. We thus obtain the set S of convex constraints:

S =                            s r ij + Gij(e 2 i + f 2 i ) -Gij(eiej + fifj) + Bij(eifj -ejfi) -λ(A r ij ) k∈B e 2 k + f 2 k -z e k -z f k ≤ 0 (i, j) ∈ L -s r ij -Gij(e 2 i + f 2 i ) + Gij(eiej + fifj) -Bij(eifj -ejfi) -λ(-A r ij ) k∈B e 2 k + f 2 k -z e k -z f k ≤ 0 (i, j) ∈ L s c ij -Bij(e 2 i + f 2 i ) + Bij(eiej + fifj) + Gij(eifj -ejfi) -λ(A c ij ) k∈B e 2 k + f 2 k -z e k -z f k ≤ 0 (i, j) ∈ L -s c ij + Bij(e 2 i + f 2 i ) -Bij(eiej + fifj) -Gij(eifj -ejfi) -λ(-A c ij ) k∈B e 2 k + f 2 k -z e k -z f k ≤ 0 (i, j) ∈ L
By replacing Constraints (1)-( 8) by Constraints ( 12)-( 21), together with set S in (OP F ), we then obtain an equivalent problem to (OP F ).

We now introduce a parameterized family of compact quadratic convex relaxations of (OP F ). For simplicity, we start by rewriting the initial equality constraints ( 1)-( 6) by using the notation

x = (e, f ) ∈ R 2n , s = (s r , s c ) ∈ R 2m
, and y = (p, q) ∈ R 2|Bg| , as follows:

⟨A k , xx ⊤ ⟩ + a y⊤ k y + a s⊤ k s = b k k ∈ C where C = (B g , B g , B d , B d , L, L), with |C| = 2(n+m), and ∀ k ∈ C, A k ∈ S 2n is the Hessian matrix of constraint k (i.e. matrices A rg k , A rd k , A cg k , A cd k , A r k , and A c k for Constraints (1)-(6) respectively), (a y k , a s k ) ∈ (R 2|Bg| , R 2m
) are the vectors of linear coefficients of constraint k, and b ∈ R 2(n+m) , where coefficient b k is the the right-hand side of constraint k.

Let (ϕ, γ, δ) ∈ (R 2(n+m) , R n , R m ) be three vector parameters, we build the following parameterized objective function:

h ϕ,γ,δ (x, y, s, z, w) =h(y) + k∈C ϕ k (⟨A k , xx ⊤ ⟩ + a y⊤ k y + a s⊤ k s -b k ) + i∈B γ i x 2 i + x 2 i+n -z i -z i+n + (i,j)∈L δ ij (s ij ) 2 + (s i+m,j+m ) 2 -w ij -w i+m,j+m
where h(y) is the initial objective function, and we recall that for all i ∈ B,

x i = e i , x i+n = f i , z i = z e i , z i+n = z f i , and for all (i, j) ∈ L, s ij = s r ij , s i+m,j+m = s c ij , w ij = w s r ij
, and w i+m,j+m = w s c ij . Observe that there exist parameters (ϕ, γ, δ) such that h ϕ,γ,δ is a convex function. Indeed, as mentioned above, function h(y) is convex and separable. Now, the two additional terms are linear in y, z and w, separable in s, and quadratic in x. By taking ∀ k ∈ C, φk = 0, and ∀i ∈ B, γi ≥ 0, and ∀(i, j) ∈ L, δij ≥ 0, the associated function h φ,γ, δ (x, y, s, z, w) is obviously convex.

By denoting ∀k ∈ C, λ k = λ min (A k ) and λ ′ k = λ min (-A k ),
we are now able to build a family of equivalent formulations to (OP F ):

(OP F ϕ,γ,δ )                                            min h ϕ,γ,δ (x, y, s, z, w) s.t. (9)(10)(12) -(21) ⟨A k , xx ⊤ ⟩ + a y⊤ k y + a s⊤ k s -λ k 2n i=1 (x 2 i -z i ) ≤ b k k ∈ C (26) ⟨-A k , xx ⊤ ⟩ -a y⊤ k y -a s⊤ k s -λ ′ k 2n i=1 (x 2 i -z i ) ≤ -b k k ∈ C (27) x = (e, f ) ∈ R 2n , s = (s r , s c ) ∈ R 2m , y = (p, q) ∈ R 2|Bg| (28) z = (z e , z f ) ∈ R 2n , w = (w s r , w s c ) ∈ R 2m (29)
where Constraints ( 26)-( 27) are Constraints of set S written in a compact form. It is easy to see that problem (OP F ϕ,γ,δ ) is equivalent to problem (OP F ), in the sense that any optimal solution from one is an optimal solution from the other. Indeed, h ϕ,γ,δ (x, y, s, z, w) = h(y) when Constraints ( 16)-( 19), ( 26), ( 27) and ( 12)-( 15) are satisfied.

We already observed that we can choose parameters such that the objective function h ϕ,γ,δ is a convex function. Thus, the only constraints that remain non-convex are Constraints ( 12)-(15). To derive a quadratic convex relaxation of (OP F ϕ,γ,δ ), we relax the latter equalities. For this, we need upper and lower bounds on each variable x i and s ij . For variables x i , some trivial initial bounds can easily be deduced from Constraints

(7), i. e. - √ v i ≤ x i ≤ √ v i , and - √ v i ≤ x i+n ≤ √ v i . We denote by (ℓ, u) ∈ (R 2n , R 2n ) these bounds (i.e. ℓ = (- √ v, - √ v) and u = ( √ v, √ v)).
To deduce bound for variables s ij , we use Constraints (8), i.

e. -S ij ≤ s ij ≤ S ij , and we denote by (ℓ ′ , u ′ ) ∈ (R 2m , R 2m ) these bounds (i.e. ℓ ′ = (-

√ S, - √ S) and u ′ = ( √ S, √ S)
). Then, we replace Constraints ( 12)-( 15) by the following set of convex inequalities:

D = (x, s, z, w)                z i ≤ (u i + ℓ i )x i -u i ℓ i z i ≥ x 2 i w ij ≤ (u ′ ij + ℓ ′ ij )s ij -u ′ ij ℓ ′ ij w ij ≥ s 2 i
Finally, we get (OP F ϕ,γ,δ ), a compact family of quadratic convex relaxations to (OP F ):

(OP F ϕ,γ,δ )        min h ϕ,γ,δ (x, y, s, z, w) s.t. (9)(10)(16) -(21)(26) -(29) (x, s, z, w) ∈ D (30)
For any parameters ϕ, γ, and δ such that h ϕ,γ,δ is a convex function, problem (OP F ϕ,γ,δ ) is a convex QCQP and can thus be solved in polynomial time. Our aim is to embed it within a spatial branch-andbound algorithm. Performing such an algorithm is highly dependant on the quality of the bound at the root node. Moreover, we know that for many instances of the OPF, the rank relaxation provides a tight lower bound. This is why in the rest of the paper, we focus on the computation of a quadratic convex relaxation of (OP F ) whose value equals to the optimal value of the rank relaxation.

Computing a strong quadratic convex relaxation

We are now interested in the best parameters (ϕ * , γ * , δ * ) that maximize the optimal value of (OP F ϕ,γ,δ ) while making the parameterized function h ϕ,γ,δ convex. We prove that these best parameters can be deduced from the dual optimal solution of the rank relaxation of (OP F ). For simplicity, we denote by γ ′ = (γ, γ) ∈ R 2n , and δ ′ = (δ, δ) ∈ R 2m . With this notation, we can rewrite function h ϕ,γ,δ as follows:

h ϕ,γ,δ ′ (x, y, s, z, w) = i∈Bg Ciiy 2 i + ciyi + ⟨ k∈C ϕ k A k + d(γ ′ ), xx ⊤ ⟩ + ⟨d(δ ′ ), ss ⊤ ⟩ + k∈C ϕ k (a y⊤ k y + a s⊤ k s -b k ) -γ ′ ⊤ z-δ ′ ⊤ w
where d(v) is the diagonal matrix of whose the i th -diagonal coefficient equals v i . We formally pose the problem we aim to solve as follows:

(P )

                 max ϕ,γ,δ v(OP F ϕ,γ,δ ) k∈C ϕ k A k + d(γ ′ ) ⪰ 0 d(δ ′ ) ⪰ 0 γ ′ = (γ, γ), δ ′ = (δ, δ)
where v(OP F ϕ,γ,δ ) is the optimal value of problem (OP F ϕ,γ,δ ).

We state in Theorem 3 that the optimal value of (P ) equals the optimal value of the following the so-called rank relaxation of (OP F ):

(SDP )                                                            min h(Y, y) = i∈Bg CiiYii + ciyi s.t. ⟨A k , X⟩ + a y⊤ k y + a s⊤ k s = b k ∀k ∈ C (31) Xii + Xi+n,i+n ≤ vi i ∈ B (32) -Xii -Xi+n,i+n ≤ -v i i ∈ B (33) W k+1,k+1 + W k+m+1,k+m+1 ≤ S k k = (i, j) ∈ L (34)
p i ≤ pi ≤ p i i ∈ Bg (35) q i ≤ qi ≤ q i i ∈ Bg (36)   1 y ⊤ s ⊤ y Y ⋆ s ⋆ W   ⪰ 0 (37) X ⪰ 0 (38) y = (p, q) ∈ R 2|Bg | , s ∈ R 2m , (Y, X, W ) ∈ (S 2|Bg | , S2n, S2m)
where Constraints (31) are the compact form Constraints (1)-( 6).

                                       pi -pi = gii(Xii + Xi+n,i+n) + k=(i,j):j∈δ(i) s k i ∈ Bg -pi = gii(Xii + Xi+n,i+n) + k=(i,j):j∈δ(i) s k i ∈ B d qi -qi = -bii(Xii + Xi+n,i+n) + k=(i,j):j∈δ(i) s k+m i ∈ Bg -qi = -bii(Xii + Xi+n,i+n) + k=(i,j):j∈δ(i) s k+m i ∈ B d s k = -Gij(Xii + Xi+n,i+n) + Gij(Xij + Xi+n,j+n) -Bij(Xi,j+n -Xj,i+n) k = (i, j) ∈ L s k+m = Bij(Xii + Xi+n,i+n) -Bij(Xij + Xi+n,j+n) -Gij(Xi,j+n -Xj,i+n) k = (i, j) ∈ L
Theorem. The optimal value of (P ) equals the optimal value of (SDP ).

Proof.

⋄ To prove that v(P ) ≤ v(SDP ), we show that for any feasible solution ( φ, γ, δ) to (P ), we have v(OP F φ,γ, δ ) ≤ v(SDP ), which in turn implies that v(P ) ≤ v(SDP ) since the right hand side is constant. Let (ȳ, s, Ȳ , X, W ) be a feasible solution of (SDP ), and build the solution (x = 0, y = ȳ, s = s, z = D( X), w = D( W )), where D(M ) is the vector composed of the diagonal terms of matrix M . We prove that: i) (x, y, s, z, w) is feasible for (OP F φ,γ, δ ), and ii) its objective value is smaller or equal than v(SDP ). Since both (OP F φ,γ, δ ) and

(SDP ) are minimization problems, (OP F φ,γ δ ) ≤ v(SDP ) follows.

i) We show that (0, ȳ, s, D( X), D( W )) is feasible to (OP F φ,γ, δ ). Obviously, Constraints ( 9)-(10), and ( 16)-( 21) are satisfied. We now prove that Constraints (26), ( 27), and (30) are satisfied.

(a) Constraints (26). We start by observing that, since x = 0, Constraints (26) can be rewritten as

b k -a y⊤ k ȳ -a s⊤ s -λ k 2n i=1
Xii ≥ 0, and by Constraints (31), we have: Xii , and with Constraints (31) we have:

b k -a y⊤ k ȳ -a s⊤ s -λ k 2n i=1 Xii = ⟨A k , X⟩ -λ k 2n i=1 Xii = ⟨A k -diag(λ k ),
-b k + a y⊤ k ȳ + a s⊤ s -λ ′ k 2n i=1 Xii = ⟨-A k , X⟩ -λ ′ k 2n i=1 Xii = ⟨-A k -diag(λ ′ k ), X⟩ ≥ 0 by Constraints (38) and since -A k -diag(λ ′ k ) ⪰ 0 (c) Constraints (30). Since x = 0, the set D becomes: Xii ≤ v i Xii ≥ 0
Since X ⪰ 0, we have Xii ≥ 0. The first inequality comes from Xi+n,i+n ≥ 0 and Constraints (32).

ii) Let us now compare the objective values of the two problems to show that v(OP F φ,γ, δ ) ≤ v(SDP ).

Since x = 0, the objective function of (OP F φ,γ, δ ) can be rewritten as:

h φ,γ, δ (0, ȳ, s, D( X), D( W )) = i∈Bg C ii ȳ2 i + c i ȳi + ⟨d( δ′ ), ss ⊤ ⟩ + k∈C φk (a y⊤ k ȳ + a s⊤ s -b k ) - γ′ ⊤ D( X) -δ ′ ⊤ D( W )
We prove below that ∆ = h φ,γ, δ (0, ȳ, s, D( X), D

( W )) -h( Ȳ , ȳ) ≤ 0 ∆ = i∈Bg C ii ȳ2 i + c i ȳi + ⟨d( δ′ ), ss ⊤ ⟩ + k∈C φk (a y⊤ k ȳ + a s⊤ s -b k ) - γ′ ⊤ D( X) -δ ′ ⊤ D( W ) - i∈Bg C ii Ȳii + c i ȳi ∆ = i∈Bg C ii (ȳ 2 i -Ȳii ) + ⟨d( δ′ ), ss ⊤ ⟩ + k∈C φk (a y⊤ k ȳ + a s⊤ s -b k ) - γ′ ⊤ D( X) -δ ′ ⊤ D( W )
By constraints (31), and by definition of γ′ and δ′ , we have:

∆ = i∈Bg C ii (ȳ 2 i -Ȳii ) + ⟨d( δ′ ), ss ⊤ ⟩ - k∈C φk ⟨A k , X⟩ -⟨d(γ ′ ), X⟩ -⟨d( δ′ ), W ⟩ ∆ = i∈Bg C ii (ȳ 2 i -Ȳii ) + ⟨d( δ′ ), ss ⊤ -W ⟩ -⟨ k∈C φk A k + d(γ ′ ), X⟩
We claim that ∆ ≤ 0 since each of its 3 terms are non positive: i∈Bg C ii (ȳ 2 i -Ȳii ) ≤ 0. By Constraint (37), we know that matrix

  1 y ⊤ y Y   ⪰ 0, which implies that
all its 2 × 2 minors are non negative, and in particular, we have ∀i, Ȳii -ȳ2 i ≥ 0. Since moreover C ii ≥ 0, we get the result.

⟨d( δ′ ), ss ⊤ -W ⟩ = 2m i=1 δ′ i (s 2 i -Wii ) ≤ 0.
By Constraint (37), we have ∀i, Wii -s2 i ≥ 0. Moreover, by feasibility of (P ), we have d( δ′ ) ⪰ 0 and we get the result.

-⟨ k∈C φk A k + d(γ ′ ), X⟩ ≤ 0. By Constraint (38), we have X ⪰ 0. Moreover, by feasibility of (P ), we have k∈C φk A k + d(γ ′ ) ⪰ 0 and we get the result.

⋄ Let us secondly prove that v(P ) ≥ v(SDP ). We suppose here that the original problem (OP F ) is feasible, and by Proposition 1 of [START_REF] Godard | Global optimality of optimal power flow using quadratic convex optimization[END_REF], we know that strong duality holds. Let (D) be the dual of (SDP ), under these hypothesis, we have v(SDP ) = v(D). To prove that v(P ) ≥ v(SDP ), we equivalently prove that v(P ) ≥ v(D) where (D) is the dual of (SDP ):

(D)                                                                max i∈Bg (θ p i p i + θ q i q i -θ p i p i -θ q i q i ) + i∈B (γ i v i -γ i vi) - k∈L δ k S k - k∈C ϕ k b k -ρ s.t. M =             ρ 1 2 (c + θ -θ + k∈C ϕ k a y k ) ⊤ ( k∈C ϕ k a s k ) ⊤ 0 ⊤ 2n 1 2 (c + θ -θ + k∈C ϕ k a y k ) C 0 2|Bg |,2m 0 2|Bg |,2n k∈C ϕ k a s k 0 2m,2|Bg | d(δ ′ ) 02m,2n 02n 0 2n,2|Bg | 02n,2m k∈C ϕ k A k + d(γ ′ )             ⪰ 0 (39) θ = (θ p , θ q ), θ = (θ p , θ q ), γ ′ = ((γ -γ), (γ -γ)), δ ′ = (δ, δ) (40)
C = C 0 |Bg |,|Bg | 0 |Bg |,|Bg | 0 |Bg |,|Bg | ∈ S 2|Bg | (41) c = (c, 0 |Bg | ), a k = (a y k , a s k ) (42) (ϕ, γ, γ, δ, θ p , θ p , θ q , θ q , ρ) ∈ (R |C| , R n , R n , R m , R |Bg | , R |Bg | , R |Bg | , R |Bg | , R)
where ϕ, γ, γ, δ, (θ p , θ p ), (θ q , θ q ), ρ are the dual variables associated to Constraints (31)-( 37) respectively. We notice here that the dual variable ρ ∈ R is associated to the constraint which sets the value of the first diagonal term of the matrix M to 1. We denote by 0 n ( 0 n,n respectively ) the n-dimensional (n × n-dimensional resp.) vector (matrix resp. ) where each coefficient equals 0.

Problems (D) and (P ) are both maximization problems. To prove that v(P ) ≥ v(D), we start with an optimal solution to (D), from which we build a feasible solution to (P ) whose objective value is greater than v(D).

Let (ϕ * , γ * , γ * , δ * , θ p * , θ p * , θ q * , θ q * , ρ * ) be an optimal solution to (D), we build the following solution

(ϕ = ϕ * , γ = (γ * -γ * ), δ = δ * ) that is obviously feasible for (P ), i.e. k∈C ϕ * k A k + d(γ ′ * ) ⪰ 0, and d(δ ′ * ) ⪰ 0,
by Constraint (39). The objective value of this solution is equal to v(OP F ϕ * ,γ * -γ * ,δ * ). To prove that v(OP F ϕ * ,γ * -γ * ,δ * ) ≥ v(D), we prove that for any feasible solution (x, y, s, z, w) to (OP F ϕ * ,γ * -γ * ,δ * ), the associated objective value is not smaller than the optimal value of (D). Denote by ∆ the difference between the objective values, we prove below that ∆ ≥ 0.

∆ = i∈Bg C ii y 2 i + c i y i + ⟨d(δ ′ * ), ss ⊤ ⟩ + ⟨ k∈C ϕ * k A k + d(γ ′ * ), xx ⊤ ⟩ + k∈C ϕ * k (a y⊤ k y + a s⊤ k s -b k ) -γ ′ * ⊤ z -δ ′ * ⊤ w - i∈Bg (θ p * i p i + θ q * i q i -θ p * i p i -θ q * i q i ) - i∈B (γ * i v i -γ * i v i ) + k∈L δ * k S k + k∈C ϕ * k b k + ρ * ∆ = ⟨C, yy ⊤ ⟩ + ⟨d(δ ′ * ), ss ⊤ ⟩ + ⟨ k∈C ϕ * k A k + d(γ ′ * ), xx ⊤ ⟩ - i∈Bg (θ p * i p i + θ q * i q i -θ p * i p i -θ q * i q i ) + k∈C ϕ * k (a y⊤ k y + a s⊤ k s) + i∈Bg c i y i - i∈B (γ * i v i -γ * i v i ) + k∈L δ * k S k - i∈B (γ * i -γ * i )(z e i + z f i ) - k∈L δ * k (w s r k + w s c k ) + ρ *
By Constraints ( 9) and ( 10) and since all coefficients θ p * i , θ p * i , θ q * i , θ q * i are non-negative, we get:

∆ = ⟨C, yy ⊤ ⟩ + ⟨d(δ ′ * ), ss ⊤ ⟩ + ⟨ k∈C ϕ * k A k + d(γ ′ * ), xx ⊤ ⟩ - i∈Bg (θ p * i p i + θ q * i q i -θ p * i p i -θ q * i q i ) + k∈C ϕ * k (a y⊤ k y + a s⊤ k s) + i∈Bg c i y i + i∈B γ * i (v i -z e i -z f i ) + γ * i (z e i + z f i -v i ) + k∈L δ * k (S k -w s r k -w s c k ) + ρ *
By Constraints ( 20) and ( 21) and and since all coefficients γ * i , γ * i , δ * k are non-negative, we get:

∆ ≥ ⟨C, yy ⊤ ⟩ + ⟨d(δ ′ * ), ss ⊤ ⟩ + ⟨ k∈C ϕ * k A k + d(γ ′ * ), xx ⊤ ⟩ + (θ -θ) ⊤ y + k∈C ϕ * k a y⊤ k y + c ⊤ y + k∈C ϕ * k a s⊤ k s + ρ * ∆ ≥ ⟨C, yy ⊤ ⟩ + ⟨d(δ ′ * ), ss ⊤ ⟩ + ⟨ k∈C ϕ * k A k + d(γ ′ * ), xx ⊤ ⟩ + (θ -θ + k∈C ϕ * k a y k + c) ⊤ y + k∈C ϕ * k a s⊤ k s + ρ * ∆ ≥         1 y s x         ⊤ M         1 y s x        
Finally, by Constraint (39) ∆ ≥ 0

□

In Corollary 3, we give a characterization of an optimal solution of (P ).

Corollary.

If (OP F ) is feasible, an optimal solution (ϕ * , γ * = (γ * -γ * ), δ * ) of (P ) can be computed by solving (SDP ). In particular, ϕ * is the vector of optimal dual variables associated to Constraints (31), γ * , γ * , the vectors of optimal dual variables associated to Constraints ( 32) and ( 33) respectively, and δ * the vectors of optimal dual variables associated to Constraints (34) .

Proof.

We know by Constraint ( 39) that (ϕ * , γ * = (γ * -γ * ), δ * ) is feasible for (P ), and in the proof of Theorem 3, we proved that the associated value of (P ) reaches v(SDP ). □

The idea is now to perform a spatial branch-and-bound algorithm based on the relaxation (OP F ϕ * ,γ * ,δ * ).

In our method, it is sufficient to solve (SDP ) once at the root node, then, in all other nodes, the computation of the bound will be done by solving a QCQP. Usually, and as proposed in [START_REF] Chen | A spatial branch-and-cut method for nonconvex qcqp with bounded complex variables[END_REF]; Gopinath et al.

[2020], branch-and-bound algorithms that take advantage of the quality of the SDP bound, solve at each node an SDP relaxation whose ranges on the variables are increasingly smaller. A fundamental difference with our approach is that we solve a QCQP at each node, which is most often faster. To further strengthen the value of the bound calculated at the intermediate nodes of the tree, we can add to our relaxation the convex quadratic inequalities of the initial formulation. Finally, the quadratic convex relaxation we use in our branch-and-bound is thus the following problem:

(OP F * )                min h ϕ * ,γ * ,δ * (x, y, s, z, w) s.t. (9)(10)(16) -(21)(26) -(30) e 2 i + f 2 i ≤ v i i ∈ B ( 43
) (s r ij ) 2 + (s c ij ) 2 ≤ S ij (i, j) ∈ L (44)
Note however that these Inequalities ( 43)-( 44) will not tighten the bound at the root node, as they are already considered in (SDP ). We sum up our global optimization algorithm Compact OPF (COPF) in Algorithm 1.

Algorithm 1 Solution algorithm COPF for exact solution of (OP F )

step 1: Solve (SDP ).

step 2: Deduce ϕ * , γ * ′ , and δ * .

step 3: Solve (OP F ) with a spatial B&B based on the quadratic convex relaxation (OP F * ) .

A practical advantage of our compact relaxation, in comparison to methods based on complete linearization of the constraints, is that we only have to enforce 2(n + m) equalities, instead of (2(n + m)) 2 , to prove global optimality. Another contribution is that since any convex QCQP can be reformulated as a SOCP, it means that our new method COPF allows to derive a SOCP relaxation that reaches the value of the semidefinite rank relaxation.

Numerical experiments

To evaluate our new method, we first compare it with the method RC-OPF which is also a method based on a convex quadratic relaxation. As RC-OPF only supports a variant of problem OPF where the thermal line limits are not considered, we evaluate in a first part COPF on this variant. Then, in a second part, we present a comparison of COPF with the method SDP- BT Gopinath et al. [2020] on instances of problem (OP F ).

Experimental environment:

Our experiments were carried out on a server with 2 CPU Intel Xeon each of them having 12 cores and 2 threads of 2.5 GHz and 4 * 16 GB of RAM using a Linux operating system. We used the semidefinite solver

Mosek ApS [2019] for solving the semidefinite programs. At each node of the spatial branch-and-bound, we used the solver Mosek for solving the QCQP of method COPF, and the solver Cplex 12.9 for solving QP of method RC-OPF. For computing feasible local solutions, we use Matpower Zimmerman & Murillo-Sánchez

[2020]; [START_REF] Zimmerman | Matpower: Steady-state operations, planning, and analysis tools for power systems research and education[END_REF].

Results for instances without thermal line limits

In this section, we make a detailed comparison between methods COPF and RC-OPF [START_REF] Godard | Global optimality of optimal power flow using quadratic convex optimization[END_REF].

We start by outlining RC-OPF that applies to the following variant of (OP F ):

(OP F ′ )                            min h(y) = i∈Bg Ci,iy 2 i + ciyi s.t. ⟨A k , xx ⊤ ⟩ + a ⊤ k y = b k k ∈ C (45) v i ≤ e 2 i + f 2 i ≤ vi i ∈ B (46)
p i ≤ pi ≤ p i i ∈ Bg q i ≤ qi ≤ q i i ∈ Bg x = (e, f ) ∈ (R n , R n ), y = (p, q) ∈ (R |Bg | , R |Bg | )
where Constraints 45 are the compact form of the following set of constraints:

                             p i -p i = G ii (e 2 i + f 2 i ) + j∈δ(i) G ij (e i e j + f i f j ) -B ij (e i f j -e j f i ) i ∈ B g -p i = G ii (e 2 i + f 2 i ) + j∈δ(i) G ij (e i e j + f i f j ) -B ij (e i f j -e j f i ) i ∈ B d q i -q i = -B ii (e 2 i + f 2 i ) + j∈δ(i) -B ij (e i e j + f i f j ) -G ij (e i f j -e j f i ) i ∈ B g -q i = -B ii (e 2 i + f 2 i ) + j∈δ(i) -B ij (e i e j + f i f j ) -G ij (e i f j -e j f i ) i ∈ B d
The basic idea is to introduce a matrix variable X ∈ S 2n that model the products xx ⊤ . With these additional variables, it is easy to linearize Constraints ( 45) and ( 46). Then, for a given semi-definite matrix M ∈ S + 2n , we consider the parameterized convex objective function: h M (x, y, X) = h(y) + ⟨M, xx ⊤ -X⟩. Obviously function h M (x, y, X) = h(y) if equalities X = xx ⊤ are satisfied. To build a family of convex relaxation of (OP F -R), we relax the latter non-convex equalities with the McCormick envelopes [START_REF] Mccormick | Computability of global solutions to factorable non-convex programs: Part i -convex underestimating problems[END_REF]).

Then, the idea is to compute a positive semi-definite matrix M * that maximizes the value of the obtained convex relaxation. It is proven in [START_REF] Godard | Global optimality of optimal power flow using quadratic convex optimization[END_REF] that M * can be deduced from the optimal dual variables of the rank relaxation of (OP F -R). In particular, by denoting ϕ * and γ * the dual optimal variables of Constraints ( 45) and ( 46), respectively,

M * = k∈C ϕ * k A k + d(γ ′ *
). Finally, we obtain the following quadratic convex relaxation:

(OP F ′ * )                                                min f M * (x, y, X) = i∈Bg C ii p 2 i + c i p i + ⟨ r∈C ϕ * k A k + d(γ ′ * ), xx ⊤ -X⟩ s.t. ⟨A k , X⟩ + a ⊤ k y = b k k ∈ C v i ≤ X ii + X i+n,i+n ≤ v i i ∈ B X ij ≤ u i x j + ℓ j x i -u i ℓ j (i, j) ∈ B 2 X ij ≤ ℓ i x j + u j x i -ℓ i u j (i, j) ∈ B 2 X ij ≥ u i x j + u j x i -u i u j (i, j) ∈ B 2 X ij ≥ ℓ i x j + ℓ j x i -ℓ i ℓ j (i, j) ∈ B 2 x = (e, f ) ∈ R 2n , y = (p, q) ∈ R 2|Bg| , X ∈ S 2n
As in method COPF, we have the property that the optimal value of (OP F ′ * ) reaches the optimal value of the rank relaxation of (OP F ′ ). However, the two convex relaxations differ both by their sizes and structures.

Indeed, in method RC-OPF, we build a linearly constrained quadratic program with O(n 2 ) variables and constraints, while in method COPF, we compute a quadratically constrained quadratic program with only O(n) variables and constraints.

In our experiences, we considered medium-sized instances of power networks having 3 to 300 buses, without thermal line limits. We report in To compare the performances of methods COPF, RC-OPF, and the solver Baron 19.3.24, we use a performance profile (see [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]) of the CPU times. A performance profile plots one curve for each solver considered. Each point of a curve gives, for a given factor τ , the proportion of instances whose CPU time was at most τ times greater than the fastest solver. In particular, for τ = 1, we have the proportion of instances on which the solver was the fastest. More precisely, for each instance i and each solver s, we denote by t is the time for solving instance i by solver s, and we define the performance ratio as r is = tis min s t is .

Let N be the total number of instances considered, an overall assessment of the performance P ∈ [0, 1] of solver s for a given τ is given by P (r is ≤ τ ) = 1 N * number of instance such that r is ≤ τ . In Figure 1, we present the performance profile of the CPU times for methods COPF, RC-OPF, and the solver Baron 19.3.24 of the instances described in Table 1. We observe that COPF and RC-OPF significantly outperform the solver Baron. In fact Baron solves to optimality only 6 instances out of the 33 considered, the largest of which is pglib opf case14 ieee. The two other approaches are more efficient, since they solve within 1 hours of CPU time, 18 instances for RC-OPF and 23 for COPF. Moreover, this profile shows that COPF is faster than RC-OPF for these instances. Note that T = 60 minutes corresponds the time limit. If the instance is solved in less than T minutes, we report between brackets the total CPU time in seconds to solve the instance. If the value is in bold, it means that it is faster, or that it ends with a better gap after 60 minutes of CPU time. Finally, Column Nodes is the number of nodes visited by the branch-and-bound.

A first observation concerns the quality of the initial gap for 15 instances out of the 33 considered that confirms the strength of the rank relaxation. For these instances, the results of the two approaches are similar, even if COPF is a bit faster with a CPU time that is reduced by a factor 1.34 on average. On the other hand, these experiments clearly show that the exact resolution of the instances where the gap is non-zero remains very difficult. In fact, during its branch-and-bound, RC-OPF does not decrease the lower bound, despite a large number of explored nodes. This is not the case for COPF, which, with a much smaller number of nodes, slightly increases the lower bound over the course of the branch-and-bound, even for the largest instances. This is because the number of auxiliary variables and relaxed equalities z i = x 2 i is strongly reduced in COPF (by a factor 4 on average). Let us finally mention that the reformulation time is (always less than 1 minute) significantly shorter than the global resolution time. Column Ratio is the ratio between the time of COPF and that of SDP-BT, it is in bold if it is smaller than 576. For this experiences, we use the same optimality threshold ϵ = 10 -2 than in [START_REF] Gopinath | Proving global optimality of acopf solutions[END_REF].

A first observation is that SDP-BT is able to reduce the gap of all the considered instances to less than 1% within the time limit, while method COPF reduces it for 21 instances out of 26 to the optimality threshold.

More precisely, for these 21 instances, SDP-BT takes on average 2 seconds and COPF 44 seconds to reach a gap smaller than ϵ, this means that SDP-BT is on average 22 time faster than COPF. Recall that the results of SDP-BT reported in

Conclusion

We consider the OPF problem that determines the power production at each bus of an electric network minimizing a production cost. In this paper, we introduce a global optimisation algorithm that is based on a new quadratically constrained quadratic relaxation. This relaxation is compact in the sense that it has only O(n + m) auxiliary variables and constraints, where n is the number of buses of the network, and m the number of transmission lines. We moreover prove that our quadratic relaxation has the same optimal value as the rank relaxation. Finally, to solve (OP F ) to global optimality, we perform a spatial branchand-bound algorithm based on our new quadratic convex relaxation. Another advantage of our approach is that to prove global optimality, we have a reduced number of non-convex equalities to force into spatial the branch-and-bound. We report computational results on instances of the literature. These results show that this new approach is more efficient than the method RC-OPF, and competitive with state-of-the-art methods.

A future work consists in using Bound Tightening Techniques to further improve the behaviour of COPF on the most difficult instances.

  X⟩ ≥ 0 by Constraint (38) and since A k -diag(λ k ) ⪰ 0 (b) Constraints (27). Similarly, since x = 0, Constraints (27) can be rewritten as -b k + a y⊤ k ȳ + a s⊤ s -

Figure 1 :

 1 Figure 1: Performance profile of the CPU time for networks with 2 to 300 buses (time limit 1 hour -optimality threshold ϵ = 10 -5 ).

Finally

  , we present in Table2, a detailed comparison between methods COPF and RC-OPF,where each line corresponds to one instance. Column Gap-SDP : = Opt -SDP Opt * 100, is the initial gap at the root node of the branch-and-bound, where SDP is the optimal value of the rank relaxation of (OP F -R), andOpt its best known solution value. Columns #vars report the number of auxiliary variables in COPF or in RC-OPF. This is also the number of non-convex equalities to force during the spatial branch-and-bound of each method. Columns Tm report the gap obtained after running the branch-and-bound during T minutes.

  seconds, we report between brackets the final gap = Opt -LB Opt * 100 where LB is the lower bound obtained after 1800 seconds of CPU time, and Opt its best known solution value. Columns Iterations and N odes report the number of iterations in the loop of SDP-BT, and of nodes in the b&b of COPF, respectively. Finally,

Table 1 :

 1 Table 1 the characteristics of each instance: its Name, and the number of Buses, Generators, and Lines of the considered power network. We indicate in Column Opt the best known solution value of each instance. Column |(y, x)| specifies the number of variables of each instance. Characteristics of the considered instances of PG-lib library.

	Name	Buses Generators Lines	Opt	|(y, x)|
	WB2 typ	2	1	1	9.06	6
	3 lmbd typ	3	3	3	5 694.54	12
	WB5 typ	5	2	6	13.78	14
	5 pjm typ	5	5	5	14 997.04	20
	6ww typ	6	3	11	3 126.31	18
	14 ieee typ	14	5	20	2 178.08	38
	24 ieee rts typ	24	33	38	63 352.21	114
	30 as typ	30	6	41	801.55	72
	30 ieee typ	30	6	41	6 592.95	72
	39 epri typ	39	10	46	133 801.71	98
	57 ieee typ	57	7	80	37 589.34	128
	73 ieee rts typ	73	99	120	189 764.08	344
	89 pegase typ	89	12	210	106 697.06	202
	118 ieee typ	118	54	186	96 881.51	344
	162 ieee dtc typ	162	12	284	84 785.01	348
	179 goc typ	179	29	263	750 173.90	416
	200 activ typ	200	38	245	27 557.57	476
	240 pserc typ	240	143	448	3 223 503.88	766
	300 ieee typ	300	69	411	546 890.15	738
	3 lmbd api	3	3	3	10 077.59	12
	5 pjm api	5	5	5	73 253.27	20
	14 ieee api	14	5	20	5 688.57	38
	24 ieee rts api	24	33	38	104 439.96	114
	30 as api	30	6	41	2 770.30	72
	30 ieee api	30	6	41	15 007.92	72
	39 epri api	39	10	46	237 200.66	98
	57 ieee api	57	7	80	49 290.36	128
	73 ieee rts api	73	99	120	366 984.79	344
	118 ieee api	118	54	186	167 810.79	344
	162 ieee dtc api	162	12	284	109 391.13	348
	179 goc api	179	29	263	1 670 159.94	416
	200 activ api	200	38	245	26 129.06	476
	300 ieee api	300	69	411	678 486.38	738

Table 3 :

 3 Table3, corresponds to a parallel implementation, carried out on 576 threads. In that context, it is hard to make a fair comparison of the two methods. Two remarks are in order. First, since COPF is only 22 slower than SDP-BT, it can be considered competitive with SDP-BT. Second, including Bound-Tightening techniques to COPF should probably helps it to converge faster to an optimal solution. Comparison of the CPU times of methods COPF and SDP-BT (time limit 1800s -optimality threshold ϵ = 10 -2 )

		SDP-BT Gopinath et al. [2020]	COPF
	Name	Time (s)	Iterations	Time (s) Nodes Ratio
	3 lmbd typ	0.03	0	5	0	167
	5 pjm typ	0.05	0	316	6475	6320
	14 ieee typ	0.19	0	5	0	26
	24 ieee rts typ	0.31	0	7	0	23
	30 as typ	0.37	0	6	0	16
	30 ieee typ	0.27	0	6	0	22
	39 epri typ	0.52	0	7	0	13
	57 ieee typ	1.07	0	9	0	8
	73 ieee rts typ	1.55	0	27	0	17
	89 pegase typ	9.39	0	57	0	6
	118 ieee typ	7.07	0	66	0	9
	162 ieee dtc typ	773.94	1	(1.78%)	35
	179 goc typ	3.57	0	102	0	29
	3 lmbd api	0.04	0	109	2227	2725
	5 pjm api	0.07	0	6	0	86
	14 ieee api	0.17	0	6	0	35
	24 ieee rts api	17.38	1	(3.08%)	3929
	30 as api	0.28	0	9	1	32
	30 ieee api	0.44	0	6	0	14
	39 epri api	0.35	0	9	0	26
	57 ieee api	0.99	0	11	0	11
	73 ieee rts api	67.71	1	(5.66%)	212
	118 ieee api	408.67	11	(7.83%)	23
	162 ieee dtc api	1111.21	1	(1.52%)	0
	179 goc api	6.23	0	112	0	18

Results for instances including thermal line limits

We now evaluate the performances of COPF on instances of (OP F ) and compare it with the method SDP- BT Gopinath et al. [2020]. This approach solves (OP F ) to global optimality with an iterative algorithm.

At each iteration, problem (SDP ) strengthened by RLT inequalities is first solved using the solver Mosek.

Then, to reduce the ranges of the variables, they solve up to T = 576 SDP Bound Tightening problems in parallel. The loop ends either when all variables are fixed, or when the number of iteration reaches a threshold that is set to 100, or when the current gap is smaller than ϵ = 10 -2 . It is important to note that for method COPF, each node is evaluated in a sequential mode. Thus, a rigorous comparison of the two methods would require running the algorithm of [START_REF] Gopinath | Proving global optimality of acopf solutions[END_REF] algorithm with T = 1.

We present in Table 3 the results for instances of (OP F ) having 3 to 200 buses. The results of method SDP-BT are taken from [START_REF] Gopinath | Proving global optimality of acopf solutions[END_REF]. Each line corresponds to one instance. Column Time (s)

is the total CPU time in seconds for solving the instance. If it is not solved within the time limit of 1800