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
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.
Related 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