GAMS World Forum

Hi everyone,
As I am new to GAMS and really want to get my head around it for modelling, I tried to compile the examples in the GAMS Studio library myself. I could not really understand the x(i,ip,ipp) in the example given, as I thought the decision variable should be a binary to see whether a certain arc is taken. I have compiled the problem with the binary variable instead but had some problems with the constraints for the product flow balance in each node.

Can anyone tell me if to model with a binary variable, how to rectify this? Otherwise, what does the x(i,ip,ipp) mean exactly in the given example? Thank you very much indeed!

Hi,

You might think that since the edge weights of a pair-wise shortest-path solution should be 0 or 1 (i.e. the edge is-not or is part of the shortest path) that the variables should be binary, but the LP constraint matrix has some nice properties (I recall learning about totally unimodular matrices years ago) that allow us to conclude the optimal basic solutions will be integral. Or, just ask yourself how or why the LP solution could ever have fractional values (assuming an absence of ties) if that suits you better.

Wikipedia has a description of how to formulate the shortest path model for a given pair as an LP that covers this in more detail:

https://en.wikipedia.org/wiki/Shortest_ ... test_paths

To go from there to the sroute model in GAMSLIB, imagine solving (n-1) LPs: the pairwise shortest path LP from node 1 to node i, for i = 2 .. n. Now include the constraints for all these models into one big LP, whose objective is the sum of the individual objectives. This gives the shortest path from node 1 to all other nodes: call this LP-1.

Now, formulate LP-i for all i, not just i=1, and add an index to the x variable to indicate the start-vertex. Again combine these constraints and sum the objectives and you get the sroute LP. I don't have the Dantzig reference from the GAMSLIB model handy, but I'd guess that it offers some proof that this really works. Or perhaps it states the result and leaves the proof to the reader . . .

HTH,

-Steve