shortest path example with intervening lake 10/03/01 11:09:39 PAGE 1 GAMS Rev 121 Linux/Intel 2 3 option limcol=0; 4 5 set 6 nodes /node1*node8/ 7 coords /x,y/ 8 arcs(nodes,nodes) / 9 node1 . (node2,node3) 10 node2 . node4 11 node3 . node6 12 node4 . node7 13 node6 . node5 14 node7 . node6 15 (node5, node6, node7) . node8/ 16 lakeCrossings(nodes,nodes) / 17 node4 . node7 18 node6 . node8 19 node7 . node6 /; 20 21 alias (i,j,nodes); 22 23 table posn(nodes,coords) 24 x y 25 node1 0 1 26 node2 0 0 27 node3 1 2 28 node4 1 0 29 node5 2 2 30 node6 2 1 31 node7 2 0 32 node8 3 1; 33 34 parameter supply(nodes) / node1 1, node8 -1/; 35 36 * figure the distances 37 parameter distance(nodes, nodes); 38 distance(arcs(i,j)) = sqrt(sum(coords,sqr(posn(i,coords) - posn(j,coords)))); 39 40 * double the distance if the route goes over a lake 41 distance(lakeCrossings) = 2*distance(lakeCrossings); 42 43 display distance; 44 45 variables flow(nodes,nodes), totalDistance; 46 positive variables flow; 47 equations balance(nodes), objective; 48 49 balance(nodes).. 50 sum(arcs(nodes,j), flow(nodes,j)) - sum(arcs(i,nodes), flow(i,nodes)) 51 =e= supply(nodes); 52 53 objective.. 54 totalDistance =e= sum(arcs, flow(arcs) * distance(arcs)); 55 56 model short1/balance, objective/; 57 58 solve short1 minimizing totalDistance using lp; 59 60 option flow:5:0:2; 61 display flow.l, totalDistance.l; 62 63 64 65 66 COMPILATION TIME = 0.000 SECONDS 0.7 Mb LNX200-121 shortest path example with intervening lake 10/03/01 11:09:39 PAGE 2 E x e c u t i o n GAMS Rev 121 Linux/Intel ---- 43 PARAMETER distance node2 node3 node4 node5 node6 node7 node8 node1 1.000 1.414 node2 1.000 node3 1.414 node4 2.000 node5 1.414 node6 1.000 2.000 node7 2.000 1.414 shortest path example with intervening lake 10/03/01 11:09:39 PAGE 3 Equation Listing SOLVE short1 USING LP FROM LINE 58 GAMS Rev 121 Linux/Intel ---- balance =E= balance(node1).. flow(node1,node2) + flow(node1,node3) =E= 1 ; (LHS = 0, INFES = 1 ***) balance(node2).. - flow(node1,node2) + flow(node2,node4) =E= 0 ; (LHS = 0) balance(node3).. - flow(node1,node3) + flow(node3,node6) =E= 0 ; (LHS = 0) REMAINING 5 ENTRIES SKIPPED ---- objective =E= objective.. - flow(node1,node2) - 1.4142*flow(node1,node3) - flow(node2,node4) - 1.4142*flow(node3,node6) - 2*flow(node4,node7) - 1.4142*flow(node5,node8) - flow(node6,node5) - 2*flow(node6,node8) - 2*flow(node7,node6) - 1.4142*flow(node7,node8) + totalDistance =E= 0 ; (LHS = 0) shortest path example with intervening lake 10/03/01 11:09:39 PAGE 4 Model Statistics SOLVE short1 USING LP FROM LINE 58 GAMS Rev 121 Linux/Intel MODEL STATISTICS BLOCKS OF EQUATIONS 2 SINGLE EQUATIONS 9 BLOCKS OF VARIABLES 2 SINGLE VARIABLES 11 NON ZERO ELEMENTS 31 GENERATION TIME = 0.000 SECONDS 1.3 Mb LNX200-121 EXECUTION TIME = 0.000 SECONDS 1.3 Mb LNX200-121 shortest path example with intervening lake 10/03/01 11:09:39 PAGE 5 GAMS Rev 121 Linux/Intel S O L V E S U M M A R Y MODEL short1 OBJECTIVE totalDistance TYPE LP DIRECTION MINIMIZE SOLVER CPLEX FROM LINE 58 **** SOLVER STATUS 1 NORMAL COMPLETION **** MODEL STATUS 1 OPTIMAL **** OBJECTIVE VALUE 4.8284 RESOURCE USAGE, LIMIT 0.010 1000.000 ITERATION COUNT, LIMIT 2 10000 GAMS/Cplex Mar 21, 2001 LNX.CP.CL 20.0 019.019.039.LNX For Cplex 7.0 Cplex 7.0.0, GAMS Link 19 Optimal solution found. Objective : 4.828427 ---- EQU balance LOWER LEVEL UPPER MARGINAL node1 1.0000 1.0000 1.0000 4.0000 node2 . . . 3.0000 node3 . . . 2.5858 node4 . . . 2.0000 node5 . . . 0.5858 node6 . . . 1.1716 node7 . . . . node8 -1.0000 -1.0000 -1.0000 -0.8284 LOWER LEVEL UPPER MARGINAL ---- EQU objective . . . 1.0000 ---- VAR flow LOWER LEVEL UPPER MARGINAL node1.node2 . . +INF . node1.node3 . 1.0000 +INF . node2.node4 . . +INF . node3.node6 . 1.0000 +INF . node4.node7 . . +INF . node5.node8 . . +INF . node6.node5 . . +INF 0.4142 node6.node8 . 1.0000 +INF . node7.node6 . . +INF 3.1716 node7.node8 . . +INF 0.5858 LOWER LEVEL UPPER MARGINAL ---- VAR totalDist~ -INF 4.8284 +INF . **** REPORT SUMMARY : 0 NONOPT 0 INFEASIBLE 0 UNBOUNDED shortest path example with intervening lake 10/03/01 11:09:39 PAGE 6 E x e c u t i o n GAMS Rev 121 Linux/Intel ---- 61 VARIABLE flow.L node1.node3 1.00000, node3.node6 1.00000 node6.node8 1.00000 ---- 61 VARIABLE totalDistance.L = 4.828 EXECUTION TIME = 0.000 SECONDS 1.3 Mb LNX200-121 USER: Computer Sciences Dept. G010628:1627AS-LNX University of Wisconsin-Madison DC2621 **** FILE SUMMARY INPUT /afs/cs.wisc.edu/u/s/w/swright/public/html/635/examples/short1.gms OUTPUT /afs/cs.wisc.edu/u/s/w/swright/public/html/635/examples/short1.lst