(!****************************************************** Mosel Example Problems ====================== file f5tour.mos ``````````````` Planning a flight tour (c) 2008 Fair Isaac Corporation author: S. Heipcke, Mar. 2002, rev. Mar. 2014 *******************************************************!) model "F-5 Tour planning" uses "mmxprs" forward procedure break_subtour forward procedure print_sol declarations NCITIES = 7 CITIES = 1..NCITIES ! Cities DIST: array(CITIES,CITIES) of integer ! Distance between cities NEXTC: array(CITIES) of integer ! Next city after i in the solution fly: array(CITIES,CITIES) of mpvar ! 1 if flight from i to j end-declarations initializations from 'f5tour.dat' DIST end-initializations forall(i,j in CITIES | i<j) DIST(j,i):=DIST(i,j) Objective: total distance TotalDist:=sum(i,j in CITIES>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 integer end-declarations forall(i in CITIES) NEXTC(i):= integer(round(getsol(sum(j in CITIES) j*fly(i,j) ))) ! Print the current solution print_sol ! Get (sub)tour containing city 1 TOUR:={} first:=1 repeat TOUR+={first} first:=NEXTC(first) until first=1 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 integer end-declarations writeln("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