Friday, December 2, 2016

Support for Benders Decomposition in CPLEX

As of version 12.7, CPLEX now has built-in support for Benders decomposition. For details on that (and other changes to CPLEX), I suggest you look at this post on J-F Puget's blog and Xavier Nodet's related slide show. [Update 12/7/16: There is additional information about the Benders support in a presentation by IBM's Andrea Tramontani at the 2016 INFORMS national meeting, "

I've previously posted Java code for a simple example of Benders decomposition (a fixed-cost warehousing/distribution problem). To get a feel for the new features related to Benders, I rewrote that example. The code for the revised example is in this Git repository, and is free for use under a Creative Commons 3.0 license. There is also an issue tracker, if you bump into any bugs.

Going through the code here would be pretty boring, but there are a few bits and pieces I think are worth explaining, and I'll show some far from definitive timing results.

Modeling Approaches

I have five modeling approaches in the code.
• STANDARD: This is just a single MIP model, using no decomposition. It's present partly for benchmark purposes and partly because a few of the newer approaches build on it.
• MANUAL: This is essentially a reprise of my earlier code. I write two separate models, a master problem (MIP) and a subproblem (LP), just as one would do prior to CPLEX 12.7.
• ANNOTATED: This is the first of three methods exploiting the new features of CPLEX 12.7 I create a single model (by duplicating the STANDARD code) and then annotate it (using the annotatiion method added to CPLEX 12.7) to tell CPLEX how to split it into a master problem and a single subproblem. The annotation method would also let me create multiple disjoint subproblems, but the example we are using only needs one subproblem.
• WORKERS: This is the ANNOTATED method again, but with a parameter setting giving CPLEX the option to split the single subproblem into two or more subproblems if it sees a structure in the subproblem that suggests partitioning is possible.
• AUTOMATIC: Here I create a single model (identical to the STANDARD method) and, via a parameter setting, let CPLEX decide how to split it into a master problem and one or more subproblems.

Benders Strategy Parameter

The key to all this is a new parameter, whose Java name is IloCplex.Benders.Strategy. It is integer valued, but for some reason is not part of the IloCplex.IntParam class hierarchy (which threw me off at first when I tried to use it in my code). The values defined for it are:
• -1 = OFF: Use standard branch and cut, doing no Benders decomposition (even if annotations are present). Note that this will not stop manually coded Benders from working (as in my MANUAL method); it just stops CPLEX for creating a decomposition. This is the default value.
• 0 = AUTO: If no annotations are present, do standard branch and cut (akin to the OFF value). If the user supplies annotations, set up a Benders decomposition using those annotations, but partition the subproblems further if possible (akin to the WORKERS behavior below). If the user supplies incorrect annotations, throw an exception. This is the default value.
• 1 = USER: Decompose the problem, adhering strictly to the user's annotations (with no additional decomposition of subproblems). If the user fails to annotate the model, or annotates it incorrectly, throw an exception.
• 2 = WORKERS: This is similar to USER, but gives CPLEX permission to partition subproblems into smaller subproblems if it identifies a way to do so.
• 3 = FULL: CPLEX ignores any user annotations and attempts to decompose the model. If either all the variables are integer (no LP subproblem) or none of them are (no MIP master problem), CPLEX throws an exception.
There are also two other Benders-related parameters, in Java IloCplex.Param.Benders.Tolerances.feasibilitycut and IloCplex.Param.Benders.Tolerances.optimalitycut, that set tolerances for feasibility and optimality cuts. (In my code I leave those at default values. If it ain't broke, don't fix it.)

Syntax

Coding the strategy parameter looks like the following.
IloCplex cplex;      // declare a model object
// ... build the model ...
int strategy = ...;  // pick the strategy value to use
cplex.setParam(IloCplex.Param.Benders.Strategy, strategy);


Annotations

Annotations can be specified in a separate file (if you are reading in a model) or added in code (which is what I do in my demo program). IBM apparently intends annotations to be used more generally than just for Benders decomposition. To use them for Benders, what you do is annotate each model variable with index number of the problem into which it should be placed (where problem 0 is the master problem and problems 1, 2, ... are subproblems). Only variables are annotated, not constraints or objective functions. If you fail to annotate a variable, it is given a default annotation (discussed further below). If you assign a negative integer as an annotation, the universe will implode spectacularly, and CPLEX with throw an exception just before it does.

You start by creating a single MIP model, as if you were not going to use Benders decomposition. Assuming again that your model exists in a variable named cplex, you begin the decomposition process with a line like the following:
IloCplex.LongAnnotation benders =
cplex.newLongAnnotation("cpxBendersPartition");
The name "benders" for the variable in which the annotation is stored is arbitrary, but the name cpxBendersPartition for the annotation must be used verbatim. This version of the annotation constructor sets the default value to 0, so that variables lacking annotations are assumed to belong to the master problem. An alternate version of newLongAnnotation uses a second argument to set the default value.

Next, you annotate each variable with the index of the problem into which it should be placed. Suppose that we have two variables defined as follows.
IloIntVar x = cplex.boolVar("Use1");
// open warehouse 1?
IloNumVar y = cplex.numVar("Ship12")
// amount shipped from warehouse 1 to customer 2

Assuming that we want x to belong to the master problem (index 0) and y to belong to the first and only subproblem (index 1), we would add the following code:
cplex.setAnnotation(benders, x, 0);
cplex.setAnnotation(benders, y, 1);
where benders is the variable holding our annotation.

There are versions of setAnnotation that take vector arguments, so that you can annotate a vector of variables in a single call. If the model in question has a fairly small number of integer variables and a rather large number of continuous variables (which is pretty common), you might want to use the two-argument version of newLongAnnotation to set the default value at 1, and then annotate only the integer variables, letting the continuous variables take the default annotation (i.e., be assigned to subproblem 1).

That's all there is to creating a Benders decomposition from a standard MIP model. Note, in particular, that you do not need to create callbacks. CPLEX handles all that internally. You can still add things like lazy constraint callbacks if you have a reason to do so; but for a "typical" Benders decomposition (dare I use that phrase?), you just need to create a single MIP model, annotate it, and set the Benders strategy parameter. What could be easier than that? Well, actually, one thing. If you set the Benders strategy to FULL, you don't even have to annotate the model! You can let CPLEX figure out the decomposition on its own.

Performance

Test runs of a single model (especially one as simple as the fixed-charge warehouse problem) on a single computer (especially one with a measly four cores) written by a single programmer (who happens not to be terribly good at it) don't prove anything. I'll leave it to someone else to do serious benchmarking. That said, I was curious to see if there were any gross differences in performance, and I also wanted to see if all methods led to correct answers. (I'm not what you would call a trusting soul.) So I ran 25 replications of each method, using a different problem instance (and a different random seed for CPLEX) each time. In an attempt to level the playing field, I forced Java to collect garbage after each model was solved (and timing stopped), to minimize the impact of garbage collection on run times. All problem instances were the same size: 50 warehouses serving 4,000 customers. The basic model has these dimensions: 4,050 rows; 200,050 columns (of which 50 are binary variables, the rest continuous); and 400,050 nonzero constraint coefficients.

The first plot below shows the wall-clock time spent setting up (and, where relevant, decomposing) each model.
None of the methods strikes me as being overly slow, ignoring a couple of outliers. Using annotations (the "Annotated" and "Workers" methods) does seem to impose a nontrivial burden on model construction.

The second plot shows solution times. For each problem instance, all five methods achieved identical objective values (and proved optimality), and all used the same number of warehouses. (I did not check whether the values of the flow variables were identical.) So any concerns I might have had about validity were assuaged.
I'm not sure how much to read into this, but "manual" decomposition (the old fashioned approach, using explicit callbacks) seems to have the highest variance in solution time. The three approaches using new features of CPLEX 12.7 ("Annotated", "Automatic" and "Workers") had very similar run times. I'm fairly certain that the "Workers" method, wherein CPLEX tries to further partition the single subproblem I specified, wound up sticking with a single subproblem (due to the structure of the model).

Which Is Better?

Assume that you have a problem that is amenable to "standard" Benders decomposition (as opposed to some of the funky variants, such as combinatorial Benders, Benders with MIP subproblems, Benders with subproblems that are not necessarily optimization problems, ...). The easiest approach from the user perspective is clearly the automatic option (Benders strategy = FULL), in which CPLEX literally does all the work. Runner up is the annotation approach, which is both much easier and much less prone to coding errors than the "manual" approach (defining separate problems and writing a lazy constraint callback).

On the performance side, things are a bit less clear. If you dig through Xavier Nodet's slides, you'll see that CPLEX use somewhat sophisticated techniques, based on recent research, to generate Benders cuts. I suspect that, on the test problem, their cuts would be a bit stronger than the ones I generate in the "manual" approach, which may account for some of the difference (in their favor) in median run times seen in the second plot. Also, since they can access the subproblems and add cuts to the master directly, rather than having to go through callbacks, using the annotation feature may result in a bit less "drag".

With other cases, I suspect that if you have a particular insight into the model structure that lets you generate problem-specific Benders cuts that are tighter than the generic cuts, you may do better sticking to the manual approach. Fortunately, since you can turn on automatic Benders decomposition just by tweaking a single parameter, it should be easy to tell whether your cuts really do improve performance.

1. Thank you for sharing this valuable information Professor Paul. I checked the link https://gitlab.msu.edu/orobworld/bendersexample2.git but couln't see the code. Regards.

1. Thanks for bringing this to my attention. There was an incorrect permissions setting on the server. You should be able to see and click the "Repository" button now to get access to the code.

2. Thanks for the valuable preliminary comparison Prof. Rubin.

I'm an OR grad student and I was originally using Benders manually to solve my stochastic programming model. I downloaded Cplex 12.7 to try it and it has been surprisingly performing better. I wasn't able to understand the output report though. Does Cplex use a combination of both Benders and branch-and-cut when it is set to the "automatic" strategy? Can you refer me to the documentation for interpreting the output report, if there is any because I wasn't able to find it.

Also, you mentioned that Cplex uses sophisticated techniques based on new research, can you please elaborate a little on that? I went through the slides but I didn't notice where it was mentioned. Thanks a lot.

1. As far as I know, when you turn on automatic Benders, CPLEX still uses branch-and-cut on the master problem. The cuts it generates will of course be different than they would be if you were solving the original model, since the cuts (excluding Benders cuts) are generated from the master.

I have not seen any documentation about the node log specific to the Benders additions. Although I don't have any output in front of me, I don't recall any confusion with the logs when I ran my experiments.

As to the details of the Benders cut generation, it turns out I saw that in a presentation by Andrea Tramontani, not in Xavier Nodet's presentation. I've updated the first paragraph of this post with a link to Andrea's slides. They include citations of the relevant research.

2. Thanks a lot for the reply Prof. Just to clarify, I was only confused about the part of the output that is prior to the usual Cplex output (gap, incumbent, lower bound, etc.). My guess is that since I only tried it with the automatic Benders strategy and the problem I'm working with can be decomposed to up to 50 subproblems, maybe that output is where Cplex is decided what is the optimal number of subproblems to decompose the problem to.

My understanding is that you coded the problem in Java? For the manual algorithm, when you solve the master problem at every iteration, do you just add the additional cuts to the already existing Cplex object and resolve using the solution from the previous iteration or do you resolve the MP from scratch? If you do NOT resolve from scratch, then the previous iteration's solution may give an infeasible initial solution, how is that problem tackled?
I'm currently using Matlab with Cplex and I suspect that it might not have full Cplex functionality.

Thanks a lot.

3. Aliaa,

I don't use MATLAB, but I believe that you are correct in thinking that the MATLAB API is not as rich in features as the other APIs.

Yes, I used Java for the example. For the "manual" algorithm, I employed a lazy constraint callback. I described this approach in an old post (https://orinanobworld.blogspot.com/2011/10/benders-decomposition-then-and-now.html). So I do not solve from scratch each time, but the method is provably correct. I do not believe the MATLAB API has lazy constraint callbacks.

4. Great! Thanks a lot for the help.

5. Hi Aliaa
You mention your model under BD is much faster than previous way.
But I test that bd method, that method in Cplex 12.7 is worse than standard MIP mpdel in most cases. Can you give some ideas?

Thanks
Keji

6. Hi Keji,

I think it depends on the structure of the problem. I'm working on a two-stage stochastic programming model with a 50 scenarios. So for my model, applying BD helps because then the problem decomposes by scenario. But my friend mentioned to me that for her problem, BD actually performed worse than Cplex default solver.

So it depends on the particular problem, but generally I think if separating the integer variables in a given problem from the continuous results in the problem decomposing into many easier to solve subproblems, BD might work better.

Hope that helped,
Aliaa

3. Great post Prof. Paul, thanks!
Unfortunately I think Cplex 12.7 built-in Bender's algorithm is not compatible with callbacks yet (from this post: https://www.ibm.com/developerworks/community/forums/html/topic?id=261ea480-b294-4dd8-b5a9-22ba83cbf8b5).
So, for those of us having complicated complicated constraints in the master (for example sub-tour elimination constraints), the manual approach is still the way to go.

1. Thanks Alexandre. You are correct that callbacks are not (yet) compatible with automatic or annotated Benders decomposition. Just to be sure, I attached a lazy constraint callback to the annotated methods in my example code. All the callback did was print something -- it did not attempt to add any cuts -- but its mere presence caused an error.

Adding callbacks would not be entirely trivial for IBM, although some cases would be fairly straightforward. We'll see if they show up in future versions. Meanwhile, I think it's reasonable to think that if a user is sophisticated enough to implement a lazy constraint callback or a user cut callback correctly, they're probably quite capable of using the manual approach and don't need the new features. From a development standpoint, it would be a bit faster in some cases to use the new features with a customized lazy constraint callback, so I do hope we see some provision for it in the future.

If I worked for IBM in customer support, though, I wouldn't be agitating to see it any time soon. ;-)

4. And it appears they implemented Bender's using the traditional (as opposed to the single-tree) approach. Maybe in future versions they also add the possibility of using the single-tree.

1. What makes you think that? I looked at one of Matteo Fischetti's papers (referenced in Andrea Tramontani's slide show from INFORMS 2016), and it appears that Fischetti et al. use a one-tree approach with the "optimal" solution mentioned by Tramontani being the optimal solution to the node LP (not to the master MIP). I have to admit, though, that I just skimmed Matteo's paper. I'll need to read it more carefully later.

2. Thanks for posting such an impressive and helpful blog. I also have two questions.

1. The first one is very related with your reply to Alexandre. Does CPLEX 12.7 develop the modern Bender decomposition with lazy constraints callback (just similar with your blog "Benders Decomposition Then and Now" six years ago), instead of the classic benders decomposition (solving the master problem from scratch). According to your experimental result, especially the second plot in this blog, the "manual" approach is similar to three CPLEX approaches with different parameter settings in terms of solution time. Maybe the difference is because of the stronger cuts generated by CPLEX itself, as said in your blog. I think it is most likely that CPLEX 12.7 is using lazy constraints callback to achieve its inbuilt benders decomposition.

2. The second question is Why the lazy constraint callback is correct and provably to find the originally optimal results. I means that is it guaranteed that the modern Benders decomposition with callback must have the same result with the classic benders decomposition?

Thanks

3. Thanks for the kind words.

1. I don't have an "inside" knowledge about the implementation details, but judging from the solver log, my guess would be that they are using the one tree (callback) approach. The solver log shows repeated attempts to presolve at the start (I have no idea why it presolves more than once), but once it gets serious about iterating, adding cuts at the root node, there is no indication of further presolving, even after adding a Benders cut. If it were using the traditional approach, after adding a Benders cut I would expect to see a restart complete with presolving of the (new) root node.

2. The proof for the one tree (callback) method is essentially the same as the proof for the original method. In broad terms (omitting some details about edge cases), assume that the integer variables are bounded and the problem is feasible. The master problem search tree has a finite number of nodes, so Benders will eventually stop. You just have to prove that it cannot stop with an infeasible solution (because that solution would have been cut off by a feasibility cut) or a suboptimal solution. Proving the latter is a bit more work, but not hard. It could only happen if a solution with an overly charitable value for the surrogate variable for the objective contribution of the subproblem were accepted, and that can't happen if the callback is doing its job (the surrogate variable would be tightened by optimality cuts).

5. Martim Joyce-MonizFebruary 9, 2017 at 5:04 AM

I was wondering: Is there any way to get from Cplex the number of Benders cuts that were generated? Can't seem to find that option.

1. Martim: I'm fairly certain (though not completely positive) that it doesn't exist (yet). I raised the question with a contact at IBM. Maybe we'll see it in a future version.

2. Thanks for the quick reply. Indeed, it would be interesting to have it in the future!

3. Per an IBM source: it is not available in CPLEX 12.7, but is scheduled for addition in a future release (likely the next one).

6. Prof Rubin,

How do we implement a benders decomposition when we want to add constraints into the master problem itself via callbacks apart from the Benders cut being added via a lazy callback?

Thanks

1. I'm not sure I'm understanding the question. If you mean that you are generating all the cuts yourself via lazy constraint callback (not using the new feature to have CPLEX generate any Benders cuts) and want to make them a permanent part of the master problem, you just have to store them in an array (with global scope) while also adding them in the callback, and then, after the solution has ended and you've recorded the final solution, add them to the master problem as you would with any other constraints. I'm not sure why you would want to do that.

If you're saying that you want to have CPLEX generate Benders cuts and also generate your own Benders cuts, I'm not sure about the answer. Automated Benders is applied to the full model, not to a restricted master problem, so I don't see a way to do it (nor do I see a reason to).

7. Thanks for all the Benders posts. I learn a lot from you.

I dont know whether it is my fault or not. But, because INTELLIJ IDEA (IDE) does not find MAIN METHOD (even if i properly show the DEMO.CLASS to the IDE to spot the method) i can not run your code via INTELLIJ IDEA.

And, I try run it via MAC TERMINAL but i couldnt find the .jar file. So i created one, but it could not also spot the MAIN method via the .jar file. (even if i told where the method is)

I know that your code has no flaws. Could you tell me what are the possibly reasons for the problem.

Thanks. Sincerely.

1. Hi,

Sorry, but I've never used IntelliJ. With Java IDEs, there's typically a project or run setting that lets you specify the main class. Also, there may be an option to select the Demo class in the IDE and, either from a main menu or a context menu, ask IntelliJ to run that class.

Not finding the JAR file initially is correct: the repository does not have one. It's source only. If you created the JAR file in IntelliJ, and if IntelliJ could not find the main method, that would explain why the JAR you created appeared not to have one.

You might try the following from a terminal:
java -Djava.library.path= -cp BendersExample2.jar: bendersexample2.Demo

The first path leads to the directory containing the CPLEX binary files (which have extension .so on Linux; I'm not sure if that's the same on a Mac). The second path leads to the directory containing the JAR file you created, and the third leads to the directory containing cplex.jar.

2. Sorry, the command line entry was truncated because I forgot to escape angle brackets. I'll try again.

java -Djava.libraryath=<path to CPLEX binary> -cp <path to compiled jar>/BendersExample2.jar:<path to CPLEX jar> bendersexample/Demo

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.