\section{Introduction}

In order to mitigate power outages, electric companies must monitor the power grid for electrical imbalances. To observe the current and voltage levels across the power grid, sensors known as Phasor Measurement Units (PMUs) can be installed at power substations. Although outfitting all power substations with PMUs could provide the measurements necessary to monitor the power grid, installation costs make it desirable to minimize the number of sensors implemented, while still ensuring that the network can be effectively monitored. By utilizing basic circuit analysis (e.g. Kirchoff's Voltage laws and Ohm's Law) and a partial set of measurements directly obtained with PMUs, it is often possible to uniquely determine the voltage levels and currents of power grid components which are not being directly measured. The resulting optimization problem, finding minimal arrangements of sensors that can still effectively monitor the power grid, is broadly referred to as the PMU placement problem and was originally introduced by Baldwin et al. \cite{baldwin}.

Since its introduction, many strategies for the PMU placement problem have been posed, often ensuring that the resulting solutions have added resiliencies to natural disasters or malfunctioning equipment. Notably among these are fault tolerant placement strategies \cite{pmu-fault1}, strategies which can detect incorrect measurements \cite{pmu-inj2, pmu-inj1, pmu-inj3}, and multistage problems in which PMUs are installed over several time periods \cite{pmu-multi1, pmu-multi2}. 

The PMU placement problem has also been posed in terms of graph networks, where it is known as the power dominating set problem. An electrical network can be represented as a graph $G=(V,E)$, with power substations and transmission lines corresponding to vertices and edges. The set of power substations housing PMUs then corresponds to a vertex set $S \subseteq V$. A set of rules called the power domination color changing rules can be applied to $S$ in which additional vertices can also be colored. Haynes et al. \cite{haynes} introduced the first set of power dominating color changing rules and showed that if $V$ can be entirely colored by their rules, and PMUs are placed at each substation in $S$, then the state of each transmission line and power substation can be uniquely determined. Benson et al. \cite{benson} later introduced a simpler color changeing rule, and showed it to be equivalent to the color changing rule introduced by Haynes et al. \newline

\begin{minipage}{\textwidth}

\textit{Power Domination Color Changing Rule}:~\cite{benson}
\begin{enumerate}
\item[1.] Color all vertices in or adjacent to an initial vertex set $S$.
\item[2.] While there are colored vertices each adjacent to exactly one uncolored vertex, color those vertices. 
\end{enumerate}
\end{minipage} \newline \newline

The set of vertices that are colored at the end of this process is called the {\em power dominating closure} of $S$, and is denoted as $cl_P(S)$. If $cl_P(S) = V$, then $S$ is called a {\em power dominating set} in $G$. Furthermore, the cardinality of the minimum power dominating set(s) in $G$ is called the {\em power dominating number} of $G$, and is denoted as $\gamma_P(G)$. Finding minimum cardinality power dominating sets is equivalent to devising PMU placement strategies that can fully observe the network while utilizing of a minimum number of sensors.


During the first step of the power domination color changing rules, called the {\em domination step}, all uncolored vertices adjacent to an initially colored vertex are colored. In the second step, called the {\em propagation step}, additional vertices are colored if they are the unique uncolored neighbor of a colored vertex. An uncolored vertex $u$ that is colored by a vertex $v$ is said to be {\em colored} or {\em forced} by that vertex. This terminology is used due to the similarity between power domination and the related zero forcing color changing process in graphs \cite{AIM-zf}, which we briefly introduce in a later section. The propagation step corresponds to the inferences which can be made to uniquely the unmeasured states of power substations and transmission lines. This process introduces additional complexity in determining which parts of the electrical network can be observed. In many computational studies of the PMU placement problem, this step is not considered. The resulting problem more closely resembles the dominating set problem and thus computational methods for the PMU placement problem cannot be directly compared to those in power domination.

Several variations of power domination have also been proposed. These include versions in which the initial colored set must induce a connected graph \cite{conn-pd, fan&watson} or contain certain vertices \cite{bozeman, Restricted}. The computational complexity of power domination has also been a topic of interest. While the power dominating set decision problem is known to be NP-Complete even in the case of planar bipartite graphs \cite{haynes}, the power domination numbers of graphs in several classes can be computed with polynomial time complexity algorithms, including: trees~\cite{haynes}, block graphs~\cite{comp-blocks}, grid graphs~\cite{comp-grids}, interval graphs~\cite{comp-intervals}, and circular-arc graphs~\cite{comp-arcs}. Despite wide interest in power domination, relatively little work on computational methods has been published.

Currently, several integer programs (IPs) have been proposed. Each of these models have variables corresponding to the a candidate initial set of colored vertices, and the sequence in which forces occur so that all vertices are colored. Additionally, their constraints ensure that the order in which forces occur in obeys the power domination color change rules. Aazami~\cite{aazami} first introduced an IP of this style which Brimkov et al. \cite{conn-pd} improved upon by reducing the number of variables needed for the model. A third IP has also been introduced by Fan and Watson~\cite{fan&watson} which works on similar principles as the two methods previously mentioned. However, their model considers a slightly different problem than the standard power dominating set problem and cannot be directly compared.


As the main result of this paper, we propose an alternative method for computing the power domination numbers of arbitrary graphs. Our method is based on a novel integer program which exploits the neighborhood sets of structures called forts, arising in the related zero forcing problem. To formulate this IP and verify that it correctly computes the power domination numbers of arbitrary graphs, we study the structural properties of their neighborhoods, provide necessary and sufficient conditions for vertex sets to be the neighborhoods of forts, and give a practical procedure by which these neighborhoods can be identified. We also show two ways in which violated constraints for our IP can be separated, thereby allowing our model to be solved with a row generation strategy, unlike the existing methods.

In additional, we show several ways in which the runtime performance of both our method and existing methods can be improved by exploiting the presence of special optimal solutions as well as graph structures which commonly in electrical networks. We conclude with computational comparisons of the method we propose with the IP proposed by Brimkov et al. \cite{conn-pd}, and consistently demonstrate at least an order of magnitude improvement in runtime performance.
{"config": "arxiv", "file": "2006.03460/introduction.tex"}