<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Hi Albert,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
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.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
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.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
I would suggest a couple of things to better understand the root of the problem.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
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.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
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.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
I hope that this helps. Please let us know if you have any further questions.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Cheers,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Steve<br>
</div>
<div>
<div id="appendonsend"></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>From:</b> Scip <scip-bounces@zib.de> on behalf of Schrotenboer, Albert <a.h.schrotenboer@rug.nl><br>
<b>Sent:</b> 11 November 2019 20:39<br>
<b>To:</b> scip@zib.de <scip@zib.de><br>
<b>Subject:</b> [SCIP] Benders - error during generating cuts</font>
<div> </div>
</div>
<div>
<div dir="ltr">
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">Dear SCIP Community,</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">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)</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">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? <br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">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.<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">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.. )
<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
[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.<br>
[src/scip/scip_benders.c:682] ERROR: Error <0> in function call<br>
[src/scip/cons_benders.c:254] ERROR: Error <0> in function call<br>
[src/scip/cons_benderslp.c:126] ERROR: Error <0> in function call<br>
[src/scip/cons.c:3471] ERROR: Error <0> in function call<br>
[src/scip/solve.c:3361] ERROR: Error <0> in function call<br>
[src/scip/solve.c:4259] ERROR: Error <0> in function call<br>
[src/scip/solve.c:4935] ERROR: Error <0> in function call<br>
[src/scip/scip_solve.c:2693] ERROR: Error <0> in function call<br>
[src/scip/heur_alns.c:2547] ERROR: Error <0> in function call</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">Hoping I won't waste your time with a stupid coding mistake, kind regards,</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif">Albert<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif"><br>
</div>
<br>
-- <br>
<div dir="ltr" class="x_gmail_signature">
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div style="color:rgb(0,0,0); font-size:10pt; letter-spacing:normal; line-height:12pt; margin-bottom:0px; margin-top:0px">
<p class="x_MsoNormal"><span style="color:rgb(102,102,102)">Albert Schrotenboer</span></p>
<p class="x_MsoNormal"><span style="color:rgb(102,102,102)">Postdoctoral Researcher<br>
</span></p>
<p class="x_MsoNormal"><span style="color:rgb(102,102,102)">Faculty of Economics and Business</span></p>
<p class="x_MsoNormal"><span style="color:rgb(102,102,102)"></span><font color="rgb(34, 34, 34)"><span style="color:rgb(102,102,102)">University of Groningen</span></font><font color="rgb(34, 34, 34)"><span style="color:rgb(102,102,102)"><br>
</span></font></p>
<p class="x_MsoNormal"><font color="rgb(34, 34, 34)"><span style="color:rgb(102,102,102)">P.O. Box 800, 9700 AV Groningen</span>
</font></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>