How to select intermediate nodes in a network?

Question

I have a network where nodes are connected as shown in the Figure .

Nodes 2 and 4 have a connection to the cloud node. I am writing constraints where at least one node with a connection to the cloud must be selected. Furthermore, a node $P$ must also be selected. The objective is to select a minimal number of nodes while addressing the previous two constraints. However, the selected nodes must have a path directly or indirectly. If the node $P$ is node 2 or node 4, then the solution will be only node 2 or node 4. However, for other nodes, there should be a communication path to nodes 2 or 4. For example, if node $P$ represents node 5, then the solution will be nodes 2, 3, and 5.

I have written the following constraints. However, I am not able to select the intermediate node(s) which constitute a path. Any help in this regard is appreciated.

The objective function is

$$\min \sum_{i\in N} x_{i}$$

The constraints are as follows:

$$x_{P} = 1$$ $$\sum_{i\in N} CloudConnection_{i} * x_{i} \ge 1$$ $$\sum_{i\in N, i \ne j} NodeCommunication_{i, j} * x_{i} \ge x_{j} \quad \forall j \in N$$

Answer 1

Option 1: Run Dijkstra's algorithm first. Then you will have a grid of positive numbers that you can use for additional constraints. E.g. require a positive number to know that a path is available from not $i$ to node $j$. Maybe try to minimize that distance number too.

Option 2: Change your model to select all the nodes in the path. Add additional variables representing the selected edges. You can add constraints to those to ensure that any selected node has an input edge selected and an output edge selected. E.g. $$ ~\sum_i X_{ij}=m_j ~~~~~ j \in 2...n-1 ~~~~\text{(require input if output)} $$ $$ ~\sum_j X_{ij}=m_i ~~~~~ i \in 2...n-1 ~~~~\text{(require output if input)} $$