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;
202 assert(scip !=
NULL);
203 assert(lpcands !=
NULL);
204 assert(lpcandssol !=
NULL);
205 assert(lpcandsfrac !=
NULL);
206 assert(bestcand !=
NULL);
207 assert(skipdown !=
NULL);
208 assert(skipup !=
NULL);
209 assert(bestdown !=
NULL);
210 assert(bestup !=
NULL);
211 assert(bestscore !=
NULL);
212 assert(bestdownvalid !=
NULL);
213 assert(bestupvalid !=
NULL);
214 assert(provedbound !=
NULL);
215 assert(result !=
NULL);
216 assert(nlpcands > 0);
231 *provedbound = lpobjval;
234 *bestdown = lpobjval;
236 *bestdownvalid =
TRUE;
243 if( (!forcestrongbranch && nlpcands == 1) ||
SCIPisStopped(scip) )
251 assert(branchrule !=
NULL);
255 assert(branchruledata !=
NULL);
258 reevalage = branchruledata->reevalage;
261 propagate = (maxproprounds != 0);
265 probingbounds =
FALSE;
285 for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c )
288 assert(lpcands[c] !=
NULL);
300 downgain =
MAX(down - lastlpobjval, 0.0);
301 upgain =
MAX(up - lastlpobjval, 0.0);
306 downconflict =
FALSE;
309 SCIPdebugMsg(scip,
"strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT
", down=%g (%+g), up=%g (%+g))\n",
314 SCIPdebugMsg(scip,
"applying strong branching%s on variable <%s> with solution %g\n",
315 propagate ?
"with propagation" :
"",
SCIPvarGetName(lpcands[c]), lpcandssol[c]);
316 assert(i >= ncomplete || (!skipdown[i] && !skipup[i]));
325 maxproprounds, skipdown[i] ?
NULL : &down, skipup[i] ?
NULL : &up, &downvalid,
326 &upvalid,
NULL,
NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) );
328 SCIPdebugMsg(scip,
"-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
329 down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
334 skipdown[i] ?
NULL : &down, skipup[i] ?
NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
335 &downconflict, &upconflict, &lperror) );
349 "(node %" SCIP_LONGINT_FORMAT
") error in strong branching call%s for variable <%s> with solution %g\n",
355 down =
MAX(down, lpobjval);
356 up =
MAX(up, lpobjval);
357 downgain = down - lpobjval;
358 upgain = up - lpobjval;
364 assert(downinf || !downconflict);
365 assert(upinf || !upconflict);
368 if( downinf || upinf )
371 assert(allcolsinlp || propagate);
378 if( allowaddcons && downinf == downconflict && upinf == upconflict )
383 else if( downinf && upinf )
400 assert(tightened || propagate);
417 assert(tightened || propagate);
424 else if( allcolsinlp && !exactsolve && downvalid && upvalid )
429 minbound =
MIN(down, up);
430 *provedbound =
MAX(*provedbound, minbound);
438 assert(vars !=
NULL);
440 assert(newlbs !=
NULL);
441 assert(newubs !=
NULL);
445 for( v = 0; v < nvars; ++v )
449 SCIPdebugMsg(scip,
"better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
457 SCIPdebugMsg(scip,
"better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
468 SCIPdebugMsg(scip,
" -> strong branching with propagation on variable <%s> led to %d bound changes\n",
483 if( c < npriolpcands )
486 if( score > *bestscore )
491 *bestdownvalid = downvalid;
492 *bestupvalid = upvalid;
501 SCIPdebugMsg(scip,
" -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
502 c, nlpcands, npriolpcands,
SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score,
513 assert(newlbs !=
NULL);
514 assert(newubs !=
NULL);
544 assert(branchrule !=
NULL);
547 assert(result !=
NULL);
555 assert(branchruledata !=
NULL);
559 assert(nlpcands > 0);
560 assert(npriolpcands > 0);
569 if( branchruledata->skipdown ==
NULL )
571 assert(branchruledata->skipup ==
NULL);
581 branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand, allowaddcons,
582 branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand,
583 &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
595 assert(0 <= bestcand && bestcand < nlpcands);
598 var = lpcands[bestcand];
599 val = lpcandssol[bestcand];
602 SCIPdebugMsg(
scip,
" -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
603 nlpcands, bestcand,
SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore);
605 assert(downchild !=
NULL);
606 assert(upchild !=
NULL);
617 if( allcolsinlp && !exactsolve )
650 branchruledata->lastcand = 0;
651 branchruledata->skipsize = 0;
652 branchruledata->skipup =
NULL;
653 branchruledata->skipdown =
NULL;
659 assert(branchrule !=
NULL);
670 "branching/fullstrong/reevalage",
671 "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
674 "branching/fullstrong/maxproprounds",
675 "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
678 "branching/fullstrong/probingbounds",
679 "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
682 "branching/fullstrong/forcestrongbranch",
683 "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)
#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_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, SCIP_Bool allowaddcons, 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)
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)