Forum Discussion
Implementing the TSP with DFJ subtour elimination constraints
To learn how callbacks work in Xpress, based on the answer by Daniel Junglas in this question: https://community.fico.com/s/question/0D54W00008P73MsSAJ/lazy-cut-callback-in-java, I've been experimenting with a slightly different implementation of the standard TSP problem where subtours are separated through a minimum cut procedure and where cuts are added in a lazy manner.
The implementation is however not yet correct since the final solution still contains subtours. Oddly, the final solution obtained coincides with the very first integer solution found at the root node. However, for this solution a cut gets generated, so per definition this solution should be cut off. I wonder whether I made some obvious error in the definition of the callbacks, or in the way I add the cuts. One noticeable difference with the aforementioned implementation by Daniel Junglas is that I modeled part of the problem through XPRB, whereas Daniel models the problem directly in the Optimizer.
Would it be possible to have a brief glance at my code to see whether there's any obvious defects in the way I setup and invoke the callbacks and add the cuts?
3 Replies
This might be obvious, but did you check that your cut is actually (significantly) violated?
I suggest to check the cut directly on the varIndices/coefficients arrays that you pass to addCuts() and on the solution vector you get from getLpSol().
I found the issue. The cuts were correct. The problem was in the syncing between BCL and the optimizer. I incorrectly invoked problem.sync(XPRB.XPRS_SOL) instead of problem.sync(XPRB.XPRS_SOLMIP). This manual syncing is very error prone. It would perhaps be slightly more obvious if XPRB.XPRS_SOL would be renamed to XPRB.XPRS_LPSOL
I confirm, syncing with XPRS_SOL is not correct as this will only sync LP information. With only this the values returned by XPRBvar.getSol() will be fetched via XPRSgetlpsol, which is not the right thing after optimization completes. Syncing with XPRS_SOL_MIP instead sets up the problem so that solution values are fetched via XPRSgetmipsol.
