[SCIP] Custom Benders Decomposition Implementation

[Matheus Ota]

Dear Scipers,

I'm currently implementing a branch-and-cut algorithm where my cuts come
from a Benders decomposition approach. Now I want to make use of the
enhancements in the Benders Decomposition framework to accelerate my
algorithm. However, my subproblems are quite big LPs, so I can't really add
them as whole LPs into the Benders Decomposition frameworks of SCIP. On the
other hand, these subproblems are quite tractable, and they can be
efficiently solved with a simple combinatorial algorithm. In this context,
I have two questions.

1 - Can I use the Bender Decomposition framework of SCIP only by
implementing the separation routines for the optimality and
feasibility cuts? Are there any examples available?
What I tried:
- I took a look into implementing my own Benders Decomposition plugin (
https://www.scipopt.org/doc/html/BENDER.php), however it says that I should
implement the BENDERSCREATESUB method, where I should add SCIP instances
for each subproblem (which I believe are LPs). Since my LPs are too big, I
believe this is not feasible.
- Then I considered implementing my own Bender Decomposition cut methods (
https://www.scipopt.org/doc/html/BENDERSCUT.php), but this requires a
corresponding Benders decomposition plugin.

2 - If the answer to Question 1 is Yes, will I lose too much of the
enhancements provided by the current Benders Decomposition framework
embedded in SCIP? Since then I would provides less information to SCIP (in
comparison with providing the whole LPs), I'm afraid that I might lose some
of the enhancements provided by the SCIP framework.

Thanks for being so helpful!
Matheus
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20210827/149d10c8/attachment.html>