Accelerate Bender's decomposition using CPLEX

[sam_Hab]

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
BendersStrategy 3
$offEcho

option optcr =0;
option limrow =0;
option limcol =0;
option reslim =1800;
option solver = cplexd;
option solveLink = %solveLink.loadLibrary%;
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;
Execute_unload;
my_model.optFile = 3;
Solve my_model minimizing cost using mip ;
Put_utility 'exec' / 'gdx2xls  my_model.gdx ';

[bussieck]

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]

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?