Re: [Help-glpk] Solving shortest path problem and getting wrong answer
22.04.2010 22:31, Andrew Makhorin kirjutas: > Glpsol solves your instance correctly, so you need to check your mps > file. > > Writing models in mps format by hand is cumbersome. You may look at > the example model spp.mod, which solves the shortest path problem and > is written in MathProg modeling language (see subdirectory 'examples'). > Oh, I didn't generate it by hand, but programmatically. The idea of this task is to use equations to solve it, so I'm afraid that solving it with MathProg model isn't the way to go. Thanks for answering anyhow, I'll keep looking as to why these equations return answer with numbers less than minimal path for some nodes. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Solving shortest path problem and getting wrong answer
Hi, I'm trying to solve shortest path problem using glpsol and mps format. I have it working correct with one example but I'm getting wrong results with another one and I can't understand if there's something wrong with my input or if it's glpsol that gives wrong output. My directed graph is the following, first number being edge tail id, the second one head id and last one respective weight. 3 5 19 5 1 26 1 4 28 4 9 11 9 7 29 7 8 21 8 6 18 6 2 30 2 1 23 10 3 27 9 5 20 1 7 26 6 4 21 9 8 11 9 8 29 9 3 13 10 1 19 2 4 29 5 2 18 2 5 28 8 7 14 5 7 29 2 6 20 8 4 18 8 2 14 1 7 17 2 4 19 4 5 29 10 6 26 10 7 17 Based on that I generate the following mps file to find shortest path from 5 to 3: NAME shortest-path ROWS N PATH L EQ14 L EQ17 L EQ21 L EQ24 L EQ25 L EQ26 L EQ35 L EQ45 L EQ49 L EQ51 L EQ52 L EQ57 L EQ62 L EQ64 L EQ78 L EQ82 L EQ84 L EQ86 L EQ87 L EQ93 L EQ95 L EQ97 L EQ98 L EQ101 L EQ103 L EQ106 L EQ107 E START COLUMNS X1 EQ14 -1 X1 EQ17 -1 X1 EQ21 1 X1 EQ51 1 X1 EQ101 1 X2 EQ21 -1 X2 EQ24 -1 X2 EQ25 -1 X2 EQ26 -1 X2 EQ52 1 X2 EQ62 1 X2 EQ82 1 X3 EQ35 -1 X3 EQ93 1 X3 EQ103 1 X3 PATH -1 X4 EQ45 -1 X4 EQ49 -1 X4 EQ14 1 X4 EQ24 1 X4 EQ64 1 X4 EQ84 1 X5 EQ51 -1 X5 EQ52 -1 X5 EQ57 -1 X5 EQ25 1 X5 EQ35 1 X5 EQ45 1 X5 EQ95 1 X5 START 1 X6 EQ62 -1 X6 EQ64 -1 X6 EQ26 1 X6 EQ86 1 X6 EQ106 1 X7 EQ78 -1 X7 EQ17 1 X7 EQ57 1 X7 EQ87 1 X7 EQ97 1 X7 EQ107 1 X8 EQ82 -1 X8 EQ84 -1 X8 EQ86 -1 X8 EQ87 -1 X8 EQ78 1 X8 EQ98 1 X9 EQ93 -1 X9 EQ95 -1 X9 EQ97 -1 X9 EQ98 -1 X9 EQ49 1 X10 EQ101 -1 X10 EQ103 -1 X10 EQ106 -1 X10 EQ107 -1 RHS RHS1 START 0 RHS1 EQ14 28 RHS1 EQ17 17 RHS1 EQ21 23 RHS1 EQ24 19 RHS1 EQ25 28 RHS1 EQ26 20 RHS1 EQ35 19 RHS1 EQ45 29 RHS1 EQ49 11 RHS1 EQ51 26 RHS1 EQ52 18 RHS1 EQ57 29 RHS1 EQ62 30 RHS1 EQ64 21 RHS1 EQ78 21 RHS1 EQ82 14 RHS1 EQ84 18 RHS1 EQ86 18 RHS1 EQ87 14 RHS1 EQ93 13 RHS1 EQ95 20 RHS1 EQ97 29 RHS1 EQ98 11 RHS1 EQ101 19 RHS1 EQ103 27 RHS1 EQ106 26 RHS1 EQ107 17 ENDATA Which gives me: X1 9 X2 18 X3 61 X4 37 X5 0 X6 16 X7 0 X8 19 X9 48 X10 34 I haven't verified all of these but X1 being 9 cannot be correct looking at graph data. There's no way to get from 5 to 1 with total weight of 9. I can't see anything wrong with my input though. All help and pointers appreciated. Merike ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk