Forum Discussion
TSP 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 subtour elimination constraints to the B&B tree during the solve. However, the following code snippet does not quite work in Xpress. It is a simple 13-node TSP where root node's integer solution is as follows:
x[0][2] = 1
x[0][7] = 1 x[1][8] = 1 x[1][11] = 1 x[2][3] = 1 x[3][7] = 1 x[4][11] = 1 x[4][12] = 1 x[5][9] = 1 x[5][10] = 1 x[6][8] = 1 x[6][12] = 1 x[9][10] = 1Obviously, we need to add a subtour elimination constraint, such as:
CUT(0):x[0][2] + x[0][7] + x[2][3] + x[3][7] <= 3
However, the solver declare the problem infeasible after adding this valid cut.
*** Search completed *** Time: 0 Nodes: 1
Problem is integer infeasible Number of integer feasible solutions found is 0 Best bound is 1.00000E+40What am I missing?
Code Attached.
3 Replies
A couple of points regarding your code:
- Please remove the "loadMat" call within the callback.
- The 'optnode' callback function is triggered when a node relaxation has been solved to optimality and the Optimizer is about to branch or declare the node integer feasible. Only if the node is about to be declared integer feasible you should check for subtours, so start it with a test of whether XPRS.MIPINFEAS=0.
- I would also recommend to set globally XPRS.SYMMETRY=0.
- In terms of possible alternative cut formulations, you may want to take a look at the Mosel model example f5tour.mos in the subdirectory examples/mosel/ApplBook/F_TransAir of the Xpress distribution: if the problem is entirely symmetric, it can be helpful to exclude also the same tour in the other sense.
Thanks a bunch for your response. In the example f5tour.mos, my understanding is that it re-solves the whole problem from scratch after adding each subtour cut. If so, is there a way to implement do this in Mosel via a callback method that adds subtour cuts as necessary within the B&B tree?
As for BCL, I made the changes that you suggested but it still does not like the cut I am adding. Any idea what else might be going wrong here?
Code attached.
Attached a version of the Mosel model that uses the OPTNODE callback.
What kind of errors/log are you seeing from your BCL program? (It is not runnable without the definition of the class Edge.)
