CPLEX/Benders with LP problem

Solver related questions
Post Reply
Saviola87
User
User
Posts: 2
Joined: 2 weeks ago

CPLEX/Benders with LP problem

Post by Saviola87 » 2 weeks ago

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:

Code: Select all

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):

Code: Select all

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?

User avatar
bussieck
Moderator
Moderator
Posts: 645
Joined: 5 years ago

Re: CPLEX/Benders with LP problem

Post by bussieck » 2 weeks ago

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

Saviola87
User
User
Posts: 2
Joined: 2 weeks ago

Re: CPLEX/Benders with LP problem

Post by Saviola87 » 2 weeks ago

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

User avatar
bussieck
Moderator
Moderator
Posts: 645
Joined: 5 years ago

Re: CPLEX/Benders with LP problem

Post by bussieck » 2 weeks ago

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

Code: Select all

      It    Primal bound      Dual bound   #ocuts   #fcuts    Itcnt     Time
--Michael

Post Reply