How to combine the largest subtours together

Sorry the .dat file and the .mos file can be found on my profile

I have not been able to find your files - have you tried to attach them to your message via the 'attachment' icon (this icon should appear under the text editor box, not among the icons of the editor itself)?

The example implementation at https://examples.xpress.fico.com/example.pl?id=tsp has an algorithm to determine the smallest among the current subtours that could be adapted to finding the largest subtour by-and-large by inverting the sense of the tests. It also shows various subtour eliminination constraints - in this example they are added iteratively to the problem, resolving it completely. This example shows how to add subtour elimination constraints during the MIP branch-and-bound search: https://examples.xpress.fico.com/example.pl?id=f5tour_h_1

Thank you very much for your answer! I attached my files now.

I found the examples that you are pointing out to me and used these. But I don't know how to adapt the smallest to the largest. So what I basically would like the program to do is to go from the subsets:

0-18-0

20-22-20

1-4-3-9-1

to combine the 2 largest subsets and optimize this to

0-18-9-1-4-3-0

20-22-20

and lastly to find the last optimum

0-18-22-20-9-1-4-3-0

Hope you can help me out on this.

Thank you very much in advance!

Heleen Brans

And my .dat file

Here is a somewhat modified version of the subtour elimination subroutine that works with the largest subtour for defining the constraints:

procedure remove_subtours
  !declarations of the procedure
  declarations
   ROUTE,LARGEST,ALLRETAIL: set of integer
  end-declarations
 
!Determining the next retail shop visited in current solution
  forall(i in RETAIL) 
   NEXTRETAIL(i):= integer(round(getsol(sum(j in RETAIL) j*ROAD(i,j) )))
 
! Print the solution of each tour with the other procedure
  print_allsubsolution
  
  
! Subtour which contains the starting point 0  
  ROUTE:={}
  start:=0
  repeat
   ROUTE+={start}
   start:= NEXTRETAIL(start)
  until start=0
  size:=getsize(ROUTE)
 
! Find the biggest subtour
  if size < NRETAIL then
    LARGEST:=ROUTE
    ALLRETAIL:=ROUTE
    forall(i in RETAIL) do
     if(i not in ALLRETAIL) then
      ROUTE:={}
      start:=i
      repeat
       ROUTE+={start}
       start:=NEXTRETAIL(start)
      until start=i
      ALLRETAIL+=ROUTE
      if getsize(ROUTE)>size then
       LARGEST:=ROUTE
       size:=getsize(LARGEST)
      end-if
     end-if 
    end-do        
   writeln("Selected tour:", LARGEST) 
 
! constraint to exclude the subtour defined by LARGEST
sum(i in LARGEST) ROAD(i,NEXTRETAIL(i)) <= getsize(LARGEST) - 1
 
! force connection from subtour node set to a node not contained in subtour
sum(i in LARGEST,j in RETAIL-LARGEST) ROAD(i,j) >=1
 
! solve the objective function again
   minimize(TOTALDIST)
 
   remove_subtours
  end-if 
 end-procedure

Thank you very much! This is really helpful!

Then I just have 1 more question because now it gives me the following output (see below). And if i understand the code correctly it selects a tour (in the first case 1,4,3,9) and breaks this tour but I would like it to be combined with the second largest tour. So in the first case that it combines the longest tour(1,4,3,9) and the second longest tour (0,18) Is there any way this can still be implemented in the code?

Total distance: 20.8

0 - 18 - 0

1 - 4 - 3 - 9 - 1

20 - 22 - 20

Selected tour:{1,4,3,9}

Total distance: 20.9

0 - 9 - 0

1 - 3 - 4 - 1

18 - 22 - 20 - 18

Selected tour:{1,3,4}

Total distance: 20.9

0 - 9 - 3 - 4 - 1 - 0

18 - 22 - 20 - 18

Selected tour:{0,9,3,4,1}

Total distance: 21.2

0 - 18 - 9 - 3 - 1 - 4 - 0

20 - 22 - 20

Selected tour:{0,18,9,3,1,4}

Total distance: 21.5

0 - 18 - 22 - 20 - 9 - 3 - 4 - 1 - 0

What you are describing sounds like a heuristic for constructing feasible solutions for a TSP: once you have selected a first subtour it would perhaps be preferrable to select as a second subtour to be attached to the first one some tour that is close (cheapest to reach from the first). The full example in https://examples.xpress.fico.com/example.pl?id=tsp that I have referred to earlier implements such a heuristic: at first, it determines tours for small subsets (nodes lying in the same region) of nodes, then it selects two neighboring tours, fixes the flows on arcs that are far from the common border region and re-solves the optimization problem for the unfixed portion of nodes, thus keeping the problem size small for every solve. This is repeated iteratively until all subtours have been 'glued' together. Such an approach quickly leads to reasonably good solutions, but you do not have any guarantee to reach the optimum and you cannot prove optimality.

Having said that, if you really want to force the solver to keep a portion of your longest tour you could add in a lower bound constraint such as

sum(i in LARGEST) ROAD(i,NEXTRETAIL(i)) >= getsize(LARGEST) - 1 ! (or perhaps -2)

but this means that you might miss the actual optimum. Similarly, you could modify the constraint that connects the set of nodes in 'LARGEST' to the rest of the nodes by using some other subset in place of 'all other nodes' in the second constraint in my code example above - again, this may result in cutting off the actual optimum.

If you simply want to see whether you can construct a full tour out of some set of subtours I would suggest that you switch to using heuristics - you could for example try to adapt the 'two_opt' routine from the example in https://examples.xpress.fico.com/example.pl?id=f5tour_h_1 to work with arcs from different subtours.