Decision Optimization

I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN₁, EN₂, ... EN_n}. Each node in EN has a set of temperature sensors connected to it. Some of the nodes in EN have visual sensors attached to them. There is one same wind sensor attached to two nodes EN_k and EN_l. This means only these two nodes can communicate with the wind sensor. Each sensor may have a connection to more than one node. A few nodes from EN have a direct connection with data centre C. Some nodes can directly communicate with other nodes in their communication ranges. I have a specific node named RN from the set of nodes EN.

I am writing an OPL code in CPLEX where the objective is to select a minimal number of nodes meeting the following:

1. The node RN is selected.
2. The sum of temperature sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 3.
3. The sum of visual sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 2.
4. The sum of wind sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 1.
5. One of the selected nodes must have a direct connection to the data centre C.
6. All the selected nodes must have a connection to at least one other selected node, i.e., it should be a connected graph type instead of disconnected.
7. All the sensors (temperature, visual, and wind) should be directly connected to the RN or in close proximity to the RN. It means that they are selected based on their distance from the RN node. However, in this case, the distance is measured by the connection rather than the actual distance. For example, three nodes RN, EN₁ and EN₂ can satisfy all the constraints. If node RN has a communication link with node EN₁ and node EN₁ has a communication link with node EN₂, then if the nodes RN and EN₁ can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN₁ rather than EN₂.

I have written the following code:

This question was also asked on OR Stack Exchange (https://or.stackexchange.com/questions/10921/how-to-write-constraints-to-select-sensors-in-the-proximity-of-selected-nodes) and Math Stack Exchange (https://math.stackexchange.com/questions/4760731/how-to-enforce-a-constraint-to-select-a-set-of-connected-nodes-in-an-optimizatio).

I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN₁, EN₂, ... EN_n}. Each node in EN has a set of temperature sensors connected to it. Some of the nodes in EN have visual sensors attached to them. There is one same wind sensor attached to two nodes EN_k and EN_l. This means only these two nodes can communicate with the wind sensor. Each sensor may have a connection to more than one node. A few nodes from EN have a direct connection with data centre C. Some nodes can directly communicate with other nodes in their communication ranges. I have a specific node named RN from the set of nodes EN.

I am writing an OPL code in CPLEX where the objective is to select a minimal number of nodes meeting the following:

1. The node RN is selected.
2. The sum of temperature sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 3.
3. The sum of visual sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 2.
4. The sum of wind sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 1.
5. One of the selected nodes must have a direct connection to the data centre C.
6. All the selected nodes must have a connection to at least one other selected node, i.e., it should be a connected graph type instead of disconnected.
7. All the sensors (temperature, visual, and wind) should be directly connected to the RN or in close proximity to the RN. It means that they are selected based on their distance from the RN node. However, in this case, the distance is measured by the connection rather than the actual distance. For example, three nodes RN, EN₁ and EN₂ can satisfy all the constraints. If node RN has a communication link with node EN₁ and node EN₁ has a communication link with node EN₂, then if the nodes RN and EN₁ can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN₁ rather than EN₂.

I have written the following code:

I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN₁, EN₂, ... EN_n}. Each node in EN has a set of temperature sensors connected to it. Some of the nodes in EN have visual sensors attached to them. There is one same wind sensor attached to two nodes EN_k and EN_l. This means only these two nodes can communicate with the wind sensor. Each sensor may have a connection to more than one node. A few nodes from EN have a direct connection with data centre C. Some nodes can directly communicate with other nodes in their communication ranges. I have a specific node named RN from the set of nodes EN.

I am writing an OPL code in CPLEX where the objective is to select a minimal number of nodes meeting the following:

1. The node RN is selected.
2. The sum of temperature sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 3.
3. The sum of visual sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 2.
4. The sum of wind sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 1.
5. One of the selected nodes must have a direct connection to the data centre C.
6. All the selected nodes must have a connection to at least one other selected node, i.e., it should be a connected graph type instead of disconnected.
7. All the sensors (temperature, visual, and wind) should be directly connected to the RN or in close proximity to the RN. It means that they are selected based on their distance from the RN node. However, in this case, the distance is measured by the connection rather than the actual distance. For example, three nodes RN, EN₁ and EN₂ can satisfy all the constraints. If node RN has a communication link with node EN₁ and node EN₁ has a communication link with node EN₂, then if the nodes RN and EN₁ can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN₁ rather than EN₂.

I have written the following code:

Constraint 6 as stated (All the selected nodes must have a connection to at least one other selected node") does not guarantee a connected graph. If we select nodes A, B, C and D with edges between A and B and between C and D (and only those edges), every node is connected to another node but the graph is disconnected. To force the solution to be connected, consider adding flow variables from every node to every other node, with RN as the lone source node and each sensor of any type having a demand of one unit if selected and zero if not selected. At any selected node other than RN and sensors, flow in = flow out. At selected sensors, flow out = flow in - 1. At nodes that are not selected, flow in = 0 = flow out.

Constraint 7 sounds more like a secondary objective than a constraint. You can either minimize a weighted combination of the number of nodes selected and the aggregate distance of the sensors from RN, or you can use a lexicographically ordered vector of two objectives (supported by current versions of CPLEX), where the primary objective is to minimize the number of nodes and the secondary objective is to minimize the aggregate distance from RN for the sensors (without increasing the number of selected nodes beyond the minimum). To get a measure of the aggregate distance, and assuming you use the flow idea above, you can make the secondary objective the total cost of the flows in the network, where each edge has a cost of one per unit of flow over the edge.

I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN₁, EN₂, ... EN_n}. Each node in EN has a set of temperature sensors connected to it. Some of the nodes in EN have visual sensors attached to them. There is one same wind sensor attached to two nodes EN_k and EN_l. This means only these two nodes can communicate with the wind sensor. Each sensor may have a connection to more than one node. A few nodes from EN have a direct connection with data centre C. Some nodes can directly communicate with other nodes in their communication ranges. I have a specific node named RN from the set of nodes EN.

I am writing an OPL code in CPLEX where the objective is to select a minimal number of nodes meeting the following:

1. The node RN is selected.
2. The sum of temperature sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 3.
3. The sum of visual sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 2.
4. The sum of wind sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 1.
5. One of the selected nodes must have a direct connection to the data centre C.
6. All the selected nodes must have a connection to at least one other selected node, i.e., it should be a connected graph type instead of disconnected.
7. All the sensors (temperature, visual, and wind) should be directly connected to the RN or in close proximity to the RN. It means that they are selected based on their distance from the RN node. However, in this case, the distance is measured by the connection rather than the actual distance. For example, three nodes RN, EN₁ and EN₂ can satisfy all the constraints. If node RN has a communication link with node EN₁ and node EN₁ has a communication link with node EN₂, then if the nodes RN and EN₁ can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN₁ rather than EN₂.

I have written the following code:

Thank you. In my case, the graph is not complete, but a path exists between any pair of nodes. Can you please clarify what you mean by adding flow variables from every node to every other node? In the given problem, it is possible to find the minimum number of nodes and required number of sensors by expanding the graph in both directions of RN. If we consider RN to be a source node, how can it expand in both directions? I am new to CPLEX so not sure about lexicographically ordered vector of objective. Is it possible to write a minimal mathematical description/code to make it easy for me to understand? I have tried writing the code for the solution you suggested by adding a decision variable for flow. However, I could not complete it because I could not comprehend it properly. I have added a figure of a very small graph for which I am trying to solve the problem. In this figure, the sun icon represents temperature sensors, the triangle icon represents visual sensors, and the D icon represents the wind sensor.

Constraint 6 as stated (All the selected nodes must have a connection to at least one other selected node") does not guarantee a connected graph. If we select nodes A, B, C and D with edges between A and B and between C and D (and only those edges), every node is connected to another node but the graph is disconnected. To force the solution to be connected, consider adding flow variables from every node to every other node, with RN as the lone source node and each sensor of any type having a demand of one unit if selected and zero if not selected. At any selected node other than RN and sensors, flow in = flow out. At selected sensors, flow out = flow in - 1. At nodes that are not selected, flow in = 0 = flow out.

Constraint 7 sounds more like a secondary objective than a constraint. You can either minimize a weighted combination of the number of nodes selected and the aggregate distance of the sensors from RN, or you can use a lexicographically ordered vector of two objectives (supported by current versions of CPLEX), where the primary objective is to minimize the number of nodes and the secondary objective is to minimize the aggregate distance from RN for the sensors (without increasing the number of selected nodes beyond the minimum). To get a measure of the aggregate distance, and assuming you use the flow idea above, you can make the secondary objective the total cost of the flows in the network, where each edge has a cost of one per unit of flow over the edge.

I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN₁, EN₂, ... EN_n}. Each node in EN has a set of temperature sensors connected to it. Some of the nodes in EN have visual sensors attached to them. There is one same wind sensor attached to two nodes EN_k and EN_l. This means only these two nodes can communicate with the wind sensor. Each sensor may have a connection to more than one node. A few nodes from EN have a direct connection with data centre C. Some nodes can directly communicate with other nodes in their communication ranges. I have a specific node named RN from the set of nodes EN.

I am writing an OPL code in CPLEX where the objective is to select a minimal number of nodes meeting the following:

1. The node RN is selected.
2. The sum of temperature sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 3.
3. The sum of visual sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 2.
4. The sum of wind sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 1.
5. One of the selected nodes must have a direct connection to the data centre C.
6. All the selected nodes must have a connection to at least one other selected node, i.e., it should be a connected graph type instead of disconnected.
7. All the sensors (temperature, visual, and wind) should be directly connected to the RN or in close proximity to the RN. It means that they are selected based on their distance from the RN node. However, in this case, the distance is measured by the connection rather than the actual distance. For example, three nodes RN, EN₁ and EN₂ can satisfy all the constraints. If node RN has a communication link with node EN₁ and node EN₁ has a communication link with node EN₂, then if the nodes RN and EN₁ can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN₁ rather than EN₂.

I have written the following code:

You can find some discussion of selecting a connected subgraph in one of my blog posts: https://orinanobworld.blogspot.com/2023/05/finding-connected-subgraph.html. It contains a link to source code (in Java) for building/solving the model in CPLEX. In the context of your problem, we would treat every sensor as a "node", connected by edges to one or more original nodes. Your RN node would be what I called the "source vertex" in the blog post. So in your diagram there would be 17 nodes (assuming the box labeled "G" contains something useful; 16 if we can ignore "G"). For temperature sensor 4, there would be four possible flows: from node 2 to temp 4; from temp 4 to node 2; from temp 4 to node 3; and from node 3 to temp 4. A flow must be zero unless both of its endpoints are selected for the final graph. If node 2 is RN, then node 2 must be selected, and it has a supply of 12 units (assuming "G" is being used). Every sensor node has a demand of 1 if selected, 0 if not selected, which must be satisified. So you have constraints of the form "sum of flows into sensor node X - sum of flows out of sensor node X = y_X" where y_X is a binary variable with value 1 if X is selected for the final graph and 0 if not. For non-sensor nodes (other than node 2 = RN), flow out equals flow in (no demand there).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Mon September 18, 2023 01:39 AM
From: BABAR SHAHZAAD
Subject: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

Thank you. In my case, the graph is not complete, but a path exists between any pair of nodes. Can you please clarify what you mean by adding flow variables from every node to every other node? In the given problem, it is possible to find the minimum number of nodes and required number of sensors by expanding the graph in both directions of RN. If we consider RN to be a source node, how can it expand in both directions? I am new to CPLEX so not sure about lexicographically ordered vector of objective. Is it possible to write a minimal mathematical description/code to make it easy for me to understand? I have tried writing the code for the solution you suggested by adding a decision variable for flow. However, I could not complete it because I could not comprehend it properly. I have added a figure of a very small graph for which I am trying to solve the problem. In this figure, the sun icon represents temperature sensors, the triangle icon represents visual sensors, and the D icon represents the wind sensor.

------------------------------
BABAR SHAHZAAD

Original Message:
Sent: Sat September 16, 2023 03:22 PM
From: Paul Rubin
Subject: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

Constraint 6 as stated (All the selected nodes must have a connection to at least one other selected node") does not guarantee a connected graph. If we select nodes A, B, C and D with edges between A and B and between C and D (and only those edges), every node is connected to another node but the graph is disconnected. To force the solution to be connected, consider adding flow variables from every node to every other node, with RN as the lone source node and each sensor of any type having a demand of one unit if selected and zero if not selected. At any selected node other than RN and sensors, flow in = flow out. At selected sensors, flow out = flow in - 1. At nodes that are not selected, flow in = 0 = flow out.

Constraint 7 sounds more like a secondary objective than a constraint. You can either minimize a weighted combination of the number of nodes selected and the aggregate distance of the sensors from RN, or you can use a lexicographically ordered vector of two objectives (supported by current versions of CPLEX), where the primary objective is to minimize the number of nodes and the secondary objective is to minimize the aggregate distance from RN for the sensors (without increasing the number of selected nodes beyond the minimum). To get a measure of the aggregate distance, and assuming you use the flow idea above, you can make the secondary objective the total cost of the flows in the network, where each edge has a cost of one per unit of flow over the edge.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Thu August 31, 2023 03:07 AM
From: BABAR SHAHZAAD
Subject: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN₁, EN₂, ... EN_n}. Each node in EN has a set of temperature sensors connected to it. Some of the nodes in EN have visual sensors attached to them. There is one same wind sensor attached to two nodes EN_k and EN_l. This means only these two nodes can communicate with the wind sensor. Each sensor may have a connection to more than one node. A few nodes from EN have a direct connection with data centre C. Some nodes can directly communicate with other nodes in their communication ranges. I have a specific node named RN from the set of nodes EN.

I am writing an OPL code in CPLEX where the objective is to select a minimal number of nodes meeting the following:

1. The node RN is selected.
2. The sum of temperature sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 3.
3. The sum of visual sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 2.
4. The sum of wind sensors attached to the selected nodes (i.e., the total number of selected nodes rather than each selected node) should be greater than or equal to 1.
5. One of the selected nodes must have a direct connection to the data centre C.
6. All the selected nodes must have a connection to at least one other selected node, i.e., it should be a connected graph type instead of disconnected.
7. All the sensors (temperature, visual, and wind) should be directly connected to the RN or in close proximity to the RN. It means that they are selected based on their distance from the RN node. However, in this case, the distance is measured by the connection rather than the actual distance. For example, three nodes RN, EN₁ and EN₂ can satisfy all the constraints. If node RN has a communication link with node EN₁ and node EN₁ has a communication link with node EN₂, then if the nodes RN and EN₁ can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN₁ rather than EN₂.

I have written the following code:

------------------------------
BABAR SHAHZAAD
------------------------------