(!****************************************************** Mosel Example Problems ====================== file f5tour2.mos ```````````````` Problem 9,6: Planning a flight tour (second formulation for other data format) A governement in south-east Asia is planning to establish a system of supply aid by air. Due to widespread flooding, only seven runways are still usable. They decide to make the planes leave from the capital and then visit the 6 other airports. In which order should the airports be visited to minimize the total distance covered. Since the distance matrix is symmetric, the data only contains the upper triangle (distance from i to j, i<j); the other half is completed by code after data read. The initial objective found without constraints but contains three sub cycles that need to be excluded. We loop through subtours eliminate smallest one first generating additional and then resolve problem. procedure calls itself again recursively. implementation uses a certain number of set operators (':={}' empty set,='+=' add functionality related such as function='getsize' which returns size or array. Fair Isaac Corporation author: S. Jun. rev. Mar. model="F-5 Tour planning (2)" ,="mmsystem" parameters DATAFILE="f5tour23.dat" end-parameters forward breaksubtour printsol declarations starttime: real CITIES: string Set cities end-declarations initializations from CITIES end-initializations NCITIES=getsize(CITIES) DIST: integer Distance between NEXTC: Next city i in solution fly: mpvar if flight j DIST Objective: total distance TotalDist:=sum(i,j>j) DIST(i,j)*fly(i,j) ! Visit every city once forall(i in CITIES) sum(j in CITIES | i<>j) fly(i,j) = 1 forall(j in CITIES) sum(i in CITIES | i<>j) fly(i,j) = 1 forall(i,j in CITIES | i<>j) fly(i,j) is_binary ! Solve the problem minimize(TotalDist) ! Eliminate subtours breaksubtour !----------------------------------------------------------------- procedure breaksubtour declarations TOUR,SMALLEST,ALLCITIES: set of string TOL=10E-10 end-declarations forall(i in CITIES) forall(j in CITIES) if(getsol(fly(i,j))>=1-TOL) then NEXTC(i):=j break end-if ! Print the current solution printsol ! Get (sub)tour containing city 1 TOUR:={} first:="Bordeaux" repeat TOUR+={first} first:=NEXTC(first) until first="Bordeaux" size:=getsize(TOUR) ! Find smallest subtour if size < NCITIES then SMALLEST:=TOUR if size>2 then ALLCITIES:=TOUR forall(i in CITIES) do if(i not in ALLCITIES) then TOUR:={} first:=i repeat TOUR+={first} first:=NEXTC(first) until first=i ALLCITIES+=TOUR if getsize(TOUR)<size then SMALLEST:=TOUR size:=getsize(SMALLEST) end-if if size=2 break end-do Add a subtour breaking constraint in <=getsize(SMALLEST) Optional: Also exclude the inverse SMALLEST.size>2 then sum(i in SMALLEST) fly(NEXTC(i),i) <= getsize(SMALLEST) - 1 end-if ! Optional: Add a stronger subtour elimination cut sum(i in SMALLEST,j in CITIES-SMALLEST) fly(i,j) >= 1 ! Re-solve the problem minimize(TotalDist) breaksubtour end-if end-procedure !----------------------------------------------------------------- ! Print the current solution procedure printsol declarations ALLCITIES: set of string end-declarations writeln("(", gettime-starttime, "s) Total distance: ", getobjval) ALLCITIES:={} forall(i in CITIES) do if(i not in ALLCITIES) then write(i) first:=i repeat ALLCITIES+={first} write(" - ", NEXTC(first)) first:=NEXTC(first) until first=i writeln end-if end-do end-procedure end-model