Shortest Path

    {  Exmpl15.2-2_ShortestPath.mpl  }

    {  AMPL A Modeling Language for Mathematical Programming, 2nd Edition }

    {  Chapter 15.2,  Shortest Path,  Size: 7x10,  Page 330 }


TITLE
    ShortestPath;

INDEX
    inter  := (a,b,c,d,e,f,g);
    inter2 := inter;
    entr[inter] := (a);
    exit[inter] := (g);
    road[inter,inter2] := (a.b,a.c,b.d,b.e,c.d,c.f,d.e,d.f,e.g,f.g);

DATA
    Time[inter,inter2] := [a,b, 50,
                           a,c,100,
                           b,d, 40,
                           b,e, 20,
                           c,d, 60,
                           c,f, 20,
                           d,e, 50,
                           d,f, 60,
                           e,g, 70,
                           f,g, 70];

VARIABLE
    RUse[inter,inter2 IN road];

MODEL

    MIN TotalTime = SUM(inter,inter2 IN road: Time * RUse);

SUBJECT TO

    Start: SUM(inter IN entr,inter2: RUse) = 1;

    Balance[inter<>first(exit)] WHERE (inter <> first(entr)) -> BAL:
         SUM(inter2: RUse) = SUM(inter2: RUse[inter:=inter2,inter2:=inter]);

    EndBalance: SUM(inter,inter2 IN exit: RUse) = 1;



END