Queueing Cuts in XpressMP

In my previous post, I described doing Benders decomposition with the XpressMP optimizer (Java API), including some sample code. As with previous code solving the same sample problem using CPLEX, a callback was required. The callback takes candidate solutions from the master problem, solves the corresponding LP subproblem, and either accepts the candidate or rejects it by adding a Benders feasibility cut or a Benders optimality cut. Well, that's how it works with CPLEX. The Xpress callback allowed me to add Benders cuts when the candidate solution was the optimal solution to a node LP in the master search tree, but not when the candidate was found via heuristics. (With CPLEX, the source of the solution did not matter.)

Being obstinate, I tried to work around that limitation. I updated my Java source code (still in the same repository) with a second Benders approach using a cut queue. In this approach, the PreIntsol callback solves the LP subproblem and, if warranted, cranks out a Benders cut. If the source was a node optimum, the PreIntsol callback adds the cut as before. If the source was a heuristic, the PreIntsol callback adds the cut to a queue within the Java code. A second callback, which implements the XpressProblem.CallbackAPI.CutRoundCallback interface, is called when Xpress is generating cuts. If any cuts are in the queue, this callback removes them from the queue and adds them via calls to XpressProblem.addManagedCut(). Thus, in theory, the opportunity to generate Benders cuts based on heuristic solutions does not go to waste.

So did this help? Somewhat, though not as much as I had expected. The first thing I discovered is that running either of the Benders models with a single thread was faster than running them with five threads. I suspect this is partly due to the test problem being very easy and partly due to multiple threads doing redundant work (for instance, churning out the same heuristic solution multiple times). 

 With a single thread, Benders with the queue was a wee bit faster than Benders without the queue. In one run, the original Benders model needed 597 ms. versus 578 ms. for the Benders run with the cut queue. (For comparison purposes, the basic MIP model with no decomposition needed 162 ms.) This might understate the advantage of the model with cut queue very slightly, since it does a bit more printing, and when you are dealing with differences in the millisecond range maybe time printing matters (?). The original Benders model had its callback invoked 28 times with integer-feasible node solutions, resulting in 25 optimality cuts and one feasibility cut. It was invoked 74 times with heuristic solutions. The version with the cut queue was invoked only six times with integer-feasible solutions but 74 times with heuristic solutions. It generated 56 optimality cuts and 21 feasibility cuts. The higher cut counts make sense, since it can generate cuts from heuristic solutions. What is a bit perplexing to me is that it encountered the same number of heuristic solutions, suggesting that the extra cuts blocked some node optima from occurring but had no effect on Xpress's heuristics.

With five threads, the story changes.  The run times were 168 ms. for the MIP model (no change after accounting for randomness), 817 ms. using the queue and 2557 ms. without the queue. So the queue cut Benders run time by about 2/3 or so. The original Benders callback was called 84 times with integer-feasible node solutions and 142 times with heuristic solutions, versus 17 times with integer-feasible node solutions and 87 times with heuristic solutions for the version with the queue. Note that, in this case, the number of heuristic solutions also went down.

So is the cut queue worth the effort of programming it (and the extra time devoted to invoke the cut callback repeatedly)? Maybe. It appears to depend at least in part on the number of threads being used, although one or two runs on one test case is far from conclusive.