Decision Optimization

 View Only
  • 1.  How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    Posted Thu August 31, 2023 03:55 AM

    I am working on a problem where I have only one data centre node C. A set of nodes, EN={EN1, EN2, ... ENn}. 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 ENk and ENl. 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, EN1 and EN2 can satisfy all the constraints. If node RN has a communication link with node EN1 and node EN1 has a communication link with node EN2, then if the nodes RN and EN1 can fulfil the required number of sensors, then those sensors should be selected which are connected to RN and EN1 rather than EN2.

    I have written the following code:

    // Sets
    int nEN = ...;
    range EN = 1..nEN;
    int nTS = ...;
    range TS = 1..nTS;
    int nVS = ...;
    range VS = 1..nVS;
    int nWS = ...;
    range WS = 1..nWS;
    int RN = ...;
    int TempSensors[EN][TS] = ...;
    int VisualSensors[EN][VS] = ...;
    int WindSensors[EN][WS] = ...;
    int CloudConnection[EN] = ...;
    // Binary decision variables
    dvar boolean x[EN];
    dvar boolean y[en in EN][ts in TS];
    dvar boolean z[en in EN][vs in VS];
    dvar boolean w[en in EN][ws in WS];
    dvar boolean c[cc in EN];
    // Communication relationships
    int Communication[EN][EN] = ...;
    // Objective function
    minimize sum(i in EN) x[i];
    // Constraints
    subject to {
      x[RN] == 1;
      forall(en in EN, ts in TS:TempSensors[en][ts]==1)
        (sum(en in EN, ts in TS:TempSensors[en][ts]==1) y[en][ts] * x[en]) >= 3;
      sum(en in EN, vs in VS:VisualSensors[en][vs]==1) z[en][vs] * x[en] >= 2;
      sum(en in EN, ws in WS:WindSensors[en][ws]==1) w[en][ws] * x[en] >= 1;
      sum(en in EN:CloudConnection[en]==1) c[en] * x[en] >= 1;
      forall (en in EN)
        if (en != RN)
           (sum(en2 in EN : en2 != en) Communication[en][en2] * x[en2]) >= x[en];
    }
    It works fine for a set of 5 nodes if I remove the constraint 2. However, when I add constraint 2, it gives disconnected graphs. I am not sure where I am making a mistake. Furthermore, I am not sure how to enforce constraint 7. Any help or suggestion in this regard is appreciated.


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


  • 2.  RE: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    IBM Champion
    Posted Sat September 02, 2023 02:30 PM

    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).



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



  • 3.  RE: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    Posted Sun September 03, 2023 07:52 PM

    I have deleted this question from math.stackexchange.com. The reason I posted this here is to get some hint/help on my code whereas I have posted this question on or.stackexchange.com to get some hint/help on my mathematical formulation. I would appreciate if you could give some suggestion on it. Thank you.



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



  • 4.  RE: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    IBM Champion
    Posted Sat September 16, 2023 03:23 PM

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



  • 5.  RE: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    Posted Mon September 18, 2023 01:40 AM

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



  • 6.  RE: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    IBM Champion
    Posted Tue September 19, 2023 05:16 PM

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



  • 7.  RE: How to enforce constraint(s) to select sensors in the proximity of selected nodes?

    Posted Tue September 19, 2023 09:21 PM
    Edited by BABAR SHAHZAAD Tue September 19, 2023 09:32 PM

    For the sake of simplicity, I have tried it even without adding the sensor nodes. However, it still gives a disconnected graph. In my case, the number of nodes in the subgraph is not known in advance because I am simply interested in selecting a minimum number of nodes that includes the selection of at least one connection to "G", two connections to the triangle icons, and three connections to sun icons. Considering your suggestions, I have written the following constraints. However, it did not work.

    minimize sum(i in EN) x[i];

    subject to {
      
      sum(en in EN: en == RN) source[RN] == 1;
      
      forall(en in EN){
        source[en] <= x[en];
      }
      
      forall(en in EN, en2 in EN: Communication[en][en2] == 1){
        flow[en][en2] <= x[en];
      }
      
      forall(en in EN, en2 in EN: Communication[en][en2] == 1){
        flow[en][en2] <= x[en2];
      }
      
      forall(en in EN: en!=RN){
        (x[en] == 1) => (sum(en2 in EN) flow[en2][en] == sum(en2 in EN) flow[en][en2]);
      }
      
      forall(en in EN){
        (x[en] == 0) => (sum(en2 in EN) flow[en2][en] == 0);
      }
      
      
      forall(en in EN){
        (x[en] == 0) => (sum(en2 in EN) flow[en][en2] == 0);
      }
      
      sum(en in EN) CloudConnection[en] * x[en] == 1;

    }

    I have separate communication matrices for the nodes and sensors as follows:

    Communication = [[0, 1, 0, 0, 0], // EN_1 can communicate with EN_2
      [1, 0, 1, 1, 0], // EN_2 can communicate with EN_1, EN_3, EN_4
      [0, 1, 0, 0, 1], // EN_3 can communicate with EN_2 and EN_5
      [0, 1, 0, 0, 0], // EN_4 can communicate with EN_2
      [0, 0, 1, 0, 0] // EN_5 can communicate with EN_3
      ];

    TempSensors = [[1, 0, 1, 0, 0, 0, 0, 0], // EN_1 has temperature sensors 1 and 3
    [0, 0, 1, 1, 0, 0, 0, 0], // EN_2 has temperature sensors 3 and 4
      [0, 1, 0, 1, 1, 0, 0, 0], // EN_3 has temperature sensors 2, 5, and 4
      [0, 0, 1, 0, 0, 1, 0, 0], // EN_4 has temperature sensors 3 and 6
      [0, 0, 0, 0, 0, 0, 1, 1]]; // EN_5 has temperature sensors 7 and 8

    VisualSensors = [
      [1, 0], 
      [0, 0], 
      [0, 1],
      [0, 0],
      [0, 0]
    ];


    WindSensors= [
      [0], 
      [0], 
      [1],
      [0],
      [1]
    ];


    CloudConnection = [0, 1, 0, 1, 0];
    ------------------------------
    BABAR SHAHZAAD
    ------------------------------