Correct way to get a dual extreme ray for an infeasible LP in CPLEX / C++

Question

We are coding a Benders decomposition using CPLEX/Concert (C++) and we are having some troubles to generate a feasibility cut because we are not sure how to get an extreme ray of the dual for a primal infeasible problem.

According to this CPLEX FAQ, there are two ways to do that:

1. To solve the problem using Primal Simplex, and use getDuals()
2. To solve the problem using Dual Simplex, and use dualFarkas()

We are obtaining strange values using (1). We found some discussion (like this one) saying that getDuals only gives you a feasible point of the dual, not an extreme ray. I'm not sure if this is true.

We also tried method (2) following the instructions from this blog, but we are having trouble porting the Java's code to C++, apparently, because the order of the dual variables returned by dualFarkas() is not clear.

All previous blogs and forums are quite old (~2010). That's why I'm questioning myself which is the correct way to obtain this extreme ray.

Any help or hint is appreciated.

Answer 1

Can you elaborate a bit on what you mean when you say you are getting "Strange values"? One possible explanation is that if you call getDuals() on a model that includes some variables bounds other than $[0, +\infty)$, then your dual unbounded ray requires that you look at the reduced costs as well as the the dual variables returned by getDuals(). However, based on your comment that you didn't encounter this behavior with Gurobi, this seems somewhat less likely to explain this (unless you formulated the subproblem in Gurobi in a way that has such nondefault bounds, but your CPLEX subproblem uses just the default ones).

Regarding the other questions, when the primal simplex method has determined your problem is infeasible, getDuals() will return the dual variable values associated with the phase I objective from which infeasibility was determined. In the case where all variables have bounds of $[0,+\infty)$, this comprises the unbounded ray for the dual. That is also true if some of the primal variables are free variables. But if they have finite bounds, you also need to look at the reduced costs to properly construct the direction of unboundedness.

Regarding the order in which dualFarkas() the object oriented APIs returns dual variables, that depends completely on the order on which you pass the constraints in the first argument to this method. So look at the order in which the constraints were added when you built the model. If you built the model using a single IloRangeArray, then that gives you the order you seek. But, if you used multiple IloRangeArrays, or build it with individual statements where you didn't record a handle to point to some of the ranges being added (e.g. call model.add(x + y <= 2)), then you probably should maintain an IloRangeArray of handles to the individual linear constraints you created for the model, in the order you added them to the model.

And finally, regarding the experiment you are doing, note that CPLEX's automatic Benders also allows you to customize the boundary between the master and subproblems through variable annotations instead of letting CPLEX just decide the boundary. So if your Benders decomposition approach can be implemented by adjusting the boundary in this way, you might be able to just compare default and nondefault annotations.

Answer 2

Have not used CPLEX, but I've done that in Gurobi. In the latter, you just retrieve the equivalent of dualFarkas() when the primal version of the Benders subproblem you are solving is infeasible.