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

[Maher, Stephen]

Hi Mosa,

In that case, the default Benders' decomposition plugin should be suitable for your situation. There is something more going on here that we will need to investigate. We will take this discussion offline and try to work out what the issue is.

Cheers,

Steve

________________________________
From: homat <pharham at gmail.com>
Sent: 26 May 2022 22:30
To: Maher, Stephen <S.J.Maher at exeter.ac.uk>
Cc: SCIP_Mailing_list SCIP_Solver <scip at zib.de>
Subject: Re: [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.

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<mailto: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<mailto:scip-bounces at zib.de>> on behalf of homat <pharham at gmail.com<mailto:pharham at gmail.com>>
Sent: 26 May 2022 01:37
To: SCIP_Mailing_list SCIP_Solver <scip at zib.de<mailto: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

________________________________
From: homat <pharham at gmail.com>
Sent: 26 May 2022 22:30
To: Maher, Stephen <S.J.Maher at exeter.ac.uk>
Cc: SCIP_Mailing_list SCIP_Solver <scip at zib.de>
Subject: Re: [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.

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<mailto: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<mailto:scip-bounces at zib.de>> on behalf of homat <pharham at gmail.com<mailto:pharham at gmail.com>>
Sent: 26 May 2022 01:37
To: SCIP_Mailing_list SCIP_Solver <scip at zib.de<mailto: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/20220530/bf7737c0/attachment.html>