the constraints in the photo ,I need to translate to the closed-form I don't know how can I do this.
Can you help?
I need to write the mod file and dat file in Cplex for this problem
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ incidentally, I prepared exactly this for my lecture on linear programming; do you "see" the network in these equations? if so, can you describe in words, what each individual constraint means? $\endgroup$ – Marco Lübbecke May 23 '20 at 13:43
-
$\begingroup$ Please look at Shortest Path Problem Wikipedia page, linear programming section explains it. $\endgroup$ – kur ag May 23 '20 at 13:46
-
1$\begingroup$ Welcome to OR.SE! Please take a look at this MathJax guide to learn how you can type the math rather than using an image and make the post more searchable. $\endgroup$ – EhsanK♦ May 23 '20 at 14:07
Add a comment
|
$\begingroup$
$\endgroup$
In OPL to get the shortest path you could use:
.mod
tuple edge
{
key int o;
key int d;
int weight;
}
{edge} edges=...;
{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>,
};
whicg gives
{<1 4 8> <4 7 7> <7 8 4>}
