Originally posted by: Mathsg

Hi, 

I am interested in finding k shortest path from source node to destination node by dijkstra's algorithm. i have done it with the dvar boolean to declear a boolean variables for the link which can take value 1 if the link is selected for path and o otherwise but the problem is this variable calculate the shortest path for each flow which is much time consuming. Now i am interested to get rid of flow conservation constraint and use some type of algorithm in column generation approaches which can resolve the problem at once not to calculate the path for each variable. does anyone has knowledge about it? or does anyone has Dijkstra's algorithm code in OPL cplex for finding k shortest path. Your help and sincier suggestions will be highly appricated. I am looking forward to hearing form IBM team, and my respected seniors. thank you

Hi,

in OPL to get the shortest path you could use:

.mod

{int} nodes={i.o | i in edges} union {i.d | i in edges};
int st=1; // start
int en=8; // end

dvar int obj; // distance
dvar boolean x[edges]; // do we use that edge ?

minimize obj;

subject to
{
obj==sum(e in edges) x[e]*e.weight;

forall(i in nodes)
    sum(e in edges:e.o==i) x[e]
    -sum(e in edges:e.d==i) x[e]    
    ==
    ((i==st)?1:((i==en)?(-1):0));
}

{edge} shortestPath={e | e in edges : x[e]==1};

execute
{
writeln(shortestPath);
}

.dat

edges=
{
<1,2,9>,
<1,3,9>,
<1,4,8>,
<1,10,18>,
<2,3,3>,
<2,6,6>,
<3,4,9>,
<3,5,2>,
<3,6,2>,
<4,5,8>,
<4,7,7>,
<4,9,9>,
<4,10,10>,
<5,6,2>,
<5,7,9>,
<6,7,9>,
<7,8,4>,
<7,9,5>,
<8,9,1>,
<8,10,4>,
<9,10,3>,
};

But you could also implement Dijsktra in the scripting part of OPL or even call an external program in any language that will compute the shortest path you need (IloOplExec, IloOplJavaCall)

regards

Originally posted by: Mathsg

Hi, aleax, 

thank you for you prompt response. As for i understand, this code is similar to what i have wrote in my ILP formulation that each time a decesion variable calculate weather a link/edge can us for path between pair of node which leads a model too much time consuming. I am interested to put all these links as a input parameter in data file as i already know the k shortest path from source to distination. Is there anyway to formulate my model like this? I am looking forward to hearing from you. thank you

Hi,

once you have a set of shortest paths in a .dat like

shortestPath={<1 4 8> <4 7 7> <7 8 4>};

You may use that in a .mod like

tuple edge
{
   key int o;
   key int d;
   int weight;
}

{edge} shortestPath=...;

regards

Originally posted by: Mathsg

Hi Alex,

So nice of you and thank you so much for you kind guidance. The above code is for one request i means it has one o with int type and one d with int type two. How to modify the above code for multiple number of request i means flow having multiple number of flows with multiple number of source, destiniation as i have multiple number of flow. Kindly have a look my ILP Code may be you can get an idea that i want to do. Here in the code the tuple flow declear for multiple number of source and destination and in this case i have consider 2 flows which can be seen in .data file

e.g., .Mod file

tuple eccard{                     /*Tuple for EC*/
  key int id;                    /*S.N of EC starting from 0 to....*/
  int k_ec;                        /*different capacties of EC*/
  int costtype_ec;                 /*different cost of EC*/
}  
{eccard} ECcards = ...;         /*Taking tupple data of EC from data file*/

int nmbr_routes = ...;             /*Totall number of routes*/
range routes = 1..nmbr_routes;    /*range of routes*/
int nmberflow = ...;            /*Totall number of flows*/
int im_flow = ...;                /*important flows*/
tuple flow{                     /*Tuple for flows*/
key int id;                        /*S.N of flows starting from 0 to....*/
int src;                        /*Source node of flows*/
int dest;                        /*destination node of flows*/
float flow_bw;                    /*BW of flows*/
int khan;                        /*this int take two values, either 1, if flow is important or 0 if flow is non-important*/
}
{flow} flows = ...;                /*Taking tupple data of flows from data file*/
int hope_count[routes][nodes][nodes] = ...;            /*hope count between source and destination*/
int a[Lincards] = ...;                                 /*Set upper limit of LC in data file*/

.data file

ECcards = { <0, 40, 2>,
 <1,100 , 4>,
 <2, 400, 8> };

nmbr_routes = 1;

nmberflow = 2;
im_flow =1;
flows = { <0, 1, 6, 25, 0>,
 <1, 2, 1, 10, 1>};

I am interested to modify your above mention code for multiple number of requests. Kindly guide me in this regards, I am looking forward to hearing from you. thank you so much

Hi,

instead of a set like

{edge} shortestPath=...;

you could use an array of set:

{edge} shortestPath[origins][destinations]=...;

regards

Originally posted by: Mathsg

Hi Alex,

Thank you so much for your sincere help. If I declare it in. mode file as you mentioned above, then how I write the data file for it?

Hi

as far as syntax is concerned

.mod

tuple edge
{
   key int o;
   key int d;
   
}

{int} origins={1,2};
{int} destinations={3,4};

{edge} shortestPath[origins][destinations]=...;

.dat

 shortestPath=[[{<1,2>,<2,3>},{<1,2>}][{<1,2>},{<1,2>}]];

regards

Originally posted by: Mathsg

Hi Alex,

thank you for your guidance. i am a bit confused about the data part of the above  shortestPath=[[{<1,2>,<2,3>},{<1,2>}][{<1,2>},{<1,2>}]]; is it correct?

why i think it may be like  shortestPath=[[{<1,2>,<2,3>}][{<2,3>},{<3,4>}]]; as in the [] we have flow from node 1 to 3 and in the second [] we have flow from 2 to 4. am i right or if i do not quite understand then please explain me this  shortestPath=[[{<1,2>,<2,3>},{<1,2>}][{<1,2>},{<1,2>}]];

thank you

Hi

I have only just installed IBM CPLEX ILOG OPL. I cannot make out which language to code in. Does it have its own language? Which means do I need to learn an OPL syntax? 

Now, what I plan to do is I have a network flow:-

Now how do I go ahead and create this in the software to find the shortest path using Dijkstra's algorithm? 

CPLEX Studio comes with two solvers, CPLEX (for linear/integer/quadratic programs) and CP Optimizer (for constraint programming). Both have APIs to several common programming languages, including C/C++, Java and Python. In addition, you have an IDE for building and solving models using the OPL modeling language. So can choose which language you want to use.

That said, neither CPLEX nor CP Optimizer implements Dijkstra's algorithm. Dijkstra is an iterative algorithm that does not involve any LP/IP/QP/CP problems or subproblems. If you want to use Dijkstra, you should code it yourself in your favorite programming language.

Just typed the code, it has 4 errors, what's wrong?:-

Hi,

obj should be declared before as dvar int obj;

See a very basic OPL model at https://github.com/AlexFleischerParis/zooopl/blob/master/zoo.mod

int nbKids=300;
float costBus40=500;
float costBus30=400;
 
dvar int+ nbBus40;
dvar int+ nbBus30;
 
minimize
 costBus40*nbBus40  +nbBus30*costBus30;
 
subject to
{
 40*nbBus40+nbBus30*30>=nbKids;
} 

Hii code acha html 

int nbKids=300;float costBus40=500;float costBus30=400; dvar int+ nbBus40;dvar int+ nbBus30; minimize costBus40*nbBus40  +nbBus30*costBus30; subject to{ 40*nbBus40+nbBus30*30>=nbKids;}