benders.c
Go to the documentation of this file.
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58 #define SCIP_DEFAULT_TRANSFERCUTS FALSE /** should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
59 #define SCIP_DEFAULT_CUTSASCONSS TRUE /** should the transferred cuts be added as constraints? */
60 #define SCIP_DEFAULT_LNSCHECK TRUE /** should the Benders' decomposition be used in LNS heuristics */
62 #define SCIP_DEFAULT_LNSMAXCALLS 10 /** the maximum number of Benders' decomposition calls in LNS heuristics */
63 #define SCIP_DEFAULT_LNSMAXCALLSROOT 0 /** the maximum number of root node Benders' decomposition calls in LNS heuristics */
64 #define SCIP_DEFAULT_SUBPROBFRAC 1.0 /** fraction of subproblems that are solved in each iteration */
65 #define SCIP_DEFAULT_UPDATEAUXVARBOUND FALSE /** should the auxiliary variable lower bound be updated by solving the subproblem */
66 #define SCIP_DEFAULT_AUXVARSIMPLINT FALSE /** set the auxiliary variables as implint if the subproblem objective is integer */
67 #define SCIP_DEFAULT_CUTCHECK TRUE /** should cuts be generated during the checking of solutions? */
68 #define SCIP_DEFAULT_STRENGTHENMULT 0.5 /** the convex combination multiplier for the cut strengthening */
69 #define SCIP_DEFAULT_NOIMPROVELIMIT 5 /** the maximum number of cut strengthening without improvement */
70 #define SCIP_DEFAULT_STRENGTHENPERTURB 1e-06 /** the amount by which the cut strengthening solution is perturbed */
71 #define SCIP_DEFAULT_STRENGTHENENABLED FALSE /** enable the core point cut strengthening approach */
72 #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) */
73 #define SCIP_DEFAULT_NUMTHREADS 1 /** the number of parallel threads to use when solving the subproblems */
74 #define SCIP_DEFAULT_EXECFEASPHASE FALSE /** should a feasibility phase be executed during the root node processing */
75 #define SCIP_DEFAULT_SLACKVARCOEF 1e+6 /** the initial objective coefficient of the slack variables in the subproblem */
76 #define SCIP_DEFAULT_MAXSLACKVARCOEF 1e+9 /** the maximal objective coefficient of the slack variables in the subproblem */
77 #define SCIP_DEFAULT_CHECKCONSCONVEXITY TRUE /** should the constraints of the subproblem be checked for convexity? */
80 #define BENDERS_MAXPSEUDOSOLS 5 /** the maximum number of pseudo solutions checked before suggesting
85 #define AUXILIARYVAR_NAME "##bendersauxiliaryvar" /** the name for the Benders' auxiliary variables in the master problem */
86 #define SLACKVAR_NAME "##bendersslackvar" /** the name for the Benders' slack variables added to each
95 #define MIPNODEFOCUS_EVENTHDLR_DESC "node focus event handler for the MIP solve method for Benders' decomposition"
98 #define UPPERBOUND_EVENTHDLR_DESC "found solution event handler to terminate subproblem solve for a given upper bound"
236 /* sending an interrupt solve signal to return the control back to the Benders' decomposition plugin.
240 SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
246 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
259 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
319 SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
327 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
340 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
397 if( SCIPisLT(scip, SCIPgetSolOrigObj(scip, bestsol)*(int)SCIPgetObjsense(scip), eventhdlrdata->upperbound) )
405 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
418 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
471 eventhdlr = SCIPfindEventhdlr(SCIPbendersSubproblem(benders, probnumber), UPPERBOUND_EVENTHDLR_NAME);
485 * This function solves the master problem with only the auxiliary variables in the objective function.
576 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
589 /* The event is only caught if there is an active Benders' decomposition, the integer subproblem are solved and
592 if( SCIPbendersIsActive(benders) && !SCIPbendersOnlyCheckConvexRelax(benders, SCIPgetSubscipsOff(scip))
602 /* ---------------- Methods for the parallelisation of Benders' decomposition ---------------- */
688 /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
695 /* if the current Benders is the highest priority Benders, then we need to create the auxiliary variables.
696 * Otherwise, if the shareauxvars flag is set, then the auxiliary variables from the highest priority Benders' are
704 /* if the auxiliary variables are shared, then a pointer to the variable is retrieved from topbenders,
716 /* set the variable type of the auxiliary variables to implicit integer if the objective function of the
717 * subproblem is guaranteed to be integer. This behaviour is controlled through a user parameter.
718 * NOTE: It is only possible to determine if the objective function is integral if the subproblem is defined as
727 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_%d_%s", AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders) );
728 SCIP_CALL( SCIPcreateVarBasic(scip, &auxiliaryvar, varname, benders->subproblowerbound[i], SCIPinfinity(scip),
747 /** assigns the copied auxiliary variables in the target SCIP to the target Benders' decomposition data */
766 /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
773 /* if the auxiliary variable are shared, then the variable name will have a suffix of the highest priority Benders'
790 /* the prefix for the variable names is required for UG, since we don't know how many copies have been made. To
791 * find the target variable, we start with an empty prefix. Then t_ is prepended until the target variable is
798 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s%s_%d_%s", prefix, AUXILIARYVAR_NAME, i, SCIPbendersGetName(topbenders));
800 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s%s_%d_%s", prefix, AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders));
802 /* finding the variable in the copied problem that has the same name as the auxiliary variable */
868 return strcmp(SCIPbendersGetName((SCIP_BENDERS*)elem1), SCIPbendersGetName((SCIP_BENDERS*)elem2));
886 /** creates a variable mapping between the master problem variables of the source scip and the sub scip */
909 /* creating the hashmap for the mapping between the master variable of the target and source scip */
914 /* getting the variable pointer for the target SCIP variables. The variable mapping returns the target SCIP
938 SCIP_BENDERS* targetbenders; /* the copy of the Benders' decomposition struct in the target set */
948 if( benders->benderscopy != NULL && targetset->benders_copybenders && SCIPbendersIsActive(benders) )
950 SCIPsetDebugMsg(targetset, "including Benders' decomposition %s in subscip %p\n", SCIPbendersGetName(benders), (void*)targetset->scip);
978 /* When the Benders' decomposition is copied then a variable mapping between the master problem variables is
979 * required. This variable mapping is used to transfer the cuts generated in the target SCIP to the source SCIP.
980 * The variable map is stored in the target Benders' decomposition. This will be freed when the sub-SCIP is freed.
1011 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
1015 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
1016 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
1017 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
1018 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
1019 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
1020 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
1021 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
1022 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
1023 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
1024 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
1025 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
1036 /* Checking whether the benderssolvesub and the bendersfreesub are both implemented or both are not implemented */
1040 SCIPerrorMessage("Benders' decomposition <%s> requires that if bendersFreesub%s is implemented, then at least "
1041 "one of bendersSolvesubconvex%s or bendersSolvesub%s are implemented.\n", name, name, name, name);
1076 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of Benders' decomposition <%s>", name);
1083 "should Benders' cuts be generated for LP solutions?", &(*benders)->cutlp, FALSE, cutlp, NULL, NULL) ); /*lint !e740*/
1087 "should Benders' cuts be generated for pseudo solutions?", &(*benders)->cutpseudo, FALSE, cutpseudo, NULL, NULL) ); /*lint !e740*/
1091 "should Benders' cuts be generated for relaxation solutions?", &(*benders)->cutrelax, FALSE, cutrelax, NULL, NULL) ); /*lint !e740*/
1093 /* These parameters are left for the user to decide in a settings file. This departs from the usual SCIP convention
1098 "should Benders' cuts from LNS heuristics be transferred to the main SCIP instance?", &(*benders)->transfercuts,
1103 "should Benders' decomposition be used in LNS heurisics?", &(*benders)->lnscheck, FALSE, SCIP_DEFAULT_LNSCHECK,
1108 "maximum depth at which the LNS check is performed (-1: no limit)", &(*benders)->lnsmaxdepth, TRUE,
1113 "the maximum number of Benders' decomposition calls in LNS heuristics (-1: no limit)", &(*benders)->lnsmaxcalls,
1118 "the maximum number of root node Benders' decomposition calls in LNS heuristics (-1: no limit)",
1133 "should the auxiliary variable bound be updated by solving the subproblem?", &(*benders)->updateauxvarbound,
1138 "if the subproblem objective is integer, then define the auxiliary variables as implicit integers?",
1153 "the maximum number of cut strengthening without improvement", &(*benders)->noimprovelimit, TRUE,
1158 "the constant use to perturb the cut strengthening core point", &(*benders)->perturbeps, FALSE,
1163 "should the core point cut strengthening be employed (only applied to fractional solutions or continuous subproblems)?",
1164 &(*benders)->strengthenenabled, FALSE, SCIP_DEFAULT_STRENGTHENENABLED, NULL, NULL) ); /*lint !e740*/
1168 "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)",
1169 &(*benders)->strengthenintpoint, FALSE, SCIP_DEFAULT_STRENGTHENINTPOINT, "lfiroz", NULL, NULL) ); /*lint !e740*/
1178 "should a feasibility phase be executed during the root node, i.e. adding slack variables to constraints to ensure feasibility",
1183 "the initial objective coefficient of the slack variables in the subproblem", &(*benders)->slackvarcoef, FALSE,
1188 "the maximal objective coefficient of the slack variables in the subproblem", &(*benders)->maxslackvarcoef, FALSE,
1193 "should the constraints of the subproblems be checked for convexity?", &(*benders)->checkconsconvexity, FALSE,
1206 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
1220 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
1224 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
1225 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
1226 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
1227 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
1228 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
1229 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
1230 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
1231 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
1232 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
1233 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
1234 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
1242 SCIP_CALL_FINALLY( doBendersCreate(benders, set, messagehdlr, blkmem, name, desc, priority, cutlp, cutpseudo,
1243 cutrelax, shareauxvars, benderscopy, bendersfree, bendersinit, bendersexit, bendersinitpre, bendersexitpre,
1244 bendersinitsol, bendersexitsol, bendersgetvar, benderscreatesub, benderspresubsolve, benderssolvesubconvex,
1245 benderssolvesub, benderspostsolve, bendersfreesub, bendersdata), (void) SCIPbendersFree(benders, set) );
1305 /* if the Benders' decomposition is a copy and a varmap has been passed to SCIP_BENDERS, then the variable map
1356 /* checking whether the constraint is a linear constraint. If so, we add a coefficient to the constraint */
1369 "This is not supported and the slack variable will not be added to the constraint. Feasibility cuts may be invalid.\n",
1389 /* if the right hand side is finite, then we need to add a slack variable with a negative coefficient */
1394 SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), objcoef, SCIP_VARTYPE_CONTINUOUS) );
1413 /* if the left hand side if finite, then we need to add a slack variable with a positive coefficient */
1418 SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), objcoef, SCIP_VARTYPE_CONTINUOUS) );
1440 /** adds the slack variables to each of the constraints for the generation of feasibility cuts for the given non-linear
1476 SCIP_CALL( addSlackVars(subproblem, benders, cons, linearconshdlrs, nlconshdlr, NLINEARCONSHDLRS) );
1482 /** initialises a MIP subproblem by putting the problem into SCIP_STAGE_SOLVING. This is achieved by calling SCIPsolve
1484 * The LP subproblem is also initialised using this method; however, a different event handler is added. This event
1486 * The MIP solving function is called to initialise the subproblem because this function calls SCIPsolve with the
1511 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, FALSE) );
1527 /** initialises an LP subproblem by putting the problem into probing mode. The probing mode is invoked in a node focus
1528 * event handler. This event handler is added just prior to calling the initialise subproblem function.
1553 SCIP_CALL( SCIPincludeEventhdlrBasic(subproblem, &eventhdlr, NODEFOCUS_EVENTHDLR_NAME, NODEFOCUS_EVENTHDLR_DESC,
1567 /** checks whether the convex relaxation of the subproblem is sufficient to solve the original problem to optimality
1570 * To do this, we check that all variables are of continuous type and that every constraint is either handled by known
1571 * linear constraint handler (knapsack, linear, logicor, setppc, varbound) or the nonlinear constraint handler.
1573 * Further, nonlinear constraints are only considered if an NLP solver interface is available, i.e., and NLP could
1575 * If constraints are present that cannot be identified as linear or convex nonlinear, then we assume that the
1619 SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, &nbinvars, &nintvars, &nimplintvars, NULL) );
1621 /* if there are any binary, integer or implicit integer variables, then the subproblems is marked as non-convex */
1634 /* Get pointer to the nonlinear constraint handler if we also have an NLP solver to solve NLPs.
1635 * If there is no NLP solver, but there are (convex) nonlinear constraints, then the LP relaxation of subproblems
1636 * will (currently) not be sufficient to solve subproblems to optimality. Thus, we also take the presence of convex
1637 * nonlinear constraints as signal for having to solve the CIP eventually, thus, by abuse of notation,
1638 * return not-convex here. In summary, we do not need to have a special look onto non-linear constraints
1639 * if no NLP solver is present, and can treat them as any other constraint that is not of linear type.
1646 /* if the nonlinear constraint handler exists, then we create a hashmap of variables that can be assumed to be fixed.
1653 SCIP_CALL( SCIPhashmapCreate(&assumevarfixed, SCIPblkmem(set->scip), SCIPgetNVars(subproblem)) );
1682 SCIPdebugMsg(subproblem, "subproblem <%s>: constraint <%s> is linear\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1714 /* make sure activities are up to date. SCIPhasExprCurvature currently assumes that this is already the case */
1717 SCIP_CALL( SCIPhasExprCurvature(subproblem, SCIPgetExprNonlinear(cons), havelhs ? SCIP_EXPRCURV_CONCAVE : SCIP_EXPRCURV_CONVEX, &isconvex, assumevarfixed) );
1724 SCIPdebugMsg(subproblem, "subproblem <%s>: nonlinear constraint <%s> is convex\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1731 SCIPdebugMsg(subproblem, "subproblem <%s>: nonlinear constraint <%s> not convex\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1738 SCIPdebugMsg(subproblem, "subproblem <%s>: potentially nonconvex constraint <%s>\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1747 /* setting the flag for the convexity of the subproblem. If convexity doesn't need to be checked, then it is assumed
1748 * that the subproblems are convex. However, if there are discrete variables, then the problem must be set as
1749 * non-convex. The discrete master variables will be changed to continuous, but this will happen at the first call to
1776 SCIPsetDebugMsg(set, "subproblem <%s> has been found to be of type %d\n", SCIPgetProbName(subproblem),
1806 /* if the subproblems have already been created, then they will not be created again. This is the case if the
1807 * transformed problem has been freed and then retransformed. The subproblems should only be created when the problem
1822 /* the subproblem SCIP instance could be set to NULL. This is because user defined subproblem solving methods
1823 * could be used that don't solve a SCIP instance. Thus, the following setup of the subproblem SCIP instance is
1826 * NOTE: since the subproblems are supplied as NULL pointers, the internal convexity check can not be performed.
1837 /* The objective function coefficients of the master problem are set to zero. This is necessary for the Benders'
1838 * decomposition algorithm, since the cut methods and the objective function check assumes that the objective
1841 * This only occurs if the Benders' decomposition is not a copy. It is assumed that the correct objective
1844 * If the subproblems were copied, then the master variables will be checked to ensure that they have a zero
1857 /* if mastervar is not NULL, then the subproblem variable has a corresponding master problem variable */
1860 SCIPverbMessage(subproblem, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Changing the objective "
1872 SCIPverbMessage(subproblem, SCIP_VERBLEVEL_HIGH, NULL, "Benders' decomposition: Objective coefficients of "
1880 /* checking the convexity of the subproblem. The convexity of the subproblem indicates whether the convex
1885 /* if the problem is convex and has nonlinear constraints, then slack variables must be added to each of the
1892 /* the slack variables are only added to the subproblem once. If the initialisation methods are called from a
1893 * copy, then the slack variables are not re-added. Alternatively, if the copy must be threadsafe, then the
1901 /* setting the flag to indicate that slack variables have been added to the subproblem constraints. This is only
1908 /* after checking the subproblem for convexity, if the subproblem has convex constraints and continuous variables,
1913 /* if the user has not implemented a solve subproblem callback, then the subproblem solves are performed
1926 /* because the subproblems could be reused in the copy, the event handler is not created again. If the
1928 * NOTE: This currently works with the benders_default implementation. It may not be very general. */
1963 SCIPerrorMessage("If the subproblem is set to NULL, then the subproblem type must be specified.\n");
1964 SCIPerrorMessage("In the subproblem creation callback, call SCIPbendersSetSubproblemType with the appropriate problem type.\n");
1971 /* checking the convexity of the master problem. This information is useful for the cut generation methods, such as
2019 /* if the Benders' decomposition is a copy, then the auxiliary variables already exist. So they are registered with
2020 * the Benders' decomposition struct during the init stage. If the Benders' decomposition is not a copy, then the
2029 /* creates the subproblems and sets up the probing mode for LP subproblems. This function calls the benderscreatesub
2039 SCIP_ALLOC( BMSallocBlockMemoryArray(SCIPblkmem(set->scip), &benders->storedcuts, BENDERS_ARRAYSIZE) );
2058 /** Transfers Benders' cuts that were generated while solving a sub-SCIP to the original SCIP instance. This involves
2059 * creating a constraint/cut that is equivalent to the generated cut in the sub-SCIP. This new constraint/cut is then
2074 SCIP_CONSHDLR* consbenders; /* a helper variable for the Benders' decomposition constraint handler */
2075 SCIP_CONS* transfercons = NULL; /* the constraint that is generated to transfer the constraints/cuts */
2101 * SCIPcreateConsBasicLinear/SCIPcreateEmptyRowConshdlr. This should be implemented to improve the performance of the
2108 SCIP_CALL( SCIPcreateConsBasicLinear(sourcescip, &transfercons, cutname, 0, NULL, NULL, lhs, rhs) );
2113 SCIP_CALL( SCIPcreateEmptyRowConshdlr(sourcescip, &transfercut, consbenders, cutname, lhs, rhs, FALSE,
2129 /* if the source variable is not found, then the mapping in incomplete. So the constraint can not be
2252 /* if the Benders' decomposition is a copy, then is a variable mapping was provided, then the generated cuts will
2263 SCIPfreeBlockMemoryArray(set->scip, &benders->storedcuts[i]->vals, benders->storedcuts[i]->nvars);
2264 SCIPfreeBlockMemoryArray(set->scip, &benders->storedcuts[i]->vars, benders->storedcuts[i]->nvars);
2276 /* it is possible that the master problem is not solved. As such, the auxiliary variables will not be created. So
2281 /* we need to remove the locks from the auxiliary variables. This will be called always for the highest priority
2285 SCIP_CALL( SCIPaddVarLocksType(set->scip, benders->auxiliaryvars[i], SCIP_LOCKTYPE_MODEL, -1, 0) );
2333 /* looping over all subproblems to check whether there exists at least one master problem variable */
2338 /* if there are user defined solving or freeing functions, then it is not possible to declare the independence of
2353 /* if the subporblem variable is not NULL, then the subproblem depends on the master problem */
2380 /* if the Benders' decomposition is the original, then the auxiliary variables need to be created. If the Benders'
2381 * decomposition is a copy, then the auxiliary variables already exist. The assignment of the auxiliary variables
2386 /* check the subproblem independence. This check is only performed if the user has not implemented a solve
2484 /* freeing all subproblems that are independent, this is because they have not bee freed during the subproblem
2511 /* sorting the Benders' decomposition cuts in order of priority. Only a single cut is generated for each subproblem
2512 * per solving iteration. This is particularly important in the case of the optimality and feasibility cuts. Since
2513 * these work on two different solutions to the subproblem, it is not necessary to generate both cuts. So, once the
2604 SCIP_CALL( SCIPincludeEventhdlrBasic(set->scip, &eventhdlr, NODESOLVED_EVENTHDLR_NAME, NODESOLVED_EVENTHDLR_DESC,
2637 /* if the subproblems were created by the Benders' decomposition core, then they need to be freed */
2686 /** updates the lower bound for all auxiliary variables. This is called if the first LP enforced is unbounded. */
2713 SCIP_CALL( SCIPbendersComputeSubproblemLowerbound(benders, set, i, &lowerbound, &infeasible) );
2728 SCIPsetDebugMsg(set, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
2741 /** sets the core point used for cut strengthening. If the strenghtenintpoint is set to 'i', then the core point is
2755 /* if the core point is not NULL and the interior point is not reinitialised, then nothing is done */
2761 /* if the core point should be updated, then this only happens if the incumbent solution has been updated */
2794 /* if there is time remaining, then compute the relative interior point. Otherwise, return the LP solution */
2797 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Computing relative interior point (time limit: %g, iter limit: %d) ...\n", timelimit, INT_MAX);
2798 SCIP_CALL( SCIPcomputeLPRelIntPoint(scip, TRUE, FALSE, timelimit, INT_MAX, &benders->corepoint) );
2838 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
2839 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
2840 SCIP_Bool* skipsolve, /**< should the main solve be skipped as a result of this strengthening? */
2856 /* the cut stabilisation is only performed when enforcing LP solutions. The solution is not NULL if the stabilisation
2873 /* if the number of iterations without improvement exceeds 3*noimprovelimit, then the no stabilisation is performed
2878 /* if there is no incumbent solution, then it is not possible to create the core point and hence the strengthening
2884 /* if no LP iterations have been performed since the last call of the cut strenghtening, then the strengthening is
2892 /* if the separation point solution is NULL, then we create the solution using the current LP relaxation. */
2896 * TODO: This could be a little to memory heavy, it may be better just to create the separation point once and then
2905 /* creating a solution that is a convex combination of the LP solution and the separation point */
2927 /* if the variable is a linking variable and it is not fixed, then a convex combination with the corepoint is
2932 /* if the number of iterations without improvement exceeds noimprovelimit, then no convex combination is
2943 /* if the number of iterations without improvement is less than 2*noimprovelimit, then perturbation is
2961 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sepapoint, result, infeasible, auxviol, type, checkint) );
2963 SCIPsetDebugMsg(set, "solved Benders' decomposition subproblems with stabilised point. noimprovecount %d result %d\n",
2986 * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
2987 * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
3010 return (int) SCIPsetCeil(set, (SCIP_Real) SCIPbendersGetNSubproblems(benders)*benders->subprobfrac);
3093 solvestat->avgiter = (SCIP_Real)(solvestat->avgiter*solvestat->ncalls + SCIPgetNLPIterations(subproblem))
3107 /** Solves each of the Benders' decomposition subproblems for the given solution. All, or a fraction, of subproblems are
3109 * Since a convex relaxation of the subproblem could be solved to generate cuts, a parameter nverified is used to
3110 * identified the number of subproblems that have been solved in their "original" form. For example, if the subproblem
3111 * is a MIP, then if the LP is solved to generate cuts, this does not constitute a verification. The verification is
3125 SCIP_Bool** subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
3127 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
3153 * NOTE: This may not be correct. The Benders' decomposition parallelisation should not take all minimum threads if
3154 * they are specified. The number of threads should be specified with the Benders' decomposition parameters.
3161 /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
3162 * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
3163 * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
3168 SCIPsetDebugMsg(set, "Performing the subproblem solving process. Number of subproblems to check %d\n", nsolveidx);
3174 /* TODO: Check whether this is absolutely necessary. I think that this if statment can be removed. */
3180 /* TODO: ensure that the each of the subproblems solve and update the parameters with the correct return values
3183 #pragma omp parallel for num_threads(numthreads) private(i) reduction(&&:locoptimal) reduction(||:locinfeasible) reduction(+:locnverified) reduction(||:locstopped) reduction(min:retcode)
3201 /* for the second solving loop, if the problem is an LP, it is not solved again. If the problem is a MIP,
3202 * then the subproblem objective function value is set to infinity. However, if the subproblem is proven
3204 * If the solve loop is SCIP_BENDERSSOLVELOOP_USERCIP, then nothing is done. It is assumed that the user will
3218 /* if the subproblem is independent, then it does not need to be solved. In this case, the nverified flag will
3223 /* NOTE: There is no need to update the optimal flag. This is because optimal is always TRUE until a
3226 /* if the auxiliary variable value is infinity, then the subproblem has not been solved yet. Currently the
3238 SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, but has not been solved."
3246 SCIPbendersSetSubproblemObjval(benders, i, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i));
3255 SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, setting status to OPTIMAL\n", i);
3261 if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX )
3266 retcode = SCIPbendersExecSubproblemSolve(benders, set, sol, i, solveloop, FALSE, &solved, &subinfeas, type);
3285 /* if the subproblems are solved to check integer feasibility, then the optimality check must be performed.
3286 * This will only be performed if checkint is TRUE and the subproblem was solved. The subproblem may not be
3291 /* if the subproblem is feasible, then it is necessary to update the value of the auxiliary variable to the
3305 /* It is only possible to determine the optimality of a solution within a given subproblem in four
3308 * ii) solveloop == SCIP_BENDERSOLVELOOP_CONVEX and only the convex relaxations will be checked.
3309 * iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP and the subproblem was solved, since the user has
3324 SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i), SCIPbendersGetSubproblemObjval(benders, i));
3329 SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i), SCIPbendersGetSubproblemObjval(benders, i));
3334 /* the nverified variable is only incremented when the original form of the subproblem has been solved.
3335 * What is meant by "original" is that the LP relaxation of CIPs are solved to generate valid cuts. So
3336 * if the subproblem is defined as a CIP, then it is only classified as checked if the CIP is solved.
3340 * ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP or USERCIP and the CIP for the subproblem has been
3344 if( ((solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX)
3361 SCIPsetDebugMsg(set, "Local variable values: nverified %d infeasible %u optimal %u stopped %u\n", locnverified,
3377 * The priority of the results are: SCIP_CONSADDED (SCIP_SEPARATED), SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_DIDNOTRUN. In
3394 SCIP_Bool* subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
3422 /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
3423 * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
3424 * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
3431 && SCIPsetGetStage(set) != SCIP_STAGE_TRANSFORMED && SCIPsetGetStage(set) != SCIP_STAGE_PRESOLVED
3444 /* cuts can only be generated if the subproblem is not independent and if it has been solved. Additionally, the
3462 /* the result is updated only if a Benders' cut is generated or one was not found. However, if a cut has
3463 * been found in a previous iteration, then the result is returned as SCIP_CONSADDED or SCIP_SEPARATED.
3464 * This result is permitted because if a constraint was added, the solution that caused the error in the cut
3469 || (!SCIPbenderscutIsLPCut(benderscuts[j]) && ((solveloop == SCIP_BENDERSSOLVELOOP_CIP && !convexsub)
3496 /* the highest priority for the results is CONSADDED and SEPARATED. The solveloopresult will always be
3515 /* since a cut was not found, then merging could be useful to avoid this in subsequent iterations. The
3526 /* if the subproblem is infeasible and no cut generation methods were run, then the infeasibility will
3527 * never be resolved. As such, the subproblem will be merged into the master problem. If the subproblem
3566 if( addedcuts == 0 && SCIPbendersGetNConvexSubproblems(benders) < SCIPbendersGetNSubproblems(benders)
3575 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
3576 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
3577 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
3580 * TODO: consider allowing the possibility to pass solution information back from the subproblems instead of the scip
3581 * instance. This would allow the use of different solvers for the subproblems, more importantly allowing the use of an
3589 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
3590 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
3620 SCIPsetDebugMsg(set, "Starting Benders' decomposition subproblem solving. type %d checkint %u\n", type, checkint);
3634 /* It is assumed that the problem is optimal, until a subproblem is found not to be optimal. However, not all
3635 * subproblems could be checked in each iteration. As such, it is not possible to state that the problem is optimal
3636 * if not all subproblems are checked. Situations where this may occur is when a subproblem is a MIP and only the LP
3637 * is solved. Also, in a distributed computation, then it may be advantageous to only solve some subproblems before
3638 * resolving the master problem. As such, for a problem to be optimal, then (optimal && allverified) == TRUE
3649 /* if the Benders' decomposition is called from a sub-SCIP and the sub-SCIPs have been deactivated, then it is
3650 * assumed that this is an LNS heuristic. As such, the check is not performed and the solution is assumed to be
3657 || (type != SCIP_BENDERSENFOTYPE_CHECK && SCIPgetDepth(set->scip) == 0 && benders->lnsmaxcallsroot > -1
3664 /* it is not necessary to check all primal solutions by solving the Benders' decomposition subproblems.
3666 * If the solution is non-improving, the result FEASIBLE is returned. While this may be incorrect w.r.t to the
3667 * Benders' subproblems, this solution will never be the optimal solution. A non-improving solution may be used
3668 * within LNS primal heuristics. If this occurs, the improving solution, if found, will be checked by the solving
3672 if( checkint && SCIPsetIsLE(set, SCIPgetPrimalbound(set->scip)*(int)SCIPgetObjsense(set->scip),
3679 /* if the enforcement type is SCIP_BENDERSENFOTYPE_LP and the LP is currently unbounded. This could mean that there
3680 * is no lower bound on the auxiliary variables. In this case, we try to update the lower bound for the auxiliary
3683 if( type == SCIP_BENDERSENFOTYPE_LP && SCIPgetLPSolstat(set->scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY
3702 SCIP_CALL( benders->benderspresubsolve(set->scip, benders, sol, type, checkint, infeasible, auxviol, &skipsolve,
3712 SCIPerrorMessage("the user-defined pre subproblem solving method for the Benders' decomposition <%s> returned "
3717 /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
3726 /* the cut strengthening is performed before the regular subproblem solve is called. To avoid recursion, the flag
3727 * strengthenround is set to TRUE when the cut strengthening is performed. The cut strengthening is not performed as
3730 * NOTE: cut strengthening is only applied for fractional solutions and integer solutions if there are no CIP
3734 && (!checkint || SCIPbendersGetNConvexSubproblems(benders) == SCIPbendersGetNSubproblems(benders)) )
3739 /* if the user has not requested the solve to be skipped, then the cut strengthening is performed */
3740 SCIP_CALL( performInteriorSolCutStrengthening(benders, set, sol, type, checkint, FALSE, infeasible, auxviol,
3744 /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
3769 /* only a subset of the subproblems are initially solved. Both solving loops are executed for the subproblems to
3770 * check whether any cuts are generated. If a cut is generated, then no further subproblems are solved. If a cut is
3778 /* by default the number of solve loops is 1. This is the case if all subproblems are LP or the user has defined a
3779 * benderssolvesub callback. If there is a subproblem that is not an LP, then 2 solve loops are performed. The first
3786 SCIP_BENDERSSOLVELOOP solveloop; /* identifies what problem type is solve in this solve loop */
3788 /* if either benderssolvesubconvex or benderssolvesub are implemented, then the user callbacks are invoked */
3803 /* if the solving has been stopped, then the subproblem solving and cut generation must terminate */
3807 /* Generating cuts for the subproblems. Cuts are only generated when the solution is from primal heuristics,
3812 SCIP_CALL( generateBendersCuts(benders, set, sol, result, type, solveloop, checkint, subprobsolved,
3817 /* The first solving loop solves the convex subproblems and the convex relaxations of the CIP subproblems. The
3818 * second solving loop solves the CIP subproblems. The second solving loop is only called if the integer
3819 * feasibility is being checked and if the convex subproblems and convex relaxations are not infeasible.
3821 if( !(*infeasible) && checkint && !SCIPbendersOnlyCheckConvexRelax(benders, SCIPsetGetSubscipsOff(set))
3833 /* if the result is CONSADDED or SEPARATED, then a cut is generated and no further subproblem processing is
3848 SCIPsetDebugMsg(set, "End Benders' decomposition subproblem solve. result %d infeasible %u auxviol %u nverified %d\n",
3858 /* if the number of checked pseudo solutions exceeds a set limit, then all subproblems are passed as merge
3859 * candidates. Currently, merging subproblems into the master problem is the only method for resolving numerical
3862 * We are only interested in the pseudo solutions that have been checked completely for integrality. This is
3863 * identified by checkint == TRUE. This means that the Benders' decomposition constraint is one of the last
3864 * constraint handlers that must resolve the infeasibility. If the Benders' decomposition framework can't resolve the
3873 /* if a priority merge candidate already exists, then no other merge candidates need to be added.*/
3876 /* all subproblems are added to the merge candidate list. The first active subproblem is added as a
3891 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, " The number of checked pseudo solutions exceeds the "
3892 "limit of %d. All active subproblems are merge candidates, with subproblem %d a priority candidate.\n",
3900 /* if the result is SCIP_DIDNOTFIND, then there was a error in generating cuts in all subproblems that are not
3901 * optimal. This result does not cutoff any solution, so the Benders' decomposition algorithm will fail.
3903 * It could happen that the cut strengthening approach causes an error the cut generation. In this case, an error
3905 * TODO: Work out a way to ensure Benders' decomposition does not terminate due to a SCIP_DIDNOTFIND result.
3914 SCIPerrorMessage("An error was found when generating cuts for non-optimal subproblems of Benders' "
3915 "decomposition <%s>. Consider merging the infeasible subproblems into the master problem.\n", SCIPbendersGetName(benders));
3917 /* since no other cuts are generated, then this error will result in a crash. It is possible to avoid the error,
3920 * NOTE: If the error occurs while checking solutions, i.e. SCIP_BENDERSENFOTYPE_CHECK, then it is valid to set
3937 /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
3938 * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
3947 /* if the subproblems are being solved as part of conscheck, then the results flag must be returned after the solving
3956 /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
3957 * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
3965 /* calling the post-solve call back for the Benders' decomposition algorithm. This allows the user to work directly
3973 SCIP_CALL( benders->benderspostsolve(set->scip, benders, sol, type, mergecands, npriomergecands, nmergecands,
3980 /* since subproblems have been merged, then constraints have been added. This could resolve the unresolved
3987 SCIPerrorMessage("An error occurred during Benders' decomposition cut generations and no merging had been "
4026 SCIPsetDebugMsg(set, "End Benders' decomposition execution method. result %d infeasible %u auxviol %u\n", *result,
4039 /* if there was an error in generating cuts and merging was not performed, then the solution is perturbed in an
4050 /* if the user has not requested the solve to be skipped, then the cut strengthening is performed */
4051 SCIP_CALL( performInteriorSolCutStrengthening(benders, set, sol, type, checkint, TRUE, infeasible, auxviol,
4061 /* if the Benders' decomposition subproblem check stopped, then we don't have a valid result. In this case, the
4067 /* if the subproblem verification identifies the solution as feasible, then a check whether slack variables have been
4068 * used is necessary. If any slack variables are non-zero, then the solution is reverified after the objective
4089 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(set->scip), set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "Increasing the slack variable coefficient to %g.\n", benders->slackvarcoef);
4093 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(set->scip), set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "Fixing the slack variables to zero.\n");
4097 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sol, result, infeasible, auxviol, type, checkint) );
4108 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sol, result, infeasible, auxviol, type, checkint) );
4126 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
4136 assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
4140 /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
4168 SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned invalid result <%d>\n",
4179 SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned objective value %g\n",
4197 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
4219 if( subproblem == NULL && (benders->benderssolvesubconvex == NULL || benders->benderssolvesub == NULL) )
4221 SCIPerrorMessage("The subproblem %d is set to NULL, but both bendersSolvesubconvex%s and bendersSolvesub%s "
4230 /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
4231 if( solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
4233 /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
4235 SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &objective, &result) );
4247 /* if the limits of the master problem were hit during the setup process, then the subproblem will not have
4259 SCIP_CALL( updateEventhdlrUpperbound(benders, probnumber, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, probnumber)) );
4268 SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, &solvestatus, &objective) );
4281 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, FALSE) );
4286 /* if the generic subproblem solving methods are used, then the CIP subproblems are always solved. */
4304 * If a subproblem is unbounded, then the auxiliary variables are set to -infinity and the unbounded flag is
4319 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, " Benders' decomposition: Error solving "
4325 SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4331 SCIPerrorMessage("Invalid status returned from solving Benders' decomposition subproblem %d. Solution status: %d\n",
4338 assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
4345 SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4351 SCIPerrorMessage("Invalid result <%d> from user-defined subproblem solving method. This should not happen.\n",
4385 SCIPerrorMessage("The subproblem %d is NULL. Thus, the subproblem setup must be performed manually in either "
4394 /* if the Benders' decomposition subproblem is convex and has continuous variables, then probing mode
4396 * If the subproblem contains non-convex constraints or discrete variables, then the problem must be initialised,
4397 * and then put into SCIP_STAGE_SOLVING to be able to change the variable bounds. The probing mode is entered once
4422 /* looping over all variables in the subproblem to find those corresponding to the master problem variables. */
4423 /* TODO: It should be possible to store the pointers to the master variables to speed up the subproblem setup */
4430 /* It is possible due to numerics that the solution value exceeds the upper or lower bounds. When this
4431 * happens, it causes an error in the LP solver as a result of inconsistent bounds. So the following statements
4432 * are used to ensure that the bounds are not exceeded when applying the fixings for the Benders'
4458 /* if the slack variables have been added to help improve feasibility, then they remain unfixed with a large
4459 * objective coefficient. Once the root node has been solved to optimality, then the slack variables are
4462 if( benders->feasibilityphase && SCIPgetDepth(set->scip) == 0 && type != SCIP_BENDERSENFOTYPE_CHECK )
4464 /* The coefficient update or variable fixing can only be performed if the subproblem is in probing mode.
4481 /* if the subproblem is non-linear and convex, then slack variables have been added to the subproblem. These
4482 * need to be fixed to zero when first solving the subproblem. However, if the slack variables have been added
4496 /* if the subproblem contain non-convex constraints or discrete variables, then the probing mode is entered after
4510 /** Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving
4511 * methods. If the generic method is called, then the subproblem must be set up before calling this method. */
4529 if( SCIPbendersSubproblem(benders, probnumber) != NULL && !SCIPbendersSubproblemIsSetup(benders, probnumber)
4532 SCIPerrorMessage("Benders' decomposition subproblem %d must be set up before calling SCIPbendersSolveSubproblem(). Call SCIPsetupSubproblem() first.\n", probnumber);
4536 /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
4548 SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &subobj, &result) );
4561 if( solvecip && SCIPbendersGetSubproblemType(benders, probnumber) != SCIP_BENDERSSUBTYPE_CONVEXCONT )
4565 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, solvecip) );
4570 (*objective) = SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem);
4576 /* if the subproblem has convex constraints and continuous variables, then it should have been initialised and
4581 /* if the subproblem is not in probing mode, then it must be put into that mode for the LP solve. */
4600 SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, &solvestatus, &lpobjective) );
4634 /* setting the time limit for the Benders' decomposition subproblems. It is set to 102% of the remaining time. */
4644 submemorylimit = mastermemorylimit - (SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0;
4668 SCIP_CALL( SCIPgetBoolParam(subproblem, "lp/alwaysgetduals", &origparams->lp_alwaysgetduals) );
4671 SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxrounds", &origparams->prop_maxrounds) );
4672 SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxroundsroot", &origparams->prop_maxroundsroot) );
4673 SCIP_CALL( SCIPgetIntParam(subproblem, "constraints/linear/propfreq", &origparams->cons_linear_propfreq) );
4750 SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxroundsroot", origparams->prop_maxroundsroot) );
4751 SCIP_CALL( SCIPsetIntParam(subproblem, "constraints/linear/propfreq", origparams->cons_linear_propfreq) );
4787 /* TODO: This should be solved just as an LP, so as a MIP. There is too much overhead with the MIP.
4792 /* only solve the NLP relaxation if the NLP has been constructed and there exists an NLPI. If it is not possible to
4828 if( nlptermstat == SCIP_NLPTERMSTAT_OKAY && (nlpsolstat == SCIP_NLPSOLSTAT_LOCINFEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_GLOBINFEASIBLE) )
4848 SCIPerrorMessage("The NLP of Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4859 SCIPwarningMessage(scip, "The NLP solver stopped due to an iteration limit for Benders' decomposition subproblem %d. Consider increasing benders/%s/nlpiterlimit.\n", probnumber, SCIPbendersGetName(benders));
4868 SCIPerrorMessage("Invalid solution status: %d. Termination status: %d. Solving the NLP relaxation of Benders' decomposition subproblem %d.\n",
4898 SCIPerrorMessage("The LP of Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4922 SCIPerrorMessage("Invalid status: %d. Solving the LP relaxation of Benders' decomposition subproblem %d.\n",
4963 /* If the solve has been stopped for the subproblem, then we need to restart it to complete the solve. The subproblem
4967 /* the subproblem should be in probing mode. Otherwise, the event handler did not work correctly */
4973 /* the problem was interrupted in the event handler, so SCIP needs to be informed that the problem is to be restarted */
4991 /* if the problem is not in probing mode, then we need to solve the LP. That requires all methods that will
5016 SCIPerrorMessage("Invalid status: %d. Solving the CIP of Benders' decomposition subproblem %d.\n",
5039 || (benders->bendersfreesub == NULL && benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL));
5055 /* ending probing mode to reset the current node. The probing mode will be restarted at the next solve */
5063 /* if the subproblems were solved as part of an enforcement stage, then they will still be in probing mode. The
5080 /** compares the subproblem objective value with the auxiliary variable value for optimality */
5099 SCIPsetDebugMsg(set, "Subproblem %d - Auxiliary Variable: %g Subproblem Objective: %g Reldiff: %g Soltol: %g\n",
5101 SCIPrelDiff(SCIPbendersGetSubproblemObjval(benders, probnumber), auxiliaryvarval), benders->solutiontol);
5103 if( SCIPrelDiff(SCIPbendersGetSubproblemObjval(benders, probnumber), auxiliaryvarval) < benders->solutiontol )
5128 /** Solves an independent subproblem to identify its lower bound. The lower bound is then used to update the bound on
5157 SCIPinfoMessage(set->scip, NULL, "Benders' decomposition: a bendersSolvesub or bendersSolvesubconvex has been "
5160 "SCIPbendersUpdateSubproblemLowerbound in bendersCreatesub. The auxiliary variable %d will remain as %g\n",
5167 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Computing a lower bound for"
5188 /* if the subproblem is independent, then the default SCIP settings are used. Otherwise, only the root node is solved
5199 /* if the subproblem not independent and is convex, then the probing LP is solved. Otherwise, the MIP is solved */
5223 if( nlptermstat == SCIP_NLPTERMSTAT_OKAY && (nlpsolstat == SCIP_NLPSOLSTAT_LOCINFEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_GLOBINFEASIBLE) )
5247 /* if the subproblem is not convex, then event handlers have been added to interrupt the solve. These must be
5250 eventhdlrdata = SCIPeventhdlrGetData(SCIPfindEventhdlr(subproblem, MIPNODEFOCUS_EVENTHDLR_NAME));
5273 /* the subproblem must be freed so that it is reset for the subsequent Benders' decomposition solves. If the
5274 * subproblems are independent, they are not freed. SCIPfreeBendersSubproblem must still be called, but in this
5275 * function the independent subproblems are not freed. However, they will still be freed at the end of the
5283 /** Merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and
5284 * constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. The reason for
5285 * keeping the subproblem available is for when it is queried for solutions after the problem is solved.
5287 * Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that
5290 * The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem
5296 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of subproblem variables corresponding