Originally posted by: BerkUstun

I'm currently trying to implement a version of Bender's Decomposition using the CPLEX API in MATLAB. Unfortunately, I am running into a memory issue since I have to set up a giant LP each time I need to generate a feasibility cut.

As a reminder, you need to generate a feasibility cut when using Bender's Decomposition when your second stage problem is infeasible given your first stage solution. You can get the appropriate parameters for the feasibility cut by setting up a 'slack variable minimization LP' where you add slack variables to each constraint/bound and then minimize the total slack in the system. The issue with this LP is that it can get pretty big, prety fast (for an infeasible LP with N variables, M constraints and non-trivial upper and lower bounds, the feasibility cut LP needs a M+N constraints and N+2M+2N variables).

My main idea is to try and get the information I need from the infeasible primal problem. One fix that I had in mind was having CPLEX pass me the extreme ray when the primal is infeasible. Although CPLEX usually offers this functionality, https://www-304.ibm.com/support/docview.wss?uid=swg21400058. Does anyone know a way around this requirement?

Otherwise, I had was that I may be able to get around this idea using the FeasOpt method. Having said this, I'm somewhat confused about what exactly FeasOpt does and whether I can get the appropriate dual information using it.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am not familiar with the Matlab interface but if you are searching for possibilities of extracting rays from the infeasible LP, it has been already discussed sevral times in this forum.
Also Paul Rubin has a nice explanation of this in his blog here [url]http://orinanobworld.blogspot.com/2010/07/infeasible-lps-and-farkas-certificates.html[url]
The whole thing is to use DualFarkas function which i believe must also be available in Matlab Interface.

good luck
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

As a friendly comment, in the case you are facing with a huge problem and there is no guaranty for the master problem solution to be feasible in the sub-problem, PERHAPS you can would like also to think of reformulation of your problem to enure always-feasibility of MP solutions OR some alternative solution methods since Benders bound will not usually improve with feasibility cuts and you keep adding those cuts almost for ever.
#CPLEXOptimizers
#DecisionOptimization