Originally posted by: lxysjtu

Dear all,

I am implementing the Benders decompositon algorithm, following the example "bendersatsp.c".  In this example, the lazyconstraintcallback is used to add cut for unbounded subproblem. My question is how does CPLEX accept a feasible solution? In the lazyconstraintcallback, if the subproblem is feasible, no cut is added. Then how does the callback tells CPLEX that this is a feasible solution and update the incumbent?

Another question is that suppose in the benderscallback,  the subproblem is feasible and I can get an upper bound using some method. That is, the upper bound is indirectly determined by sovling a problem defined by the node solution. How can I tell CPLEX to update the incumbent, if it applies.

Thanks,

Shaon  

There is no need to explicitly accept a solution in a lazy constraint callback. The proposed solution is accepted unless the callback generates a constraint.

You cannot inject an incumbent from the lazy constraint callback. You need to use a heuristic callback for that (and potentially communicate your solution from the lazy constraint callback to the heuristic callback). Or you can use the new generic callback, see the bendersatsp2 example.

Originally posted by: lxysjtu

Thanks. You mean that if I add an optimality cut in the benderscallback, the proposed solution is not accepted. Actually it is a feasible solution and may be an incumbent. 

In the benderscallback, I always add either optimality cut or feasibility cut. As a result, when will CPLEX accept an integer solution?

Originally posted by: lxysjtu

Thanks, Daniel. How to inject a feasible solution in the generic callback? I saw CPXcallbackpostheursoln can be used for this purpose. But it is pointed in the manual:  

You must not call this routine with Benders algorithm in any context

Thanks.

Originally posted by: dominiqs81

You cannot call CPXcallbackpostheursoln() if you are using CPLEX internal implementation of Benders. However, I understand that you are implementing Benders yourself, so the restriction does not apply.

In Benders, a feasibility cut is added only if the proposed incumbent is infeasible in the subproblem (in which case it is infeasible in the original problem and cannot possibly be a new incumbent). An optimality cut is added only if the proposed incumbent is feasible but the master variable that acts as a surrogate for the objective contribution of the subproblem variables is wrong (too small in a min problem, too large in a max problem). In that case, the optimality cut causes the proposed incumbent to be rejected, but the master solver is free to come back with the same values of the integer variables and a new (hopefully correct) value for the surrogate variable. The master solver can keep generating the same integer solution, with progressively less inaccurate values of the surrogate variable, until it gets a valid value for the surrogate. At that point, the callback generates no cuts and the solution is accepted as a new incumbent.

Originally posted by: lxysjtu

Thanks. My question is:

For feasible integer solution (the subproblem is feasible), I always find an optimality cut and add it to the master problem. So when will the callback generate no cuts? Or I need to check if the generated optimality cut is violated by the current solution.  If it is not vioalted, I should not add this cut, which means that the callback generate no cuts. 

As I said, the subproblem should generate an optimality cut only if the value of the surrogate variable is wrong. Let's say that you have a minimization problem with variables x in the master and y in the subproblem, and original objective function c'x + d'y. With Benders, you will minimize c'x + z in the master and d'y in the subproblem, where z is a new variable that represents the d'y term. When CPLEX finds what it thinks is an incumbent (x*, z*), it will send that solution to the callback, where you solve for y. Call the solution y*. If d'y* > z*, then z* is too small. Even if x* is okay, (x*, z*) is not a feasible solution to the master, and you add an optimality cut forcing z to be larger when x = x*. Eventually, CPLEX will find a solution where z* = d'y*. When that happens, you callback should not (must not) generate a cut.

If your callback is generating optimality cuts even when x* is integer-feasible and z* = d'y*, then your code is wrong.

Originally posted by: lxysjtu

Thank you very much. As you said, in the callback, I first need to check if the subproblem is feasible. If x* is infeasible, an optimality cut will be added. If x* is feasible, I then check if  z* = d'y*. If it is, the callback will not add an optimaility cut. Is it correct?

Originally posted by: open_ball

Hello Dr. Rubin,

Does (z* = d'y*) imply that we reached the optimal solution? I was reading one of your posts (https://drive.google.com/file/d/0B-BSG5eMtXyJZjc3NGY0MTUtMDBlYS00MjUzLWE5ODctOWQ2MzE2MDJmZjE3/view) In the diagram, when z* = d'y*, you indicate that we accept x,z. Does that mean we stop the algorithm?

No. You accept the solution as a new incumbent, but then you keep going until the search tree for the master problem contains no live nodes.

Originally posted by: lxysjtu

Do we need to check if  z* = d'y* when x is integer feasible?  Thanks.