[SCIP] Custom Benders Decomposition Implementation

[Maher, Stephen]

Hi Matheus,

Sorry for the delay in responding. I was away on leave and your question required a considered answer.

Unfortunately, we don't currently have an example available in the SCIP distribution that covers your situation. However, what you are trying to achieve is definitely possible. I have used the Benders' decomposition framework in SCIP with subproblems solved using combinatorial algorithms. That example will be included in a future release of SCIP. But until then, I will attempt to provide some guidance how to use a custom solving method.

If you wish to use a combinatorial algorithm to solve the subproblem, you will need to implement both a custom benders and benderscut plugin.

  *   The documentation that you reference about the benders plugin is a little out of date. You can now supply a NULL pointer to the SCIPaddBendersSubproblem method which is called within the BENDERSCREATESUB callback. By providing a NULL pointer to SCIPaddBendersSubproblem, you inform SCIP that a custom algorithm is used to solve the subproblem.
  *   Your combinatorial algorithm should be called from the BENDERSSOLVESUBCONVEX callback function (if the subproblem is an LP).
  *   In the BENDERSCREATESUB callback, you also need to inform SCIP about the subproblem type, i.e. whether it is convex with continuous variables, convex with discrete variables, non-convex with continuous variables or non-convex with discrete variables (the convex/non-convex relates to the relaxation of the subproblem). This is achieved by calling SCIPbendersSetSubproblemType. In your case, since you say that the subproblem is an LP, your subproblem type would be SCIP_BENDERSSUBTYPE_CONVEXCONT.
  *   Since you are using a custom solving method for the subproblem, the included Benders' cuts are not available (they will not be called because you have supplied a NULL pointer to SCIPaddBendersSubproblem). However, you can use available interface functions to generate optimality cuts from feasible subproblems. The plugin benderscut_opt (for the optimality Benders' cuts) has an interface method SCIPgenerateAndApplyBendersOptCut that can be called with an arbitrary set of dual values to generate an optimality cut. In your custom benderscut plugin, you are able to call this method. Unfortunately, there is no such method for feasibility cuts, but there are versions of feasibility cuts that use SCIPgenerateAndApplyBendersOptCut (see benderscut_feasalt).

By implementing the custom benders and benderscut plugins you will get access to most of the enhancements available with the Benders' framework, such as cut strengthening, two-phase method, and generating cuts from feasible solutions. If you use SCIPgenerateAndApplyBendersOptCut, then you will also get access to the methods that perform the mixed integer rounding procedure on the generated optimality cuts.

My above comment answers most of question 2. In short, you don't lose anything by implementing your own custom subproblem solver. The only "cost" is that you have to implement the benders and benderscut plugins.

I hope that this helps. Please let me know if there is anything that needs further explanation.

Cheers,

Steve

________________________________
From: Scip <scip-bounces at zib.de> on behalf of Matheus Ota <matheusota at gmail.com>
Sent: 27 August 2021 22:16
To: scip at zib.de <scip at zib.de>
Subject: [SCIP] Custom Benders Decomposition Implementation

CAUTION: This email originated from outside of the organisation. Do not click links or open attachments unless you recognise the sender and know the content is safe.

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<https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.scipopt.org%2Fdoc%2Fhtml%2FBENDER.php&data=04%7C01%7CS.J.Maher%40exeter.ac.uk%7C93cb4bed12db4555fb6c08d969a0646b%7C912a5d77fb984eeeaf321334d8f04a53%7C0%7C0%7C637656959859866300%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=oZMsGywa0yDlijqfxhYyrI%2FfXlHapFBQKoucIxBIPQw%3D&reserved=0>), 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<https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.scipopt.org%2Fdoc%2Fhtml%2FBENDERSCUT.php&data=04%7C01%7CS.J.Maher%40exeter.ac.uk%7C93cb4bed12db4555fb6c08d969a0646b%7C912a5d77fb984eeeaf321334d8f04a53%7C0%7C0%7C637656959859866300%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=gzCjqHHUIrS6vk3ciEeJBuTdmibENziJq4ZNWPRZUDw%3D&reserved=0>), 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/20210908/eb6f56cd/attachment.html>