2
$\begingroup$

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

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$$

$\endgroup$
6
  • $\begingroup$ Does this really justify MIP? It's a very simple (and thankfully acyclic) graph $\endgroup$
    – Reinderien
    Commented Sep 13, 2023 at 12:51
  • $\begingroup$ I believe it can be solved using MIP. This problem is part of a big optimization problem where the objective is to select a minimal number of nodes subjected to a set of constraints. $\endgroup$
    – bsha
    Commented Sep 14, 2023 at 1:08
  • $\begingroup$ In the big optimization problem, does this network remain exactly as shown? $\endgroup$
    – Reinderien
    Commented Sep 14, 2023 at 3:14
  • $\begingroup$ The base network will remain as it is. However, each node will have more devices attached to it and the optimization problem will select a certain number of devices that are directly attached to node P or in the close proximity of node P. $\endgroup$
    – bsha
    Commented Sep 14, 2023 at 5:55
  • $\begingroup$ Based on description I believe you can formulate as min cost flow (P is source and Cloud is sink, cost is equal across all edges). $\endgroup$
    – Andy W
    Commented Sep 14, 2023 at 11:40

1 Answer 1

1
$\begingroup$

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)} $$

$\endgroup$
6
  • $\begingroup$ In my case, there are no specific source and destination nodes for which I will select the path. Each node has a set of different devices attached to it. Therefore, to select the minimun number of nodes and the required number of devices the graph may expand on both sides of P node, i.e., towards the Cloud connected and in the opposite direction. $\endgroup$
    – bsha
    Commented Sep 14, 2023 at 16:11
  • $\begingroup$ For example, node 2 is node P and also have connection to the Cloud and required number of attached devices, then the solution will provide only node 2. However, if node 3 is node P, node 2 has connection to the Cloud, and node 5 has required number of attached devices, then the solution will be nodes 2, 3, and 5. If we consider node P (i.e., 3) as source node, then it should expand in both directions to select the minimum number of nodes meeting required constraints. $\endgroup$
    – bsha
    Commented Sep 14, 2023 at 16:19
  • $\begingroup$ @bsha This "number of attached devices" is not described in your problem, and makes it sound like you need two paths: one from P to the cloud, and one from P to the "attached devices". Please edit your question. $\endgroup$
    – Reinderien
    Commented Sep 15, 2023 at 13:10
  • $\begingroup$ @Brannon what does $m$ represent in your answer? $\endgroup$
    – bsha
    Commented Sep 20, 2023 at 2:53
  • $\begingroup$ $m$ is a flag for enforcing that a node has both an input and an output (or neither and no other option is allowed). Your needs may vary, should you allow multiple inputs to one output, etc. $\endgroup$
    – Brannon
    Commented Sep 20, 2023 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.