<div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Hi Steve,</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Thanks for the detailed response. I should've mentioned that as a first step I indeed generated all columns. Then, in a completely separated procedure from my actual program, I create a new master and a subproblem, with new variables and constraints, so there is no relation with the previous column generation phase. I give the master and the subproblem their own `SCIP*'. If I understand correctly, the mapping between master and subproblem variables is created by the naming of the variables, right? So I *need* to create the master variables both in the master and in the subproblem, meaning that both SCIP* entities have their own set of master variables. A mapping is then created by calling the benders default plugin with the right arguments, and I can call the SCIPsolve() on the SCIP* entity related to the master, right? I've copy pasted the procedure that tries to apply default benders below.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Thanks in advance,</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Albert<br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">SCIP_RETCODE TimedModel::solve_with_benders()<br>{<br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"> cout << "TRYING BENDERS FOR ONCE " << endl << endl;<br> <br> /* create master */<br> SCIP *scip_master;<br> VarConsInfoTimed varConsInfoBendersMaster(d_nNodes, d_allTimes.size(), num_edges(d_graph), d_nCommodities); // This is a struct in which I story all the variables and constraints<br> SCIP_CALL(SCIPcreate(&scip_master));<br> SCIP_CALL(SCIPcreateProb(scip_master, "Master", 0, 0, 0, 0, 0, 0, 0)); <br> SCIP_CALL(SCIPincludeDefaultPlugins(scip_master));<br> SCIP_CALL(SCIPsetObjsense(scip_master, SCIP_OBJSENSE_MINIMIZE) );<br> SCIP_CALL( SCIPsetIntParam(scip_master,"presolving/maxrestarts",0) );<br><br> /* turn off all separation algorithms */<br> SCIP_CALL( SCIPsetPresolving(scip_master, SCIP_PARAMSETTING_OFF, true) );<br> SCIP_CALL( SCIPsetSeparating(scip_master, SCIP_PARAMSETTING_OFF, true) );<br> SCIP_CALL( SCIPsetIntParam(scip_master, "propagating/maxrounds", 0) );<br> SCIP_CALL( SCIPsetIntParam(scip_master, "propagating/maxroundsroot", 0) );<br><br> create_benders_master(scip_master, varConsInfoBendersMaster); // this creates the master -> i.e., the constraints and the variables and stores them in varConsInfoBendersMaster<br> <br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br> /* create subproblem*/<br> vector<SCIP *> scip_subproblem(1);<br> VarConsInfoTimed varConsInfoBendersSubproblem(d_nNodes, d_allTimes.size(), num_edges(d_graph), d_nCommodities);<br> <br> SCIP_CALL(SCIPcreate(&scip_subproblem[0]));<br> SCIP_CALL(SCIPcreateProb(scip_subproblem[0], "Subproblem", 0, 0, 0, 0, 0, 0, 0)); <br> SCIP_CALL(SCIPincludeDefaultPlugins(scip_subproblem[0]));<br> SCIP_CALL( SCIPsetObjsense(scip_subproblem[0], SCIP_OBJSENSE_MINIMIZE) );<br> <br> create_subproblem(scip_subproblem[0], varConsInfoBendersSubproblem);<br> <br> <br> /* use benders */<br> SCIP_CALL( SCIPcreateBendersDefault(scip_master, scip_subproblem.data(), 1));<br> SCIP_CALL( SCIPsetBoolParam(scip_master, "constraints/benders/active", true) );<br> SCIP_CALL( SCIPsetBoolParam(scip_master, "constraints/benderslp/active", true) ); <br> SCIP_CALL( SCIPsetIntParam(scip_master, "constraints/benders/maxprerounds", 0) );<br> SCIP_CALL( SCIPsetIntParam(scip_master, "presolving/maxrounds", 0) );<br> <br> /* attack */<br> SCIP_CALL(SCIPsolve(scip_master));<br> <br> return SCIP_OKAY;<br>}</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Nov 12, 2019 at 10:34 AM Maher, Stephen <<a href="mailto:S.J.Maher@exeter.ac.uk">S.J.Maher@exeter.ac.uk</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div 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="gmail-m_9174790968531416947appendonsend"></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">
<br>
</div>
<hr style="display:inline-block;width:98%">
<div id="gmail-m_9174790968531416947divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>From:</b> Scip <<a href="mailto:scip-bounces@zib.de" target="_blank">scip-bounces@zib.de</a>> on behalf of Schrotenboer, Albert <<a href="mailto:a.h.schrotenboer@rug.nl" target="_blank">a.h.schrotenboer@rug.nl</a>><br>
<b>Sent:</b> 11 November 2019 20:39<br>
<b>To:</b> <a href="mailto:scip@zib.de" target="_blank">scip@zib.de</a> <<a href="mailto:scip@zib.de" target="_blank">scip@zib.de</a>><br>
<b>Subject:</b> [SCIP] Benders - error during generating cuts</font>
<div> </div>
</div>
<div>
<div dir="ltr">
<div style="font-family:arial,helvetica,sans-serif">Dear SCIP Community,</div>
<div style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div 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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div 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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div 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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div 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 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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div style="font-family:arial,helvetica,sans-serif">Hoping I won't waste your time with a stupid coding mistake, kind regards,</div>
<div style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div style="font-family:arial,helvetica,sans-serif">Albert<br>
</div>
<div style="font-family:arial,helvetica,sans-serif"><br>
</div>
<br>
-- <br>
<div dir="ltr">
<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><span style="color:rgb(102,102,102)">Albert Schrotenboer</span></p>
<p><span style="color:rgb(102,102,102)">Postdoctoral Researcher<br>
</span></p>
<p><span style="color:rgb(102,102,102)">Faculty of Economics and Business</span></p>
<p><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><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>
</div>
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr" class="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="MsoNormal"><span style="color:rgb(102,102,102)">Albert Schrotenboer</span></p><p class="MsoNormal"><span style="color:rgb(102,102,102)">Postdoctoral Researcher<br></span></p><p class="MsoNormal"><span style="color:rgb(102,102,102)">Faculty of Economics and Business</span></p><p class="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="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>