Benders decomposition and two stage stochastic Programm

[Christin]

Hello,

i know that you can't use the Stochastic Benders Decomposition on a mixed integer two stage stochastic linear Programm with mixed integer in the recourse.

So my idea is, to transform my stochastic programm in the equivlant deterministic one and use the normal benders decomposition module ( NOT stochastic). So the master problem consists of all integer variables and the subproblems of all continous ones.
This really drastically reduced my solving time but only for small numbers.The thing is, that for 5-15 nodes my solving time is lower than 1 second, but for 20 nodes it needs 500s to solve this problem. Furthermore, by adding one more scenario it takes for 20 nodes more than 1000s.

My new idea is to tell AIMMS to use the benders decomposition for the determinitic MILP but to give him the "first-stage-variables" of the stochastic programm as master variables, and the "second stage variables" of the stochastic programm as subproblem variables, which leads to creating a subproblem for each scenario.
Is this possible with AIMMS or are there some limitations?
Or are there any other ways to reduce my solving time?

Thank you for your answers!
Best regards,
Christin

[Marcel Hunting]

Hi Christin,

Using the normal Benders' decomposition module to solve the deterministic equivalent of a stochastic program with integer variables is a clever approach.

Unfortunately, creating a subproblem for each scenario will not work as the normal Benders' decomposition module does not support multiple subproblems.

You could try out different Benders' modes (Classic, Modern, TwoPhaseClassic or TwoPhaseModern). Are you using the defaults settings for the Benders' parameters (UseDual, FeasibilityOnly, etc)?

What do you mean by nodes? The number of branch-and-bound nodes?

Which solver (CPLEX, Gurobi, CBC,...) are you using?

Best regards,

Marcel Hunting

AIMMS

[Christin]

Hello Marcel,

thank you for your quick answer.

First of all I'm using the CPLEX solver.

What I mean with nodes : (I'm sorry for not explaining) I have a location problem on a graph. In other words: I try to find the best node(s) on my graph for installing hubs (first stage) and to find the cheapest route for sending products from and to all nodes (second stage). I am trying to increase my number of nodes for using realistic data with about 50-100 nodes.

I already tried all Benders modes and TwoPhaseModern is the best so far. But in comparisson to the normal standard CPLEX solver, I could hardly reduce the solving time when the problem gets bigger ( around 20 nodes). If i have less than 20 nodes, the benders decomposition is 100times faster than CPLEX.

Yes I'm using the default setting for benders. Where can I change the settings for the Benders' parameters? I would really like to try that!

I also think that the integer L-shaped method would reduce my solving time, but I think it's impossible for me to implement that without examples ( I'm quite new with AIMMS). Do you know any similar examples or detailed manual descriptions which might help ?

Thank you so much for your help.

Best regards,
Christin

[Marcel Hunting]

Hi Christin,

You could try the solver Gurobi, both when solving the model directly and with Benders.

The parameters in the Benders' module can be found in the section 'Benders Control Declarations'. You can change them by adding:

   GMPBenders::FeasibilityOnly := 0;

   GMPBenders::UseDual:= 1;

before the call to the Benders' procedure. But usually the default settings work best. I've not seen an example for which changing the setting of one of these parameters resulted in a speed-up.

I've never tried to implement the integer L-shaped method and we do not have an example for that, so I am afraid that I cannot help you much with it.

If you want, you can send your project to our support (or add it here) such that I can take a quick look.

Best regards,

Marcel

[Christin]

Dear AIMMS Team,

i successfully used the deterministic Benders Decomposition to divide my deterministic large scale mixed integer program( originally a two stage stochastic programm) in one master problem with all integer, and one subproblem with all continuous variables. My aim was to improve my solving time.  Now I have some problems with interpreting the results.

While trying all variants of the Benders like the classic, two phase classic, modern and two phase modern approach, i realized that the modern/twophasemodern approach worked best for my problem. After reading the referenced blog site with the explanation of the difference between these variants, it seems that the only difference between the classic and modern approach is the use of the single MIP search tree in the modern variant. Which means, that by using the classic approach in my case, the benders decomposition revisits many times the same nodes?

Furthermore I tested some other options for UseDual, AddTighteningConstraint and FeasabilityOnly.
This worked best for me  :
GMPBenders::UseDual := 0;   
GMPBenders::FeasibilityOnly:= 0;

Changing the AddTighteningConstraint didnt make such a difference in my solution time.
Is there any explanation why these options work best? It seems obvious to me that using feasibility and optimality cuts is always better than only using feasibility cuts, but i'm surprised that this is not the standard option in AIMMS when using benders?

What does it mean not to use the Dual of the Subproblem? Does Aimms solve the primal problem then and uses the dual variables only for generating the cuts? If yes, then i assume that it has no effect wheter using the dual oder primal subproblem for generating the cuts, because of the duality theory we get the same solution anyway? The only difference in my case is, that the primal subproblem is easier to solve than the dual one?

In addition to that, in my specific case the performance of the Benders Decomposition really depends on some constraints in my problem. So if i generate a tighter upper bound for one specific constraint in my problem, then CPLEX Solver is faster than the Benders Decomposition. If i generate a higher upper bound, then benders decomposition is much faster. Does the benders decomposition really depend so much on the specific problem that even the change of one parameter can influence the solving so much?

Do you have any suggestions for further reading about the performance of benders? I already read in this forum, that only the l-structure of the problem doesnt gurantee the successfull perfomance of benders and "if you take a random MIP problem then the chance that Benders' Decomposition module will be more efficient than CPLEX or Gurobi is small. The MIP problem has to "lend" itself to Benders' Decomposition.".

Thank you for your help.
Best regards,
Christin

[Marcel Hunting]

Hi,

Q: Which means, that by using the classic approach in my case, the benders decomposition revisits many times the same nodes?

A: That is correct.

Q: Changing the AddTighteningConstraint didnt make such a difference in my solution time.

A: It only has an effect if the model has some special structure. See section 21.5.5 of the Language Reference (AIMMS 4).

Q: Is there any explanation why these options work best? It seems obvious to me that using feasibility and optimality cuts is always better than only using feasibility cuts, but i'm surprised that this is not the standard option in AIMMS when using benders? 

A: FeasibilityOnly means that AIMMS will first reformulate the model such that the objective coefficients of the continuous variables are moved from the objective to the constraints (see section 21.5.2 of the Language Reference). That way the subproblem becomes a pure feasibility problem and therefore only feasibility cuts are added. The main advantage of this approach is that the feasibility cuts can be normalized according to M. Fischetti, D. Salvagni, and A. Zanette (2010). This normalization cannot be used if optimality cuts are added. In our experiments the approach using normalized feasibilty cuts was the most effective, and therefore that was made the default approach.

Q: What does it mean not to use the Dual of the Subproblem? Does Aimms solve the primal problem then and uses the dual variables only for generating the cuts? If yes, then i assume that it has no effect wheter using the dual oder primal subproblem for generating the cuts, because of the duality theory we get the same solution anyway? The only difference in my case is, that the primal subproblem is easier to solve than the dual one?

A: If UseDual equals 0 then AIMMS uses the primal subproblem and the dual variables to generate the cuts. If one of the subproblems has multiple optimal dual solutions (as is often the case in practice) then the solutions paths will be different. If the primal problem is easier to solve you should set UseDual to 0 and otherwise to 1.

Q: In addition to that, in my specific case the performance of the Benders Decomposition really depends on some constraints in my problem. So if i generate a tighter upper bound for one specific constraint in my problem, then CPLEX Solver is faster than the Benders Decomposition. If i generate a higher upper bound, then benders decomposition is much faster. Does the benders decomposition really depend so much on the specific problem that even the change of one parameter can influence the solving so much?

A: You do not mention the influence of setting this upper bound on CPLEX (only the relative influence compared to Benders). One possible explanation could be the following. CPLEX will do preprocessing using the complete model, including "relations" between integer and continuous variables. That last part Benders misses as it separates the integer part from the continuous part. You could try using the function GMP::Instance::CreatePresolved to create a preprocessed GMP using the AIMMS presolver, and use that GMP for Benders. However, the AIMMS preprocessor is much less powerful than the CPLEX preprocessor, at least for linear models, so probably this will not improve the performance.

Q: Do you have any suggestions for further reading about the performance of benders? I already read in this forum, that only the l-structure of the problem doesnt gurantee the successfull perfomance of benders and "if you take a random MIP problem then the chance that Benders' Decomposition module will be more efficient than CPLEX or Gurobi is small. The MIP problem has to "lend" itself to Benders' Decomposition.".

A: The Benders' cuts that are generated use the solution of the complete subproblem. In case of 2-stage stochastic programming the subproblems are independent. It might be that you would get better Benders' cuts by solving the subproblems separately, but that is currently not supported by the Benders' Decomposition module.

Best regards,

Marcel Hunting

AIMMS Optimization Specialist

[Christin]

Hallo Marcel,

thank you very much for your response. It was really helpfull!!!

I wouldn't have asked all this question if i found the updated language reference before! I would kindly ask you to update the link in  :

http://www.aimms.com/downloads/manuals/language-reference/

Because there i only get the version of 2012 without anything about the Benders Decomposition. I think it would be really helpful for other users, too.

Thank you really much!
Best regards,
Christin