[SCIP] Custom Benders Decomposition Implementation

[Matheus Ota]

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>
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> 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/20220320/5af8cdb2/attachment.html>