Originally posted by: andvise

Hello!

I'm trying to improve the performances of a MILP with Benders decomposition. The problem is known to be efficiently solved with Benders. It similar to the Facility locations problem. 

The master problem contains only binary variables. The subproblems only linear ones. 

I tried:

• to set the Benders strategy to 1 (User) and annotate to different subproblems the linear variables
• to set the Benders strategy to 1 and annotate to a single subproblem the linear variables
• to set the Benders strategy to 3 (FULL). This behave like the previous decomposition.

In all the cases the computational times are identical, only in the first case the number of Benders cut is different.

What is surprising is that the performances are strongly worse than the normal MIP model solved with CPLEX, between 2 to 10 times. 

In my machines (I tried in 3 different ones), even in the Facility example available in CPLEX, "No Benders" outperforms the Benders decomposition, even if the test instance is particularly small.

My env is Ubuntu 18.04 with CPLEX 12.8 and Python 3.6

My questions are:

• Is there any problem with my configuration of CPLEX? Is it normal that in the facility example Benders is outperformed?
• Why dividing the variables in independent subproblems instead of a single subproblem is not improving(nor changing) the performances? 

I attach the CPLEX output of my model and of the facility example.

Thanks in advance,

Andrea

Originally posted by: dominiqs81

The performance of the Benders algorithm w.r.t. regular branch&cut is quite difficult to predict. And in particular if the instance is small regular branch&cut can indeed be (much) faster, even if the problem class is amenable to Benders.

Can you share the model (and annotation) so that we can do some tests?