optimizationgraphmodelinglinear-programmingampl

How to define a set of paths, or set of sequences of links, in AMPL?


I'm trying to define a structure to capture something like below:

set NODES := A B C;
set LINKS := (A,B) (B,C);
set PATHS := ((A,B)) 
             ((A,B), (B,C))
             ((B,C));

Nodes are a set. Links are a set of node pairs.

I am having trouble defining Paths as a set of sequences of links. I have not seen any solutions in the AMPL graph examples that make explicit use of paths, and I am wondering if there is a simple way to construct them?

Here are the definitions in my .mod file:

set NODES; 
set LINKS within (NODES cross NODES);
set PATHS # ??? ;

Please help.


Solution

  • Given that your paths do not have repeated nodes, the most natural way I can think of to define paths would be as a collection of ordered sets of nodes.

    reset;
    model;
    set NODES;
    set LINKS within {NODES,NODES};
    
    param n_paths;
    set PATHS{1..n_paths} within NODES ordered;
    
    # Optional: identify all of the links implied by these paths, so we can
    # check that they are in fact within LINKS. 
    
    param longest_path_length := max{i in 1..n_paths} card(PATHS[i]);
    set LINKS_IMPLIED_BY_PATHS within LINKS := setof{
          i in 1..n_paths, 
          j in 1..(longest_path_length-1): j < card(PATHS[i])
        } (member(j,PATHS[i]),member(j+1,PATHS[i]))
        ;
    
    data;
    set NODES := A B C;
    set LINKS := (A,B) (B,C);
    
    param n_paths := 3;
    set PATHS[1] := A B;
    set PATHS[2] := A B C;
    set PATHS[3] := B C;
    
    display LINKS_IMPLIED_BY_PATHS;
    # if we include a path like C A, we will get an error here because ("C","A") 
    # is not within LINKS.
    # It should be possible to do this more tidily with a check statement but
    # for the moment the syntax escapes me.
    # Note that this error will ONLY appear at the point where we try to
    # do something with LINKS_IMPLIED_BY_PATHS; it's not calculated or checked
    # until then. 
    

    This isn't quite what you asked for, since it defines paths as a sequence of nodes rather than links, but it's the closest I could get.