The shortest Route problem

Problems with modeling
Post Reply
lixlz51
User
User
Posts: 11
Joined: 5 years ago
Location: University of Nottingham, UK

The shortest Route problem

Post by lixlz51 »

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!
Attachments
Capture.PNG
User avatar
dirkse
Moderator
Moderator
Posts: 214
Joined: 7 years ago
Location: Fairfax, VA

Re: The shortest Route problem

Post by dirkse »

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
Post Reply