The Branch-and-Bound Algorithm in Optimizing Mathematical Programming Models to Achieve Power Grid Observability

Abstract

Phasor Measurement Units (PMUs) are the backbone of smart grids that are able to measure power system observability in real-time. The deployment of synchronized sensors in power networks opens up the advantage of real-time monitoring of the network state. An optimal number of PMUs must be installed to ensure system observability. For that reason, an objective function is minimized, reflecting the cost of PMU installation around the power grid. As a result, a minimization model is declared where the objective function is defined over an adequate number of constraints on a binary decision variable domain. To achieve maximum network observability, there is a need to find the best number of PMUs and put them in appropriate locations around the power grid. Hence, maximization models are declared in a decision-making way to obtain optimality satisfying a guaranteed stopping and optimality criteria. The best performance metrics are achieved using binary integer, semi-definite, and binary polynomial models to encounter the optimal number of PMUs with suitable PMU positioning sites. All optimization models are implemented with powerful optimization solvers in MATLAB to obtain the global solution point.

1. Introduction

An electricity power grid network is a complex and dynamic arrangement that must be observed without interruption to provide a continuous power supply to the customers [1,2].

The power network state is determined by the assignment of phasor voltages to nodes, electrical current values, and power values to generators and loads. One preferred method to make the power grid smart is to observe its state in real-time [1,2].

These days, power systems are transformed into smart grids (SGs) [1,2,3]. To implement a modern power system, improved sensors that will observe the power grid’s state must be taken into consideration for installation [1,2,3].

Such technologically advanced sensors are synchrophasor devices, which are well-known as PMUs [1,2,3]. Over the past two decades, there has been a lot of investigation of synchronized measurement derived by PMUs in wide-area processors for applications such as observation of the entire power grid and stability, control, and protection tasks involved with a secured condition of the grid. Also, a large number of PMUs are installed in transmission and distribution power grids [1,2].

PMU measures electrical quantities such as phasor voltage at a power network node and the phasor current emanating from that bus to the adjacent neighborhood nodes [1].

PMUs are smart devices that provide unprecedented factors leading to success for the operation of the system and control applications due to their accessible voltage phasors and currents related to a frequent global time reference, despite the fact that they are calculated by remote system parts [1].

A PMU is a monitoring device, also known as a synchrophasor, that is installed on a power grid bus. The synchrophasor is able to measure the voltage magnitude and phase angle fully synchronized with a signal achieved continuously from the global positioning system (GPS) [1].

PMUs supply precisely the power quality view around the wide of an electricity power grid [1]. Each synchrophasor device is installed at a selected network bus, collects the voltage at that node and the current measurement towards the neighborhood nodes, and sends them to the system operator for wide-area applications [1].

All electrical quantities are sent to the phasor data concentrator (PDC), which works together with the supervisory control and data acquisition (SCADA) system [1]. Smart grids, together with the Internet of Things, are taken into account as the future of modern electricity power grids [3].

The electricity power grid is defined as fully observable on the condition that the phasor voltage of all system nodes is calculated utilizing synchronized or pseudo-measurements [1,2].

A full observability scenario is defined as the system state where all voltage-phasor buses can be observed. A PMU is a monitoring device that can be installed at a power graph vertex to directly observe the voltage phasor at that vertex and the current phasors of all adjacent edges to that vertex [3,4,5]. Technical or economic restrictions forbid the installation of these measuring and monitoring devices at each system node [1].

The optimal PMU placement (OPP) problem is an optimization problem [1] abstracted from an approach to observe the state of a power electricity grid. The OPP problem is considered to be a discrete optimization problem reflecting the smallest minimum dominating set problem [4,5,6,7,8]. Its solution is to pose a minimum number of PMUs to observe the whole power grid [9,10,11,12,13,14,15,16,17,18].

The power grid is studied as a graph, and for a good enough act of watching over the power grid, the supervision of the power grid needs the monitoring of the voltage phasor at each vertex as well as the current emanating from that vertex to be observed [3,4,5,6,7,8].

To determine the observability state of a modern power grid, many placement models have been implemented in the past based on finding the optimal number of PMUs [12,13,14,15,16,17,18]. An optimization model is based on a constraint function and leads to a solution that satisfies all the restrictions that meet the cost requirement [12,13,14,15,16,17,18].

Until now, the OPP problem has been studied to come across a suboptimal or optimal number of PMUs, and a placement site is delivered to cover the complete observation scenario of the power grid state [12,13,14,15,16,17,18].

Mathematical or heuristic algorithms encounter the number of PMUs required to be posed at selected buses around the power grid [12,13,14,15,16,17,18]. The most commonly utilized algorithm to solve the OPP problem is binary integer programming, and some pioneering works are reported in the bibliography [19,20,21,22,23]. In [24], integer quadratic programming is utilized to handle optimality and measurement redundancy tasks. A Groebner base algorithm is utilized to solve the OPP problem in [25].

Semi-definite programming optimizes a linear objective function under linear matrix inequality (LMI) constraints, whereas the solution is found in a binary decision domain [26,27,28]. An optimization strategy is presented in which the task of maximum measurement redundancy is considered based on a neighborhood search [29].

A three-phase algorithm is utilized to find the minimum number of PMUs required to render the system entirely observable [29]. The numerical outcome illustrates that the proposed methodology is easy to implement and gives optimal placement sites to achieve effective observation in wide area monitoring systems (WAMS). WAMS is a system operator application that is able to observe the entire power grid through an adequate number of PMUs properly installed at appropriate power grid nodes [1,2].

The authors in [30] utilized the graph theory method to find a solution for the OPP and the minimum PMU number. A genetic algorithm (GA) [31,32], a binary cuckoo optimization algorithm (BCOA) [33], a binary gravitational search algorithm (BGSA) [34], a binary particle swarm algorithm (BPSO) [35,36,37], and a crow search algorithm (CSA) [38] are utilized to solve heuristically the OPP problem.

GAs [31,32] or BPSO [35,36,37] heuristically search the feasible areas constituted by the integer linear program’s constraint to converge to a local solution point. To reach a desired solution, a comparative study with BBA’s metrics is required [32].

This is a general remark that an evolutionary algorithm’s output must be compared with that found by BBA to judge if this outcome is the local solution or the global one [9].

In an evolutionary code, there is no sufficient stopping criterion that absolutely indicates when the output is exactly perfect. This makes it impossible to predict when the output will be accurate [9].

Works in [39,40] propose a multi-objective function to be optimized for achieving maximum observability. Both works utilize evolutionary algorithms such as the whale optimization algorithm (MWOA) [39] and the dingo optimizer [40].

The outcomes are credible, and they can be used for validation of the proposed algorithmic scheme’s results. Both algorithms are based on a trial-and-error effort to locate a solution with uncertainties about whether this solution is global or not [9,10,11].

Despite this algorithmic truth, the authors in both works succeed in finding solutions that satisfy the maximum network observability [22]. A two-step method and a quadratic programming method are utilized in [41] to gather those solutions with maximum measurement redundancy. Although there is no strictly mathematical rule leads to a global solution, these algorithms locate the optimal number of PMUs [19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46].

A weighted least squares algorithm is studied where a quadratic function is optimized under an equality constraint function [43]. Although it is promising to use a nonlinear approach in a binary domain, this solution suffers from approximate solutions [43].

A nonlinear optimization algorithm’s return must satisfy specific tolerances such as objective function evaluation, constraint violation, and the tolerance of the step size on the decision variable change per iteration [44].

Mathematical algorithms such as recursive quadratic programming (RQP) [45] or generalized pattern search algorithm (GPSA) [46] utilize function evaluations and step-size on the decision variables to end the iterative process with care that the final output is a local and feasible solution at the same time as pointed out in [44].

RQP [45] and GPSA [46] were studied by the authors to solve a nonlinear system where the equality constraints are fewer than the number of decision problems [9]. RQP [45] and GPSA [46] handle the nonlinear problem and result in a pure binary local point without approximate uncertainties on the quality of the solution [45].

Both nonlinear algorithms find locally optimal solutions satisfying specific feasibility and iteration-stopping criteria [44].

Moreover, GPSA is considered an improvement because it optimizes a one-product cost function that leads to solutions with maximum network observability [22]. In this study, binary variables are employed to convert the nonlinear problem originally defined within a continuous variable domain [45,46] into a binary quadratic polynomial problem.

GPSA locates optimal solutions with the same quantity and quality as those found in [34,35,39,40,41]. Works in [34,35,39,40,41] optimize a multi-objective function to find a desired solution, whereas a GPSA [46] minimizes a one-cost function to be optimized. All scientific works define the upper limit of the system redundancy observability index (SORI) as proposed in [22], and the outcomes are used as a comparative study to validate our algorithmic scheme results.

These solutions are utilized in this study for further validation of the robustness of the presented optimization results from the aspect of maximum network observation of the power grid [22]. Also, a wide-area monitoring application is studied in [47] to upgrade protection and control issues using PMUs in addition to a communication infrastructure (CI) to bring all PMUs to the PDC [1].

A symmetry topological observability based on the ILP method is proposed in [48] for the solution to the OPP problem. Also, an optimization based on the OPP model is presented in [49] under several contingencies for reliable power system monitoring.

An ILP-based method deliver the number of the intelligent monitoring devices and their best optimal sites in [50].

Nonlinear approaches like RQP [45,51] are reported in [52] for power system and analysis applications. Also, OpenEdgePMU architecture is presented in [53]. Other techniques, such as an optimized extreme learning machine-based procedure and the utilization of synchrophasors to guarantee real-time power transient stability prediction, are proposed in [54].

Lately, micro-PMUs have been installed in power distribution systems, and papers have been published to review the utilization of these monitoring devices in this domain [55,56,57]. Also, new state estimation tools are proposed in [58,59] or further processing of PMUs and SCADA measurements to obtain better power grid monitoring [1,2].

Also, recently published papers have illustrated the benefit of the utilization of PMU data with the Kalman filter for actual-time state estimation of the power grid [60,61].

Also, a state estimator based on least-trimmed squares is proposed in [62]. A newly published work proposes a state estimation process using SCADA and PMU in AC/DC grids in [63].

2. Knowledge Gap of Past Studies and Contribution Declared in This Work

Algorithms such as GA [31,32], BCOA [33], BGSA [34], BPSO [35,36,37], CSA [38], RQP [45], and GPSA [46] locate locally optimal solutions either in the continuous or binary decision variable domain. Also, previous efforts in the BBA [20,21,22,23] and semi-definite [26,27,28] domains didn’t give the appropriate attention to this optimality criterion.

Integer programming and semi-definite programs are introduced in previous studies [20,21,22,23,26] without illustrating that the solution does not suffer from uncertainties related to suboptimality criteria. Moreover, the proposal of SDP in [28] suffers from uncertainties if the return solution satisfies the maximum network observability [22].

None of the cited articles dealing with binary or continuous decision variables in the OPP gives prominence to the issue of solution uncertainty. Optimization models such as binary integer linear programs [19,20,21,22,23], $0/1$ semi-definite programming formulation [26,27,28], and quadratic binary polynomial problems are solved by a BBA implemented by the YALMIP software package (https://yalmip.github.io/ accessed on 15 October 2023) [26,27,28].

In addition to solving such kinds of optimization problems through BBA, a solution must fulfill a suboptimality criterion [9,10,11]. As far as we know, there is not much attention to deal with a solution if it ranges in the 0.00% optimality criterion [20,21,22,23].

This study resolves the OPP problem and presents a branch-and-bound algorithm for a binary integer program [19,20,21,22,23], a Boolean semi-definite program, and a binary quadratic polynomial model [26,27,28].

This work studies these optimization problems and solves them exactly by the BBA in a zero-gap tolerance, and based on this computational logic, the maximization problem is also considered, studied, and solved [9,10,11].

This optimality criterion is primarily utilized to find any solution for either the minimization or maximization problem in fields such as binary integer programming [19,20,21,22,23], semi-definite programs [26,27,28], and polynomial models. All optimization problems are written in YALMIP using symbolic syntax, with a strict declaration of the binary nature of the decision variables [26,27,28]. We initially optimize the $0/1$ ILP model with a BBA [64,65,66,67,68] implemented by the bmibnb built-in solver in the YALMIP program in collaboration with external optimizer routines to find optimality [69,70,71,72,73,74,75,76,77,78,79].

It invokes an ILP routine to estimate the first feasible solution, the upper and lower bounds, and finally to obtain a global solution point [70,72,73,74,77,79]. This optimization solver utilizes a standard BBA, builds a binary tree, and constantly calculates an upper and lower bound estimation on the objective function, whereas a percentage relative gap is given at each explored node [70,72,73,74,77,79]. Finally, an optimal solution has been discovered with a 0.00% optimality criterion [9,10,11,42,44].

To solve the quadratic constraint polynomial problem, the bmibnb built-in YALMIP solver invokes two optimizer routines, such as a local NLP solver [70] and an ILP solver [69,70,71,72,73,74,77,79].

The bmibnb invokes the MATLAB^® function fmincon to find the first feasible solution and an upper bound on the objective function [71]. On the other hand, the MATLAB^® function intlinprog [70], for example, is utilized to solve the linear programming relaxations at each explored node and estimate the lower bound [70].

The optimization routine constantly estimates the difference between those bounds and delivers an optimal solution within a 0.00% criterion [9,10,11,42,44,76,77]. Therefore, no better solution can be found, and this point is a global one [76].

Finally, the CUTSDP built-in YALMIP solver relaxes the conic constraints and solves the Boolean semi-definite program either in the minimization or maximization problem [69,78]. It also invokes any powerful MILP solver to count the optimality criteria through the cutting-plane strategy in optimizing the mathematical model [70,72,74,79]. The entire optimization process results in a global optimum point [9,10,11,42,44].

3. Novelty and Computational Methods Related to Discrete Optimization

The goal of this work is to improve the reliability of the local and wide transmission grids by using PMUs to enable and enhance system monitoring, control, and protection applications [1]. As a result, the power system state is obtainable in actual time [1].

As the PMU installation in a power grid transmission system is yet a costly devoting investment, it is not possible to pose PMU at each power grid node aiming at power grid monitoring. As a result, the motivation is to find global algorithms to find out the exact number of PMUs in a single run without needing any comparison with the existing methods and where this algorithm is superior to the previous algorithm.

Our algorithmic scheme can find the accurate number of PMUs and their location sites within an adequate stopping criterion that satisfies globality [9,10,11,42,44].

The main algorithm is the BBA, which solves the binary integer program, the semi-definite program, and the quadratic constraint Boolean model.

Another target is to declare a maximization problem to obtain those solutions to ensure the maximum observation of the power grid monitoring, which is a challenging task.

The aim of the system operator is to constantly supply electricity to the customers. To implement a combinatorial problem as the OPP, a decision computational way must be followed. The objective function is stated generally as [11]:

$$\min J\left(\mathrm{x}\right)=={\sum }_{\mathrm{i}}^{\mathrm{n}}{w}_i|{\mathrm{x}}_{\mathrm{i}}=true/false$$

(1)

Also, a logical constraint function is taken into account to cover the complete observation scenario of the power grid state as first declared in [11,20,21].

$$F\left(\mathrm{x}\right)=F\left({\mathrm{x}}_1,{\mathrm{x}}_2,\dots ,{\mathrm{x}}_{\mathrm{n}}\right)=\left\{\begin{array}{c}true\\ false\end{array}\right.$$

(2)

This optimization formulation model is stated in an $go-no-go$ integer linear program defined on decision variables with a binary nature. In this process, the decision variables are stated to be $0-1$ values [9,10,11]. As a result, an assignment problem is declared [10]. Branch-and-bound algorithms (BBAs) are capable of solving assignment problems, such as the OPP, or power dominating set in graph theory terminology [5,19].

• Minimizing the number of PMUs achieves optimization of the models towards a solution with a 0.00% optimality criterion. Consequently, the placement of PMUs at appropriate sites reduces the total installation cost.
• Proposing maximization models that yield solutions with maximum observatory indicators. In other words, the reliability of the power grid is enhanced by achieving the upper limit related system indicator, by which a power grid network node how much time is observed.
• So, if solutions with maximum SORI are placed at appropriate sites, the electricity transmission system becomes better at monitoring and avoiding interrupted conditions. This index defines the total knowledge of the observations for the WAMS.

Our algorithmic approach is based on four parameters to obtain an optimal solution inside a zero absolute gap and a percentage relative gap equal to 0.00% [76]:

(1)

To obtain an adequate number of PMUs by minimizing a linear objective function under a set of topologic or numerical constraints, the topologic constraints are formulated considering Kirchhoff’s and Ohm’s rules [20,21,22,23]. On the other hand, the numerical constraints are based on a linear estimator procedure [26,27,28].

(2)

To achieve those optimal PMU arrangements where each power grid node is observed for a maximum time, directly or indirectly [22,34,35,39,41,42,43,44,45,46].

(3)

As a result, minimization and maximization problems are symbolically programmed in MATLAB using a specialized library like YALMIP [69].

(4)

The minimization problems are solved by a BBA building an enumeration tree to find a global solution point inside an objective function gap [9,10,11,44]. On the other hand, the maximization problems are declared based on the optimal solution returned by the minimization model. Then, the BBA returns optimal solutions with high quality, satisfying the maximum network reliability for each mathematical model.

4. Power Dominating Set (PDS)-Optimal PMU Placement Problem

Many integer programming (IP) problems arise in graph theory. Graph theory and integer linear problems have been extensively treated elsewhere, for example, by Christoforides (1975) [8]. One of the most significant relevances of graph theory in mathematical computing science is its utilization in electrical network theory [3,4,5,6,7,8].

Let $G=(V,E)$ be a graph reflecting an electric power network, where a vertex depicts an electrical node (a substation bus where transmission lines, loads, and generators are connected) and an edge depicts a transmission line connecting two electrical nodes.

The optimal PMU allocation maps to the smallest minimal dominant set on the graph. The OPP problem is also known as the Power Dominating Set (PDS), which needs a minimum number of PMUs to pose on the nodes. As the graph is fully observed, the network state is to be calculated [3,4,5].

Haynes et al. considered the graph-theoretical representation of this problem as a variation of the power domination set problem [5]. They declared a set $S$ to be a power-dominating set of a graph if every vertex and every edge in the power system is observed by the set $S$ that follows a set of rules for power network observation [5,19].

As a result, the problem of the installation of the smallest set of PMUs to observe the whole power system is a graph theory problem physically closely related to the commonly accepted vertex covering and domination problems [3,4,5,19].

A graph $G=\left\{V,E\right\}$ consists of objects $V=\left\{v_1,v_2,\dots \right\}$ called vertices and another set $E=\left\{e_1,e_2,\dots \right\}$, whose elements are called edges, such that each edge $e_k$ is recognized with an unordered pair $\left\{v_i,v_j\right\}$ of vertices. The vertices $\left\{v_i,v_j\right\}$ associated with the edge $e_k$ are called the end vertices of $e_k$ [6,7,8].

A PMU calculates the voltage and phase angle for the vertex at which it is installed, its adjacent edges, and their end vertices. These vertices and edges are considered to be monitored. Any vertex that is adjacent to a monitored edge is observed, and any edge joining two monitored vertices is observed [3,4,5].

The problem of observing an electricity power network is solved by placing a selected number of measurement devices around the power system, which is closely related to the well-known domination problem in graphs [1,5,19].

A PMU calculates the state variable, which is the voltage and phase angle for the vertex at which it is installed and its adjacent edges and their end vertices [1].

Definition 1.

Declaration of the observability laws related to the PDS model [5,19]:

• Any vertex that is adjacent to a monitored edge is observed.
• Any edge connecting two observed vertices is monitored.
• If a vertex is adjacent to a total of $k>1$ edges, and if $k-1 o$ f these edges are monitored, then all $k$ of these edges are observed.

The binary connectivity matrix, $A_{PMU}$ as declared in [20,21,22,23], is given by the ‘‘vertex-node adjacency matrix’’ for the matrix $X=\left[{\mathrm{x}}_{\mathrm{i}\mathrm{j}}\right]$, on which the elements along the main diagonal of it are adjusted to 1, that is $\left[{\mathrm{x}}_{\mathrm{i}\mathrm{j}}\right]=1,\forall \mathrm{i}=\mathrm{j}$ [6,7,8].

Provided that all the diagonal elements of the matrix are $1$ on condition that every vertex is ‘‘reachable’’ from itself by a path of cardinality $0$, the set of ${\mathrm{x}}_{\mathrm{i}}$ which are reachable by ${\mathrm{x}}_{\mathrm{j}}$ along a path of cardinality $1$, i.e., the set of the arcs $\left({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{j}}\right)$ exist in the graph, as noted in [6,7,8]. As a result, the binary connectivity matrix as declared for solving the OPP problem is the reachability matrix $R=\left[{\mathrm{r}}_{\mathrm{i}\mathrm{j}}\right]$ as defined in [5,6,7,8]:

$$r_{\mathrm{i}\mathrm{j}}=\left\{\begin{array}{c}1 if vertex {\mathrm{x}}_{\mathrm{j}} is reachable from vertex {\mathrm{x}}_{\mathrm{i}}\hfill \\ 0 otherwise\hfill \end{array}\right.$$

(3)

Evidently, all the diagonal elements of $R$ are $1$ since every vertex is reachable from itself by a path of cardinality $0$ [5,6,7,8]:

$$A_{k,m}=\left\{\begin{array}{c}1, \mathrm{if} k=m, \mathrm{or} k \mathrm{and} m \mathrm{are} \mathrm{connected}\\ 0, \mathrm{otherwise} \end{array}\right.$$

(4)

The determination of the minimum cardinality power dominating set is equivalent to the PMU placement methodologies that can completely monitor the network state, whereas the system operator utilizes a minimum number of synchronized sensors to be installed at selected power grid nodes.

We utilize basic circuit rules, that is, Kirchhoff’s Voltage Laws and Ohm’s Law, and measurement sets directly achieved by PMUs, which aim at determining the voltage phasors at all power grid nodes that are not directly measured [19,23,32,45,46].

The first observable rule of optimal allocation of PMUs is: A bus that has a PMU installed at that bus will have its voltage phasor and all branch currents adjacent to it observed by the PMU monitoring device [19,20,21].

The second one is as follows: By applying Ohm’s law, the voltage phasor at one end of a branch current can be computed if the voltage phasor at the other end of the branch current is known [19,20,21]. Through the simulation results, it is proven that there is a direct connection between the optimal allocation of PMUs and the determination of the smallest dominating set. The resulting optimization model being constructed for that purpose is to find the minimum number of PMUs that are adequate to observe the electricity power transmission grid, which is also mentioned as the OPP problem.

The OPP problem is declared based on Kirchhoff’s Voltage laws and Ohm’s Law and was at the beginning presented by Abur [20,21]. The work by Haynes et al. [5] was one of the first of this kind to utilize a graph theoretical approach for solving the PDS as an OPP problem. Based on graph theory, this study utilizes the Vertex-to-Vertex Connectivity Matrix to build the binary connectivity matrix to reconsider the binary integer program as presented in [20,21]. The steps of the implementation of the Vertex-to-Vertex connection matrix are the following in the optimization run of the integer linear program [19,20,21,22,23].

The pseudo-code presents the Algorithm 1 used to build the Vertex-to-Vertex Connectivity Matrix [6,7,8] in Algorithm 1.

Algorithm 1: Vertex-to-Vertex Connectivity Matrix

A graph vertex is considered to be directly monitored if a PMU is posed at that vertex and also indirectly monitored by a PMU installed at its incident vertex [5].

If all vertices in the graph are observed directly or indirectly, the graph is considered to be fully observable [5]. The number of lines connecting with each vertex aims at maximizing the maximum observability indicator so that the measurement redundancy can be preserved [22,33,34,35,39,41,46].

The neighborhood buses connected to a network bus with a PMU help a lot to count the BOI, the summation of this index reflecting the SORI, and a global solution point [22].

The resulting solutions have such BOI indices, counting the maximum SORI satisfying a secure state estimator process [22,33,34,35,39,41,46].

During the first phase, the optimization of the binary program is conducted, assigning equal weight to each decision variable. Analyzing the format of the binary program is performed based on the connectivity of the transmission lines, followed by an exact solution using a BBA [9,10,11].

Subsequently, a revisitation of the semi-definite program is performed, leading to the declaration of a quadratic constraint binary program [9,10,11].

All minimization problems are solved by a BBA in an absolute gap equal to a zero-value price. In the second stage, a maximization problem is declared, incorporating an additional linear constraint that reflects the optimal solution achieved in the minimization problem.

5. Mathematical Programming Models

The study of PDS in a graph representing an electricity transmission system network aims at placing a minimum number of PMUs to observe the entire grid state [4].

It is illustrated that the PDS is NP-hard to optimize, and this remark is based on the bibliography [3,4,5], but it can be computed exactly without using evolutionary algorithms to locate a suboptimal solution [12]. The theoretic analysis is given by previous studies in the graph theory domain [3,4,5].

In fact, the set of power nodes where the PMUs have to be posed reflects a dominant set of the graph [3,4,5]. As a result, the OPP problem maps to the smallest dominating set problem on the graph, as pointed out in [3,4,5].

The combination of the PDS with the OPP problem has been adopted. As a result, revisiting certain programming models is necessary to solve the OPP problem exactly.

Our purpose is to give a computational way to solve it through reconsidering the existing models and also to propose a quadratic constraint binary problem. The integer programming model is the state-of-the-art computational method to solve the PDS or OPP, showing competitive elapsed time performance metrics [3,4,5].

This work presents a mathematical formulation and implementation in YALMIP in collaboration with MATLAB to find a cure for the determination of a global solution point related to minimization or maximization problems [69,77].

The BBA built-in BMIBNB function, which is global nonlinear nonconvex integer programming, is utilized for solving binary integer and polynomial problems and a CUTSDP optimizer routine to the $0/1$ SDP problem solving [69,70,71,72,73,74,77]. The proposed algorithmic scheme is applied to validate the functionality based on two observability scenarios [20,21,22,23,24,25,26,27,28,32,45,46]:

• Complete Observability
• Maximum Network Observability

The first scenario is to ensure that the power grid state is fully observed, whereas the second scenario gives those solutions to the state estimator tool for maximum reliability of the measurements.

The algorithm is the BBA to solve it, and the same algorithm is followed to solve the Boolean semi-definite program and the quadratic constraint programming model.

Although the PDS or OPP is known to be NP-complete [4], the instances are presented in this study, and they are solved exactly within a zero-valued absolute gap.

The PDS has been widely studied in the literature [12,13,14,15,16,17,18]; for example, it is an NP-complete problem [4,5,19]. Despite this general truth, the instances studied in this work are exactly solved by BBA [9,10,11,70,71,72,74,77].

BBA can solve the proposed models by building an enumeration tree, exploring nodes, solving linear programming relaxations, and finally getting a solution with a 0.00% optimality criterion [77].

This criterion means that no higher-quality solution can be found; hence, the optimization problem can be solved globally [77]. The YALMIP state-of-the-art mathematical models are used for integer, semi-definite, and polynomial problems [77].

BBA solves the binary integer and polynomial problems following the same tactic procedure. An upper solver estimates the upper bound on the objective value, whereas a lower solver produces the lower bound to obtain the best objective bound [77].

Also, an LP-optimization function is utilized to explore the nodes, solve linear problems, and implement a suitable branch strategy to build the BBA tree [9,10,11].

Finally, a global solution point is achieved for both optimization models that range in the binary domain. We also utilize the other built-in YALMIP solver called CUTSDP to relax the semi-definite program’s conic constraint function, where a linear objective function is optimized under conic constraints in a binary symbolic format [26,27,28,78].

This function calls a powerful advanced ILP solver to return an optimal solution for the minimization and maximization problems [70,72,74,79]. The innovation of this work entails the fact that optimization problems are symbolically programmed in MATLAB [10]. The optimization model is written using a specialized YALMIP library, which derives a log file that sufficiently shows that a global solution point is derived within an absolute and relative gap both equal to zero [69,70,71,72,73,74,77].

5.1. Constrained Integer Programming with Binary Decision Values

Most practical integer program models restrict the integer variables to two values; such $0/1$ variables are utilized to represent ‘‘yes’’ or ‘‘no’’ decisions [10].

The electricity transmission grid is fully observable if the voltage phasor is computed for each power bus directly or indirectly [19,20,21]. The most frequent conception formulation is a constraint integer program with binary decision variables [20,21,22,23].

The PDS problem can be interpreted through a constraint-integer linear programming model with binary-valued variables [5].

Logical associations between such decisions can often be enforced using linear constraints. As the assignment placement variables in the OPP problem demand a value of only 0 or 1, BBA locates the decision variable vector in that domain [9,10,11].

To obtain a complete observation of the power grid state using the mathematical models, we found the exact number of PMUs replying to their localization sites around any IEEE power transmission network [80].

As a result, the OPP is initially written in an integer program with a binary decision domain. Let n be the number of decisions to be charged with a task. For an n-node electrical power grid, the optimization model is stated as follows in integer linear programming with binary decision variables [20,21,22,23].

Definition 2.

Declaration of the nature of the decision variables in decision-making and problem solving [20,21,22,23]:

The decision variables are set to be as follows [20,21,22,23]:

$${\mathrm{x}}_{\mathrm{i}}=\left\{\begin{array}{c}1 \mathrm{if} \mathrm{a} \mathrm{PMU} \mathrm{is} \mathrm{installed} \mathrm{at} \mathrm{bus} \mathrm{i}\\ 0 \mathrm{otherwise}\end{array}\right.$$

(5)

The $0/1$ ILP model is written as follows [20,21,22,23]:

$$\mathrm{m}\mathrm{i}\mathrm{n}{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}$$

(6)

$$\mathrm{s}.\mathrm{t}.\mathrm{A}\cdot \stackrel{⃑}{\mathrm{x}}\ge \widehat{1}$$

Let us define the binary connectivity matrix of the power network as follows [20]:

$${\mathrm{a}}_{\mathrm{i}\mathrm{j}}=\left\{\begin{array}{c}1 \mathrm{if} \mathrm{i}=\mathrm{j} \mathrm{or} \mathrm{j}\in {\mathcal{A}}_{\mathrm{i}}\\ 0 \mathrm{otherwise}\end{array}\right.$$

(7)

The inequality constraints are multiple-choice restrictions or logical constraints [10]. Given that we have the choice of investment to be at least one of the available alternatives, these constraints have a Boolean logic [10].

Where $\mathrm{x}={\left({\mathrm{x}}_1,{\mathrm{x}}_{2,},...,{\mathrm{x}}_{\mathrm{n}}\right)}^{\mathrm{T}}$ is a binary design variable vector, whose entries are declared in the current yes or no decision [20,21,22,23].

The objective function (6) reflects the cost of the entire investment. Constraints involved Equation (7) remain in force for each placement variable, and the objective function is optimized under this constraint function in a binary domain. The MILP model with binary decision variables is solved by BBA for each IEEE power system [80].

As a result, the focus is on bringing into clear view the BBA, which is used to solve linear programming relaxations in order to obtain bounds on the cost function value of the initial model within a binary domain [9,10,11].

A global solution point is obtainable within a zero MIPGapAb [69,70,71,72,73,74]. Τhis solution is considered an extra constraint function in the declaration of the maximization problem in a mixed-integer-linear program (Equations (14)–(18)). We highlight the following five elements to solve the $0/1$ ILP mathematical model as shown in Algorithm 2 [9]:

Algorithm 2: Steps of BBA implementation

Lower bounding methodology: A strategy is utilized to attain the lower bound on the objective function to obtain a solution to a specified sub-problem.

2. Upper bounding methodology: An upper bound is estimated at the optimum solution point.

3. Branching methodology: A process is followed to partition a sub-problem to generate more than two children.

4. Search Strategy: A process is followed to determine the search order to build the binary tree.

5. If the absolute gap between the upper and lower bounds is within a predefined tolerance, the algorithm stops giving an output.

This optimization process can be interpreted as a repetitive scheme to improve the difference between the current upper bound, which is the incumbent objective function value, and the current lower bound, which is the least value of the lower bounds generated by solving the candidate sub-problems as shown in Algorithm 2 [9,10,11].

The difference between the upper and lower bounds is the optimality gap utilized to achieve termination of the BBA [9,10,11]. To execute this optimization, MILP solvers such as MATLAB function intlinprog [70], SCIP optimizer [72], Gurobi function and MOSEK [79] can be invoked in the MATLAB environment to obtain a global solution point inside a predefined absolute gap equal to zero [74].

5.2. Boolean Semi-Definite Programming Model

Additionally to the constraint integer program, OPP can be formulated as mixed-integer semi-definite programming (MISDP) under linear matrix inequality (LMI) constraints, as presented in [26,27,28].

$0/1$ Semi definite programming model considering the OPP problem can be formulated as follows (Equations (8)–(10)), as found in [26,27,28].

$$\mathrm{m}\mathrm{i}\mathrm{n}{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}$$

(8)

$$\mathrm{G}\left(\mathrm{x}\right)={\mathrm{G}}_0+{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}\cdot {\mathrm{G}}_{\mathrm{i}}\succ 0$$

(9)

$$\stackrel{⃑}{\mathrm{x}}\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{n}}$$

(10)

The LMI constraint is positive-definite and ensures numerically the power system’s observability [26,27,28]. $G_0$ is a gain matrix related to the existing power flow and injection measurements in the power network.

On the other hand, $G_i$ is a gain matrix representing the phasor voltage as well as current phasors calculated by a PMU located at a bus i [26,27,28].

By transforming the inequality constraint of Equation (6) into an equivalent LMI restriction, Boolean semidefinite programming can be stated and symbolically programmed in YALMIP [69]. The main optimizer, the CUTSDP solver, relaxes the LMI constraints [69].

This solver implements a cutting-plane approximation to solve semi-definite programs. With this computational method, the optimization solver relaxes the conic constraint function, solves a mixed-integer-linear program, puts in linear cuts to the mathematical model, and repeats the optimization process until it finds a global solution [69].

To accomplish this optimization and locate an exact optimum point, the program’s user invokes an external MILP solver, such as the MATLAB function intlinprog [70], the SCIP optimizer [72], and the Gurobi function [74].

State-of-the-art-optimizer routines such as MATLAB^® function intlinprog [70], Gurobi optimizer engine [74], SCIP optimizer routine [72], and MOSEK [79] are utilized to detect those optimal solutions that optimize the linear objective satisfying the LMI restrictions under the Boolean decision variable restriction [26,27,28].

As a result, the CUTSDP solver [78] is based on a fast MILP solver embedded in a specialized optimization toolbox such as the MATLAB optimization library [70], the Gurobi toolbox [74], MOSEK [79], or an open-source SCIP optimizer routine [72].

5.3. Quadratic Constrained Binary Optimization Model

If the optimization problem is convex, this is adequate to ensure that the solution is at a globally optimal point. Nonconvex problems may have many various local minima points, and selecting the best one is a very hard issue [9,10,11]. Multi-start procedures are able to run nonlinear problems with high probability, but in real optimization, there is no warranty that the localized point will be a global optimum point [9,10,11].

One of the models that permits us to declare OPP is quadratic constrained binary optimization (QCBO), which extends quadratic unconstrained binary optimization (QUBO) [68]. QUBO has been used to solve optimization problems such as vertex cover, max-cut, and other graph theory problems [68]. Although QUBOs are NP-complete problems, solutions can be found by utilizing evolutionary algorithms [68].

The proposed QCBO model is an extended nonlinear problem that is symbolically programmed in YALMIP with its BBA built-in solver [77]. A QCBO model is formulated and solved to obtain global optimality [9,10,11]. The structure of this kind of discrete optimization model is non-convex, with a strict declaration of binary decision variables.

The solution can be exactly found given that the absolute and relative gaps are equal to zero [77]. The QCBO model is declared as follows (Equations (11)–(13)):

$$\mathrm{m}\mathrm{i}\mathrm{n}{\mathrm{x}}^{\mathrm{T}}\cdot \mathrm{Q}\cdot \mathrm{x},\mathrm{Q}\in {\mathrm{I}}_{\mathrm{n}\times \mathrm{n}}$$

(11)

$${\mathrm{f}}_{\mathrm{i}}\left(\stackrel{⃑}{\mathrm{x}}\right)=\left(1-{\mathrm{x}}_{\mathrm{i}}\right)\cdot {\prod }_{\mathrm{j}\in \mathrm{n}}\left(1-{\mathrm{x}}_{\mathrm{j}}\right)=0,\forall \mathrm{i}\in \mathrm{n}$$

(12)

$$\stackrel{⃑}{\mathrm{x}}\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{n}}$$

(13)

Non-convex optimization models [41,42] have multiple local solutions, and theoretically as well as through the optimization, it is difficult to prove which global one is [8]. In this study, we reconsider the optimization problem with a non-convex structure declared in a binary symbolic decision domain [69,77].

Therefore, non-convex problems are transformed into Boolean polynomial problems. Global optimization algorithms such as spatial branch-and-bound algorithms (SBBAs) are utilized to find a global solution point for such an optimization problem as shown in the Appendix A and Appendix B [9,10,11].

The leading concept is to try to find a global solution point regarding model-solving, and the entire optimization run is summarized in the following steps [77]:

• An s-BBA is utilized and applied to an optimization problem to obtain a global solution point. The performance of the BBA depends on the capability of the relaxations of the polynomial constraint function so that convergence can be achieved [9,10,11].
• The iterative process ends up with two explored nodes, as we illustrate in the log files in the Appendix C and Appendix D. This solution is established on the optimization run of two external solvers at the same time [9,10,11].
• Finally, a solution is found within a predefined absolute and relative gap with zero value at the final explored node of the BBA tree [9,10,11].

The BMIBNB function optimizes the non-convex problem in the binary decision domain based on linear programming relaxations and a convex envelope approximation strategy [69,77].

This function invokes a local non-linear solver to find the first feasible solution, if one exists. Also, it invokes an ILP solver to solve the linear programming relaxation [69,77].

Finally, the nonlinear solver and the integer solver constantly estimate the upper and lower bounds, calculating the difference between them, and if it goes to zero, a global solution has been achieved [69,77].

5.4. Maximizing Programming Models

In the first phase, the OPP problem results in a globally optimal point. This phase determines the solution that satisfies the complete scenario [21,32,45].

In the second phase, we mainly optimize the results attained in the previous phase and produce those solutions that ensure the maximum reliability of the power network [22,33,34,35,39,41,46].

PMUs must be installed at vertices with a maximum degree of connectivity to maximize coverage [5,50]. The investigation of the OPP problem involves deriving an optimal solution, wherein each power network node is assessed using the Bus Observability Index (BOI) as a measurement index [22].

This index for a network node is a measuring parameter that determines whether the bus is observed directly or indirectly [22]. The summation of BOI is the SORI, and it is more appropriate for the maximum observability network [22,33,34,35,39,41,46,50]. Those indices are used to estimate the relative excellence of optimal PMU arrangements [50]. The steps in relation to the algorithm for counting the maximum network observability are summarized as follows:

• An objective function is declared in getting optimized by giving the number of times a power network is observed.
• The observability of every vertex is measured, and the BOI is calculated for every vertex.
• Afterward, the sum of all times by which the power network is monitored is summed, and the SORI is derived.
• An optimal PMU placement set is given as having the maximum SORI.

The factors of the BOI and SORI perform as a measuring quantity, reflecting the redundancy of measurements [50]. The number of measurements obtained from a power node rises with the larger number of lines attached to that node [22].

The number of PMUs needed for full observability is the same for all the power grids. However, the BOI and SORI rely on the selection of the optimal PMU placement sites.

This quantity is the BOI. The idea of BOI utilization guarantees the spreading out of the PMUs within the power system. As a result, the PMUs number is limited with SORI to give the sign of maximum redundancy given for the resulting set [22].

Maximum observation of the power grid is the supplementary objective of a proposed mathematical program that increases the power grid reliability [22,34,35,39,40,41,46].

One considerable effect of the OPP problem is to obtain the maximum observability of the whole system in the event of any disruption [22,34,35,39,40,41,46].

As a result, the maximization problem is stated to maximize the observation of the power grid. In this study, we maximize a cost function, looking for cost-effective solutions in various domains such as ILP, SDP, and polynomial problems.

To solve the problem of maximizing the observability indicator, whereas the system observability is preserved, with a minimum number of PMUs, we implement the secondary optimization problem [22,34,35,39,40,41,46]. We minimize the OPP problem, and a global solution point is achieved. Afterward, we seek out those optimal solutions with the maximum indicator of the power grid state.

A linear objective function is maximized under ILP [20,21], LMI [26,27,28], polynomial constraints, and a supplementary linear equality constraint reflecting the PMU number in the solution.

Our study is extended to work out maximization problems, considered secondary problems in getting those solutions satisfying the maximum observation of the power grid state. The optimal solution given by the optimization of the primal problem is considered an extra constraint taken into account in the maximization problem.

i.

Constrained Integer Programming with Binary Decision Values

The maximization problem is given in an integer linear program (Equations (14)–(18)), whereas an equivalent problem is proposed in a binary polynomial model (Equations (19)–(22)).

$$\mathrm{m}\mathrm{a}\mathrm{x}\frac{1}{\mathrm{n}}{\mathrm{e}}^{\mathrm{T}}\cdot \mathrm{A}\cdot \mathrm{x}$$

(14)

$$\mathrm{Subject} \mathrm{to} {\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}={\mathrm{x}}_{\mathrm{m}\mathrm{i}\mathrm{n}}$$

(15)

$${\sum }_{\mathrm{i}\mathrm{j}}{\mathrm{a}}_{\mathrm{i}\mathrm{j}}{\mathrm{x}}_{\mathrm{i}}\ge 1$$

(16)

$${\mathrm{a}}_{\mathrm{i}\mathrm{j}}=\left\{\begin{array}{c}1 \mathrm{i}\mathrm{f} \mathrm{i}=\mathrm{j} \mathrm{or} \mathrm{j}\in {\mathcal{A}}_{\mathrm{i}}\\ 0 \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right.$$

(17)

$$\stackrel{⃑}{\mathrm{x}}\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{n}}$$

(18)

ii.

Constrained Polynomial Optimization Problem with Binary Decision Variables

$$\mathrm{m}\mathrm{a}\mathrm{x}\frac{1}{\mathrm{n}}{\mathrm{e}}^{\mathrm{T}}\cdot \mathrm{A}\cdot \mathrm{x}$$

(19)

$${\mathrm{f}}_{\mathrm{i}}\left(\stackrel{⃑}{\mathrm{x}}\right)=\left(1-{\mathrm{x}}_{\mathrm{i}}\right)\cdot {\prod }_{\mathrm{j}\in \mathrm{n}}\left(1-{\mathrm{x}}_{\mathrm{j}}\right)=0,\forall \mathrm{i}\in \mathrm{n}$$

(20)

$${\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}={\mathrm{x}}_{\mathrm{m}\mathrm{i}\mathrm{n}}$$

(21)

$$\stackrel{⃑}{\mathrm{x}}\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{n}}$$

(22)

iii.

Boolean Semi-Definite Programming Model

The maximization problem is also declared in a Boolean Semi-definite Programming model in getting that solution with a maximum observability indicator.

$$\mathrm{m}\mathrm{a}\mathrm{x}\frac{1}{\mathrm{n}}{\mathrm{e}}^{\mathrm{T}}\cdot \mathrm{A}\cdot \mathrm{x}$$

(23)

$$\mathrm{G}\left(\mathrm{x}\right)={\mathrm{G}}_0+{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}\cdot {\mathrm{G}}_{\mathrm{i}}\succ 0$$

(24)

$${\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}}={\mathrm{x}}_{\mathrm{m}\mathrm{i}\mathrm{n}}$$

(25)

$$\stackrel{⃑}{\mathrm{x}}\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{n}}$$

(26)

where x_min is the minimum number of PMUs achieved by the primary-based OPP for full observability. The optimization framework is summarized as follows:

• The BILP model is written in symbolic format, where the YALMIP BBA solves the problem by invoking a powerful advanced ILP solver to count the upper and lower bounds and solve the linear programming relaxations.
• The Boolean polynomial model is transformed into a polyhedron and solved by the YALMIP BBA function, which constructs a BBA tree where the upper and lower bounds are computed to be equal at the final root node.
• The Boolean SDP model is also written in the same programming language, where the CUTSDP relaxes the second-order conic constraints through a cutting-plane strategy implemented by an ILP function.
• The optimization ends with accuracy because the difference between these bounds delivers a zero-tolerance gap. This tolerance measure means that a global optimal solution is obtained.
• The objective value is considered to be the upper bound for the minimization problem and the lower bound for the maximization problem.

The binary integer program is symbolically programmed in YALMIP software, where the BBA built-in solver interfaces with external MILP solvers to count the upper and lower bounds and the relaxation problem-solving at the explored nodes [77].

The QCBO model is solved with a polyhedron approximation, building a BBA tree utilizing linearized techniques. The output is obtained within an absolute and relative gap, with values equal to zero [77].

This linearization is performed using a software package that utilizes a standard MILP solver in collaboration with a nonlinear function [9,10,11]. The YALMIP BBA calls these optimizer routines to count the upper and lower bounds, to implement a branching strategy, and finally to return a global optimal solution [77].

The CUTSDP built-in solver relaxes the SDP’s conic constraint function, and a cutting-plane strategy through a MILP solver transforms the model into a MILP model [26,27,28]. Then, the BBA solves the MILP problem exactly with a cutting-plane strategy [9,10,11].

The entire optimization process is a required thought task related to the utilization of global optimization functions in $0/1$ decision-making problem solving [9,10,11]. All optimization models are solved either in minimization or maximization format.

The optimality criterion yields an attractive computational method to find the value of the quality of the solution given by the solution of each mathematical programming model. The algorithm returns a solution within a 0.00% optimality metric for either the minimization or the maximization problems [9,10,11].

iv.

Solving the optimization models with a BBA inside an absolute gap

The easiest and most intuitive computational manner to solve a $0/1$ combinatorial problem as the OPP, either in minimization or maximization format, is to take into account the $0/1$ decision variables as a continuous variable [9,10,11].

Specifically, the CUTSDP relaxes the conic constraint function, by which a linear objective function is optimized in a symbolic binary domain [69,77]. In the first instance, a cutting-plane strategy transforms the Boolean semi-definite program into a mixed-integer solver, and in the second one, an upper and lower solver are taken into consideration for counting and comparing the upper and lower bounds on the objective function [9,10,11].

On the other hand, the YALMIP BBA solves the binary integer linear and quadratic polynomial models in the same computational way [69].

The YALMIP BBA is a spatial BBA implementation. The steps of the implementation of the spatial branch-and-bound algorithm (s-BBA) in the YALMIP solver are summarized as follows [8,9,10,11,69,76,77,78]:

• Initialization;
• Choose region;
• Lower bound;
• Upper bound;
• Pruning;
• Check region; and
• Branching.

The proposed mathematical models are solved by a BBA following strictly mathematical rules, avoiding suboptimal solutions. Solving the linear programming relaxations produces a bound on the optimum point and gives the optimal solution for all optimization models studied in this work. This truth is confirmed by the log files that show convergence at a constraint minimum point, avoiding a suboptimal solution [9,10,11,42].

The suboptimality criterion is calculated at the final stage of the implementation of BBA and is fully satisfied, which means a globally optimal solution has been found.

The maximization models are stated in a decision-making way to obtain optimality satisfying a stopping criterion under guarantee. The best optimality metrics are reached using binary integer, semi-definite, and binary polynomial models to find out the best number of PMUs with the maximum network observability indicator [22].

We declare the quadratic polynomial optimization problem in a symbolic language in MATLAB, and the decision variables are binary. A global search methodology is required to obtain a global solution. A BBA is implemented by YALMIP software to achieve a solution point with a fully met optimality criterion [77].

BBA solves the Boolean polynomial model by relaxing the polynomial constraint function, the binary resection of the design variables, and constructing an enumeration tree to obtain a global optimal solution. Two optimization processes are used to find optimality.

The first optimization function estimates the upper bound, and the second one computes the lower bound in the s-BBA tree implementation. An LP solver solves the relaxed problems, and a suitable branch strategy is followed [9,10,11].

The built-in YALMIP solver interfaces the MATLAB^® function fmincon to calculate the upper bounds and a powerful advanced ILP function to estimate the lower bounds and solve the relaxed linear programming problems [69].

Those routines measure the difference between those bounds and finally detect a global optimal solution within a zero-gap optimality as well as a percentage relative gap. Let us define the s-BBA implementation in the following stages as shown in

Table 1. Steps of BBA implementation.

A process to work out the lower bounds.

2. A process to work out the upper bounds.

3. A branching process and exploring nodes.

4. A termination to be met satisfying predefined tolerances, such as an absolute zero-gap and a percentage relative gap.

[77].

To begin the iterative process, the binary restriction $\stackrel{⃑}{x}\in {\left\{\mathrm{0,1}\right\}}^n$ in the initial problem is replaced by the following interval-continuous constraint [9,10,11].

$$0\le \overrightarrow{\mathrm{x}}\le 1$$

(27)

BBA follows an LP-relaxation problem that is being solved where the binary integer requirement on the decision variables is substituted by the weaker constraint presented in Equation (27). If the solution is an integer, then the algorithm terminates [9,10,11].

Otherwise, two new sub-problems are created by a branching strategy on a fractional variable. The BBA concept is to end the optimization run the moment that the incumbent solution’s quality is evaluated by the measured absolute as well as relative gap to be satisfactory within the prescribed tolerances [9,10,11,74].

The incumbent solution is always the best solution found up until now in the BBA search tree [9,10,11]. The termination criterion is adjusted to be equal to the TolGapAbs $\mathrm{G}\mathrm{a}\mathrm{p}=0$ [72]. The entire optimization process results in a ϵ-optimality criterion. The quality of the numerical results was measured by the relative TolGapAbs [72,73]:

Definition 3.

Definition of the percentage relative to TolGapAbs:

$$\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} \mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e} \mathrm{g}\mathrm{a}\mathrm{p}=100\cdot |\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}-\mathrm{d}\mathrm{u}\mathrm{a}\mathrm{l}|/\mathrm{M}\mathrm{I}\mathrm{N}\left(\right|\mathrm{d}\mathrm{u}\mathrm{a}\mathrm{l}|,|\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}\left|\right)$$

(28)

BBA solves the semi-definite programming [26,27,28], binary integer [20,21,22,23], and polynomial models exactly with an optimal solution and a zero-gap tolerance [9,10,11,74].

That means that no higher-quality solution can be found, and the solution is not suffering from suboptimality uncertainties [9,10,11,74]. Therefore, a global solution point is achieved for all instances.

6. Suboptimality Criteria and Convergence Tasks

Global optimization is a well-accepted and widespread application in various domains of science and engineering. A global optimizer solver is used to solve the binary integer as well as the quadratic Boolean constraint minimization problems [9,10,11].

Also, a semi-definite solver named CUTSD is utilized to relax the conic constraint of the $0/1$ semi-definite programs [26,27,28] with the help of a cutting plane strategy to solve it as a mixed-integer program as the log presents in the Appendix C and Appendix D.

The cutting-plane strategy is utilized to tighten the linear programming relaxations in order to obtain the solution. Then, the maximization problems are solved based on the optimal solution achieved by solving the minimization problems in order to obtain the best reliability optimal solution for WAMS applications [1,2].

BBA is the only algorithm able to solve all the instances studied in this work. In this study, we present a BBA convergent for the OPP problem and its models. We consider convergence on three-parameter criteria: (I) upper objective bound, (II) lower objective bound, and (III) tolerance objective gap [9,10,11].

An algorithm produces an iterative process that is fully convergent when the iteration run goes to the objective function evaluation nearer and nearer to a desired solution. BBA runs the optimization runs and constantly measures the difference between the upper and lower bounds to be less than a default value, which is a specified tolerance.

The optimization solver returns an optimal solution for the objective function gap, and the simulation results validate our symbolic programming models without needing to compare them with the existing ones published in the bibliography [16,17,18].

When solving each optimization model, the BBA constantly works out both an upper and lower bound on the objective function value. The mixed-integer programming (MILP) solver ends up with an optimal result when the gap between the objective upper and lower bounds is less than MIPGapAb [9,10,11,74].

More accurately, the incumbent solution is the upper bound for a minimization problem, whereas a lower bound is taken into account in order to count the absolute gap; its acronym is MIPGapAb [9,10,11,74].

For a minimization model, the objective upper bound is considered the best-known solution and feasible at the same time, whereas the bound of the best possible objective is the lower bound [9,10,11,42,44]. On the other hand, the lower bound is considered the best-known solution for the maximization problems [9,10,11,74].

6.1. Termination Criteria of BBA for Convergence of the Optimization Run [64,65,66,67]

BBA is an in-front algorithm that is utilized to solve the proposed methods due to a good enough stopping criterion to fully accomplish the optimality criterion. As a result, the integer solver successfully returns a globally optimal point, avoiding being trapped in a local minimum or a suboptimal point [74]. Our aim is accomplished, that is, to solve exactly the minimization and maximization problems [9,10,11,74].

The quality of the solution depends on the termination criteria used in the implementation of BBA. The termination criteria are the absolute gap and the relative gap. The default tolerances are given by the software specification [77,78].

The absolute gap is declared equal to zero. If the BBA returns a solution with a zero-valued absolute gap, then the solution is characterized as a global one [70,72,73]. BBA ends up after spending a limited number of iterations [9,10,11,74].

To this end, the optimizer solver considers some stopping criteria in order to give a global optimal solution [44]. BBA embedded in an integer linear programming (ILP) solver such as MATLAB^® function intlinprog [70] ends up if the difference between the internally calculated $upper$ and $lower$ bounds on the objective function is less than or equal to Absolute Gap Tolerance [9,10,11,74].

Definition 4.

The mixed-integer program’s absolute gap (MIPGapAb) is declared as [9,10,11,69,70,71,72,73,74,77]:

$$Gap=upper-lower<\in$$

(29)

where $\in$ is the default tuning parameter to return an optimal solution point under warranty [70]. If, for a prescribed tolerance $\mathsf{\epsilon }>0$, the BBA produces bounds, then the termination criteria described in Equation (29) are fully satisfied [9,10,11,74].

The optimization function observes this difference. If the algorithm is converging, anticipating that $\epsilon \to 0$, and the solver terminates the optimization when the tolerances are relatively small [9,10,11,70,71,72,73,74].

In other words, the algorithm terminates at an optimal solution or ends up at an ε-optimum point based on the stopping criterion tolerance given in Equation (29) [9,10,11].

This prescribed tolerance is considered to be zero by the MATLAB^® function intlinprog or relatively small $1e-04$, defined by the Gurobi MILP solver [70,74].

Definition 5.

The relative gap is declared as found in [70]:

$$relative gap=(upper-lower)/(1+|upper\left|\right)$$

(30)

The optimizer MILP solver calculates, without stopping the upper and lower bounds on the objective function, the difference between those bounds. Absolute and relative gaps are computed and confirm the entire optimization run of the algorithm [9,10,11].

The BBA’s stopping criterion is determined by three states: optimality, elapsed time, and memory utilization. BBA solves all instances rapidly, as the log files show in the Appendix C and Appendix D. The tuning parameters help a lot to achieve convergence to a desired outcome within the predefined tolerances [9,10,11,42,44].

A global solution point is dependent on the satisfaction of parameters such as feasibility, tolerance, and optimality metrics [44]. As illustrated by the log file of the optimizer routine, the lower bound is a culprit in closing the gap, giving a certificate of global optimality [9,10,11,69,70,71,72,73,74].

The objective function is to obtain a value equal to the upper bound, which is the appropriate cost price for the minimization models [9,10,11]. On the other hand, the lower bound is considered to be the best solution for the maximization problems [9,10,11].

6.2. Convergence Analysis

A solution without suboptimality uncertainty is ensured by carefully examining optimality criteria, optimal solutions, and convergence to an adequate stopping criterion.

The LP-based BBA ensures convergence when a convergent branching method is utilized in the MILP solver implementation. A feasible solution is produced and satisfies the original model constraint function, or an infeasible output is proved or pruned by a bound [9,10,11]. We illustrate that the BBA converges to a solution by spending a finite number of explored nodes where the linear programming relaxations are solved [9,10,11].

The optimization function derives an upper bound on the objective function for the minimization models and a lower bound for the maximization models [9,10,11].

The computation complexity of the s-BBA is based on the fact that it must reach a solution satisfying a specific convergence criterion, such as when $upper-lower<\in$ [9,10,11,69,70,71,72,73,74,75,76,77,78,79].

The termination criterion is constantly evaluated based on a bound for the possible improvement of some lower bounds in contrast with the upper bounds [9,10,11].

If the absolute gap between the upper and lower bounds is within a predefined tolerance, the algorithm stops [9,10,11,74]. The optimizer routine constantly calculates the upper and lower bounds, and the entire optimization run ends up with the best incumbent solution, characterized as a global one [9,10,11,70,72,74,77,78,79].

As a result, the convergence is followed by the consideration that the $\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{e}\mathrm{r}-\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}$ is less than the default tolerance [9,10,11,77]. The algorithm constantly searches for a trade-off relationship between the upper and lower bounds and tries to terminate within an absolute tolerance gap with a predefined gap [9,10,11].

7. Solution of the Algorithmic Scheme Approaches and Optimization Results

PMU is a costly monitoring device [1]. Each PMU price ranges from USD 1260 to USD 10,000, depending on the number of PMU channel capacities [18].

As a result, it is not practical to install a PMU at every network node of any electricity transmission grid. Cost-efficient solutions are needed, which means that an appropriate number of PMUs must be located around the power grid at selected buses [12,13,14,15,16,17,18].

Our goal is to minimize the total cost and also maximize the maximum network observability index of this solution [22,34,35,39,41].

PMU placement algorithmic schemes are basically cost-efficient solutions related to PMU deployment around a modern power grid. They give the system operator the chance to guarantee full condition and improve power grid monitoring.

PMUs provide extensive and precise power monitoring and quality points of view in a large, wide geographic grid. The measurements are collected and help the system operator judge if the voltage, current, and frequency are staying within specific tolerances.

The principal concept of strategically posing PMUs is to help the state estimator tool observe the entire power grid state to be fully observable [2]. In addition to that purpose, our algorithms return solutions with maximum redundancy of the measurements in certain feasibility, tolerance, and optimality metrics [9,10,11].

The proposed PMU arrangement formulation concludes the terms involved in the objection function to find parameters (I) the number of PMUs, (II) PMU placement sites, and (III) maximize the measurement redundancy [46].

In this, we reconsider $0/1$ ILP [20,21,22], $0/1$ SDP [26,27,28], and quadratic binary polynomial problems to find an optimal solution within a 0.00% optimality criterion [69,70,71,72,73,77]. Many applications simply need a black-box approach that takes a given formulation as an input and delivers an optimal solution as an output. For such black-box procedures, the program’s user interacts with the optimizer solver. A command-line interface or an interactive shell calls the optimizer function.

This optimizer function is utilized by invoking the m-script files in MATLAB that contain the description of the objective function to be optimized under the constraint function [10]. We follow a decision-making method of calculation that minimizes an objective function under ILP, LMI, and polynomial constraints [9,10,11].

BBA optimizes a variety of optimization models, such as binary integer linear program (BILP) [20,21,22,23] and Boolean optimization models such as the semi-definite model [26] and the proposed polynomial problem [11].

BBA enacts optimization with multiple-choice constraints on the cost function [9]. BBA has the following merits to solve the ILP [20,21,22,23], SDP [26,27,28], and binary constraint polynomial models. The implementation in MATLAB is as follows [9,10,11]:

• BBA reduces the computational complexity based on the constraint function; either binary connectivity, LMI constraints, or polynomial constraints are easy to optimize. This can speed up the optimization process related to existing methods for obtaining a global solution point.
• The proposed optimization models are easy to implement in a symbolic format in YALMIP/MATLAB, and BBA makes it easy to optimize those models.
• The time spent on the entire optimization process illustrates that the procedure has low time complexity in achieving optimality.
• The proposed models are tested on 14-, 30-, 57, and a medium-size model of the IEEE-118 bus system. This fact enacts the tendency to extend the OPP to larger power systems.

Algorithms are symbolically implemented in MATLAB, with the model being optimized while the optimization is executed by YALMIP. The primal and secondary optimization models are solved through a BBA solver built-in in YALMIP calling external routines [77,78]. The primal and secondary problems are characterized by their solution robustness given by the log file of the BBA embedded in the MATLAB function, such as the MATLAB^® function intlinprog [70], the SCIP optimizer [72], and the Gurobi function [74].

IEEE 14-, 30-, 57-, and 118-bus network systems are utilized for the implementation of the proposed optimization models performed in the MATLAB environment [70,71,72,73,74,77,80]. We utilize a symbolic language using the YALMIP library to build the proposed optimization models [69,76,77,78].

As a result, it is based on common sense to validate the proposed minimization and maximization models on the classical IEEE power systems to show their implementation based on convergence and stopping criteria [44].

The resulting solution covers a solution within a 0.00% optimality criterion, staying within specific tolerances such as absolute and relative gaps [9,10,11,70,72].

The solution of the maximization problem shows that the maximum network observability is preserved [22,34,35,39,41]. The resulting solutions have specific maximum indices as proposed in [22], and a comparative study is conducted with optimality metrics presented in [35,46]. BPSO optimizes a two-product objective function, whereas GPSA minimizes a cost function with one criterion [35,46].

Also, GSA is utilized in [34] to optimize the OPP problem. A two-objective function is well optimized in order to locate those optimal solutions that satisfy the observation of the entire power network while preserving maximum network observability [22,33,34,35,39,41,46].

Although a $0/1$ semi-definite programming formulation is proposed in [28], its capability to achieve optimal results in terms of maximum network observation of the power grid state must be reconsidered [22,34,35,39,41,46].

Although the SCIP is utilized with CUTSDP as an outer approximation optimizer function to solve the SDP relaxations, the optimal solution is not feasible in terms of maximum network observation [34,35,39,41]. All optimization models are symbolically implemented using the YALMIP program [69] with powerful advanced optimization solvers to obtain an optimal solution within a 0.00% criterion [74].

To prove such an optimality criterion being achieved by the algorithm’s run, the log file is given in the Appendix C and Appendix D following the main body of this work [70,71,72].

As a result, all instances were solved using an optimality criterion equal to 0.00%. That means that no higher-quality solution can be found. Hence, reliable power system monitoring is now attainable by synchronized measurements [77].

Considering that our approach is to compare the performance of several global ILP solvers to the YALMIP problem-based optimal PMU placement implementation, we illustrate all the solution outcomes tabulated in relative tables in the Appendix B, Appendix C, Appendix D, Appendix E.

7.1. Results of Complete Observability of the Electricity Power Transmission Grid

The present study aims at minimizing an objective function to find a global solution point, meaning that this solution satisfies the by-default tuning or tolerance parameters. As a result, the outcome of each state-of-the-art solver gives an optimal solution within a zero-gap absolute gap as well as a zero price percentage relative gap [10,11,12].

We used the MATLAB R2018a [70,71] to optimize the mathematical models in collaboration with the SCIP optimization suite 8.0 [72,73], Gurobi 10.0.1 [74] and MOSEK 10.1 [79]. All optimization models are symbolically programmed with YALMIP 20210331 [69,76,78] and giving an optimal outcome.

Simulation results for the minimization problem applied to benchmark IEEE power systems [80] have been presented to illustrate that an optimal solution is achieved with feasibility and stopping criteria to be satisfied [44]. The PMU numbers needed for full observation of the power grid estimation and their positioning sites are shown in the tables in the Appendix B, Appendix C, Appendix D, Appendix E.

7.2. Results of Maximum Observation of the Electricity Power Transmission Grid

The main target is to make the state estimation process fully functional. PMU monitoring devices must be located strategically at power network nodes with appropriate placement sites and thereby succeed at maximizing the coverage of the obtainable measurement redundancy [22,33,34,35,39,41,46].

A unified effort has been spent to highlight a compact solution obtained by a primary-secondary optimization process. First, we minimize the total investment cost of PMUs to minimize the entire set of PMUs to be desired [33,45,46].

An optimal solution is attained through the solution of ILP, SDP, and polynomial problems with Boolean consideration [9,10,11]. Then, a maximization problem follows the solution of the minimization problem with an extra constraint function reflecting the optimal solution satisfying the criterion of full observation of the power grid state.

Solving such a kind of optimization problem, we derive solutions with maximum network observability. Each maximization model is solved by comparing several global ILP solver outcomes. As we can see, the outcomes are different, and they depend on a different search order in building the enumeration tree while an optimal solution is achieved [9,10,11].

All maximization problems are exactly solved with the suboptimality criteria fully met [9,10,11]. Simulation results for maximization problems applied to standard IEEE power systems have been reported to illustrate that an optimal solution is achieved with feasibility and stopping criteria satisfied [44]. The placement results with the maximum SORI are shown in relative tables in the Appendix B, Appendix C, Appendix D, Appendix E.

We return those solutions with maximum SORI. The selected strategic sites maximize measurement redundancy. The maximum observability indicators for each power network are illustrated in

Table A1. Best objective function value for standard IEEE system with minimum and maximum SORI.

IEEE-Power Systems	PMUs Number	Minimum SORI	Maximum SORI
IEEE-14 bus	4	14	19
IEEE-30 bus	10	35	52
IEEE-57 bus	17	61	72
IEEE-118 bus	32	145	164

. The same indices are found in [22,34,35,39,41,46].

With the maximum values of the SORI for the suggested maximization problem, it is clearly deduced that the proposed algorithms would count the maximum measurement redundancy. This truth validates our extended work in this research domain related to the maximum reliability of measurements in the state estimator process [1,2,59,60,61,62,63].

Appendix B, Appendix C, Appendix D, Appendix E illustrates the simulation results derived for both case studies namely full network observability and maximum network observability as well [20,21,22]. For each IEEE system, the best objective function value is illustrated with minimum and maximum SORI as defined in [22].

8. Discussion

The PDS, known as the OPP problem [3,4,5], is one of the greatest mathematical formulations studied, belonging to the combinatorial optimization problems [9,10,11,12,13,14,15,16,17,18].

Our proposal gives a structured procedure for solving the discrete optimization model in mathematical domains such as ILP [20,21,22,23], SPD [26,27,28], and Boolean polynomial models [9,10,44].

For that purpose, minimization models such as ILP [20,21,22,23] and SDP [26,27,28] are reconsidered to obtain a necessary and sufficient condition for optimality, and a quadratic Boolean polynomial is also proposed [9,10,42,44].

Then, a maximization model is implemented, taking into account the global solution achieved by the minimization problem, to deliver those solutions with SORI [22,46].

Initially, a minimization model is optimized to find the optimal number of PMUs, and then, following that number, a maximization model is constructed to give this solution, which satisfies the maximum network observation of the power state grid [22,46].

The former model is a binary integer linear programming model that can be solved by any powerful advanced MILP solver. Then, a CBQP model is utilized that is fully equivalent to the former integer linear programming model with binary values [10].

Both algorithmic models are solved by the YALMIP BBA built-in BMIBNB routine [77]. We utilize this routine to solve the CQBO model and then a linear CBO to achieve the placement of PMU sets with the highest SORI [22,34,35,39,41,46].

BMIBNB is based on external MILP optimizer functions to solve the lower bounding relaxation programming problems and a nonlinear function to estimate the upper bound.

The lower solver is used to solve the relaxed problems, the local solver to count the upper bound, and an LP solver to calculate the bound strengthening [77].

The upper bound is produced by invoking the upper solver; the relaxed problems are implemented by an LP solver; and a lower bound is generated with a lower solver constantly compared with the upper bound. The solution is found to be inside a zero-valued absolute and relative gap, and that means no higher-quality solution can exist.

As a result, it is characterized as a globally optimal solution. Also, a Boolean SDP is reconsidered by using a CUTSDP solver and powerful optimizer solvers such as MATLAB^® function intlinprog [70], SCIP optimizer function [72,73], Gurobi function [74], and MOSEK [79] to obtain an optimal solution.

The algorithm returns a global optimum objective function value and its corresponding binary-valued decision vector to the decision-making problem.

BBA terminates within specific tolerances and gives the global solution for $0/1 \mathrm{I}$LP [20,21,22,23], $0/1 \mathrm{S}$DP [26,27,28], and $0/1$ constraint polynomial problems [9,10].

Despite the notation that the ILP model is trapped in the same solution and cannot handle the task of measurement redundancy [24,36], we utilize the GUROBI to implement it and collect all the optimal solutions [74].

We illustrate that the BBA gives all the solutions using the solution pool option of GUROBI for both case observability scenarios, as illustrated in Figure 1 [74].

As a result, our innovation, besides the fact that the solution is a global outcome discovered inside a zero-gap tolerance, is that we deliver all the optimal solutions through binary integer linear programming [9,10,11]. Also, we bring to your attention that the same number of PMUs has been found in [25] for the IEEE-30 bus system [80] to further validate our approach.

The total number of PMUs and the number of PMU placements as well are shown in Figure 1 for the complete observability scenario. The total number of PMUs is produced by optimizing the binary integer program using the GUROBI optimizer [74].

GUROBI solves exactly the optimization problem within a zero-gap tolerance, giving all the optimal solutions as shown in Figure 1 and the relative tables in the Appendix E.

In addition, we declare a maximization problem by which the ILP can handle with efficiency the measurement redundancy task. Figure 2 illustrates the minimum and maximum SORI observability indicators produced by optimizing the binary integer, Boolean semi-definite, and constraint polynomial models [22,46].

This chart shows that our methodology is superior to the work published in [28,50]. The values of the maximum observability indicator as shown in Figure 2 are in full agreement with those found in [9,10,11,34,35,41,46].

The minimum values of SORI are produced by minimizing the maximization problem. As a result, our study illustrates the best outcomes related to this observability index, as proposed in [22]. Figure 3 illustrates the total number of PMU set solutions with the maximum observability index [22,35,39,46].

Placing an exact number of PMUs helps the system operator avoid abnormal situations and guarantees a constant supply of power and electricity to the utilities and customer satisfaction (Figure 1). The total number of PMUs is derived using the GUROBI optimizer engine, which adjusts the solution pool option properly [9,11,74].

Also, the best number of PMUs can be posed at specific power grid nodes to satisfy the measurement redundancy, as shown in Figure 3. As a consequence of this, a power grid node will be observed the maximum possible number of times, either directly or indirectly, by the laws of Kirchhoff and Ohm [19,20,21,22,23,32,45,46].

9. Conclusions

In this work, two goals have been studied to satisfy a need to observe the power grid state with the declaration of one objective function representing the total cost of PMU installation. The aim is to decrease the PMU numbers to satisfy the observation of the electricity power transmission grid.

The second goal is to maximize the power system observation of the power grid through the declaration of a maximization problem. The minimization problem is considered the primal optimization, which gives a global solution point.

This solution is used as an extra constraint in a maximization problem to derive those solutions that are best and satisfy the maximum reliability of the electricity power transmission grid at the same time.

For the minimization problem, optimization of a linear objective function was conducted under ILP, polynomial, and LMI constraints. The primary outcome is the discovery of a binary-valued optimum point. We implement optimization models using a YALMIP library fully compatible with MATLAB. Our main solution algorithm is the branch-and-bound algorithm, which returns a globally high-quality solution for each optimization model. Optimizing the tuning parameters of the BBA, solutions are derived based on the accuracy of an optimal criterion equal to 0.00%. Illustrating its robustness, a solution was achieved by meeting a 0.00% optimality criterion.

In the second step of the process, the consideration shifts towards maximization problems, adhering to the logic of primal and secondary solutions. Leveraging the high-quality solution derived from the minimization problem, the aim is to identify a solution that satisfies the requirement for comprehensive monitoring across a wide area from the perspective of maximizing network observability.

The implementation of the proposed methods, either in minimization or maximization problems unambiguously programmed in MATLAB and easy to solve, proved the iterations of the BBA to achieve the desired constraint minimum point under sufficient global optimality conditions.

As a result, both optimization schemes are well optimized at finding constraint minimum points satisfying indisputable optimality conditions. BBA succeeds in building a binary tree, explores a suitable number of nodes, solves linear problem relaxations, and finally terminates the entire optimization with the exact solution.

We find out that the upper bound is the optimal objective value of the minimization problem at the final root node, whereas the lower bound is equal to the upper bound, closing the absolute gap. As a result, the BBA terminates with a stopping criterion to be met. For the maximization problem, the lower bound is considered the best solution.

All models are solved by building a binary tree as small as possible, and the solution is found inside a zero-valued absolute and relative gap.

These stopping criteria are necessary and sufficient conditions to show if the solution is a global solution point or a suboptimal outcome. We accomplish our target, and the optimization problems are solved globally.

As a result, we fill the knowledge gap about OPP problem solving and whether it derives optimal or suboptimal solutions. These algorithms perform with high accuracy and optimize small and medium-sized optimization problems without losing the chance of determining the global optimum as the size of the dimensions increases.

To enhance our proposal, log files are given in the Appendix C, Appendix D, Appendix E. As the log files illustrate, the binary search tree is small in size due to the simplicity of the symbolic reformulation of the proposed optimization models.

Our proposal gives a trade-off optimization run in terms of the implantation of the best optimal solution in the first stage and the second solution satisfying maximum reliability. In summary, an actual-world problem is stated in a decision-making way as a solution without facing any uncertainty about optimality.

10. Further Research Based on the Topics Studied in This Study

Minimizing the number of PMUs reduces the entire investment cost of PMU installation needed to fully monitor an electricity power transmission system, which is the principal concern for strategically posing PMUs around the power transmission grid.

The task studies in this work contain SynchroPhasors for the performance of the power grid; the best reliability of the system observability redundancy index (SORI) for the best arrangement of PMUs around the power grid; and complete and maximum observation of the power grid.

At the moment, PMUs are integrated with the SCADA system to observe the power grid state. In the recent past, artificial intelligence (AI) and machine learning (ML) methods were used for the detection of abnormal situations occurring in the electricity transmission power grids, such as fault events.

These algorithms are able to detect, recognize, and locate the fault occurring on a transmission line. The strategic implications of our proposed method cover a wide range of methodological and applied contributions. The planning consequences of our proposed algorithmic approach are summarized in the following items:

PMUs are technology-advanced devices designed to observe power flows regarding power generation, demand, turn-on features, and advanced system management.

• The future grid will have the capability to incorporate a large number of PMUs to help a lot with utilities and customers’ requirements for constant power supply at the lowest possible cost.
• We propose those PMU arrangements that improve power grid reliability through the maximum observation of the power grid state estimator tool installed in the system operator.
• It produces a complete working OPP solution with accuracy and improved ability to accomplish the aim for the exact number of PMUs under guarantee as well as those solutions satisfying maximum reliability.
• A future direction is to extend our symbolic programming models and computational way of their solutions under any contingencies in SGs.
• Future research could investigate the combination of PMUs with AI and ML algorithms to enable real-time detection and response to cyberattacks.
• It also works as a first test for a novel algorithmic scheme to use a global optimizer routine for solving combinatorial problems with the symbolical programming language and finding a global solution point.