## Accelerate Bender's decomposition using CPLEX

Problems with modeling
sam_Hab
User
Posts: 10
Joined: 11 months ago

### Accelerate Bender's decomposition using CPLEX

Hello everyone,
I am trying to apply the benders decomposition using CPLEX (strategy 3), I want to know if I am doing it the right way because I only found one example using it. Here is the link
https://www.gams.com/latest/gamslib_ml/ ... nders.html

Also, I want to know if there is an accelerated version of Benders using Cplex or is there any other possibility to accelerate it by adding heuristics or cutting plans using BCH facility? https://www.gams.com/latest/docs/UG_Sol ... CHFacility

Or can we use these CPLEX facilities Benders feasibility cut tolerance, Benders optimality cut tolerance or RLT cuts in GAMS: https://www.ibm.com/support/knowledgece ... eters.html

You find below my code:

Code: Select all

``````Sets i products / i0*i55 /
j suppliers / j0*j55  /
t time periods / t0*t55 /
sub_j(j)   dynamic subset for j
sub_t(t)   dynamic subset for t
sub_i(i)   dynamic subset for i ;

Alias ( k , t ) ;
Parameter D( i , t ) demand of product ;
Parameter C( i , j ) porduction capacity ;
Parameter P( i , j ) purchase price ( \$ per unit );
Parameter H( i ) product-dependent holding cost ( \$ per unit )  ;
Parameter O( j ) supplier-dependent ordering cost ( \$ per unit ) ;

Variables x ( i , j , t )
y ( j , t )
R( i , t )
cost ;

Positive Variables x ,R;
Binary Variable y ;
Equations obj objective function
con1 ( i , t )
con2 ( i , j , t ) feasibility constraint;

obj ..  cost =E= sum ( ( sub_i(i) , sub_j(j) , sub_t(t) ) ,P( i , j )* x ( i , j , t ))+sum ( ( sub_j(j) , sub_t(t) ) ,O( j )* y ( j , t ) )
+ sum ( ( sub_i(i) , sub_t(t) ) ,H( i ) * ( sum ( k\$ ( ord ( t ) GE ord ( k ) ) , sum ( sub_j(j) , x ( i , j , k))-D( i , k ) ) ) ) ;

con1 ( sub_i(i) , sub_t(t) ) .. R( i , t ) =E= sum ( k\$ ( ord ( t ) GE ord ( k ) ) , sum ( sub_j(j) , x ( i , j , k))-D( i , k ) ) ;

con2 ( sub_i(i) , sub_j(j) , sub_t(t) ) .. C( i , j )* y ( j , t ) - x ( i , j , t ) =G= 0 ;

display "---------------------formulation ----------------------";

\$onEcho > cplexd.op3
\$offEcho

option optcr =0;
option limrow =0;
option limcol =0;
option reslim =1800;
option solver = cplexd;
Model my_model /all/;

option savepoint = 3;
Scalar cpxOptFile;
File myput;
Put myput;
put_utility 'gdxin' / 'data.gdx';
execute_load D, P, C, H, O, sub_i, sub_j,sub_t;
my_model.optFile = 3;
Solve my_model minimizing cost using mip ;
Put_utility 'exec' / 'gdx2xls  my_model.gdx ';

``````

bussieck
Moderator
Posts: 322
Joined: 2 years ago

### Re: Accelerate Bender's decomposition using CPLEX

I am not sure I understand the question "if I am doing it the right way". But with BendersStrategy=3 you use Benders by putting the discrete variables in the first stage and the rest in the second stage. Benders requires all discrete variables to be in the first stage, but perhaps some continuous variables could also be placed in the first stage, that depends on your model. If you think that's the way to go you can use the user annotation in the GAMS/CplexD option file (or using the .stage variable suffix plus option "BendersPartitionInStage", see https://www.gams.com/latest/docs/S_CPLE ... ioninstage) and a different BendersStrategy (see https://www.gams.com/latest/docs/S_CPLE ... rsstrategy). The options you mention are all available in GAMS/Cplex:

- https://www.gams.com/latest/docs/S_CPLE ... feascuttol
- https://www.gams.com/latest/docs/S_CPLE ... soptcuttol
- https://www.gams.com/latest/docs/S_CPLE ... EXrtlcuts

The latter has nothing directly to do with Benders.

-Michael

sam_Hab
User
Posts: 10
Joined: 11 months ago

### Re: Accelerate Bender's decomposition using CPLEX

Thanks a lot for your answer, I was wondering if there is a way to add a heuristic to Benders decomposition under GAMS and how to do it?