[SCIP] Benders - error during generating cuts

[Maher, Stephen]

Hi Albert,

It is great that you are using the Benders' decomposition framework. It is definitely unfortunate that it doesn't work for you directly out of the box. Hopefully we can work out a way to save you having the code up the Benders' decomposition algorithm from scratch.

First, the fact that you are using column generation in the master problem is likely to complicate matters. The default Benders' plugin relies on knowing all master problem variables at the start of the solve to produce a variable mapping between the master and subproblems. This mapping is used to set up the Benders' decompostion subproblem given a master solution and then generate a cut for the master given a subproblem solution. If you are using column generation it is not possible to produce such a mapping, so then no valid default Benders' cuts will be produce. I suspect that this is a source of the error.

I would suggest a couple of things to better understand the root of the problem.

The first is to run a small test by applying column generation to solve the master problem, without using Benders' decomposition. Save this master problem and then try to solve the problem with Benders' decomposition without column generation in the master. This will tell us whether the issue is coming from the integration of column generation and Benders' decomposition or just the Benders' decomposition framework itself.

The second thing, if you want to use column generation in the master, I suggest that you write your own Benders' decomposition plugin. There are two fundamental callback functions for the Benders' decomposition plugin: bendersCreatesub and bendersGetvar. The former is used to register your subproblem with the Benders' decomposition core, then latter is used for the variable mapping. If you are using column generation, you can dynamically update the variable mapping as you add variables. If you subproblem is a SCIP instance and you don't specify any other callback functions, then the default Benders' solving methods and cut generation methods will be used.

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

Cheers,

Steve

________________________________
From: Scip <scip-bounces at zib.de> on behalf of Schrotenboer, Albert <a.h.schrotenboer at rug.nl>
Sent: 11 November 2019 20:39
To: scip at zib.de <scip at zib.de>
Subject: [SCIP] Benders - error during generating cuts

Dear SCIP Community,

I am using the Benders (default) plugin for the first time. I consider a classic network design problem with some side constraints and some bits and pieces of column generation, but that is all done and covered by the Master Problem (MP). The MP has only binary variables, encoding to `open' an arc or not, and will take value 0 in the first iteration as no benders cuts are yet included. (If this is the wise thing to do, that must be found out, but assume for now this is what I want ;p)

The subproblem (SP) then matches the stream of commodities to the opened arcs defined by the MP. Obviously, as no arcs will be opened, it will be infeasible and corresponding infeasibility cuts should be generated, right?

Whatever I do, SCIP keeps telling me to merge my infeasible SP into the master ;p!  See the error messages  below.  Is the sole solution for me to make my own benders plugin? Should I consider doing it differently? Why is SCIP not able to generate these cuts in its default plugin?  What are the possible causes? I run in debug mode.

At the moment, I've chosen to make a single subproblem. I.e., different types of commodities need to be routed along the opened arcs. I can decompose it for each commodity individually if required. But, still, it should be solvable with a single subproblem, right (before I spend hours on coding it differently and see it still wont work.. )

[src/scip/benders.c:2755] ERROR: An error was found when generating cuts for non-optimal subproblems of Benders' decomposition <default>. Consider merging the infeasible subproblems into the master problem.
[src/scip/scip_benders.c:682] ERROR: Error <0> in function call
[src/scip/cons_benders.c:254] ERROR: Error <0> in function call
[src/scip/cons_benderslp.c:126] ERROR: Error <0> in function call
[src/scip/cons.c:3471] ERROR: Error <0> in function call
[src/scip/solve.c:3361] ERROR: Error <0> in function call
[src/scip/solve.c:4259] ERROR: Error <0> in function call
[src/scip/solve.c:4935] ERROR: Error <0> in function call
[src/scip/scip_solve.c:2693] ERROR: Error <0> in function call
[src/scip/heur_alns.c:2547] ERROR: Error <0> in function call

Hoping I won't waste your time with a stupid coding mistake,  kind regards,

Albert


--

Albert Schrotenboer

Postdoctoral Researcher

Faculty of Economics and Business

University of Groningen

P.O. Box 800, 9700 AV Groningen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191112/d3ac448b/attachment.html>