Originally posted by: sszwaczyk

Hi,

I am a novice user and I try to use CPLEX to describe the problem of routing in the network. Verbal description of the problem:

This example assumes that security policy requirements must be fulfilled in order for the transfer of information to be possible. The security policy applies only to links. The security policy applies only to confidentiality.

The value of confidentiality for the route is calculated as the minimum confidentiality value from all links included in the route - c_r. The resulting utility (U) is the product of potential utility (U_p) and confidentiality value for the route:

U = U_p * c_r

The problem is to choose the route for which the resulting utility is maximum.

 

Network Topology
Assumed network topology:
|--(0.7)--v2--(0.7)--v3--(0.7)--|
|                                                  |
v1-----------(0.3)----------------v4
|                                                 |
|-----(0.6)----v5-----(0.6)-------|
 

The confidentiality value for individual links is given in brackets.

 

Old traffic
It was assumed that there is no traffic in the network.

 

Demand
It is assumed that information have to be sent from v1 to v4. The security policy for this information requires confidentiality at least at level 0.5. Potential utility for this information is 100.

 

Result
All possible paths between v1 and v4 are:
1. r₁ = {v1 - v4}
2. r₂ = {v1 - v2 - v3 - v4}
3. r₃ = {v1 - v5 - v4}

Due to the policy requirements, the route r₁ does not allow transfer of information.

Resulting utility for route r₂ is: 100 * 0.7 = 70.

Resulting utility for route r₃ is: 100 * 0.6 = 60.

Hence, it follows that the route r₂ should be chosen.

 

I tried to implement problem in CPLEX:

/*********************************************
 * OPL 12.8.0.0 Model
 * Author: sszwaczyk
 * Creation Date: Mar 26, 2018 at 11:24:38 AM
 *********************************************/
 
{string} Nodes = ...;
 
tuple arc {
    string source;
    string destination;
}

tuple demand{
    string source;
    string destination;
}  

{arc} Neighbours with source in Nodes, destination in Nodes = ...;
{arc} Arcs = Neighbours;
float ArcsConfidentiality[a in Arcs] = ...;

demand Demand = ...;
float Volume = ...;
float PotentialUtility = ...;
float SecurityPolicy = ...;

{arc} OkArcs = {a | a in Arcs: ArcsConfidentiality[a] >= SecurityPolicy};

execute {
    writeln("Links that fulfill security policy: ");
    for(var a in OkArcs) {
        writeln(a);    
    }
}

{string} NbsO[i in Nodes] = {j | <i,j> in OkArcs};
{string} NbsI[i in Nodes] = {j | <j,i> in OkArcs};

dvar float+ flow[OkArcs];

dexpr float utility = PotentialUtility * min(a in OkArcs : flow[a] > 0) ArcsConfidentiality[a];
maximize utility;

subject to {

    forall(n in Nodes) {
        if(n != Demand.source)
            if(n !=Demand.destination)
                constr_intermediary:
                    sum(nodes_out in NbsO[n]) flow[<n,nodes_out>] - sum(nodes_in in NbsI[n]) flow[<nodes_in,n>] == 0;
         if(n == Demand.source)
                 constr_source:
                     sum(nodes_out in NbsO[n]) flow[<n,nodes_out>] - sum(nodes_in in NbsI[n]) flow[<nodes_in,n>] == Volume;
         if(n == Demand.destination)    
                 constr_destination:    
                    sum(nodes_out in NbsO[n]) flow[<n,nodes_out>] - sum(nodes_in in NbsI[n]) flow[<nodes_in,n>] == -Volume;
    }        
     
}

execute {
    write("Demand ",Demand," is realizing on links: ");
    for(var a in OkArcs)
        if(flow[a] > 0)
            write(a,", ");
    writeln("");
} 

 

The problem is in utility expression where flow[a] > 0 cannot be used. I tried to use flow[a] > 0 to get only used links in route and get min confidentiality value from them. Please help me figure out how to find links in route in different way.

I attach mod and dat files.

Regards,

Sebastian Szwaczyk

 

 

#CPLEXOptimizers
#DecisionOptimization

Hi

if you write

dexpr float utility = PotentialUtility * min(a in OkArcs ) ( flow[a]>=0)*ArcsConfidentiality[a];

the model will work better

regards

https://www.ibm.com/developerworks/community/forums/html/topic?id=1bf1f4de-b6fa-4375-a397-741e9239513e&ps=25

#CPLEXOptimizers
#DecisionOptimization