[SCIP] Benders - error during generating cuts

Maher, Stephen S.J.Maher at exeter.ac.uk
Mon Nov 18 14:09:48 CET 2019 

Hi Albert,

Thanks for sending through the extra details of you model. The set up for using Benders' decomposition looks correct to me. You are also disabling the features, such as presolving and propagation, that can be problematic when using Benders.

I must admit, I got a little distracted by the fact that you said you were using column generation, that I didn't see the actual issue here. In the backtrace of the error from you first email, it shows that the error is coming from heur_alns. I have found in some of my own applications that the ALNS can cause errors when using Benders' decomposition. This is due to the Large Neighbourhood Benders' Search that applies Benders' decomposition to solve LNS auxiliary problems. Another heuristic that also causes issues is the RENS heuristic.

Could you add the following parameter settings in you solve_with_benders function or settings file?

heuristics/alns/freq = -1
heuristics/rens/freq = -1

This will disable both the ALNS and RENS heuristics.

If this doesn't work, then we might take this off the mailing list and look at the way you build the master and subproblems.

Please let us know if using these settings helps.

Cheers,

Steve

________________________________
From: Schrotenboer, Albert <a.h.schrotenboer at rug.nl>
Sent: 18 November 2019 12:40
To: Maher, Stephen <S.J.Maher at exeter.ac.uk>
Cc: scip at zib.de <scip at zib.de>
Subject: Re: [SCIP] Benders - error during generating cuts

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<mailto: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<mailto:scip-bounces at zib.de>> on behalf of Schrotenboer, Albert <a.h.schrotenboer at rug.nl<mailto:a.h.schrotenboer at rug.nl>>
Sent: 11 November 2019 20:39
To: scip at zib.de<mailto:scip at zib.de> <scip at zib.de<mailto: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/8971a56f/attachment.html>

More information about the Scip mailing list