Originally posted by: open_ball

Hi,

I am implementing Benders decomposition with the lazy callback function in Java API. After I completed my implementation, the final result that I obtain turned out to be wrong (i.e., underestimated the true optimal for a maximization problem). When I get into the callback function, I solve the primal problem and use getDual() method to obtain the dual values to generate the Benders cut. 

I created a toy example where only six cuts are added into the pool. For every iteration, I stored the objective value and the optimal values for the primal variable.  For example, here is the results for the first iteration together with the cut generated.

objective of primal-> 1.0

x[0] ->0.0

x[1] ->0.0

x[2] ->0.0

x[3] ->1.0

IloRange  : -infinity <= (1.0*dual_estimation - 1.25*masterVariable_0  - 1.5*masterVariable_1 - 2.5*masterVariable_2- 2.25*masterVariable_3 - 3.75*masterVariable_4 - 5.0*masterVariable_5 - 1.0*masterVariable_6 - 0.75*masterVariable_7) <= 0.0

Now, just to make sure that these are correct values, for each iteration, I took the fixed master variables and solved the primal problem outside of my Benders implementation. It seems like everything is correct. That is why only thing that could be wrong is the dual values that I obtain via the getDual() method. 

Hence, I also stored the dual values and tried to match  them by solving the dual problem outside of the Benders implementation (I also coded the dual problem and fed the fixed master values into the dual). It turned out that dual values are way different than each other.  

When I create the primal, I store the constraints in a map.

ArcTime arcTime =new ArcTime(i,j,t)
…
IloRange constraint = (IloRange) sub.addLe(subVariable,upperBound.get(arc), "myConstraint_"+arcTime.toString());
constraintMap.put(arcTime, constraint);

Then, when I enter into the callback function, after solving the sub problem, I get the dual values as:

Iterator<ArcTime> set = indexSet.iterator(); 
         while(set.hasNext()){
                ArcTime arcTime = set.next();           
                IloRange constraint = constraintMap.get(arcTime);
                expr = cplex.sum(expr, sub.getDual(constraint) * constraint.getUB());   
        }

My only guess is that when I call the getDual() method, I might be doing something wrong. I was wondering if someone has any thought on what I could be doing wrong. 

Originally posted by: T_O

Do your variables have non-trivial upper or lower bounds?

Originally posted by: open_ball

Yes, they do. They are non-negative continuous variables corresponding the each arc. In fact, the map called upperBound.get(arc) stores the capacity of each arc. Also, when I define subVariable, I use 

        IloNumVar subVariable = sub.numVar(0,capacity.get(arc),"x_"+arcTime.toString());                                                                      
        sub.add(subVariable);                                                           
        subVariables.put(arcTime, subVariable);

By the way, I am not sure if they are related, but when I define sub = new IloCplex();, I was setting sub.setParam(IloCplex.IntParam.RootAlg, 3);  to make sure that the sub problem is solved via network simplex. When I comment it out, interestingly the solution obtained by Benders became different. It is still the wrong solution, but I believe this guarantees that my Benders cuts are wrong and that may be explained by the wrong dual values. 

Originally posted by: open_ball

Alright, your comment made me suspicious about my implementation and I changed the way I define my variable as 

 IloNumVar subVariable = sub.numVar(0,Double.MAX_VALUE,"x_"+arcTime.toString());

This actually solved my issue. Now, I am getting the correct result :) 

Originally posted by: T_O

You can use upper bounds if you also take their duals (the reduced costs) into account for the Benders Calculation, see e.g. here (including the comments).