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, "Recent advances in IBM ILOG CPLEX".]

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.
box plot of model setup times
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.
box plot of solution times
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.

50 comments:

  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.

    ReplyDelete
    Replies
    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.

      Delete
  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.

    ReplyDelete
    Replies
    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.

      Delete
    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.

      Delete
    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.

      Delete
    4. Great! Thanks a lot for the help.

      Delete
    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

      Delete
    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

      Delete
  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.

    ReplyDelete
    Replies
    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. ;-)

      Delete
  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.

    ReplyDelete
    Replies
    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.

      Delete
    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

      Delete
    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).

      Delete
  5. 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.

    ReplyDelete
    Replies
    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.

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

      Delete
    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).

      Delete
  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

    ReplyDelete
    Replies
    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).

      Delete
  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.

    ReplyDelete
    Replies
    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.

      Delete
    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

      Delete
  8. Professor Rubin,

    Thank you very much for your detailed and illuminating examples of Benders Decomposition. I have gone through your posts and code in detail. Both resources have greatly increased my understanding of the decomposition technique.

    I do have one question on the material: what happens if the cost vector c (in the notation from your 2012 post) is all zeros? That is, what happens if the continuous variables do not have a cost and the subproblem is a feasibility problem rather than an LP? At first, I thought that maybe it would be okay because the dual still has an objective, but now I am not so sure. Would you only have the option of using a combinatorial benders approach, or are there more alternatives?

    ReplyDelete
    Replies
    1. In general, the subproblem is still an LP (with an objective function that is the constant 0). Feasibility cuts (primal subproblem infeasible, dual unbounded) are unchanged, and there are no optimality cuts.

      There are some cases where people (myself included) will extend Benders decomposition, using a feasibility-only subproblem that is not an LP (and maybe not a mathematical program of any kind). Typically, in cases like this, the master problem has binary variables. Again, you only get feasibility cuts, not optimality cuts. How you generate them depends on the specific nature of the subproblem.

      Delete
  9. Professor Paul
    i have tried to apply the cplex.param.benders.strtegey with 3, but i have an exception which say : exception = CPLEX Error 2004: problem not compatible with Benders.

    Thanks for any help.

    ReplyDelete
  10. Dear Professor Paul,

    Is it possible to use any of the new Benders framework options (annotated, workers, automatic), if lets say we are solving the subproblems by employing column generation?

    Thanks.

    ReplyDelete
    Replies
    1. Vedat: No, that is not an option. You can, of course, still do your own Benders decomposition using a callback.

      Delete
  11. Dear Prof. Rubin,

    I am trying to learn working with this new way of Benders implementation through Annotation. I tried to follow your code example. Can you please illustrate any change needed in code if my subproblem is separable over scenarios (indexed by 's')? I tried to annotate my second stage 4-indexed flow variable x[i][j][t][s] as follows:

    code snippet 1:
    x = new IloNumVar[num_source][num_destination][num_period][num_scenario];
    for(int i = 0; i<num_source; i++)
    for (int j = 0; j < num_destination; j++)
    for (int t = 0; t < num_period; t++)
    for (int s = 0; s < num_scenario; s++)
    x[i][j][t][s] = cplex.numVar(0.0, 1, "X("+i+")("+j+")("+t+")("+s+")");

    code snippet 2:
    for(int s = 0; s <num_scenario; s++) {
    for (IloNumVar[][][] x1 : x) {
    for (IloNumVar[][] x2 : x1) {
    for (IloNumVar x3[] : x2) {
    for (IloNumVar x4 : x3) {
    wholeModel.setAnnotation(benders, x4, (s+1));
    }}
    }
    }

    However cplex threw an error, stating that the decomposition is wrong. Am I doing a syntax error somewhere? I want to set x[i][j][t][0] for subproblem 1, x[i][j][t][1] for subproblem 2 etc until num_scenario.

    Thanks in advance for your time.

    Jyotirmoy Dalal

    ReplyDelete
    Replies
    1. I'm pretty sure your Java code does not do what you think it does. What happens if you get rid of the innermost loop (looping over x3), move the outermost loop (looping over s) to innermost, and inside the "for (int s=0, ...)" loop change the middle argument of setAnnotations to x3[s]?

      Delete
    2. Thanks a lot for the help, Prof. Rubin. Your explanation helped to fix the issue. A related question: is there a way to check if the desired decomposition has really been followed? For example, in case I use FULL decomposition strategy, can I see how CPLEX chose to decompose a MIP? I saw the content of ".ann" file, but not sure whether the "values" entries represent the subproblem numbers.
      Also, as we now have the option of providing an annotation file to CPLEX as an input, how can one generate the xml structure for a large scale instance?
      Any pointer?

      Regards
      Jyotirmoy.

      Delete
  12. Yes, the value entries in the .ann file are the subproblem numbers, and as far as I know that is the only way to see how CPLEX did the decomposition. As far as generating your own annotation file, I suppose you would want to write a script or program to do so. You could use a library designed for output XML files, but the structure is simple enough you might be just as well off just writing the tags yourself. Your XML generating program would need to use the same variable names that your MIP program assigns to the variables.

    ReplyDelete
  13. Dear Prof. Rubin,

    Thanks for your valuable blog.

    I was wondering is there any way to add some arbitrary optimality cuts to the Benders master problem when we are utilizing built-in IloBenders?
    In other words, do we have access to the master's surrogate variable/s when we use IloBenders?

    Thanks

    ReplyDelete
  14. By "IloBenders" I assume you mean the built-in Benders decomposition. I'm not aware of any way to access the surrogate variables, and in any case I don't think you would be able to use the information. According the user manual (Discrete optimization > Advanced programming techniques > Generic callbacks > What is a context ...), the built-in Benders algorithm is "incompatible" with the candidate, relaxation and branching callback contexts. The "candidate" context would be where you would want to add optimality cuts.

    ReplyDelete
  15. Dear Professor Paul,

    Thank you so much for this impressive blog, going through it I learned a lot. I am trying to implemented benders manually going through your code (Manuelbenders). My sub-problem becomes is feasibility problem since no costs are associated with the continuous var,
    hence an objective function of constant 0 and only constrains to be satisfied given the fixed integer variables from the master problem.

    After solving the sub-problem , in the first iteration the sub is infeasible I tried to get the Farkas certificate, hence I did as you suggested:

    IloConstraint[] constraints = new IloConstraint[N]; however constraints is filled with null and obviously java.lang.NullPointerException is raised. The log shows following information:

    Iteration log . . .
    Iteration: 1 Dual objective = 0.000000
    CPXPARAM_Preprocessing_Presolve 0
    CPXPARAM_LPMethod 2
    CPLEX status: Infeasible
    is Primal feasible: false
    is Dual feasible: true

    Is it because my dual is feasible ? If yes how to resolve this issue?
    Thank you so much in advance.

    ReplyDelete
    Replies
    1. Sorry, I'm having trouble understanding your question. Yes, the constraints[] array is initially filled with nulls. The integer N must be the number of constraints in the subproblem. After you pass constraints[] as an argument to IloCplex.dualFarkas() (along with a double array of the same dimension), it should be filled with the constraints from the subproblem. Is it not?

      Delete
  16. Thank you professor for your prompt reply. Actually, I had an error in the number of constraints N. After getting it right, indeed both the constraints array and the coefficient double array were filled.

    However, after adding the feasibility cut (the sumproduct of the coefficients and the rhs of the constraints is = 263529.0 :( ) making the master problem infeasible, although the original problem was solved using usual MIP model.

    What could have caused the issue in the sub-problem ? Thank you in advance for your time and help.

    Best regards.



    ReplyDelete
    Replies
    1. Did you take into account the order of the returned array entries? The reason for the first argument to dualFarkas() (an initially empty array of constraints) is that CPLEX does not return the dual values (second argument) in the same order that you specified the constraints in the original model. So you need to use the first argument to figure out which dual value goes with which constraint.

      Delete
  17. Thank you Professor for your reply. Indeed my rhs HashMap didn't have the correct constraints (I should probably stop coding after work hours). Thank you for precious guidance.

    However professor, I am having difficulties understanding an issue.

    For some problems, both STANDARD MIP and MANUALbenders give the same result, however when I use CPLEX automatic benders regardless of the strategy (FULL, WORKERS, or USERS),
    CPLEX raise this warning BENDERS WARNING: no sub-problems left, and the problems become infeasible.

    The annotation file below shows that only some variables have the same value.

    CPLEXAnnotation name='cpxBendersPartition' type='long' default='0'
    object type='1'


























    I am wondering my CPLEX annotate the same variables which are continuous and should be in the same sub-problem, to different sub-problems, or am I missing something?
    Even when use the strategy USER and annotate the variables like this cplex.setAnnotation(benders, y, 1) for every variable I have the same issue.

    Thank you for your time and help. It is greatly appreciated.
    Best regards.

    ReplyDelete
    Replies
    1. There is a large gap in your comment above, which makes me wonder if perhaps something was inadvertently omitted. In any case, a detailed question like this is better suited to a Q&A forum. I would suggest either the IBM Data Science Community forum or Operations Research Stack Exchange. The links to those are in the right margin of the blog (under "Places to Ask Questions").

      Delete
  18. Yes actually it was the CPLEX annotation file given by cplex.writeBendersAnnotation ommited probably for some not accepted characters. It was supposed to look something like this CPLEXAnnotation name='cpxBendersPartition' type='long' default='0'
    object type='1'
    anno name='y_0_0_0' index='0' value='1'
    anno name='y_0_0_1' index='1' value='2'
    anno name='y_0_0_2' index='2' value='3' etc.

    Ok sure thank you so much for your swift replies. They have been very helpful.
    Best regards.

    ReplyDelete
  19. Dear Dr. Rubin,
    Thanks for your helpful blog; I've learned a lot.
    I have a question about improvements we can have in benders decomposition. Lets say we have N sub problems and each of them has an optimality cut. Is it possible to add linear combination of them to master problem by using annotations? In general do we have access to generated cuts by benders algortihm?

    Also, I was wondering if we can annotate the constraints of original problem (instead of variable) in CPLEX Benders Strategy.

    Once again, thanks for the blog!

    ReplyDelete
    Replies
    1. You're welcome. The answers to all three questions are (AFAIK) "no": you cannot use annotations to combine the cuts, I don't know of a way to access the cuts generated by CPLEX, and there is no provision for annotating constraints. (They automatically go into whichever problem makes sense given the annotations of the variables.) If you want to generate Benders cuts for multiple subproblems and then combine them somehow, you will need to use callbacks (which means creating the subproblems and master problem yourself, solving the subproblems when the master problem has a candidate solution, getting the individual cuts and then doing whatever magic you have in mind before adding the resulting cut to the master from within the callback).

      Delete
    2. Dr. Rubin: Thanks a lot for help. I just forgot to ask one last question. In IBM documentation, its been mentioned that we can annotate all parts of model including constraints (First paragraph of: https://www.ibm.com/docs/en/cofz/12.10.0?topic=algorithm-annotating-model). I was wondering if you can explain a little bit about annotating constraints.

      Delete
    3. I am not sure, but I suspect that when IBM added annotations to CPLEX they added capabilities beyond what is used for Benders decomposition (or anything else at the moment). In other words, they put in "plumbing" for future possible uses. I'm not aware of any current use for long annotations of constraints or objective functions, nor any use whatsoever for the DoubleAnnotation class that they also added.

      Delete
  20. Hello again Prof Rubin,
    I'm confused about using Lazy Constraint Callback (LCC) in CPLEX Benders Strategy. As far as I understand, I should add LCCs using LasyConstraintCallBack; however, I have no idea how should I annotate LCCs so CPLEX be able to consider them. Am I even in right direction?
    Thanks for your time in advance.

    ReplyDelete
    Replies
    1. Annotations are not used with lazy constraint callbacks (or any other kind of callback). If you click the Benders link in the labels section (bottom right area of every post here) you will get a list of posts I've done involving Benders. Some of them describe the use of callbacks, and most have links to Java code.

      Delete
  21. Dear Prof. Rubin,
    AFAIK, automated benders put integer varaibles in MP and other in SP(s). However, when I tried to have same conditions using WORKER strategy, it doesn't respond same, and I wondered why. Any ideas?
    Bests

    ReplyDelete
  22. I don't know how to interpret "doesn't respond same". I think you are correct about automatic Benders.

    ReplyDelete

Due to intermittent spamming, comments are being moderated. 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 Operations Research Stack Exchange.