Benders Decomposition in XpressMP

Thirteen and a half years ago (yikes!) I posted about doing Benders decomposition in CPLEX, including source code (Java) for solving a small fixed-cost transportation problem using Benders. The source code changed a couple of years later and I moved it to a new repository. I probably should state up front that when I allude to Benders decomposition I mean what is known in some quarters as "one tree Benders" -- solving the problem in a single pass, using callbacks, rather than Jacques Benders's original approach, which solved the master problem to "optimality", added cuts and then started the master problem solution again from scratch.

I decided to try applying Benders to the same problem using the Java API to FICO's XpressMP solver. It turns out that implementing callbacks in XpressMP is a bit of an adventure, in part due to its design and in part due to rather sparse documentation for the Java API. (Someone at FICO advised me to consult the documentation for the C API whenever I could not find some detail in the Java documentation.) Eventually, I managed to get a working implementation of Benders for the same example used in those old posts. I will not repeat the formulation here. You can find it in the first of the posts above. It involves deciding which of a given set of warehouses to open and how much to ship from each opened warehouse to each client. Clients have demands that must be met, warehouses have capacities, there are fixed charges to open warehouses and per-unit flow costs between warehouses and customers. The warehouse-customer links do not have any capacity limits. In the Benders decomposition, the master problem (MIP) contains binary variables indicating which warehouses are opened plus a surrogate variable for the total flow cost. It initially has no constraints. The subproblem (LP) contains continuous flow variables for each combination of warehouse and customer, demand constraints for the customers and capacity constraints for the warehouses.

The Java code for my implementation can be found in this repository. The "Code" drop-down menu provides options for downloading the code. Running it requires that you have a recent version of XpressMP installed. Outside that (and having Java, of course) there are no software requirements. The code first runs a single MIP model as a benchmark, then runs the Benders model.

Callbacks

The Benders implementation requires only one callback in the master problem. It implements the XpressProblem.CallbackAPI.PreIntsolCallback interface. According to the C documentation, Xpress calls it "when an integer solution is found by heuristics or during the branch and bound search, but before it is accepted by the Optimizer". One of the arguments (soltype) tells you whether the solution is an integer-feasible node optimum (soltype = 0) or a heuristic solution (soltype = 1). The distinction is important because Xpress will allow you to add cuts when it has a node solution but will not allow you to add cuts when it has a heuristic solution.

The callback includes an argument (pReject in my code) that you set to 0 to accept the solution or 1 to reject it. Somewhat curiously, if a node solution is infeasible or underestimates flow costs and you are able to add a Benders cut, you are supposed to "accept" the solution (set pReject to 0) in the callback (else the cuts are lost, if I understand this correctly). If a heuristic solution is infeasible or underestimates the flow cost, you reject it (set pReject to 1). The argument has class IntHolder, so you do not directly set it to 0 or 1; you instead set its value field to the desired value (for instance, pReject.value = 0 to accept the solution).

According to a source at FICO, there is currently no callback that allows you to add Benders cuts when dealing with a heuristic solution. All you can do is reject it if it is infeasible or underestimates the flow costs. This results in the master problem solver repeatedly generating (via heuristic) the same or similar infeasible solutions, which could be avoided if Benders cuts could be added.

While researching this, I came across a Benders example (in Python)  that also used a callback which in Java would implement the OptNodeCallback interface. This is apparently no longer necessary, due to changes to the solver.

Variable names

As with all other solvers, Xpress lets you assign names to variables.  In my code, I print out the Benders cuts being added. This is mainly for debugging purposes. I certainly would not do it in a production problem with hundreds or thousands of binary variables. It turns out this is not as easy as one might think. For rather arcane reasons that I will not get into (since I would get the explanation wrong), inside the callback the variables are named X[0], X[1], X[2] etc., regardless of whatever names you originally assigned them. This is a bit confusing (and makes debugging tricky, since it's unclear which of the original variables is now known as X[12]). Daniel Junglas at FICO provided me Java code for a workaround, which is included in my code. You will find it in the BendersModel.printCut method.

Thread safety

When using multiple threads, there is good news and bad news. The good news is that Xpress goes to great lengths to be thread-safe.  Part of their implementation of thread safety is the first argument of the callback function, which is a presolved (I believe) copy of the original (master) problem. This means that if the callback is running simultaneously in multiple threads, each thread is working with a different copy of the problem, avoiding collisions. 

The bad news is that this introduces some rather curious problems. In my case, problems arose when printing the cuts being added. The cuts were expressed in terms of the original variables (defined in the master problem and saved in an array for later use generating cuts). For whatever reason, the cuts themselves came out fine, and adding them worked, but when I went to print them (which implicitly meant invoking toString() on the cut expressions) Xpress threw exceptions and eventually crashed. This only happened when using multiple threads. If I throttled Xpress to a single thread, printing the cuts caused no problems. Fortunately, the workaround of the variable naming issue (implemented in the printCut method) also eliminated the exceptions occurring when I printed the cuts.

So, bottom line, I now have working code that solves a problem via Benders decomposition with the Java API to Xpress. You are free to download it if you wish, provided you promise not to laugh at it. Okay, not to laugh at it too much.