0
$\begingroup$

currently I am working on implementing Benders Decomposition for a large-scale stochastic MIP in C++ using the CPLEX Solver. I've been spending the last couple of months learning the programming language, understanding the method and now I feel ready to tackle this problem.

Nevertheless, I feel a bit overwhelmed and I am worried I'm moving in a wrong direction with how I structure my code. For that reason, I wanted to ask if some of you have some tips on the best way to implement Benders?

Maybe there even exists some kind of guide to help me along the way?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Recent versions of CPLEX (12.7 or later) have built in support for Benders. You can let CPLEX decide what to put in the master problem and what goes in the subproblems, or you can use annotations to specify what goes where. I did a blog post about it quite a while back.

If you want to code your own, you might wish to look at some examples that ship with CPLEX Studio. If X is the installation directory for CPLEX Studio, look in X/cplex/examples/src/cpp. Examples you might find interesting are facility.cpp, ilobendersatsp2.cpp, ilobendersatsp.cpp and ilobenders.cpp.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for that helpful explanation! I have another quick question. If I model my stochastic problem in CPLEX and solve it using the standard solver, obviously it needs the deterministic equivalent model (DEM) to work with. Now, if I want it to use automatic Benders to solve the problem (Benders Strategy Parameter set at 3 (FULL), do I also use the DEM as the base model that I give to the solver? Or is there a different approach that is more efficient? Right now for my problem, standard solving technique of CPLEX is way faster than using Benders set to 3. Both are slow though overall. $\endgroup$
    – Arctic_Skill
    Sep 6 at 14:43
  • $\begingroup$ Sorry, no idea. I don't do stochastic optimization. $\endgroup$
    – prubin ♦
    Sep 6 at 15:43
  • $\begingroup$ No worries! I'll try to find more info on it. $\endgroup$
    – Arctic_Skill
    Sep 7 at 6:58
1
$\begingroup$

For example, If your problem is two-stages stochastic programming, then you can separate your problem into master problem and sub-problem by your hands. Then you can use CPLEX to model both stages in different files, then go back to your main function to call them respectively. In addition, based on different situation to generate feasibility cuts or optimality cuts until your gap within the tolerance you setting.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.