Forum Discussion
Implementing Lazy Constraints (Java)
We are interested in using Lazy Constraints in Xpress (Java) to implement a TSP algorithm. In particular, after each integer solution is generated, we would like to search for violated constraints and add the needed cuts if necessary. We have tried to use the XPRSpreIntsolListener callback, but keep getting jre memory access error messages. Any help, especially actual code, on how to do this would be greatly appreciated.
6 Replies
With the Xpress-Optimizer, you could implement "lazy constraints" as "delayed rows" (see XPRSloaddelayedrows; or if you are using a modelling tool for stating your problem: Mosel: defdelayedrows, BCL C: XPRBsetdelayed) - however, this means that you need to state all constraints upfront which certainly is impractical in the context of TSP.
Regarding the use of Optimizer callbacks from Java, please take a look at the examples FICO Xpress Examples Repository: Demonstrates setting up and using callbacks (http://examples.xpress.fico.com/example.pl?id=optimizer_java_1) and FICO Xpress Examples Repository: Els - An economic lot-sizing problem solved by cut-and-branch and branch-and-cut heuris… (http://examples.xpress.fico.com/example.pl?id=bcl_java_12_2)
One of the Mosel examples implements a subtour elimination algorithm for TSP, looping over complete MIP solves: FICO Xpress Examples Repository: Air transport (http://examples.xpress.fico.com/example.pl?id=mosel_book_6_11)
which is extended to a heuristic for larger instances in this version of the example: FICO Xpress Examples Repository: Solving the TSP problem by a series of optimization subproblems. (http://examples.xpress.fico.com/example.pl?id=mosel_solv_11)
Below I am attaching an alternative Mosel implementation of the TSP subproblem solving that uses MIP callbacks: if your initial problem statement does not correspond to the full problem and you wish to use the cut manager to add further constraints during the MIP search you need to configure the solver correspondingly (in particular, disable dual reductions).
See PDF attached.
See PDF attached.
The above code is being used to detect any violated constraint and add the lazy constraints. However, the optimizer is not rejecting the integer solution. How do I ensure that the model doesn't accept the integer solution?
It is not possible to define new constraints (XPRBctr) for a problem during the MIP search, instead you need to create cuts (XPRBcut) and add them to the problem via XPRBprob.addcuts.
CUT(0):- 586*x_0,1,0 - t_0 + t_1 >= 558
CUT(0):- 636*x_2,5,23 - t_2 + t_5 >= 558
CUT(0):- 606*x_4,2,20 + t_2 - t_4 >= 558
CUT(0):- 595*x_6,3,9 + t_3 - t_6 >= 558
CUT(0):- 561*x_7,8,31 - t_7 + t_8 >= 558
BCL: Warning 1587: Switch to cut mode.
BCL: Warning 1570: XPRS: ?405 Error: Invalid column number passed to XPRSaddcuts.
Column number 2048 is invalid
Exception in thread "main" com.dashoptimization.XPRBerror: (addcuts) Xpress-Optimizer error 405 during 'addcuts'. Return value: 32.
Any ideas? I switched over to using cuts and added them at the end. All cuts are valid for the problem, but maybe Xpress doesn't like them since the current solution to be accepted is violated by them.
You need to be careful about not using destructive presolve (you seem to be trying to add constraints on variables that have been removed by presolve):
The Mosel code example above sets different bits of the PRESOLVEOPS control, a simpler approach is to call
XPRBprob.setcutmode(1)
before you invoke the optimization (this simply turns presolve off altogether).
