Decision Optimization

 View Only
Expand all | Collapse all

Bender's decomposition implementation through lazyconstraints callback

  • 1.  Bender's decomposition implementation through lazyconstraints callback

    Posted Sat January 08, 2022 12:26 PM
    Dear all, 

    I'm implementing a bender's decomposition by using a lazyconstraints callback for adding feasibility and optimality cuts. The CPLEX object runs the master problem and the callback calls the subproblem solver to construct these cuts. However, this approach leads to an issue that CPLEX log reports "no solution" until the optimal solution has been found.

    I suspect this issue comes from optimality cuts are added through lazyconstraints. If a feasible solution is not optimal then it violates optimality cuts and so CPLEX views it as "infeasible" solution. Is there a better way to implement optimality cut so that CPLEX can still be aware of feasible solutions?

    Many thanks

    ------------------------------
    Yiran Zhu
    ------------------------------


  • 2.  RE: Bender's decomposition implementation through lazyconstraints callback

    Posted Sat January 08, 2022 02:30 PM
    The approach is correct, and there is no alternative way to implement the optimality cut. I think you may be misunderstanding how the optimality cut works.

    A suboptimal feasible solution does not necessarily violate an optimality cut. For concreteness, I will assume that the master problem's objective is minimization and that the master problem contains a surrogate variable representing the objective contribution of the subproblem variables. Violation of an optimality cut does not mean the solution is suboptimal; it means that the master problem solution is feasible, in the sense that the subproblem can find a feasible solution, but that the master problem is underestimating its objective value (the value assigned to the surrogate variable by the master problem is too small).

    Once the optimality cut is added, CPLEX should solve the LP relaxation at the current node again. That might result in the same integer solution with a higher value for the surrogate, which might yield a feasible solution (or might need another optimality cut). If it yields a feasible solution, that might be a new incumbent, or it might be cut off because it is inferior to the current bound (which does not appear to be the case in your runs). Alternatively, the fact that the optimality cut forced an increase in the value of the surrogate variable might result in the node LP yielding an entirely different solution.

    There is one more consideration, which could possibly explain what you are seeing. If you have an upper bound on the objective value, either as an explicit constraint, an explicit upper bound on the surrogate variable or a bound set using the upper cutoff parameter, the optimality cut added by the subproblem could make the master solution infeasible due to its violating the upper bound. In that case, CPLEX moves on to another node and you still do not have an incumbent solution.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------