Originally posted by: Selectedbetter

Hello everyone!
We now try to use a simple example to write the benders code.
The problem is:(image)

We have already written the benders code, and here is the code:

TESTone.cpp|View Details

Though the code can run with no error, but the result is wrong.We don't know where would be wrong.

Maybe we don't know how to express correctly in somewhere, just like get the extrem point of the worker problem.
Coule someone can give us some advice?
Thanks a lot!
 

"Result is wrong" is not very informative. If you get a solution that is superoptimal (optimal or better) but infeasible, it could be infeasible for one of two reasons. First, it might violate a constraint that should be part of the master problem. You can check that by substituting it into the constraint that was supposed to cut it off, and see why that fails. Second, it might violate a constraint not part of the original master problem that should have been generated by your subproblem. In that case, you should review your subproblem code and try to see why it would fail to cut off that solution.

On the other hand, if you get a solution that is feasible but suboptimal, then at least one of the constraints (either in the original master or added as a Benders cut) is formulated incorrectly. You need to figure out the true optimal solution, then substitute it into each constraint and each Benders cut generated until you find the one that it violates.

If you get a solution that is both suboptimal and infeasible, do both the above.

Originally posted by: Selectedbetter

Thank for you reply!

We think the constraints of the simple problem are all correct, so what lead to the wrong result would be the cut generated by subproblem.

We are not so familiar with the C++ API, hence we think there would be some wrong in using the codes, especially how to get the extrem point. 

For example, if the subproblem is optimal, we want to get the extrem point of dual variables,like alpha, beta and gamma, to genera the cut.

else if(cplex.getStatus() == IloAlgorithm::Optimal)
    {
        IloNumArray alphaR(env,NumVars);
        IloNumArray betaR(env,NumVars);
        IloNumArray gammaR(env,NumVars);
        
        cplex.getValues(alphaR,alpha);
        cplex.getValues(betaR,beta);
        cplex.getValues(gammaR,gamma);
        
        cutLhs.clear();

        cutLhs+=alphaR[0]*(2*x1-3*x2);
        cutLhs+=betaR[0]*(11-2*x1+x2);
        cutLhs+=gammaR[0]*(7-x1-x2);
                        
        alphaR.end();
        betaR.end();
        gammaR.end();
       
        violatedCutFound = 2;
    }

Is that right? When we only consider the situation of unbound of subproblem, the result is suboptimum, and then comes to the situation of both unbound and optimal of subplem, there is no available solution.

What can we do under this condition?  Maybe all because we could not realize the benders with what we have grasped of C++API.

Could you please give us some tips or find what is uncorrect in our code?

Thanks!

I don't use the C++ interface, so I can't comment on whether your use of the API is correct. It seems, though, as if you generate a cut any time your subproblem is solved to optimality. Your master problem should contain one continuous variable, which is a surrogate for the contribution of the y variables in the master problem objective. Assuming your subproblem (this is the dual to the actual subproblem?) has an optimal solution, you should generate a Benders cut only if the subproblem objective is strictly greater than the value of that surrogate variable in the proposed master solution. I don't see that check in your code segment.

Originally posted by: Selectedbetter

Thank for you reply!

The surrogate variable in our code is tempZ0, and it is a continuous variable in master problem.

When we  generate a Benders cut, we consider unbound and optimal of subproblem which is dual to the actual subproblem.

Just like:

if (sepStat = 1)
    {
        add(cutLhs <=0).end();
    }
    else if(sepStat = 2)
    {
        add(cutLhs <= tempZ0).end();
    }

Is there another items need to be judged by if?

We are very puzzled.

Is there anyone use C++API can help us?

If you really have "sepStat = 1" rather than "sepStat == 1", that is in all likelihood a bug. Otherwise, how is sepStat defined, and in particular under exactly what circumstances will sepStat equal 2?

Originally posted by: Selectedbetter

Dear Paul,

In the iloatsp.cpp which is a example of benders, it use   "sepStat = 1" rather than "sepStat == 1".

But ,when we correct it to "sepStat == 1", the result is right.

And should we only see the ObjValue of master problem? The GAP of the result is 120.69%, it's unreasonable.

Is it a right result?

What's more, when the problem is optimal, we want to output the result of variables, but it fails though we tried several ways. Just like:

if ( solStatus == IloAlgorithm::Optimal ) 
          {
              IloNum x1Result;
              IloNum x2Result;
             

              x1Result= masterCplex.getValue( x1Result);
              or  x1Result=getValue( x1);

              or masterCplex.getValue(x2Result,x2);

              masterEnv.out() <<"x1="<< x1Result<<endl;
              masterEnv.out() <<"x2="<< x2Result<<endl;

              ......

}

Do you know where is the fault?

Thanks!

In the iloatsp.cpp which is a example of benders, it use   "sepStat = 1" rather than "sepStat == 1".

I assume you mean ilobendeersatsp.cpp; there is no iloatsp.cpp that I can find. The line

if ( cplex.getStatus() == IloAlgorithm::Unbounded ) {

in that file clearly uses the logical comparison (==) operator, not the assignment (=) operator.

The GAP of the result is 120.69%, it's unreasonable.

The final gap is zero (or at least close enough to zero to satisfy the relative MIP gap tolerance). CPLEX does not necessarily print a line of log output every time the gap changes. When the feasible solution with objective value 29 was found (at the root node), the best bound known to that point left a gap of 120.69%. Additional operations at the root node apparently reduced the gap to below the default gap tolerance, so CPLEX terminated. The message "Solution status: Optimal" tells you that this happened.

As to how to recover the optimal variable values, check any of the C++ code samples (including ilobendersatsp.cpp). They will show you the proper method.