[SCIP] Benders decomposition and column generation. Error in `SCIPpriceLoop`

[homat]

Thank you, Steve, for your suggestion.

The master problem variables that I generate are not involved in the
Benders subproblem. In other words, the variables in the Benders subproblem
always map to the same set of variables in the master problem.
Do I still need to add my own Benders plugin?

Mosa

On Thu, May 26, 2022 at 3:08 AM Maher, Stephen <S.J.Maher at exeter.ac.uk>
wrote:

> Hi Mosa,
>
> The default Benders' decomposition algorithm in SCIP has not been designed
> to work with column generation. This is because the default Benders'
> decomposition algorithm requires a mapping between the master problem and
> their counterpart in the subproblem. This mapping is produced at the start
> of the solving process in the default algorithm. Since column generation
> prices in new master problem variables, this mapping is not available
> because the variables themselves are still unknown at the start of the
> solving process.
>
> While the Benders' decomposition framework has not been designed to work
> with a column generation scheme, it still may be possible. My best thoughts
> as to what you need to do are the following (however, I have never done
> this so there could be something that I miss):
>
>    - Implement a custom Benders' decomposition plugin. This plugin will
>    need to update the variable mapping between the master and subproblems as
>    new variables are generated. The variable mapping is accessed in
>    the bendersGetvarXyz that you will implement.
>    - You can still use the default solving methods and cut generation
>       methods.
>    - When you generate master problem variables, then you need to add a
>    counterpart to the Benders' decomposition subproblem. Then update the
>    variable mapping in the Benders' decomposition plugin. This will allow the
>    default cut generation methods to work correctly.
>
> This idea is completely untested. However, I do expect that it is possible
> to combine column generation and Benders' decomposition using the Benders'
> framework in SCIP.
>
> Please let me know if you have any further questions.
>
> Cheers,
>
> Steve
>
> ------------------------------
> *From:* Scip <scip-bounces at zib.de> on behalf of homat <pharham at gmail.com>
> *Sent:* 26 May 2022 01:37
> *To:* SCIP_Mailing_list SCIP_Solver <scip at zib.de>
> *Subject:* [SCIP] Benders decomposition and column generation. Error in
> `SCIPpriceLoop`
>
> 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
>
> I am trying to solve a problem using Benders decomposition and column
> generation.
> I followed your VRP and SCFLP examples to add a pricer and a
> default benders decomposition algorithm.
> The master problem is solved using column generation, and I expect the
> algorithm to add optimality cuts to the master problem by solving a benders
> subproblem.
> The master problem is integer, but I do not use any special branching
> strategies for now.
> Presolving is disabled by calling `SCIPsetPresolving(scip,
> SCIP_PARAMSETTING_OFF, true)` as well.
> However, in some of my tests, I get the following error:
> scipoptsuite-8.0.0/scip/src/scip/solve.c:2160: SCIPpriceLoop: Assertion
> `cutoff == FALSE' failed.
>
> Could you please tell my how I can resolve this issue?
>
> Mosa
>


-- 
M Saleh F
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220526/8667a949/attachment.html>