Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively. Below is shown a graph with 9 nodes and 12 edges, which I will use as an example.
7
.*.
. .
. .
. 9 .
8 * . . . * . . . .* 6
. . .
. . .
. . .
4 *. . . .* 5 * 1
. . .
. . .
. . .
3 *. . . .*
2
I need a subgraph of $G$ (let's call the subgraph $g$). The subgraph must be both connected and radial. The topics of connectivity as well as radiality have already been well discussed here (Ensure a graph is connected in a linear programming problem) and I will briefly discuss them below before I go over my major question.
To formulate the connectivity constraint, I use the flow of a phantom commodity. All the nodes of the original graph must be retained in the subgraph. Assume the graph is undirected with $|V(G)|=n$. In what follows I will assume that if $(i,j)$ is an edge, $(j,i)$ is recognized as the same edge and the variable $x_{ji}$ exits (and is constrained to equal $x_{ij}$). $x_{ij}$ is a binary variable representing the status of the edge connecting node $i$ to $j$. If $x_{ij}$ is zero then the edge $(i,j)$ is removed. Arbitrarily pick one vertex $υ_0∈V(G)$ as the source, with a supply of $n-1$ units of the phantom commodity. Every other vertex has demand 1. Add variables $y_{ij}$, representing the flow of whatever it is from $i$ to $j≠i$ across the edge between them, together with the below constraints:
$$-(n-1)x_{ij}\le y_{ij}\le (n-1)x_{ij}, \quad \forall i,j∈V(G),i≠j$$
$$\sum_{j\in V:(v_0,j)\in E(G)}y_{v_0,j} = n-1,$$
and
$$\sum_{j:(i,j)\in E(G)}y_{i,j}=\sum_{j:(j,i)\in E(G)}y_{j,i}-1\quad \forall i\in V(G)\backslash \lbrace v_0 \rbrace.$$
The first constraint essentially says that you cannot move the commodity across an edge that was not chosen for the subgraph. The second constraint dictates the flow out of the chosen source vertex (and serves to ensure that it is connected to the rest of the subgraph). The third constraint says that at every other node, one unit of supply gets absorbed and anything left gets passed along. The approach I use for representing the radiality of the subgraph is to model the network as a directed graph. The clear statement of the constraints is as follows:
$$B_{ij}+B_{ji}=x_{ij} ,(i,j)∈E(G)$$
$$\sum_{j\in N_i}B_{i,j} = 1,i=2,3,…,n$$
$$B_{1j}=0,j∈N_1$$
$$B_{ij}∈\{0,1\} ,(i,j)∈E(G)$$
The above-explained methodologies for modeling the connectivity and radiality constraints are well-known and work very well. Below is shown a random subgraph of $G$ that meets both the connectivity and radiality conditions.
7
.*
.
.
. 9
8 * . . . * . . . .* 6
.
.
.
4 *. . . .* 5 * 1
. .
. .
. .
3 *. . . .*
2
From now on I will explain what my major question is. We can calculate the number of the edges of the subgraph as below:
$$|E(g)|=\sum_{(i,j)\in E(G)} x_{ij}$$
Now we introduce binary variable $z_{ij}$, which is constrained as below:
$$z_{ij}\le x_{ij}, \quad ∀ (i,j)∈E(G), \quad z_{ij}∈\{0,1\}$$
$z_{ij}$ represents if the edge connecting node $i$ to $j$ is switched off or not. In other words, if it is 1, the edge (line) is kept. Otherwise, the edge is removed. Look at the edge like a power line that can be switched on or off under abnormal situations.One snapshot of the subgraph after some of the lines are switched off is shown below:
7
.*
.
.
. 9
8 * * . . . .* 6
.
.
.
4 *. . . .* 5 * 1
. .
. .
. .
3 * *
2
As it is seen, the subgraph is now disconnected and consisted of 3 smaller subgraphs, which I would like to call islands hereinafter. This happens whenever some of $z_{ij}$s are zero. You may ask why the connectivity, which was important to us, is now compromised. Please note that the subgraph, which represents a power network, will not remain in the above-described islanded mode and it will return to the topology of the subgraph right after the abnormal situation is over, which often is not long. Since the subgraph was connected and radial, the number of the islands is equal to the number of the switched-off edges plus one. This is calculated as below:
$$number \quad of \quad islands=1+\sum_{(i,j)∈E(G)} x_{ij} -\sum_{(i,j)∈E(G)}z_{ij}$$
I need to assign one and only one energy source to any node of each island. The capacity of the energy source does not matter and only its location is important to us. Since I do not know which node(s) will appear in which island, I introduce the binary variable $s_i$ where $i∈\{1,2,…,n\}$. Remember that $n$ is a known parameter (i.e., $|V(G)|=n$). $s_i$ is 1 if an energy source is located at node $i$ and zero if otherwise. Since each island hosts only one energy source, the sum of $s_i$ is equal to the number of islands. That is,
$$\sum_{i∈V(G)}s_i =1+\sum_{(i,j)∈E(G)} x_{ij} -\sum_{(i,j)∈E(G)} z_{ij}$$
The above equality constraint is helpful, but I still need to put more linear constraints on $s_i$ for feasibility purposes. My question is what are the additional constraints I need to put on $s_i$?
For instance, the solution $=[1,1,1,0,0,0,0,0,0]^T$ satisfies the above constraint, but it is not feasible since 2 energy sources will be put on the island made of nodes 1 and 2 (look at the above islanded subgraph).To further clarify, below are given some of the feasible solutions for $s$.
$=[1,0,1,0,0,1,0,0,0]^T$
$=[0,1,0,0,1,0,0,0,1]^T$
$=[1,0,0,1,0,1,0,0,0]^T$