MPL Model Library MPL Model Library



JoeState, Example 11, Winston

   {  Exmpl9.6-11_JoeState.mpl  }

   {  Winston, Operations Research, Applications and Algorithms, 4th ed.  }

   {  Chapter 9.3,  Example 11,  Travelling Salesman (MIP),  Size: 5x6,  Page 530  }


TITLE    
    JoeState;

INDEX
    city := (1..5);
    city2 := city;

DATA
    Distance[city,city2] := (  0,132,217,164, 58,
                             132,  0,290,201, 79,
                             217,290,  0,113,303,
                             164,201,113,  0,196,
                              58, 79,303,196,  0);    
    NumCity := count(city);

VARIABLE
    Pn[city];

BINARY VARIABLES
    Route[city,city2] WHERE (Distance);
   
MODEL

    MIN TotalDistance = SUM(city,city2: Route * Distance);
                
SUBJECT TO

    VisitOnceA[city] -> VOA: 
              SUM(city2: Route
                WHERE city2 <> city) = 1;
   
    VisitOnceA[city2] -> VOA: 
              SUM(city: Route
                WHERE city <> city2) = 1;

    PrevSubTour[city,city2<>1] WHERE (city <> city2) -> PST: 
              Pn[city] - Pn[city:=city2] + NumCity * Route <= NumCity - 1;

 
BOUNDS
    Tour[city]:  1 <= Pn <= NumCity;  
  
END






Return to MPL Model Library