(!****************************************************** Mosel Example Problems ====================== file f5tour2.mos ```````````````` Problem 9,6: Planning a flight tour (second formulation for other data format) (c) 2008 Fair Isaac Corporation author: S. Heipcke, Jun. 2002, rev. Mar. 2014 *******************************************************!) model "F-5 Tour planning (2)" uses "mmxprs", "mmsystem" parameters DATAFILE="f5tour23.dat" end-parameters forward procedure break_subtour forward procedure print_sol declarations starttime: real CITIES: set of string ! Set of cities end-declarations starttime:=gettime initializations from DATAFILE CITIES end-initializations finalize(CITIES) declarations NCITIES=getsize(CITIES) DIST: array(CITIES,CITIES) of integer ! Distance between cities NEXTC: array(CITIES) of string ! Next city after i in the solution fly: array(CITIES,CITIES) of mpvar ! 1 if flight from i to j end-declarations initializations from DATAFILE DIST end-initializations ! Objective: total distance TotalDist:= sum(i,j in CITIES | i<>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 break_subtour !----------------------------------------------------------------- procedure break_subtour 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 print_sol ! 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) break_subtour end-if end-procedure !----------------------------------------------------------------- ! Print the current solution procedure print_sol 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