benders.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49 #define SCIP_DEFAULT_TRANSFERCUTS FALSE /** should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
50 #define SCIP_DEFAULT_CUTSASCONSS TRUE /** should the transferred cuts be added as constraints? */
51 #define SCIP_DEFAULT_LNSCHECK TRUE /** should the Benders' decomposition be used in LNS heuristics */
53 #define SCIP_DEFAULT_LNSMAXCALLS 10 /** the maximum number of Benders' decomposition calls in LNS heuristics */
54 #define SCIP_DEFAULT_LNSMAXCALLSROOT 0 /** the maximum number of root node Benders' decomposition calls in LNS heuristics */
55 #define SCIP_DEFAULT_SUBPROBFRAC 1.0 /** fraction of subproblems that are solved in each iteration */
56 #define SCIP_DEFAULT_UPDATEAUXVARBOUND FALSE /** should the auxiliary variable lower bound be updated by solving the subproblem */
57 #define SCIP_DEFAULT_AUXVARSIMPLINT FALSE /** set the auxiliary variables as implint if the subproblem objective is integer */
58 #define SCIP_DEFAULT_CUTCHECK TRUE /** should cuts be generated during the checking of solutions? */
59 #define SCIP_DEFAULT_STRENGTHENMULT 0.5 /** the convex combination multiplier for the cut strengthening */
60 #define SCIP_DEFAULT_NOIMPROVELIMIT 5 /** the maximum number of cut strengthening without improvement */
61 #define SCIP_DEFAULT_STRENGTHENPERTURB 1e-06 /** the amount by which the cut strengthening solution is perturbed */
62 #define SCIP_DEFAULT_STRENGTHENENABLED FALSE /** enable the core point cut strengthening approach */
63 #define SCIP_DEFAULT_STRENGTHENINTPOINT 'r' /** where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros) */
64 #define SCIP_DEFAULT_NUMTHREADS 1 /** the number of parallel threads to use when solving the subproblems */
65 #define SCIP_DEFAULT_EXECFEASPHASE FALSE /** should a feasibility phase be executed during the root node processing */
66 #define SCIP_DEFAULT_SLACKVARCOEF 1e+6 /** the initial objective coefficient of the slack variables in the subproblem */
67 #define SCIP_DEFAULT_MAXSLACKVARCOEF 1e+9 /** the maximal objective coefficient of the slack variables in the subproblem */
68 #define SCIP_DEFAULT_CHECKCONSCONVEXITY TRUE /** should the constraints of the subproblem be checked for convexity? */
70 #define BENDERS_MAXPSEUDOSOLS 5 /** the maximum number of pseudo solutions checked before suggesting
75 #define AUXILIARYVAR_NAME "##bendersauxiliaryvar" /** the name for the Benders' auxiliary variables in the master problem */
76 #define SLACKVAR_NAME "##bendersslackvar" /** the name for the Benders' slack variables added to each
85 #define MIPNODEFOCUS_EVENTHDLR_DESC "node focus event handler for the MIP solve method for Benders' decomposition"
88 #define UPPERBOUND_EVENTHDLR_DESC "found solution event handler to terminate subproblem solve for a given upper bound"
226 /* sending an interrupt solve signal to return the control back to the Benders' decomposition plugin.
230 SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
236 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
249 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
309 SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
317 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
330 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
387 if( SCIPisLT(scip, SCIPgetSolOrigObj(scip, bestsol)*(int)SCIPgetObjsense(scip), eventhdlrdata->upperbound) )
395 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
408 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
461 eventhdlr = SCIPfindEventhdlr(SCIPbendersSubproblem(benders, probnumber), UPPERBOUND_EVENTHDLR_NAME);
475 * This function solves the master problem with only the auxiliary variables in the objective function.
566 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
579 /* The event is only caught if there is an active Benders' decomposition, the integer subproblem are solved and
582 if( SCIPbendersIsActive(benders) && !SCIPbendersOnlyCheckConvexRelax(benders, SCIPgetSubscipsOff(scip))
592 /* ---------------- Methods for the parallelisation of Benders' decomposition ---------------- */
678 /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
685 /* if the current Benders is the highest priority Benders, then we need to create the auxiliary variables.
686 * Otherwise, if the shareauxvars flag is set, then the auxiliary variables from the highest priority Benders' are
694 /* if the auxiliary variables are shared, then a pointer to the variable is retrieved from topbenders,
706 /* set the variable type of the auxiliary variables to implied integer if the objective function of the
707 * subproblem is guaranteed to be integer. This behaviour is controlled through a user parameter.
708 * NOTE: It is only possible to determine if the objective function is integral if the subproblem is defined as
717 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_%d_%s", AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders) );
718 SCIP_CALL( SCIPcreateVarBasic(scip, &auxiliaryvar, varname, benders->subproblowerbound[i], SCIPinfinity(scip),
737 /** assigns the copied auxiliary variables in the target SCIP to the target Benders' decomposition data */
756 /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
763 /* if the auxiliary variable are shared, then the variable name will have a suffix of the highest priority Benders'
780 /* the prefix for the variable names is required for UG, since we don't know how many copies have been made. To
781 * find the target variable, we start with an empty prefix. Then t_ is prepended until the target variable is
788 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s%s_%d_%s", prefix, AUXILIARYVAR_NAME, i, SCIPbendersGetName(topbenders));
790 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s%s_%d_%s", prefix, AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders));
792 /* finding the variable in the copied problem that has the same name as the auxiliary variable */
858 return strcmp(SCIPbendersGetName((SCIP_BENDERS*)elem1), SCIPbendersGetName((SCIP_BENDERS*)elem2));
876 /** creates a variable mapping between the master problem variables of the source scip and the sub scip */
899 /* creating the hashmap for the mapping between the master variable of the target and source scip */
904 /* getting the variable pointer for the target SCIP variables. The variable mapping returns the target SCIP
928 SCIP_BENDERS* targetbenders; /* the copy of the Benders' decomposition struct in the target set */
938 if( benders->benderscopy != NULL && targetset->benders_copybenders && SCIPbendersIsActive(benders) )
940 SCIPsetDebugMsg(targetset, "including Benders' decomposition %s in subscip %p\n", SCIPbendersGetName(benders), (void*)targetset->scip);
968 /* When the Benders' decomposition is copied then a variable mapping between the master problem variables is
969 * required. This variable mapping is used to transfer the cuts generated in the target SCIP to the source SCIP.
970 * The variable map is stored in the target Benders' decomposition. This will be freed when the sub-SCIP is freed.
1001 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
1005 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
1006 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
1007 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
1008 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
1009 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
1010 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
1011 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
1012 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
1013 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
1014 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
1015 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
1026 /* Checking whether the benderssolvesub and the bendersfreesub are both implemented or both are not implemented */
1030 SCIPerrorMessage("Benders' decomposition <%s> requires that if bendersFreesub%s is implemented, then at least "
1031 "one of bendersSolvesubconvex%s or bendersSolvesub%s are implemented.\n", name, name, name, name);
1065 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of Benders' decomposition <%s>", name);
1072 "should Benders' cuts be generated for LP solutions?", &(*benders)->cutlp, FALSE, cutlp, NULL, NULL) ); /*lint !e740*/
1076 "should Benders' cuts be generated for pseudo solutions?", &(*benders)->cutpseudo, FALSE, cutpseudo, NULL, NULL) ); /*lint !e740*/
1080 "should Benders' cuts be generated for relaxation solutions?", &(*benders)->cutrelax, FALSE, cutrelax, NULL, NULL) ); /*lint !e740*/
1082 /* These parameters are left for the user to decide in a settings file. This departs from the usual SCIP convention
1087 "should Benders' cuts from LNS heuristics be transferred to the main SCIP instance?", &(*benders)->transfercuts,
1092 "should Benders' decomposition be used in LNS heurisics?", &(*benders)->lnscheck, FALSE, SCIP_DEFAULT_LNSCHECK,
1097 "maximum depth at which the LNS check is performed (-1: no limit)", &(*benders)->lnsmaxdepth, TRUE,
1102 "the maximum number of Benders' decomposition calls in LNS heuristics (-1: no limit)", &(*benders)->lnsmaxcalls,
1107 "the maximum number of root node Benders' decomposition calls in LNS heuristics (-1: no limit)",
1122 "should the auxiliary variable bound be updated by solving the subproblem?", &(*benders)->updateauxvarbound,
1127 "if the subproblem objective is integer, then define the auxiliary variables as implied integers?",
1142 "the maximum number of cut strengthening without improvement", &(*benders)->noimprovelimit, TRUE,
1147 "the constant use to perturb the cut strengthening core point", &(*benders)->perturbeps, FALSE,
1152 "should the core point cut strengthening be employed (only applied to fractional solutions or continuous subproblems)?",
1153 &(*benders)->strengthenenabled, FALSE, SCIP_DEFAULT_STRENGTHENENABLED, NULL, NULL) ); /*lint !e740*/
1157 "where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros)",
1158 &(*benders)->strengthenintpoint, FALSE, SCIP_DEFAULT_STRENGTHENINTPOINT, "lfiroz", NULL, NULL) ); /*lint !e740*/
1167 "should a feasibility phase be executed during the root node, i.e. adding slack variables to constraints to ensure feasibility",
1172 "the initial objective coefficient of the slack variables in the subproblem", &(*benders)->slackvarcoef, FALSE,
1177 "the maximal objective coefficient of the slack variables in the subproblem", &(*benders)->maxslackvarcoef, FALSE,
1182 "should the constraints of the subproblems be checked for convexity?", &(*benders)->checkconsconvexity, FALSE,
1190 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
1204 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
1208 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
1209 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
1210 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
1211 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
1212 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
1213 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
1214 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
1215 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
1216 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
1217 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
1218 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
1226 SCIP_CALL_FINALLY( doBendersCreate(benders, set, messagehdlr, blkmem, name, desc, priority, cutlp, cutpseudo,
1227 cutrelax, shareauxvars, benderscopy, bendersfree, bendersinit, bendersexit, bendersinitpre, bendersexitpre,
1228 bendersinitsol, bendersexitsol, bendersgetvar, benderscreatesub, benderspresubsolve, benderssolvesubconvex,
1229 benderssolvesub, benderspostsolve, bendersfreesub, bendersdata), (void) SCIPbendersFree(benders, set) );
1289 /* if the Benders' decomposition is a copy and a varmap has been passed to SCIP_BENDERS, then the variable map
1340 /* checking whether the constraint is a linear constraint. If so, we add a coefficient to the constraint */
1353 "This is not supported and the slack variable will not be added to the constraint. Feasibility cuts may be invalid.\n",
1373 /* if the right hand side is finite, then we need to add a slack variable with a negative coefficient */
1378 SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), objcoef, SCIP_VARTYPE_CONTINUOUS) );
1397 /* if the left hand side if finite, then we need to add a slack variable with a positive coefficient */
1402 SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), objcoef, SCIP_VARTYPE_CONTINUOUS) );
1424 /** adds the slack variables to each of the constraints for the generation of feasibility cuts for the given non-linear
1460 SCIP_CALL( addSlackVars(subproblem, benders, cons, linearconshdlrs, nlconshdlr, NLINEARCONSHDLRS) );
1466 /** initialises a MIP subproblem by putting the problem into SCIP_STAGE_SOLVING. This is achieved by calling SCIPsolve
1468 * The LP subproblem is also initialised using this method; however, a different event handler is added. This event
1470 * The MIP solving function is called to initialise the subproblem because this function calls SCIPsolve with the
1495 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, FALSE) );
1511 /** initialises an LP subproblem by putting the problem into probing mode. The probing mode is invoked in a node focus
1512 * event handler. This event handler is added just prior to calling the initialise subproblem function.
1537 SCIP_CALL( SCIPincludeEventhdlrBasic(subproblem, &eventhdlr, NODEFOCUS_EVENTHDLR_NAME, NODEFOCUS_EVENTHDLR_DESC,
1551 /** checks whether the convex relaxation of the subproblem is sufficient to solve the original problem to optimality
1554 * To do this, we check that all variables are of continuous type and that every constraint is either handled by known
1555 * linear constraint handler (knapsack, linear, logicor, setppc, varbound) or the nonlinear constraint handler.
1557 * Further, nonlinear constraints are only considered if an NLP solver interface is available, i.e., and NLP could
1559 * If constraints are present that cannot be identified as linear or convex nonlinear, then we assume that the
1603 SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, &nbinvars, &nintvars, &nimplintvars, NULL) );
1605 /* if there are any binary, integer or implied integer variables, then the subproblems is marked as non-convex */
1618 /* Get pointer to the nonlinear constraint handler if we also have an NLP solver to solve NLPs.
1619 * If there is no NLP solver, but there are (convex) nonlinear constraints, then the LP relaxation of subproblems
1620 * will (currently) not be sufficient to solve subproblems to optimality. Thus, we also take the presence of convex
1621 * nonlinear constraints as signal for having to solve the CIP eventually, thus, by abuse of notation,
1622 * return not-convex here. In summary, we do not need to have a special look onto non-linear constraints
1623 * if no NLP solver is present, and can treat them as any other constraint that is not of linear type.
1630 /* if the nonlinear constraint handler exists, then we create a hashmap of variables that can be assumed to be fixed.
1637 SCIP_CALL( SCIPhashmapCreate(&assumevarfixed, SCIPblkmem(set->scip), SCIPgetNVars(subproblem)) );
1666 SCIPdebugMsg(subproblem, "subproblem <%s>: constraint <%s> is linear\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1698 /* make sure activities are up to date. SCIPhasExprCurvature currently assumes that this is already the case */
1701 SCIP_CALL( SCIPhasExprCurvature(subproblem, SCIPgetExprNonlinear(cons), havelhs ? SCIP_EXPRCURV_CONCAVE : SCIP_EXPRCURV_CONVEX, &isconvex, assumevarfixed) );
1708 SCIPdebugMsg(subproblem, "subproblem <%s>: nonlinear constraint <%s> is convex\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1715 SCIPdebugMsg(subproblem, "subproblem <%s>: nonlinear constraint <%s> not convex\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1722 SCIPdebugMsg(subproblem, "subproblem <%s>: potentially nonconvex constraint <%s>\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1731 /* setting the flag for the convexity of the subproblem. If convexity doesn't need to be checked, then it is assumed
1732 * that the subproblems are convex. However, if there are discrete variables, then the problem must be set as
1733 * non-convex. The discrete master variables will be changed to continuous, but this will happen at the first call to
1760 SCIPsetDebugMsg(set, "subproblem <%s> has been found to be of type %d\n", SCIPgetProbName(subproblem),
1790 /* if the subproblems have already been created, then they will not be created again. This is the case if the
1791 * transformed problem has been freed and then retransformed. The subproblems should only be created when the problem
1806 /* the subproblem SCIP instance could be set to NULL. This is because user defined subproblem solving methods
1807 * could be used that don't solve a SCIP instance. Thus, the following setup of the subproblem SCIP instance is
1810 * NOTE: since the subproblems are supplied as NULL pointers, the internal convexity check can not be performed.
1821 /* The objective function coefficients of the master problem are set to zero. This is necessary for the Benders'
1822 * decomposition algorithm, since the cut methods and the objective function check assumes that the objective
1825 * This only occurs if the Benders' decomposition is not a copy. It is assumed that the correct objective
1828 * If the subproblems were copied, then the master variables will be checked to ensure that they have a zero
1841 /* if mastervar is not NULL, then the subproblem variable has a corresponding master problem variable */
1844 SCIPverbMessage(subproblem, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Changing the objective "
1856 SCIPverbMessage(subproblem, SCIP_VERBLEVEL_HIGH, NULL, "Benders' decomposition: Objective coefficients of "
1864 /* checking the convexity of the subproblem. The convexity of the subproblem indicates whether the convex
1869 /* if the problem is convex and has nonlinear constraints, then slack variables must be added to each of the
1876 /* the slack variables are only added to the subproblem once. If the initialisation methods are called from a
1877 * copy, then the slack variables are not re-added. Alternatively, if the copy must be threadsafe, then the
1885 /* setting the flag to indicate that slack variables have been added to the subproblem constraints. This is only
1892 /* after checking the subproblem for convexity, if the subproblem has convex constraints and continuous variables,
1897 /* if the user has not implemented a solve subproblem callback, then the subproblem solves are performed
1910 /* because the subproblems could be reused in the copy, the event handler is not created again. If the
1912 * NOTE: This currently works with the benders_default implementation. It may not be very general. */
1947 SCIPerrorMessage("If the subproblem is set to NULL, then the subproblem type must be specified.\n");
1948 SCIPerrorMessage("In the subproblem creation callback, call SCIPbendersSetSubproblemType with the appropriate problem type.\n");
1955 /* checking the convexity of the master problem. This information is useful for the cut generation methods, such as
2003 /* if the Benders' decomposition is a copy, then the auxiliary variables already exist. So they are registered with
2004 * the Benders' decomposition struct during the init stage. If the Benders' decomposition is not a copy, then the
2013 /* creates the subproblems and sets up the probing mode for LP subproblems. This function calls the benderscreatesub
2023 SCIP_ALLOC( BMSallocBlockMemoryArray(SCIPblkmem(set->scip), &benders->storedcuts, BENDERS_ARRAYSIZE) );
2042 /** Transfers Benders' cuts that were generated while solving a sub-SCIP to the original SCIP instance. This involves
2043 * creating a constraint/cut that is equivalent to the generated cut in the sub-SCIP. This new constraint/cut is then
2058 SCIP_CONSHDLR* consbenders; /* a helper variable for the Benders' decomposition constraint handler */
2059 SCIP_CONS* transfercons = NULL; /* the constraint that is generated to transfer the constraints/cuts */
2085 * SCIPcreateConsBasicLinear/SCIPcreateEmptyRowConshdlr. This should be implemented to improve the performance of the
2092 SCIP_CALL( SCIPcreateConsBasicLinear(sourcescip, &transfercons, cutname, 0, NULL, NULL, lhs, rhs) );
2097 SCIP_CALL( SCIPcreateEmptyRowConshdlr(sourcescip, &transfercut, consbenders, cutname, lhs, rhs, FALSE,
2113 /* if the source variable is not found, then the mapping in incomplete. So the constraint can not be
2236 /* if the Benders' decomposition is a copy, then is a variable mapping was provided, then the generated cuts will
2247 SCIPfreeBlockMemoryArray(set->scip, &benders->storedcuts[i]->vals, benders->storedcuts[i]->nvars);
2248 SCIPfreeBlockMemoryArray(set->scip, &benders->storedcuts[i]->vars, benders->storedcuts[i]->nvars);
2260 /* it is possible that the master problem is not solved. As such, the auxiliary variables will not be created. So
2265 /* we need to remove the locks from the auxiliary variables. This will be called always for the highest priority
2269 SCIP_CALL( SCIPaddVarLocksType(set->scip, benders->auxiliaryvars[i], SCIP_LOCKTYPE_MODEL, -1, 0) );
2317 /* looping over all subproblems to check whether there exists at least one master problem variable */
2322 /* if there are user defined solving or freeing functions, then it is not possible to declare the independence of
2337 /* if the subporblem variable is not NULL, then the subproblem depends on the master problem */
2364 /* if the Benders' decomposition is the original, then the auxiliary variables need to be created. If the Benders'
2365 * decomposition is a copy, then the auxiliary variables already exist. The assignment of the auxiliary variables
2370 /* check the subproblem independence. This check is only performed if the user has not implemented a solve
2468 /* freeing all subproblems that are independent, this is because they have not bee freed during the subproblem
2495 /* sorting the Benders' decomposition cuts in order of priority. Only a single cut is generated for each subproblem
2496 * per solving iteration. This is particularly important in the case of the optimality and feasibility cuts. Since
2497 * these work on two different solutions to the subproblem, it is not necessary to generate both cuts. So, once the
2588 SCIP_CALL( SCIPincludeEventhdlrBasic(set->scip, &eventhdlr, NODESOLVED_EVENTHDLR_NAME, NODESOLVED_EVENTHDLR_DESC,
2621 /* if the subproblems were created by the Benders' decomposition core, then they need to be freed */
2670 /** updates the lower bound for all auxiliary variables. This is called if the first LP enforced is unbounded. */
2697 SCIP_CALL( SCIPbendersComputeSubproblemLowerbound(benders, set, i, &lowerbound, &infeasible) );
2712 SCIPsetDebugMsg(set, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
2725 /** sets the core point used for cut strengthening. If the strenghtenintpoint is set to 'i', then the core point is
2739 /* if the core point is not NULL and the interior point is not reinitialised, then nothing is done */
2745 /* if the core point should be updated, then this only happens if the incumbent solution has been updated */
2778 /* if there is time remaining, then compute the relative interior point. Otherwise, return the LP solution */
2781 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Computing relative interior point (time limit: %g, iter limit: %d) ...\n", timelimit, INT_MAX);
2782 SCIP_CALL( SCIPcomputeLPRelIntPoint(scip, TRUE, FALSE, timelimit, INT_MAX, &benders->corepoint) );
2822 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
2823 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
2824 SCIP_Bool* skipsolve, /**< should the main solve be skipped as a result of this strengthening? */
2840 /* the cut stabilisation is only performed when enforcing LP solutions. The solution is not NULL if the stabilisation
2857 /* if the number of iterations without improvement exceeds 3*noimprovelimit, then the no stabilisation is performed
2862 /* if there is no incumbent solution, then it is not possible to create the core point and hence the strengthening
2868 /* if no LP iterations have been performed since the last call of the cut strenghtening, then the strengthening is
2876 /* if the separation point solution is NULL, then we create the solution using the current LP relaxation. */
2880 * TODO: This could be a little to memory heavy, it may be better just to create the separation point once and then
2889 /* creating a solution that is a convex combination of the LP solution and the separation point */
2911 /* if the variable is a linking variable and it is not fixed, then a convex combination with the corepoint is
2916 /* if the number of iterations without improvement exceeds noimprovelimit, then no convex combination is
2927 /* if the number of iterations without improvement is less than 2*noimprovelimit, then perturbation is
2945 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sepapoint, result, infeasible, auxviol, type, checkint) );
2947 SCIPsetDebugMsg(set, "solved Benders' decomposition subproblems with stabilised point. noimprovecount %d result %d\n",
2970 * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
2971 * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
2994 return (int) SCIPsetCeil(set, (SCIP_Real) SCIPbendersGetNSubproblems(benders)*benders->subprobfrac);
3077 solvestat->avgiter = (SCIP_Real)(solvestat->avgiter*solvestat->ncalls + SCIPgetNLPIterations(subproblem))
3091 /** Solves each of the Benders' decomposition subproblems for the given solution. All, or a fraction, of subproblems are
3093 * Since a convex relaxation of the subproblem could be solved to generate cuts, a parameter nverified is used to
3094 * identified the number of subproblems that have been solved in their "original" form. For example, if the subproblem
3095 * is a MIP, then if the LP is solved to generate cuts, this does not constitute a verification. The verification is
3109 SCIP_Bool** subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
3111 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
3137 * NOTE: This may not be correct. The Benders' decomposition parallelisation should not take all minimum threads if
3138 * they are specified. The number of threads should be specified with the Benders' decomposition parameters.
3145 /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
3146 * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
3147 * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
3152 SCIPsetDebugMsg(set, "Performing the subproblem solving process. Number of subproblems to check %d\n", nsolveidx);
3158 /* TODO: Check whether this is absolutely necessary. I think that this if statment can be removed. */
3164 /* TODO: ensure that the each of the subproblems solve and update the parameters with the correct return values
3167 #pragma omp parallel for num_threads(numthreads) private(i) reduction(&&:locoptimal) reduction(||:locinfeasible) reduction(+:locnverified) reduction(||:locstopped) reduction(min:retcode)
3185 /* for the second solving loop, if the problem is an LP, it is not solved again. If the problem is a MIP,
3186 * then the subproblem objective function value is set to infinity. However, if the subproblem is proven
3188 * If the solve loop is SCIP_BENDERSSOLVELOOP_USERCIP, then nothing is done. It is assumed that the user will
3202 /* if the subproblem is independent, then it does not need to be solved. In this case, the nverified flag will
3207 /* NOTE: There is no need to update the optimal flag. This is because optimal is always TRUE until a
3210 /* if the auxiliary variable value is infinity, then the subproblem has not been solved yet. Currently the
3222 SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, but has not been solved."
3230 SCIPbendersSetSubproblemObjval(benders, i, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i));
3239 SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, setting status to OPTIMAL\n", i);
3245 if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX )
3250 retcode = SCIPbendersExecSubproblemSolve(benders, set, sol, i, solveloop, FALSE, &solved, &subinfeas, type);
3269 /* if the subproblems are solved to check integer feasibility, then the optimality check must be performed.
3270 * This will only be performed if checkint is TRUE and the subproblem was solved. The subproblem may not be
3275 /* if the subproblem is feasible, then it is necessary to update the value of the auxiliary variable to the
3289 /* It is only possible to determine the optimality of a solution within a given subproblem in four
3292 * ii) solveloop == SCIP_BENDERSOLVELOOP_CONVEX and only the convex relaxations will be checked.
3293 * iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP and the subproblem was solved, since the user has
3308 SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i), SCIPbendersGetSubproblemObjval(benders, i));
3313 SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i), SCIPbendersGetSubproblemObjval(benders, i));
3318 /* the nverified variable is only incremented when the original form of the subproblem has been solved.
3319 * What is meant by "original" is that the LP relaxation of CIPs are solved to generate valid cuts. So
3320 * if the subproblem is defined as a CIP, then it is only classified as checked if the CIP is solved.
3324 * ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP or USERCIP and the CIP for the subproblem has been
3328 if( ((solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX)
3345 SCIPsetDebugMsg(set, "Local variable values: nverified %d infeasible %u optimal %u stopped %u\n", locnverified,
3361 * The priority of the results are: SCIP_CONSADDED (SCIP_SEPARATED), SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_DIDNOTRUN. In
3378 SCIP_Bool* subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
3406 /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
3407 * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
3408 * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
3415 && SCIPsetGetStage(set) != SCIP_STAGE_TRANSFORMED && SCIPsetGetStage(set) != SCIP_STAGE_PRESOLVED
3428 /* cuts can only be generated if the subproblem is not independent and if it has been solved. Additionally, the
3446 /* the result is updated only if a Benders' cut is generated or one was not found. However, if a cut has
3447 * been found in a previous iteration, then the result is returned as SCIP_CONSADDED or SCIP_SEPARATED.
3448 * This result is permitted because if a constraint was added, the solution that caused the error in the cut
3453 || (!SCIPbenderscutIsLPCut(benderscuts[j]) && ((solveloop == SCIP_BENDERSSOLVELOOP_CIP && !convexsub)
3480 /* the highest priority for the results is CONSADDED and SEPARATED. The solveloopresult will always be
3499 /* since a cut was not found, then merging could be useful to avoid this in subsequent iterations. The
3510 /* if the subproblem is infeasible and no cut generation methods were run, then the infeasibility will
3511 * never be resolved. As such, the subproblem will be merged into the master problem. If the subproblem
3550 if( addedcuts == 0 && SCIPbendersGetNConvexSubproblems(benders) < SCIPbendersGetNSubproblems(benders)
3559 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
3560 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
3561 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
3564 * TODO: consider allowing the possibility to pass solution information back from the subproblems instead of the scip
3565 * instance. This would allow the use of different solvers for the subproblems, more importantly allowing the use of an
3573 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
3574 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
3604 SCIPsetDebugMsg(set, "Starting Benders' decomposition subproblem solving. type %d checkint %u\n", type, checkint);
3618 /* It is assumed that the problem is optimal, until a subproblem is found not to be optimal. However, not all
3619 * subproblems could be checked in each iteration. As such, it is not possible to state that the problem is optimal
3620 * if not all subproblems are checked. Situations where this may occur is when a subproblem is a MIP and only the LP
3621 * is solved. Also, in a distributed computation, then it may be advantageous to only solve some subproblems before
3622 * resolving the master problem. As such, for a problem to be optimal, then (optimal && allverified) == TRUE
3633 /* if the Benders' decomposition is called from a sub-SCIP and the sub-SCIPs have been deactivated, then it is
3634 * assumed that this is an LNS heuristic. As such, the check is not performed and the solution is assumed to be
3641 || (type != SCIP_BENDERSENFOTYPE_CHECK && SCIPgetDepth(set->scip) == 0 && benders->lnsmaxcallsroot > -1
3648 /* it is not necessary to check all primal solutions by solving the Benders' decomposition subproblems.
3650 * If the solution is non-improving, the result FEASIBLE is returned. While this may be incorrect w.r.t to the
3651 * Benders' subproblems, this solution will never be the optimal solution. A non-improving solution may be used
3652 * within LNS primal heuristics. If this occurs, the improving solution, if found, will be checked by the solving
3656 if( checkint && SCIPsetIsLE(set, SCIPgetPrimalbound(set->scip)*(int)SCIPgetObjsense(set->scip),
3663 /* if the enforcement type is SCIP_BENDERSENFOTYPE_LP and the LP is currently unbounded. This could mean that there
3664 * is no lower bound on the auxiliary variables. In this case, we try to update the lower bound for the auxiliary
3667 if( type == SCIP_BENDERSENFOTYPE_LP && SCIPgetLPSolstat(set->scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY
3686 SCIP_CALL( benders->benderspresubsolve(set->scip, benders, sol, type, checkint, infeasible, auxviol, &skipsolve,
3696 SCIPerrorMessage("the user-defined pre subproblem solving method for the Benders' decomposition <%s> returned "
3701 /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
3710 /* the cut strengthening is performed before the regular subproblem solve is called. To avoid recursion, the flag
3711 * strengthenround is set to TRUE when the cut strengthening is performed. The cut strengthening is not performed as
3714 * NOTE: cut strengthening is only applied for fractional solutions and integer solutions if there are no CIP
3718 && (!checkint || SCIPbendersGetNConvexSubproblems(benders) == SCIPbendersGetNSubproblems(benders)) )
3723 /* if the user has not requested the solve to be skipped, then the cut strengthening is performed */
3724 SCIP_CALL( performInteriorSolCutStrengthening(benders, set, sol, type, checkint, FALSE, infeasible, auxviol,
3728 /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
3753 /* only a subset of the subproblems are initially solved. Both solving loops are executed for the subproblems to
3754 * check whether any cuts are generated. If a cut is generated, then no further subproblems are solved. If a cut is
3762 /* by default the number of solve loops is 1. This is the case if all subproblems are LP or the user has defined a
3763 * benderssolvesub callback. If there is a subproblem that is not an LP, then 2 solve loops are performed. The first
3770 SCIP_BENDERSSOLVELOOP solveloop; /* identifies what problem type is solve in this solve loop */
3772 /* if either benderssolvesubconvex or benderssolvesub are implemented, then the user callbacks are invoked */
3787 /* if the solving has been stopped, then the subproblem solving and cut generation must terminate */
3791 /* Generating cuts for the subproblems. Cuts are only generated when the solution is from primal heuristics,
3796 SCIP_CALL( generateBendersCuts(benders, set, sol, result, type, solveloop, checkint, subprobsolved,
3801 /* The first solving loop solves the convex subproblems and the convex relaxations of the CIP subproblems. The
3802 * second solving loop solves the CIP subproblems. The second solving loop is only called if the integer
3803 * feasibility is being checked and if the convex subproblems and convex relaxations are not infeasible.
3805 if( !(*infeasible) && checkint && !SCIPbendersOnlyCheckConvexRelax(benders, SCIPsetGetSubscipsOff(set))
3817 /* if the result is CONSADDED or SEPARATED, then a cut is generated and no further subproblem processing is
3832 SCIPsetDebugMsg(set, "End Benders' decomposition subproblem solve. result %d infeasible %u auxviol %u nverified %d\n",
3842 /* if the number of checked pseudo solutions exceeds a set limit, then all subproblems are passed as merge
3843 * candidates. Currently, merging subproblems into the master problem is the only method for resolving numerical
3846 * We are only interested in the pseudo solutions that have been checked completely for integrality. This is
3847 * identified by checkint == TRUE. This means that the Benders' decomposition constraint is one of the last
3848 * constraint handlers that must resolve the infeasibility. If the Benders' decomposition framework can't resolve the
3857 /* if a priority merge candidate already exists, then no other merge candidates need to be added.*/
3860 /* all subproblems are added to the merge candidate list. The first active subproblem is added as a
3875 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, " The number of checked pseudo solutions exceeds the "
3876 "limit of %d. All active subproblems are merge candidates, with subproblem %d a priority candidate.\n",
3884 /* if the result is SCIP_DIDNOTFIND, then there was a error in generating cuts in all subproblems that are not
3885 * optimal. This result does not cutoff any solution, so the Benders' decomposition algorithm will fail.
3887 * It could happen that the cut strengthening approach causes an error the cut generation. In this case, an error
3889 * TODO: Work out a way to ensure Benders' decomposition does not terminate due to a SCIP_DIDNOTFIND result.
3898 SCIPerrorMessage("An error was found when generating cuts for non-optimal subproblems of Benders' "
3899 "decomposition <%s>. Consider merging the infeasible subproblems into the master problem.\n", SCIPbendersGetName(benders));
3901 /* since no other cuts are generated, then this error will result in a crash. It is possible to avoid the error,
3904 * NOTE: If the error occurs while checking solutions, i.e. SCIP_BENDERSENFOTYPE_CHECK, then it is valid to set
3921 /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
3922 * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
3931 /* if the subproblems are being solved as part of conscheck, then the results flag must be returned after the solving
3940 /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
3941 * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
3949 /* calling the post-solve call back for the Benders' decomposition algorithm. This allows the user to work directly
3957 SCIP_CALL( benders->benderspostsolve(set->scip, benders, sol, type, mergecands, npriomergecands, nmergecands,
3964 /* since subproblems have been merged, then constraints have been added. This could resolve the unresolved
3971 SCIPerrorMessage("An error occurred during Benders' decomposition cut generations and no merging had been "
4010 SCIPsetDebugMsg(set, "End Benders' decomposition execution method. result %d infeasible %u auxviol %u\n", *result,
4023 /* if there was an error in generating cuts and merging was not performed, then the solution is perturbed in an
4034 /* if the user has not requested the solve to be skipped, then the cut strengthening is performed */
4035 SCIP_CALL( performInteriorSolCutStrengthening(benders, set, sol, type, checkint, TRUE, infeasible, auxviol,
4045 /* if the Benders' decomposition subproblem check stopped, then we don't have a valid result. In this case, the
4051 /* if the subproblem verification identifies the solution as feasible, then a check whether slack variables have been
4052 * used is necessary. If any slack variables are non-zero, then the solution is reverified after the objective
4073 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(set->scip), set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "Increasing the slack variable coefficient to %g.\n", benders->slackvarcoef);
4077 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(set->scip), set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "Fixing the slack variables to zero.\n");
4081 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sol, result, infeasible, auxviol, type, checkint) );
4092 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sol, result, infeasible, auxviol, type, checkint) );
4110 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
4120 assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
4124 /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
4152 SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned invalid result <%d>\n",
4163 SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned objective value %g\n",
4181 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
4203 if( subproblem == NULL && (benders->benderssolvesubconvex == NULL || benders->benderssolvesub == NULL) )
4205 SCIPerrorMessage("The subproblem %d is set to NULL, but both bendersSolvesubconvex%s and bendersSolvesub%s "
4214 /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
4215 if( solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
4217 /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
4219 SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &objective, &result) );
4231 /* if the limits of the master problem were hit during the setup process, then the subproblem will not have
4243 SCIP_CALL( updateEventhdlrUpperbound(benders, probnumber, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, probnumber)) );
4252 SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, &solvestatus, &objective) );
4265 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, FALSE) );
4270 /* if the generic subproblem solving methods are used, then the CIP subproblems are always solved. */
4288 * If a subproblem is unbounded, then the auxiliary variables are set to -infinity and the unbounded flag is
4303 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, " Benders' decomposition: Error solving "
4309 SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4315 SCIPerrorMessage("Invalid status returned from solving Benders' decomposition subproblem %d. Solution status: %d\n",
4322 assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
4329 SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4335 SCIPerrorMessage("Invalid result <%d> from user-defined subproblem solving method. This should not happen.\n",
4369 SCIPerrorMessage("The subproblem %d is NULL. Thus, the subproblem setup must be performed manually in either "
4378 /* if the Benders' decomposition subproblem is convex and has continuous variables, then probing mode
4380 * If the subproblem contains non-convex constraints or discrete variables, then the problem must be initialised,
4381 * and then put into SCIP_STAGE_SOLVING to be able to change the variable bounds. The probing mode is entered once
4406 /* looping over all variables in the subproblem to find those corresponding to the master problem variables. */
4407 /* TODO: It should be possible to store the pointers to the master variables to speed up the subproblem setup */
4414 /* It is possible due to numerics that the solution value exceeds the upper or lower bounds. When this
4415 * happens, it causes an error in the LP solver as a result of inconsistent bounds. So the following statements
4416 * are used to ensure that the bounds are not exceeded when applying the fixings for the Benders'
4442 /* if the slack variables have been added to help improve feasibility, then they remain unfixed with a large
4443 * objective coefficient. Once the root node has been solved to optimality, then the slack variables are
4446 if( benders->feasibilityphase && SCIPgetDepth(set->scip) == 0 && type != SCIP_BENDERSENFOTYPE_CHECK )
4448 /* The coefficient update or variable fixing can only be performed if the subproblem is in probing mode.
4465 /* if the subproblem is non-linear and convex, then slack variables have been added to the subproblem. These
4466 * need to be fixed to zero when first solving the subproblem. However, if the slack variables have been added
4480 /* if the subproblem contain non-convex constraints or discrete variables, then the probing mode is entered after
4494 /** Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving
4495 * methods. If the generic method is called, then the subproblem must be set up before calling this method. */
4513 if( SCIPbendersSubproblem(benders, probnumber) != NULL && !SCIPbendersSubproblemIsSetup(benders, probnumber)
4516 SCIPerrorMessage("Benders' decomposition subproblem %d must be set up before calling SCIPbendersSolveSubproblem(). Call SCIPsetupSubproblem() first.\n", probnumber);
4520 /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
4532 SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &subobj, &result) );
4545 if( solvecip && SCIPbendersGetSubproblemType(benders, probnumber) != SCIP_BENDERSSUBTYPE_CONVEXCONT )
4549 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, solvecip) );
4554 (*objective) = SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem);
4560 /* if the subproblem has convex constraints and continuous variables, then it should have been initialised and
4565 /* if the subproblem is not in probing mode, then it must be put into that mode for the LP solve. */
4584 SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, &solvestatus, &lpobjective) );
4618 /* setting the time limit for the Benders' decomposition subproblems. It is set to 102% of the remaining time. */
4628 submemorylimit = mastermemorylimit - (SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0;
4652 SCIP_CALL( SCIPgetBoolParam(subproblem, "lp/alwaysgetduals", &origparams->lp_alwaysgetduals) );
4655 SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxrounds", &origparams->prop_maxrounds) );
4656 SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxroundsroot", &origparams->prop_maxroundsroot) );
4657 SCIP_CALL( SCIPgetIntParam(subproblem, "constraints/linear/propfreq", &origparams->cons_linear_propfreq) );
4734 SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxroundsroot", origparams->prop_maxroundsroot) );
4735 SCIP_CALL( SCIPsetIntParam(subproblem, "constraints/linear/propfreq", origparams->cons_linear_propfreq) );
4761 /* TODO: This should be solved just as an LP, so as a MIP. There is too much overhead with the MIP.
4766 /* only solve the NLP relaxation if the NLP has been constructed and there exists an NLPI. If it is not possible to
4802 if( nlptermstat == SCIP_NLPTERMSTAT_OKAY && (nlpsolstat == SCIP_NLPSOLSTAT_LOCINFEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_GLOBINFEASIBLE) )
4822 SCIPerrorMessage("The NLP of Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4836 SCIPerrorMessage("Invalid solution status: %d. Termination status: %d. Solving the NLP relaxation of Benders' decomposition subproblem %d.\n",
4866 SCIPerrorMessage("The LP of Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4890 SCIPerrorMessage("Invalid status: %d. Solving the LP relaxation of Benders' decomposition subproblem %d.\n",
4931 /* If the solve has been stopped for the subproblem, then we need to restart it to complete the solve. The subproblem
4935 /* the subproblem should be in probing mode. Otherwise, the event handler did not work correctly */
4941 /* the problem was interrupted in the event handler, so SCIP needs to be informed that the problem is to be restarted */
4959 /* if the problem is not in probing mode, then we need to solve the LP. That requires all methods that will
4984 SCIPerrorMessage("Invalid status: %d. Solving the CIP of Benders' decomposition subproblem %d.\n",
5007 || (benders->bendersfreesub == NULL && benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL));
5023 /* ending probing mode to reset the current node. The probing mode will be restarted at the next solve */
5031 /* if the subproblems were solved as part of an enforcement stage, then they will still be in probing mode. The
5048 /** compares the subproblem objective value with the auxiliary variable value for optimality */
5067 SCIPsetDebugMsg(set, "Subproblem %d - Auxiliary Variable: %g Subproblem Objective: %g Reldiff: %g Soltol: %g\n",
5069 SCIPrelDiff(SCIPbendersGetSubproblemObjval(benders, probnumber), auxiliaryvarval), benders->solutiontol);
5071 if( SCIPrelDiff(SCIPbendersGetSubproblemObjval(benders, probnumber), auxiliaryvarval) < benders->solutiontol )
5096 /** Solves an independent subproblem to identify its lower bound. The lower bound is then used to update the bound on
5125 SCIPinfoMessage(set->scip, NULL, "Benders' decomposition: a bendersSolvesub or bendersSolvesubconvex has been "
5128 "SCIPbendersUpdateSubproblemLowerbound in bendersCreatesub. The auxiliary variable %d will remain as %g\n",
5135 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Computing a lower bound for"
5156 /* if the subproblem is independent, then the default SCIP settings are used. Otherwise, only the root node is solved
5167 /* if the subproblem not independent and is convex, then the probing LP is solved. Otherwise, the MIP is solved */
5191 if( nlptermstat == SCIP_NLPTERMSTAT_OKAY && (nlpsolstat == SCIP_NLPSOLSTAT_LOCINFEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_GLOBINFEASIBLE) )
5216 /* if the subproblem is not convex, then event handlers have been added to interrupt the solve. These must be
5219 eventhdlrdata = SCIPeventhdlrGetData(SCIPfindEventhdlr(subproblem, MIPNODEFOCUS_EVENTHDLR_NAME));
5242 /* the subproblem must be freed so that it is reset for the subsequent Benders' decomposition solves. If the
5243 * subproblems are independent, they are not freed. SCIPfreeBendersSubproblem must still be called, but in this
5244 * function the independent subproblems are not freed. However, they will still be freed at the end of the
5252 /** Merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and
5253 * constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. The reason for
5254 * keeping the subproblem available is for when it is queried for solutions after the problem is solved.
5256 * Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that
5259 * The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem
5265 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of subproblem variables corresponding
5292 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, " Benders' decomposition: Infeasibility of subproblem %d can't "
5293 "be resolved. Subproblem %d is being merged into the master problem.\n", probnumber, probnumber);