CPLEX/Benders with LP problem

GAMS
1

Hi,

I would like to know if it is possible to exploit Benders decomposition contained in Cplex within a LP problem (not a MIP).

Attached you can find a super-simple code, wherein I don’t understand if GAMS is actually using the Benders decomposition using the information from the Cplex configuration file:

Variable
  x
  y
  obj;


Equation
  eq0
  eq1
  eq2
  eq3
  eq4
  eq5
  eq6
  eq7;

eq0.. obj=e=-y-(0.25*x);
eq1.. y =l= 5+x;
eq2.. y =l= 7.5 +(0.5*x);
eq3.. y =l= 17.5 -(0.5*x);
eq4.. -y =l= 10-x;
eq5.. x =g= 0;
eq6.. x =l= 16;
eq7.. y =g= 0;

Model loc / all /;

$onEcho > cplex.opt
BendersStrategy 1
x.BendersPartition 0
obj.BendersPartition 0
y.BendersPartition 1
$offEcho


option solver = cplex;

loc.optFile=1;

solve loc minimizing obj using lp;

The output that I obtain contains the correct solution, but also a Cplex error (code 1217):

Version identifier: 20.1.0.1 | 2021-04-07 | 3a818710c
CPXPARAM_Advance                                 0
CPXPARAM_Simplex_Display                         2
CPXPARAM_Threads                                 1
CPXPARAM_Benders_Strategy                        1
CPXPARAM_MIP_Display                             4
CPXPARAM_MIP_Tolerances_AbsMIPGap                0
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 4 rows, 2 columns, and 8 nonzeros.
Presolve time = 0.00 sec. (0.00 ticks)
      It    Primal bound      Dual bound   #ocuts   #fcuts    Itcnt     Time
       0                 -10000000000000        1        0        0     0.00

--- LP status (1): optimal.
--- Cplex Time: 0.00sec (det. 0.02 ticks)

CPLEX Error  1217: No solution exists.
--- Returning a primal only solution to GAMS (marginals all set to NA).

Optimal solution found
Objective:          -15.000000

--- Reading solution for model loc[LST:141]
***
*** Solver did not provide marginals for model loc
***
*** Status: Normal completion[LST:217]
--- Job Prova_S_opt.gms Stop 10/04/21 18:44:55 elapsed 0:00:00.232

Could you help me, please?

2

The Cplex Benders has been designed for MIP and that’s why Cplex does not offer any dual solution when an LP is solved with Benders. The GAMS/Cplex link tries to get the duals anyway (it might not know that you solved via Benders) and hence you get an error message from this call “CPLEX Error 1217: No solution exists.”. It’s actually okay that the call fails, you just don’t get a dual solution (which is written properly in the next line to the GAMS log “Returning a primal only solution to GAMS (marginals all set to NA).”). The channel Cplex writes the first error message to is sometimes useful and therefore redirected to the GAMS log but in this case very confusing.

At some stage we made some experiments with Cplex’ Benders for LP (stochastic models) and the performance was not great (even if you do not care for the dual solution). Barrier always beat Benders! The cuts just became numerically to bad.

-Michael

3

Thanks for the reply and also for your suggestions.

I would like to have a confirmation. I know that I won’t get a dual solution when an LP is solved with Benders, my final question is: in this implementation is the primal solution actually obtained through Benders decomposition?

I just need to make a performance comparison for a project, wherein the problem involved is more complex and stochastic (always LP) and so I would like to know if I can use the Cplex Benders as I posted in my first question.

Thanks

Matteo

4

If you Cplex log contains a header line telling you about the number of optimality andf feasibility cuts, I would say yes:

      It    Primal bound      Dual bound   #ocuts   #fcuts    Itcnt     Time

–Michael