Forum Discussion
FICO
6 years agoCommunity Manager
How to combine the largest subtours together
Hi, I worked on an assignment where i need to make a tour to visit various retail shops. Where the distance needs to be minimized. I obtained a solution with various sub-tours. I found out how to el...
FICO
6 years agoCommunity Manager
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-procedureRelated Content
Related Content
Combining sum and overall statement
Hi, I am trying to build a perishable supply chain model. To include perishability, I want to include a constraint in which for every period in time (T is the set of periods, indexed by t) the model...5 years agoPlace FICO® Xpress Optimization ForumFICO® Xpress Optimization Forum2 unread comments2 unread0Views0likes2CommentsTSP Subtour-Elimination Callback Class
I am new to Xpress and trying to implement a simple TSP instance using BCL Java to get myself up to speed. I have done this in Cplex before using the cut callbacks, which work fine for adding the sub...9 years agoPlace FICO® Xpress Optimization ForumFICO® Xpress Optimization Forum3 unread comments3 unread0Views0likes3Commentscombining mmxprs and/or nlsolv with mmquad or mmnl
I have two questions about combining mmxprs and/or nlsolv with mmquad or mmnl in Mosel: If I use the Xpress solver (mmxprs), can I trust that it will always detect that a constraint or objective is ...3 years agoPlace FICO® Xpress Optimization ForumFICO® Xpress Optimization Forum5 unread comments5 unread0Views0likes5Comments