[SCIP] Custom Benders Decomposition Implementation

Wed Mar 30 00:38:35 CEST 2022

Hi Matheus,

I am happy to help with your queries about the Benders' decomposition framework. It appears that you only need the main subproblem solving loop of the framework, and not the subproblem solving functions and cut generation. As such, you will need to implement your own Benders' decomposition plugin and Benders' Cut plugin. Since you will implement both a Benders' decomposition plugin and Benders' cut plugin, then you can easily transfer information directly between them.

You don't need to have a valid implementation of the BENDERSGETVAR callback, since you will be setting up the problem on your own and generating your own cuts. However, an implementation of BENDERSGETVAR is necessary. I suggest just having a simple callback method that always returns NULL. This will cover all of the cases where BENDERSGETVAR is called internally. Just a note, even if you are pricing variables, it is possible to update the mapping used in BENDERSGETVAR during the execution of the algorithm.

Your suggestion for BENDERSCUTEXEC is correct. All you need to do in BENDERSCUTEXEC is add a constraint or row and then return the appropriate result. Please look at type_benderscut.h for the appropriate result flags.

Your understanding is almost correct. However, the Benders plugin and the Benders cut plugin are completely different. Whether you are checking for feasibility or wanting to generate a cut, the Benders' plugin is called to solve the subproblem at the appropriate time. The Benders' cut plugin is called to generate a cut using the information from solving the subproblem in the Benders' plugin. In short, the Benders' plugin manages all of the subproblem information and solving methods, the Benders' cut plugin generates cuts given data from a solved subproblem.

In regards to your list of tasks:
- Write the BENDERSCREATESUB (in the benders plugin) method by providing NULL to SCIPaddBendersSubproblem and setting the subproblem type to SCIP_BENDERSSUBTYPE_CONVEXCONT.
    This is correct.
- Write my custom algorithm for the subproblem in the BENDERSSOLVESUBCONVEX (in the benders plugin) method.
    This is correct. This algorithm will be called for both the feasibility check and cut generation. For the cut generation, you need to store the data required to generate the cuts.
- Write my custom algorithm in BENDERSCUTEXEC (in the benderscut plugin) and in the end, separate an optimality/feasibility cut and add these with SCIPaddRow.
    This is not correct. You don't need to implement the algorithm here. If you do, you will be calling the algorithm twice. Only generate the cuts using the data from the previous solve of the algorithm.

Since you are not going to fully implement the BENDERSGETVAR callback, the cut-strengthening will not work correctly. The cut strengthening needs to know which variables in the master problem are the linking variables. If your BENDERSGETVAR can be implemented so that the linking variables are identified, then the cut strengthening should work, but this is untested.

I hope that this helps. Let us know if you have any further questions.

Cheers,

Steve

________________________________
From: Matheus Ota <matheusota at gmail.com>
Sent: 20 March 2022 18:29
To: Maher, Stephen <S.J.Maher at exeter.ac.uk>
Cc: scip at zib.de <scip at zib.de>
Subject: Re: [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.

Hi Stephen,

Thanks for the complete answer and sorry for the late answering. I had some personal problems that I had to take care of before getting back to this project. I'm now working on this again and I had new questions while I was trying to write the code. I would be very glad if you could share some information on these topics.

In my problem, we are also pricing the master variables, and there are too many variables in each subproblem, so it is not feasible to add all of these variables in the BENDERSGETVAR method to map all of them. Is it necessary to map the variables in the Master problem to variables in the subproblems in order to use the Benders Decomposition framework? Note that, in my case, when solving a subproblem for a solution \hat{x} of the LP relaxation, many of the subproblems variables will be zero, so I can still solve the subproblem efficiently. This is why I want to use a combinatorial algorithm for solving the subproblems.

In fact, I want to avoid loading the whole subproblem, so it seems to me that I will not be able to use the SCIPgenerateAndApplyBendersOptCut method. Can I implement the BENDERSCUTEXEC method just by, in the end, adding a constraint with SCIPaddRow? Also, I'm not sure that an MIR procedure is going to help me here, because the RHS is always integer. Is it still beneficial to use the MIR procedure in a single row when the RHS is integer? If so, will SCIP automatically perform the MIR procedure in a row added with SCIPaddRow?

Also, could you confirm if my understanding is correct: the benders plugin just checks the feasibility by solving the subproblems, while the benderscut plugin generates the actual cuts? I ask because the way I see it, both of these are going to be very similar. I'm solving a two-stage stochastic program, so both have to solve the subproblems in order to get an underestimator for the second-stage cost, with the difference that the latter gets the dual values to compute an optimality/feasibility cut.

So, if my assumptions are correct, in order to use a combinatorial algorithm within the Benders Decomposition framework, I need to do the following:
- Write the BENDERSCREATESUB (in the benders plugin) method by providing NULL to SCIPaddBendersSubproblem and setting the subproblem type to SCIP_BENDERSSUBTYPE_CONVEXCONT.
- Write my custom algorithm for the subproblem in the BENDERSSOLVESUBCONVEX (in the benders plugin) method.
- Write my custom algorithm in BENDERSCUTEXEC (in the benderscut plugin) and in the end, separate an optimality/feasibility cut and add these with SCIPaddRow.

I'm okay with losing some of the enhancements by not providing the whole subproblem. The feature that I'm most interested in is cut-strengthening, since by looking at the logs I can see that the algorithm is running for many iterations without improving the bound.

Thanks for your time,
Matheus

Em qua., 8 de set. de 2021 às 10:10, Maher, Stephen <S.J.Maher at exeter.ac.uk<mailto:S.J.Maher at exeter.ac.uk>> escreveu:
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<mailto:scip-bounces at zib.de>> on behalf of Matheus Ota <matheusota at gmail.com<mailto:matheusota at gmail.com>>
Sent: 27 August 2021 22:16
To: scip at zib.de<mailto:scip at zib.de> <scip at zib.de<mailto: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%7Ca596077b052944f5ffe208da0a9faf5a%7C912a5d77fb984eeeaf321334d8f04a53%7C0%7C0%7C637833978198901542%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=0g606JJ5rpmgOqMHy2nt6jstoX1NvEG4AsNwNE1Z4ds%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%7Ca596077b052944f5ffe208da0a9faf5a%7C912a5d77fb984eeeaf321334d8f04a53%7C0%7C0%7C637833978198901542%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ljrQsuL8PLfLfU4S3DSqwcLuzcoRTfgCYglhgeavnNE%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/20220329/d1556799/attachment.html>