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);
5295 /* freeing the subproblem because it will be flagged as independent. Since the subproblem is flagged as independent,
5316 SCIP_CALL( SCIPhashmapCreate(&localconsmap, SCIPblkmem(set->scip), SCIPgetNConss(subproblem)) );
5328 SCIP_CALL( SCIPcreateConsBasicLinear(set->scip, &objcons, consname, 0, NULL, NULL, -SCIPsetInfinity(set), 0.0) );
5338 /* if the master problem variable is not NULL, then there is a corresponding variable in the master problem for
5347 /* This is following the same process as in createVariableMappings. The original variable is used to map
5373 /* creating the mapping betwen the subproblem var and the master var for the constraint copying */
5394 /* NOTE: adding all subproblem constraints appears to cause an error when resolving the LP, which results in the
5395 * current incumbent being reported as optimal. To avoid this, only half of the subproblem constraints are added
5400 SCIP_CALL( SCIPgetConsCopy(subproblem, set->scip, conss[i], &targetcons, SCIPconsGetHdlr(conss[i]),
5402 SCIPconsIsEnforced(conss[i]), SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE,
5435 /* the merged subproblem is no longer solved. This is indicated by setting the subproblem as disabled. The
5443 /** when applying a decomposition from a supplied format, constraints must be transferred from the master problem to the
5450 SCIP_HASHMAP* varmap, /**< the variable hash map mapping the source variables to the target variables */
5466 SCIPdebugMessage("Adding constraint <%s> to Benders' decomposition subproblem\n", SCIPconsGetName(sourcecons));
5477 /* checking all variables to see whether they already exist in the subproblem. If they don't exist, then the variable
5488 SCIP_CALL( SCIPcreateVar(subproblem, &var, SCIPvarGetName(consvars[i]), SCIPvarGetLbGlobal(consvars[i]),
5490 SCIPvarIsInitial(consvars[i]), SCIPvarIsRemovable(consvars[i]), NULL, NULL, NULL, NULL, NULL) );
5507 SCIP_CALL( SCIPgetConsCopy(scip, subproblem, sourcecons, &cons, SCIPconsGetHdlr(sourcecons), varmap, NULL,
5509 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons), SCIPconsIsMarkedPropagate(sourcecons),
5516 SCIPerrorMessage("It is not possible to copy constraint <%s>. Benders' decomposition could not be applied.\n",
5527 /** removes the variables and constraints from the master problem that have been transferred to a subproblem when the
5573 /** Applies a Benders' decomposition to the problem based upon the decomposition selected from the storage */
5613 SCIP_CALL( SCIPcopyPlugins(set->scip, subproblems[i], TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE,
5646 /* we are only interested in the constraints that are in the blocks. These are identified by a label >= 0 */
5649 SCIP_CALL( addConstraintToBendersSubproblem(set, subproblems[conslabels[i]], varmaps[conslabels[i]],
5654 /* removing the variables and constraints from the master problem that have been added to the subproblem */
5655 SCIP_CALL( removeVariablesAndConstraintsFromMaster(set->scip, conss, vars, conslabels, varslabels, nconss, nvars) );
5664 * TODO: consider whether the two-phase method should be activated by default in the scenario stages.
5674 /* disabling aggregation since it can affect the mapping between the master and subproblem variables */
5710 /* if the variable name matches the auxiliary variable, then the master variable is returned as NULL */
5787 SCIP_DECL_BENDERSINITPRE((*bendersinitpre))/**< initialize presolving for Benders' decomposition */
5798 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))/**< deinitialize presolving for Benders' decomposition */
5809 SCIP_DECL_BENDERSINITSOL((*bendersinitsol))/**< solving process initialization callback of Benders' decomposition */
5820 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))/**< solving process deinitialization callback of Benders' decomposition */
5831 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))/**< called prior to the subproblem solving loop */
5842 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))/**< solving method for the convex Benders' decomposition subproblem */
5853 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))/**< solving method for a Benders' decomposition subproblem */
5864 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))/**< solving process deinitialization callback of Benders' decomposition */
5875 SCIP_DECL_SORTPTRCOMP((*benderssubcomp)) /**< a comparator for defining the solving order of the subproblems */
5960 /** gets the number of times, the Benders' decomposition was called and tried to find a variable with negative reduced costs */
5970 /** gets the number of optimality cuts found by the collection of Benders' decomposition subproblems */
6030 /** enables or disables all clocks of the Benders' decomposition, depending on the value of the flag */
6032 SCIP_BENDERS* benders, /**< the Benders' decomposition for which all clocks should be enabled or disabled */
6092 /** adds a subproblem to the Benders' decomposition data. If a custom subproblem solving method is used, then the
6103 /* if the subproblem pointer is NULL, then the subproblem solving callback functions must be set. */
6106 SCIPerrorMessage("The subproblem can only be set to NULL if both bendersSolvesubconvex%s and bendersSolvesub%s "
6202 /* if the slack variables have not been added, then we can immediately state that no slack variables are active */
6215 /* if the subproblem is convex and an NLP, then we need to create the NLP solution. Otherwise, the solution can be
6305 * It is possible that this can change during the solving process. One example is when the three-phase method is
6306 * employed, where the first phase solves the convex relaxation of both the master and subproblems, the second phase
6307 * reintroduces the integrality constraints to the master problem and the third phase then reintroduces integrality
6358 SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
6371 assert(benders->nnonlinearsubprobs >= 0 && benders->nnonlinearsubprobs <= benders->nsubproblems);
6399 SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
6451 /* only set the master problem variable to continuous if they have not already been changed. */
6483 /* if all of the integer variables have been changed to continuous, then the subproblem could now be a convex
6484 * problem. This must be checked and if TRUE, then the LP subproblem is initialised and then put into probing
6492 /* if the subproblem has convex constraints and continuous variables, then it is initialised and put into
6542 /* if the user has defined solving or freeing functions, then it is not possible to declare a subproblem as
6543 * independent. This is because declaring a subproblem as independent changes the solving loop, so it would change
6544 * the expected behaviour of the user defined plugin. If a user calls this function, then an error will be returned.
6546 if( benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL || benders->bendersfreesub != NULL )
6548 SCIPerrorMessage("The user has defined either bendersSolvesubconvex%s, bendersSolvesub%s or bendersFreesub%s. "
6549 "Thus, it is not possible to declare the independence of a subproblem.\n", benders->name, benders->name,
6557 /* if the active status of the subproblem changes, then we must update the activesubprobs counter */
6568 assert(benders->nactivesubprobs >= 0 && benders->nactivesubprobs <= SCIPbendersGetNSubproblems(benders));
6584 /** Sets whether the subproblem is enabled or disabled. A subproblem is disabled if it has been merged into the master
6598 /* if the active status of the subproblem changes, then we must update the activesubprobs counter */
6609 assert(benders->nactivesubprobs >= 0 && benders->nactivesubprobs <= SCIPbendersGetNSubproblems(benders));
6612 /** returns whether the subproblem is enabled, i.e. the subproblem is still solved in the solving loop. */
6634 /* if the master variables were all continuous and now are not, then the subproblem must exit probing mode and be
6646 assert(subtype == SCIP_BENDERSSUBTYPE_CONVEXCONT || subtype == SCIP_BENDERSSUBTYPE_NONCONVEXCONT);
6681 /** updates the lower bound for the subproblem. If the lower bound is not greater than the previously stored lowerbound,
6697 SCIPdebugMessage("The lowerbound %g for subproblem %d is less than the currently stored lower bound %g\n",
6752 /** returns the original problem data for the cuts that have been added by the Benders' cut plugin. The stored
6753 * variables and values will populate the input vars and vals arrays. Thus, memory must be allocated for the vars and
6907 /** returns the array of currently available Benders' cuts; active Benders' decomposition are in the first slots of
SCIP_RETCODE SCIPbenderscutExec(SCIP_BENDERSCUT *benderscut, SCIP_SET *set, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
Definition: benderscut.c:337
int SCIPbendersGetNBenderscuts(SCIP_BENDERS *benders)
Definition: benders.c:6927
void SCIPbendersSetSubproblemType(SCIP_BENDERS *benders, int probnumber, SCIP_BENDERSSUBTYPE subprobtype)
Definition: benders.c:6267
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
Definition: type_result.h:33
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3510
Definition: type_nlpi.h:155
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
Definition: type_result.h:37
Definition: struct_dcmp.h:35
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:103
static SCIP_RETCODE updateAuxiliaryVarLowerbound(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_RESULT *result)
Definition: benders.c:2672
SCIP_RETCODE SCIPbendersIncludeBenderscut(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_BENDERSCUT *benderscut)
Definition: benders.c:6864
SCIP_RETCODE SCIPcomputeLPRelIntPoint(SCIP *scip, SCIP_Bool relaxrows, SCIP_Bool inclobjcutoff, SCIP_Real timelimit, int iterlimit, SCIP_SOL **point)
Definition: scip_lp.c:1085
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6258
Definition: type_nlpi.h:154
SCIP_RETCODE SCIPbendersSetupSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type)
Definition: benders.c:4345
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6170
void SCIPsetBendersPriority(SCIP *scip, SCIP_BENDERS *benders, int priority)
Definition: scip_benders.c:581
SCIP_RETCODE SCIPsetEventhdlrInitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINITSOL((*eventinitsol)))
Definition: scip_event.c:183
Definition: type_lp.h:39
SCIP_RETCODE SCIPbendersSolveSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_Bool *infeasible, SCIP_Bool solvecip, SCIP_Real *objective)
Definition: benders.c:4496
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:438
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_linear.c:18010
Definition: struct_scip.h:59
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1706
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:188
int SCIPbendersGetNStrengthenCutsFound(SCIP_BENDERS *benders)
Definition: benders.c:5981
Definition: type_nlpi.h:156
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
int SCIPbendersGetNStoredCuts(SCIP_BENDERS *benders)
Definition: benders.c:6715
Definition: struct_benderscut.h:37
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:651
Definition: type_expr.h:52
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
Definition: type_benders.h:58
SCIP_RETCODE SCIPsetEventhdlrExitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXITSOL((*eventexitsol)))
Definition: scip_event.c:197
SCIP_Bool SCIPbendersIsInitialized(SCIP_BENDERS *benders)
Definition: benders.c:6043
internal methods for clocks and timing issues
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:88
SCIP_RETCODE SCIPsetEventhdlrExit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXIT((*eventexit)))
Definition: scip_event.c:169
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_Bool SCIPbendersSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6375
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:39
void SCIPbendersSetSolvesub(SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)))
Definition: benders.c:5851
Definition: type_result.h:38
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
static SCIP_RETCODE addSlackVars(SCIP *scip, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_CONSHDLR **linearconshdlrs, SCIP_CONSHDLR *nlconshdlr, int nlinearconshdlrs)
Definition: benders.c:1316
Definition: struct_var.h:198
SCIP_RETCODE SCIPbendersDeactivate(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:2598
Definition: type_benders.h:40
Definition: type_benders.h:46
static SCIP_RETCODE updateSubproblemLowerbound(SCIP *masterprob, SCIP_BENDERS *benders)
Definition: benders.c:478
void SCIPbendersSetMasterIsNonlinear(SCIP_BENDERS *benders, SCIP_Bool isnonlinear)
Definition: benders.c:6397
static int numSubproblemsToCheck(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_BENDERSENFOTYPE type)
Definition: benders.c:2984
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
Definition: type_message.h:45
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:897
Definition: type_message.h:41
void SCIPbendersSetData(SCIP_BENDERS *benders, SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:5730
SCIP_RETCODE SCIPbendersExit(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:2211
static SCIP_Bool subproblemIsActive(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:2999
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_RETCODE SCIPbendersExitpre(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_STAT *stat)
Definition: benders.c:2397
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
SCIP_RETCODE SCIPcreateBendersDefault(SCIP *scip, SCIP **subproblems, int nsubproblems)
Definition: benders_default.c:476
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6143
static SCIP_RETCODE initsolEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTTYPE eventtype)
Definition: benders.c:126
Definition: struct_message.h:36
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIP_Bool SCIPbendersGetMastervarsCont(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6660
Definition: type_benders.h:64
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
void SCIPbendersRemoveSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:6119
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:139
SCIP_RETCODE SCIPbendersSolveSubproblemLP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Real *objective)
Definition: benders.c:4744
void SCIPbendersSetFree(SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREE((*bendersfree)))
Definition: benders.c:5752
Definition: type_stat.h:43
void SCIPbendersSetExitpre(SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)))
Definition: benders.c:5796
Definition: type_result.h:40
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:225
SCIP_RETCODE SCIPbenderscutCopyInclude(SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SET *set)
Definition: benderscut.c:77
static SCIP_RETCODE addAuxiliaryVariablesToMaster(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders.c:666
internal methods for handling parameter settings
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4673
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:251
static SCIP_RETCODE executeUserDefinedSolvesub(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool *infeasible, SCIP_Real *objective, SCIP_RESULT *result)
Definition: benders.c:4105
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:361
Definition: type_message.h:46
void SCIPbendersSetInit(SCIP_BENDERS *benders, SCIP_DECL_BENDERSINIT((*bendersinit)))
Definition: benders.c:5763
Definition: type_lp.h:37
void SCIPbendersSetExit(SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXIT((*bendersexit)))
Definition: benders.c:5774
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
SCIP_RETCODE SCIPgetBendersSubproblemVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: scip_benders.c:687
SCIP_Bool SCIPbendersOnlyCheckConvexRelax(SCIP_BENDERS *benders, SCIP_Bool subscipsoff)
Definition: benders.c:2974
SCIP_RETCODE SCIPcopyPlugins(SCIP *sourcescip, SCIP *targetscip, SCIP_Bool copyreaders, SCIP_Bool copypricers, SCIP_Bool copyconshdlrs, SCIP_Bool copyconflicthdlrs, SCIP_Bool copypresolvers, SCIP_Bool copyrelaxators, SCIP_Bool copyseparators, SCIP_Bool copycutselectors, SCIP_Bool copypropagators, SCIP_Bool copyheuristics, SCIP_Bool copyeventhdlrs, SCIP_Bool copynodeselectors, SCIP_Bool copybranchrules, SCIP_Bool copydisplays, SCIP_Bool copydialogs, SCIP_Bool copytables, SCIP_Bool copyexprhdlrs, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:266
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6408
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
void SCIPbendersSetPostsolve(SCIP_BENDERS *benders, SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)))
Definition: benders.c:5862
static SCIP_RETCODE addConstraintToBendersSubproblem(SCIP_SET *set, SCIP *subproblem, SCIP_HASHMAP *varmap, SCIP_CONS *sourcecons)
Definition: benders.c:5447
SCIP_EXPRCURV SCIPgetCurvatureNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12326
internal methods for LP management
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
Definition: heur_padm.c:123
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18162
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPbendersApplyDecomposition(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_DECOMP *decomp)
Definition: benders.c:5574
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:171
Definition: type_benders.h:37
datastructures for Benders' decomposition cuts techniques
Definition: type_stat.h:34
Definition: type_retcode.h:44
SCIP_RETCODE SCIPconsAddCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: misc_linear.c:447
Definition: struct_benders.h:48
Definition: type_benders.h:39
static SCIP_RETCODE resetOrigSubproblemParams(SCIP *subproblem, SCIP_SUBPROBPARAMS *origparams)
Definition: benders.c:4715
SCIP_RETCODE SCIPsetAddCharParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:3086
void SCIPbendersSetFreesub(SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREESUB((*bendersfreesub)))
Definition: benders.c:5884
Definition: struct_sol.h:64
Definition: struct_set.h:63
SCIP_RETCODE SCIPbendersAddSubproblem(SCIP_BENDERS *benders, SCIP *subproblem)
Definition: benders.c:6095
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:335
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8173
Definition: struct_benders.h:37
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
SCIP_RETCODE SCIPdelVar(SCIP *scip, SCIP_VAR *var, SCIP_Bool *deleted)
Definition: scip_prob.c:1789
Definition: struct_misc.h:128
SCIP_RETCODE SCIPbendersSolveSubproblemCIP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Bool solvecip)
Definition: benders.c:4908
void SCIPbendersSetSolvesubconvex(SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)))
Definition: benders.c:5840
int SCIPbendersGetNTransferredCuts(SCIP_BENDERS *benders)
Definition: benders.c:6672
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:609
Definition: type_lp.h:40
Definition: type_clock.h:34
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1411
SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6292
static SCIP_RETCODE createSubproblems(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1773
void SCIPbendersSortBenderscutsName(SCIP_BENDERS *benders)
Definition: benders.c:6968
SCIP_RETCODE SCIPbendersInitsol(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:2423
Definition: type_nlpi.h:153
static SCIP_RETCODE createMasterVarMapping(SCIP_BENDERS *benders, SCIP_SET *sourceset, SCIP_HASHMAP *varmap)
Definition: benders.c:878
Definition: type_result.h:35
internal methods for storing and manipulating the main problem
Definition: struct_cons.h:37
SCIP_RETCODE SCIPbendersFreeSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:4999
void SCIPmessagePrintVerbInfo(SCIP_MESSAGEHDLR *messagehdlr, SCIP_VERBLEVEL verblevel, SCIP_VERBLEVEL msgverblevel, const char *formatstr,...)
Definition: message.c:669
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2558
Definition: type_paramset.h:54
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:141
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3489
static SCIP_RETCODE copyMemoryAndTimeLimits(SCIP *scip, SCIP *subproblem)
Definition: benders.c:4604
Definition: type_expr.h:51
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
static SCIP_RETCODE exitsolEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTTYPE eventtype)
Definition: benders.c:146
Definition: struct_cons.h:117
int SCIPbendersGetNNonlinearSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:6387
Definition: type_retcode.h:42
SCIP_RETCODE SCIPbenderscutFree(SCIP_BENDERSCUT **benderscut, SCIP_SET *set)
Definition: benderscut.c:194
Definition: type_benders.h:55
Definition: type_benders.h:47
void SCIPbendersSetExitsol(SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)))
Definition: benders.c:5818
static SCIP_RETCODE freeEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
Definition: benders.c:190
Definition: type_stat.h:52
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
void SCIPbendersSetPriority(SCIP_BENDERS *benders, SCIP_SET *set, int priority)
Definition: benders.c:5925
Definition: type_result.h:36
static SCIP_RETCODE initialiseLPSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:1515
Definition: struct_benders.h:169
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4763
static SCIP_RETCODE initEventhandlerData(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: benders.c:108
SCIP_RETCODE SCIPbendersExitsol(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:2456
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition: benders.c:5720
Definition: type_var.h:42
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12249
SCIP_Bool benderscutsnamessorted
Definition: struct_benders.h:159
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1482
SCIP_BENDERSCUT * SCIPfindBenderscut(SCIP_BENDERS *benders, const char *name)
Definition: benders.c:6888
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIP_RETCODE SCIPbendersSetMastervarsCont(SCIP_BENDERS *benders, int probnumber, SCIP_Bool arecont)
Definition: benders.c:6625
Definition: type_retcode.h:33
static SCIP_DECL_EVENTEXITSOL(eventExitsolBendersNodefocus)
Definition: benders.c:251
Definition: type_stat.h:33
void SCIPbendersEnableOrDisableClocks(SCIP_BENDERS *benders, SCIP_Bool enable)
Definition: benders.c:6031
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
internal methods for global SCIP settings
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
#define SCIP_DECL_BENDERSSOLVESUBCONVEX(x)
Definition: type_benders.h:250
SCIP_RETCODE SCIPbendersExec(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: benders.c:3568
Definition: type_result.h:42
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
internal methods for storing priced variables
SCIP_RETCODE SCIPhasExprCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV curv, SCIP_Bool *success, SCIP_HASHMAP *assumevarfixed)
Definition: nlhdlr_convex.c:2448
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:3014
void SCIPbendersSetSubproblemObjval(SCIP_BENDERS *benders, int probnumber, SCIP_Real objval)
Definition: benders.c:6153
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip_param.c:279
void SCIPbendersSetInitsol(SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITSOL((*bendersinitsol)))
Definition: benders.c:5807
SCIP_RETCODE SCIPbendersCreate(SCIP_BENDERS **benders, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSCOPY((*benderscopy)), SCIP_DECL_BENDERSFREE((*bendersfree)), SCIP_DECL_BENDERSINIT((*bendersinit)), SCIP_DECL_BENDERSEXIT((*bendersexit)), SCIP_DECL_BENDERSINITPRE((*bendersinitpre)), SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)), SCIP_DECL_BENDERSINITSOL((*bendersinitsol)), SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)), SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)), SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)), SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:1192
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2514
Definition: type_lp.h:34
Definition: type_retcode.h:34
SCIP_RETCODE SCIPbendersSolSlackVarsActive(SCIP_BENDERS *benders, SCIP_Bool *activeslack)
Definition: benders.c:6182
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:161
SCIP_RETCODE SCIPaddLinearVarNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_nonlinear.c:12510
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1577
SCIP_RETCODE SCIPbendersChgMastervarsToCont(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:6428
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4510
SCIP_RETCODE SCIPbendersInitpre(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_STAT *stat)
Definition: benders.c:2354
SCIP_BENDERS * SCIPfindBenders(SCIP *scip, const char *name)
Definition: scip_benders.c:484
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
void SCIPbendersSetPresubsolve(SCIP_BENDERS *benders, SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)))
Definition: benders.c:5829
public data structures and miscellaneous methods
int SCIPbendersGetNStrengthenCalls(SCIP_BENDERS *benders)
Definition: benders.c:5991
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
SCIP_RETCODE SCIPbendersComputeSubproblemLowerbound(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: benders.c:5099
Definition: type_var.h:55
int SCIPbendersGetNStrengthenFails(SCIP_BENDERS *benders)
Definition: benders.c:6001
void SCIPbendersSetSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isindep)
Definition: benders.c:6533
Definition: struct_misc.h:121
Definition: type_nlpi.h:168
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: type_message.h:43
SCIP_RETCODE SCIPsetGetIntParam(SCIP_SET *set, const char *name, int *value)
Definition: set.c:3167
SCIP_RETCODE SCIPbendersGetStoredCutOrigData(SCIP_BENDERS *benders, int cutidx, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int varssize)
Definition: benders.c:6756
Definition: struct_lp.h:192
void SCIPbendersSetInitpre(SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITPRE((*bendersinitpre)))
Definition: benders.c:5785
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_Bool SCIPbendersSubproblemIsOptimal(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber)
Definition: benders.c:5049
SCIP_RETCODE SCIPbendersFree(SCIP_BENDERS **benders, SCIP_SET *set)
Definition: benders.c:1271
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
static SCIP_RETCODE setSubproblemParams(SCIP *scip, SCIP *subproblem)
Definition: benders.c:4664
data structures required for Benders' decomposition
static SCIP_RETCODE createAndAddTransferredCut(SCIP *sourcescip, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
Definition: benders.c:2047
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:105
SCIP_RETCODE SCIPbenderscutInitsol(SCIP_BENDERSCUT *benderscut, SCIP_SET *set)
Definition: benderscut.c:289
static SCIP_RETCODE removeVariablesAndConstraintsFromMaster(SCIP *scip, SCIP_CONS **conss, SCIP_VAR **vars, int *conslabels, int *varslabels, int nconss, int nvars)
Definition: benders.c:5531
int SCIPbendersGetNCutsFound(SCIP_BENDERS *benders)
Definition: benders.c:5971
SCIP_RETCODE SCIPbendersMergeSubproblemIntoMaster(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int probnumber)
Definition: benders.c:5262
int SCIPbendersGetNConvexSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:6345
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5949
static SCIP_RETCODE transferBendersCuts(SCIP *sourcescip, SCIP *subscip, SCIP_BENDERS *benders)
Definition: benders.c:2165
SCIP_Real SCIPbendersGetAuxiliaryVarVal(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber)
Definition: benders.c:5078
Definition: type_set.h:45
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPbendersActivate(SCIP_BENDERS *benders, SCIP_SET *set, int nsubproblems)
Definition: benders.c:2512
SCIP_Bool SCIPbendersSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6573
Definition: type_set.h:42
static SCIP_RETCODE assignAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders.c:739
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12773
SCIP_Bool SCIPbendersSubproblemIsEnabled(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6613
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5939
Definition: type_nlpi.h:164
SCIP_RETCODE SCIPbendersGetVar(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: benders.c:5694
static SCIP_RETCODE exitEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
Definition: benders.c:170
void SCIPbendersSetSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isconvex)
Definition: benders.c:6310
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:652
SCIP_RETCODE SCIPsetGetRealParam(SCIP_SET *set, const char *name, SCIP_Real *value)
Definition: set.c:3195
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
Definition: type_lp.h:36
Definition: type_set.h:36
SCIP_RETCODE SCIPbendersCopyInclude(SCIP_BENDERS *benders, SCIP_SET *sourceset, SCIP_SET *targetset, SCIP_HASHMAP *varmap, SCIP_Bool threadsafe, SCIP_Bool *valid)
Definition: benders.c:918
SCIP_RETCODE SCIPbendersExecSubproblemSolve(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool enhancement, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_BENDERSENFOTYPE type)
Definition: benders.c:4176
internal methods for decompositions and the decomposition store
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition: benders.c:6418
Definition: type_set.h:35
SCIP_BENDERSCUT ** SCIPbendersGetBenderscuts(SCIP_BENDERS *benders)
Definition: benders.c:6910
static SCIP_RETCODE doBendersCreate(SCIP_BENDERS **benders, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSCOPY((*benderscopy)), SCIP_DECL_BENDERSFREE((*bendersfree)), SCIP_DECL_BENDERSINIT((*bendersinit)), SCIP_DECL_BENDERSEXIT((*bendersexit)), SCIP_DECL_BENDERSINITPRE((*bendersinitpre)), SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)), SCIP_DECL_BENDERSINITSOL((*bendersinitsol)), SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)), SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)), SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)), SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:989
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:389
static void createSolveSubproblemIndexList(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_BENDERSENFOTYPE type, int **solveidx, int *nsolveidx)
Definition: benders.c:3010
SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6703
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
static SCIP_RETCODE updateSubproblemStatQueue(SCIP_BENDERS *benders, int *solveidx, int nsolveidx, SCIP_Bool updatestat)
Definition: benders.c:3050
Definition: type_nlpi.h:151
SCIP_Bool SCIPbenderscutIsLPCut(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:574
SCIP_BENDERS * SCIPsetFindBenders(SCIP_SET *set, const char *name)
Definition: set.c:3811
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6684
Definition: type_benders.h:68
void SCIPbendersSortBenderscuts(SCIP_BENDERS *benders)
Definition: benders.c:6953
static SCIP_RETCODE checkSubproblemIndependence(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders.c:2298
void SCIPbendersSetBenderscutsSorted(SCIP_BENDERS *benders, SCIP_Bool sorted)
Definition: benders.c:6852
static SCIP_RETCODE releaseVarMappingHashmapVars(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders.c:1237
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPbenderscutExit(SCIP_BENDERSCUT *benderscut, SCIP_SET *set)
Definition: benderscut.c:259
SCIP_Bool SCIPbendersShareAuxVars(SCIP_BENDERS *benders)
Definition: benders.c:6083
public methods for message output
Definition: type_result.h:43
static SCIP_RETCODE updateEventhdlrUpperbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real upperbound)
Definition: benders.c:449
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1567
Definition: type_var.h:84
void SCIPbendersSetSubproblemComp(SCIP_BENDERS *benders, SCIP_DECL_SORTPTRCOMP((*benderssubcomp)))
Definition: benders.c:5873
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6276
static SCIP_RETCODE checkSubproblemConvexity(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:1563
SCIP_RETCODE SCIPbendersInit(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1967
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6073
Definition: type_benders.h:57
SCIP_RETCODE SCIPcreateCurrentSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:474
SCIP_Real SCIPbendersGetSetupTime(SCIP_BENDERS *benders)
Definition: benders.c:6011
SCIP_RETCODE SCIPbendersGetStoredCutData(SCIP_BENDERS *benders, int cutidx, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars)
Definition: benders.c:6725
int SCIPgetBendersNSubproblems(SCIP *scip, SCIP_BENDERS *benders)
Definition: scip_benders.c:713
Definition: type_set.h:44
Definition: type_lp.h:35
void SCIPbendersSetCopy(SCIP_BENDERS *benders, SCIP_DECL_BENDERSCOPY((*benderscopy)))
Definition: benders.c:5741
static void resetSubproblemObjectiveValue(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:823
Definition: type_nlpi.h:152
Definition: type_benders.h:56
Definition: type_benders.h:49
SCIP_Bool SCIPbendersSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6333
Definition: type_nlpi.h:165
static SCIP_RETCODE setAndUpdateCorePoint(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders.c:2729
Definition: type_lp.h:33
Definition: type_lp.h:38
SCIP_RETCODE SCIPbenderscutExitsol(SCIP_BENDERSCUT *benderscut, SCIP_SET *set)
Definition: benderscut.c:313
Definition: struct_stat.h:50
Definition: type_result.h:46
SCIP_Bool SCIPconsIsMarkedPropagate(SCIP_CONS *cons)
Definition: cons.c:8294
static SCIP_RETCODE storeOrigSubproblemParams(SCIP *subproblem, SCIP_SUBPROBPARAMS *origparams)
Definition: benders.c:4637
static SCIP_RETCODE addSlackVarsToConstraints(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:1428
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3096
static SCIP_RETCODE generateBendersCuts(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool checkint, SCIP_Bool *subprobsolved, SCIP_BENDERSSUBSTATUS *substatus, int *solveidx, int nsolveidx, int **mergecands, int *npriomergecands, int *nmergecands, int *nsolveloops)
Definition: benders.c:3370
Definition: struct_benders.h:178
common defines and data types used in all packages of SCIP
SCIPallocBlockMemory(scip, subsol))
void SCIPbendersSetSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber, SCIP_Bool issetup)
Definition: benders.c:6508
SCIP_RETCODE SCIPsetAddRealParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:3062
static SCIP_DECL_EVENTINITSOL(eventInitsolBendersNodefocus)
Definition: benders.c:238
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:325
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6131
static SCIP_RETCODE performInteriorSolCutStrengthening(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint, SCIP_Bool perturbsol, SCIP_Bool *auxviol, SCIP_Bool *infeasible, SCIP_Bool *skipsolve, SCIP_RESULT *result)
Definition: benders.c:2815
Definition: objbenders.h:33
SCIP_RETCODE SCIPsetAddBoolParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2992
Definition: type_var.h:43
Definition: type_benders.h:65
SCIP_RETCODE SCIPbendersSetBenderscutPriority(SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, int priority)
Definition: benders.c:6937
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
SCIP_RETCODE SCIPsolveBendersSubproblems(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: scip_benders.c:613
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
SCIP_Bool SCIPbendersSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6521
Definition: type_set.h:38
SCIP_RETCODE SCIPbendersStoreCut(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
Definition: benders.c:6804
Definition: type_stat.h:53
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:451
static SCIP_RETCODE solveBendersSubproblems(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool checkint, int *nverified, int *solveidx, int nsolveidx, SCIP_Bool **subprobsolved, SCIP_BENDERSSUBSTATUS **substatus, SCIP_Bool *infeasible, SCIP_Bool *optimal, SCIP_Bool *stopped)
Definition: benders.c:3099
Definition: type_stat.h:48
internal methods for Benders' decomposition cuts
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
Definition: struct_event.h:195
static SCIP_RETCODE initialiseSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber, SCIP_Bool *success)
Definition: benders.c:1474
SCIP_RETCODE SCIPbenderscutInit(SCIP_BENDERSCUT *benderscut, SCIP_SET *set)
Definition: benderscut.c:220
SCIP callable library.
Definition: type_stat.h:42
void SCIPbendersSetSubproblemEnabled(SCIP_BENDERS *benders, int probnumber, SCIP_Bool enabled)
Definition: benders.c:6587
void SCIPbendersSetSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isnonlinear)
Definition: benders.c:6355
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
Definition: type_stat.h:54
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:465
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766
Definition: type_var.h:58