Originally posted by: zhd87

I am trying to adopt the Network Flow model in my project.
The problem is, while searching the paths with minimum hops,
I want to find out two different paths from origin to destination of each pair of request.

for instance, in the image below, request pair (1,2) should possesses two paths, one for working and one for backup path.

And I want to search the two paths with minimum hops with Cplex.

I know Cplex can find the minimum hops routing path for me of each pair of request.
But I want to establish two different paths for each pair of request.
So what should I do so that Cplex can find two paths for me? 

Thank you very much!

#CPLEXOptimizers
#DecisionOptimization

 

'"Different" meaning not identical, or meaning disjoint?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: zhd87

Thank you very much for your reply, Paul!

I want to say that, one arc can only be used for working or backup path.

As shown in the figure, for pair(1,2), one path 1-2, another path 1-3-5-2 should be established.

and the path 1-2 is different with 1-3-5-2 in any arc.

So the working and backup path can possess same nodes but not arcs.

 

I find that in some papers, the authors use the equation that in each arc, 

while adding working and backup path together, the value should be less than 1 to stand for it.

But I don't know how to accomplish it with OPL.

Thank you!

 

#CPLEXOptimizers
#DecisionOptimization

First, you have to choose between solving one model with a combined objective function (minimize (length of primary path) + (small constant)*(length of secondary path)) or solving two models, the first to minimize the length of the primary path, the second to minimize the length of the secondary path. The two model approach guarantees that the primary path is as short as possible but runs a slight risk that you end up with an unnecessarily long secondary path (because there was a tie for shortest primary path between solution A and solution B, and the solver chose A even though B allows a shorter secondary path). The single model approach avoids that problem but runs a slight risk that you get an unnecessarily long primary path (because using the suboptimal primary path greatly shortens the secondary path).

Second, I'm pretty sure you will need to use binary variables to select the arcs in each path. It's possible you might have been able to use continuous variables in the interval [0, 1] for the arc selection decisions in the absence of the secondary path consideration.

Third, you need a binary variable for every combination of an arc and a path (primary or secondary). If x[i,j] is 1 if arc j is used in path i (i = 1 or 2), 0 otherwise, then you add a constraint that x[1,j] + x[2,j] <= 1 to ensure that arc j is used at most once.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: zhd87

Hi, Paul!

Thank you very much for your kindly reply!

Yes, I agree with you on the second point after one day's re-thinking.

Would you mind to give an example with OPL on the third point you mentioned?

I want to adopt this, but sorry that as a beginner, I don't know how to do it with OPL languages in Cplex...

I mean, how to define the binary variable with OPL language and use it to accomplish the constraint that x[1,j] + x[2,j] <= 1 in Cplex.

I've defined my traffic demand matrix and arc information with{fromnode, tonode, supply} value as follows:

//define the arcs

 

 

dvar float+ F[a in Arcs] in 1..a.NumWave;

dexpr float TotalFlow = sum (a in Arcs) F[a]; 

 

 

but I don't know how to combine them together with binary variable...

 

Second, in my model, the same arc cannot be included in working and backup path of one request,

but it can be used by different request.

That is, for instance, arc 1 can not be included, at the same time, in working and backup path of request 1(or request 2),

but it can be included in working(or backup) path of request 1 and working(or backup) path of request 2.

 

Thank you!

 

 

 

#CPLEXOptimizers
#DecisionOptimization

I'm not an OPL user, so I can't help with that. For the second part, you'll need an additional subscript, so that a binary variable exists for each combination of an arc, a request, and primary/secondary path.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: fbahr

>> Third, you need a binary variable for every combination of an arc and a path (primary or secondary).
>> If x[i,j] is 1 if arc j is used in path i (i = 1 or 2), 0 otherwise, then you add a constraint that
>> x[1,j] + x[2,j] <= 1 to ensure that arc j is used at most once.

> Would you mind to give an example with OPL on the third point you mentioned?

range Paths = 1 .. 2;
dvar int x[Paths][Arcs] in 0 .. 1;

subject to {
  forall(a in Arcs) {
    sum(p in Paths) x[p,a] <= 1;
  }
}

--fbahr

#CPLEXOptimizers
#DecisionOptimization