30 #define BRANCHRULE_NAME "fullstrong" 31 #define BRANCHRULE_DESC "full strong branching" 32 #define BRANCHRULE_PRIORITY 0 33 #define BRANCHRULE_MAXDEPTH -1 34 #define BRANCHRULE_MAXBOUNDDIST 1.0 36 #define DEFAULT_REEVALAGE 10LL 38 #define DEFAULT_MAXPROPROUNDS -2 40 #define DEFAULT_PROBINGBOUNDS TRUE 42 #define DEFAULT_FORCESTRONGBRANCH FALSE 46 struct SCIP_BranchruleData
71 assert(branchrule != NULL);
88 assert(branchruledata != NULL);
108 assert(branchruledata != NULL);
110 branchruledata->lastcand = 0;
123 assert(branchruledata != NULL);
124 assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL));
126 if( branchruledata->skipdown != NULL )
130 branchruledata->skipdown = NULL;
131 branchruledata->skipup = NULL;
132 branchruledata->skipsize = 0;
201 assert(scip != NULL);
202 assert(lpcands != NULL);
203 assert(lpcandssol != NULL);
204 assert(lpcandsfrac != NULL);
205 assert(bestcand != NULL);
206 assert(skipdown != NULL);
207 assert(skipup != NULL);
208 assert(bestdown != NULL);
209 assert(bestup != NULL);
210 assert(bestscore != NULL);
211 assert(bestdownvalid != NULL);
212 assert(bestupvalid != NULL);
213 assert(provedbound != NULL);
214 assert(result != NULL);
215 assert(nlpcands > 0);
230 *provedbound = lpobjval;
233 *bestdown = lpobjval;
235 *bestdownvalid =
TRUE;
242 if( (!forcestrongbranch && nlpcands == 1) ||
SCIPisStopped(scip) )
250 assert(branchrule != NULL);
254 assert(branchruledata != NULL);
257 reevalage = branchruledata->reevalage;
260 propagate = (maxproprounds != 0);
264 probingbounds =
FALSE;
284 for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c )
287 assert(lpcands[c] != NULL);
299 downgain =
MAX(down - lastlpobjval, 0.0);
300 upgain =
MAX(up - lastlpobjval, 0.0);
305 downconflict =
FALSE;
308 SCIPdebugMsg(scip,
"strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT
", down=%g (%+g), up=%g (%+g))\n",
313 SCIPdebugMsg(scip,
"applying strong branching%s on variable <%s> with solution %g\n",
314 propagate ?
"with propagation" :
"",
SCIPvarGetName(lpcands[c]), lpcandssol[c]);
315 assert(i >= ncomplete || (!skipdown[i] && !skipup[i]));
324 maxproprounds, skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid,
325 &upvalid, NULL, NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) );
327 SCIPdebugMsg(scip,
"-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
328 down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
333 skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
334 &downconflict, &upconflict, &lperror) );
348 "(node %" SCIP_LONGINT_FORMAT
") error in strong branching call%s for variable <%s> with solution %g\n",
354 down =
MAX(down, lpobjval);
355 up =
MAX(up, lpobjval);
356 downgain = down - lpobjval;
357 upgain = up - lpobjval;
363 assert(downinf || !downconflict);
364 assert(upinf || !upconflict);
367 if( downinf || upinf )
370 assert(allcolsinlp || propagate);
373 if( downinf && upinf )
390 assert(tightened || propagate);
407 assert(tightened || propagate);
414 else if( allcolsinlp && !exactsolve && downvalid && upvalid )
419 minbound = MIN(down, up);
420 *provedbound =
MAX(*provedbound, minbound);
428 assert(vars != NULL);
430 assert(newlbs != NULL);
431 assert(newubs != NULL);
435 for( v = 0; v < nvars; ++v )
439 SCIPdebugMsg(scip,
"better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
447 SCIPdebugMsg(scip,
"better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
458 SCIPdebugMsg(scip,
" -> strong branching with propagation on variable <%s> led to %d bound changes\n",
473 if( c < npriolpcands )
476 if( score > *bestscore )
481 *bestdownvalid = downvalid;
482 *bestupvalid = upvalid;
491 SCIPdebugMsg(scip,
" -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
492 c, nlpcands, npriolpcands,
SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score,
503 assert(newlbs != NULL);
504 assert(newubs != NULL);
534 assert(branchrule != NULL);
536 assert(
scip != NULL);
537 assert(result != NULL);
545 assert(branchruledata != NULL);
549 assert(nlpcands > 0);
550 assert(npriolpcands > 0);
559 if( branchruledata->skipdown == NULL )
561 assert(branchruledata->skipup == NULL);
571 branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand,
572 branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand,
573 &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
585 assert(0 <= bestcand && bestcand < nlpcands);
588 var = lpcands[bestcand];
589 val = lpcandssol[bestcand];
592 SCIPdebugMsg(
scip,
" -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
593 nlpcands, bestcand,
SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore);
595 assert(downchild != NULL);
596 assert(upchild != NULL);
607 if( allcolsinlp && !exactsolve )
640 branchruledata->lastcand = 0;
641 branchruledata->skipsize = 0;
642 branchruledata->skipup = NULL;
643 branchruledata->skipdown = NULL;
649 assert(branchrule != NULL);
660 "branching/fullstrong/reevalage",
661 "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
664 "branching/fullstrong/maxproprounds",
665 "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
668 "branching/fullstrong/probingbounds",
669 "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
672 "branching/fullstrong/forcestrongbranch",
673 "should strong branching be applied even if there is just a single candidate?",
enum SCIP_Result SCIP_RESULT
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
static SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarStrongbranchLast(SCIP *scip, SCIP_VAR *var, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Real *solval, SCIP_Real *lpobjval)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
SCIP_RETCODE SCIPselectVarStrongBranching(SCIP *scip, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Bool *skipdown, SCIP_Bool *skipup, int nlpcands, int npriolpcands, int ncomplete, int *start, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
#define BRANCHRULE_PRIORITY
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
enum SCIP_Retcode SCIP_RETCODE
static SCIP_DECL_BRANCHCOPY(branchCopyFullstrong)
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
static SCIP_DECL_BRANCHINIT(branchInitFullstrong)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
#define DEFAULT_MAXPROPROUNDS
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_Longint SCIPgetVarStrongbranchLPAge(SCIP *scip, SCIP_VAR *var)
#define DEFAULT_REEVALAGE
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
full strong LP branching rule
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPgetVarStrongbranchWithPropagation(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real lpobjval, int itlim, int maxproprounds, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Longint *ndomredsdown, SCIP_Longint *ndomredsup, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror, SCIP_Real *newlbs, SCIP_Real *newubs)
#define DEFAULT_FORCESTRONGBRANCH
int SCIPgetNVars(SCIP *scip)
#define BRANCHRULE_MAXBOUNDDIST
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
SCIP_RETCODE SCIPincludeBranchruleFullstrong(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
static SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define DEFAULT_PROBINGBOUNDS
SCIP_Bool SCIPisExactSolve(SCIP *scip)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)