[SCIP] Benders - error during generating cuts
Schrotenboer, Albert
a.h.schrotenboer at rug.nl
Mon Nov 18 13:40:30 CET 2019
Hi Steve,
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.
Thanks in advance,
Albert
SCIP_RETCODE TimedModel::solve_with_benders()
{
cout << "TRYING BENDERS FOR ONCE " << endl << endl;
/* create master */
SCIP *scip_master;
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
SCIP_CALL(SCIPcreate(&scip_master));
SCIP_CALL(SCIPcreateProb(scip_master, "Master", 0, 0, 0, 0, 0, 0, 0));
SCIP_CALL(SCIPincludeDefaultPlugins(scip_master));
SCIP_CALL(SCIPsetObjsense(scip_master, SCIP_OBJSENSE_MINIMIZE) );
SCIP_CALL( SCIPsetIntParam(scip_master,"presolving/maxrestarts",0) );
/* turn off all separation algorithms */
SCIP_CALL( SCIPsetPresolving(scip_master, SCIP_PARAMSETTING_OFF, true) );
SCIP_CALL( SCIPsetSeparating(scip_master, SCIP_PARAMSETTING_OFF, true) );
SCIP_CALL( SCIPsetIntParam(scip_master, "propagating/maxrounds", 0) );
SCIP_CALL( SCIPsetIntParam(scip_master, "propagating/maxroundsroot", 0) );
create_benders_master(scip_master, varConsInfoBendersMaster); // this
creates the master -> i.e., the constraints and the variables and stores
them in varConsInfoBendersMaster
/* create subproblem*/
vector<SCIP *> scip_subproblem(1);
VarConsInfoTimed varConsInfoBendersSubproblem(d_nNodes,
d_allTimes.size(), num_edges(d_graph), d_nCommodities);
SCIP_CALL(SCIPcreate(&scip_subproblem[0]));
SCIP_CALL(SCIPcreateProb(scip_subproblem[0], "Subproblem", 0, 0, 0, 0,
0, 0, 0));
SCIP_CALL(SCIPincludeDefaultPlugins(scip_subproblem[0]));
SCIP_CALL( SCIPsetObjsense(scip_subproblem[0], SCIP_OBJSENSE_MINIMIZE) );
create_subproblem(scip_subproblem[0], varConsInfoBendersSubproblem);
/* use benders */
SCIP_CALL( SCIPcreateBendersDefault(scip_master, scip_subproblem.data(),
1));
SCIP_CALL( SCIPsetBoolParam(scip_master, "constraints/benders/active",
true) );
SCIP_CALL( SCIPsetBoolParam(scip_master, "constraints/benderslp/active",
true) );
SCIP_CALL( SCIPsetIntParam(scip_master,
"constraints/benders/maxprerounds", 0) );
SCIP_CALL( SCIPsetIntParam(scip_master, "presolving/maxrounds", 0) );
/* attack */
SCIP_CALL(SCIPsolve(scip_master));
return SCIP_OKAY;
}
On Tue, Nov 12, 2019 at 10:34 AM Maher, Stephen <S.J.Maher at exeter.ac.uk>
wrote:
> 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
>
--
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/20191118/14db67b5/attachment.html>
More information about the Scip
mailing list