Decision Optimization

 View Only
Expand all | Collapse all

How to add user cuts with Benders decomposition

  • 1.  How to add user cuts with Benders decomposition

    Posted Thu April 09, 2020 04:08 PM

    Originally posted by: victorrn

    I'm working on a variant of the MST problem with a set x_ij of binary variables and a set u_i of float variables. Currently I'm adding SECs as user cuts, and I've tried to test the performance of the benders decomposition. I've tried to use the default benders from cplex but in order to make it work I had to turn off the user cuts. Is it possible to use both the Benders and the user cuts?


  • 2.  Re: How to add user cuts with Benders decomposition

    Posted Tue April 14, 2020 06:27 AM

    Originally posted by: AndreaTramontani


    unfortunately user cuts and lazy constraints are not compatible with automatic Benders decomposition. More specifically, in the automatic Benders algorithm there is currently no support for lazy constraint pool, user cut pool, control callbacks. Similarly, even if the new callback framework (generic callback) is partially supported in Benders, there is no support for CANDIDATE context, RELAXATION context, BRANCHING context. In other words, even from within the generic callback framework it is not possible to add user cuts and lazy constraints in Benders.

    As a partial workaround, a possibility for you could be to separate somehow some SECs a priori, to tighten the LP relaxation of the initial model, then add those SECs as hard constraints to the problem, and solve the resulting tightened model with automatic Benders decomposition. Of course this is correct only if the SECs are conceptually user cuts (i.e., they are useful to strengthen the model but they are not needed for the completeness and correctness of the model).