54#define BRANCHRULE_NAME "fullstrong"
55#define BRANCHRULE_DESC "full strong branching"
56#define BRANCHRULE_PRIORITY 0
57#define BRANCHRULE_MAXDEPTH -1
58#define BRANCHRULE_MAXBOUNDDIST 1.0
60#define DEFAULT_REEVALAGE 10LL
62#define DEFAULT_MAXPROPROUNDS -2
64#define DEFAULT_PROBINGBOUNDS TRUE
66#define DEFAULT_FORCESTRONGBRANCH FALSE
70struct SCIP_BranchruleData
72 SCIP_Longint reevalage;
76 SCIP_Bool probingbounds;
78 SCIP_Bool forcestrongbranch;
134 branchruledata->lastcand = 0;
148 assert((branchruledata->skipdown !=
NULL) == (branchruledata->skipup !=
NULL));
150 if( branchruledata->skipdown !=
NULL )
154 branchruledata->skipdown =
NULL;
155 branchruledata->skipup =
NULL;
156 branchruledata->skipsize = 0;
183 SCIP_Bool probingbounds,
185 SCIP_Bool forcestrongbranch,
189 SCIP_Real* bestscore,
190 SCIP_Bool* bestdownvalid,
191 SCIP_Bool* bestupvalid,
192 SCIP_Real* provedbound,
197 SCIP_Real* newlbs =
NULL;
198 SCIP_Real* newubs =
NULL;
201 SCIP_Longint reevalage;
202 SCIP_Longint nodenum;
209 SCIP_Bool exactsolve;
211 SCIP_Bool allcolsinlp;
216 SCIP_Bool downconflict;
217 SCIP_Bool upconflict;
254 *provedbound = lpobjval;
257 *bestdown = lpobjval;
259 *bestdownvalid =
TRUE;
281 reevalage = branchruledata->reevalage;
288 probingbounds =
FALSE;
308 for(
i = 0,
c = *start;
i <
nlpcands && (!bothgains ||
i < ncomplete); ++
i, ++
c )
319 SCIP_Real lastlpobjval;
323 downgain =
MAX(down - lastlpobjval, 0.0);
324 upgain =
MAX(up - lastlpobjval, 0.0);
329 downconflict =
FALSE;
337 SCIPdebugMsg(
scip,
"applying strong branching%s on variable <%s> with solution %g\n",
339 assert(
i >= ncomplete || (!skipdown[
i] && !skipup[
i]));
348 maxproprounds, skipdown[
i] ?
NULL : &down, skipup[
i] ?
NULL : &up, &downvalid,
349 &upvalid,
NULL,
NULL, &downinf, &upinf, &downconflict, &upconflict, &
lperror, newlbs, newubs) );
351 SCIPdebugMsg(
scip,
"-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
352 down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
357 skipdown[
i] ?
NULL : &down, skipup[
i] ?
NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
358 &downconflict, &upconflict, &
lperror) );
372 "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call%s for variable <%s> with solution %g\n",
378 down =
MAX(down, lpobjval);
379 up =
MAX(up, lpobjval);
380 downgain = down - lpobjval;
381 upgain = up - lpobjval;
387 assert(downinf || !downconflict);
388 assert(upinf || !upconflict);
391 if( !downinf && downvalid )
395 if( !upinf && upvalid )
401 if( downinf || upinf )
407 if( downinf && upinf )
416 SCIP_Bool infeasible;
432 SCIP_Bool infeasible;
448 else if( allcolsinlp && !exactsolve && downvalid && upvalid )
453 minbound =
MIN(down, up);
454 *provedbound =
MAX(*provedbound, minbound);
469 for( v = 0; v <
nvars; ++v )
473 SCIPdebugMsg(
scip,
"better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
481 SCIPdebugMsg(
scip,
"better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
492 SCIPdebugMsg(
scip,
" -> strong branching with propagation on variable <%s> led to %d bound changes\n",
501 if(
c < npriolpcands )
504 if( score > *bestscore )
509 *bestdownvalid = downvalid;
510 *bestupvalid = upvalid;
519 SCIPdebugMsg(
scip,
" -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
548 SCIP_Real* tmplpcandssol;
550 SCIP_Real* tmplpcandsfrac;
555 SCIP_Real provedbound;
556 SCIP_Bool bestdownvalid;
557 SCIP_Bool bestupvalid;
587 if( branchruledata->skipdown ==
NULL )
599 branchruledata->skipup,
nlpcands, npriolpcands,
nlpcands, &branchruledata->lastcand,
600 branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &
bestcand,
601 &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound,
result) );
609 SCIP_Bool allcolsinlp;
610 SCIP_Bool exactsolve;
620 SCIPdebugMsg(
scip,
" -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
635 if( allcolsinlp && !exactsolve )
668 branchruledata->lastcand = 0;
669 branchruledata->skipsize = 0;
670 branchruledata->skipup =
NULL;
671 branchruledata->skipdown =
NULL;
688 "branching/fullstrong/reevalage",
689 "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
692 "branching/fullstrong/maxproprounds",
693 "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
696 "branching/fullstrong/probingbounds",
697 "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
700 "branching/fullstrong/forcestrongbranch",
701 "should strong branching be applied even if there is just a single candidate?",
#define BRANCHRULE_PRIORITY
#define DEFAULT_PROBINGBOUNDS
#define DEFAULT_REEVALAGE
#define DEFAULT_FORCESTRONGBRANCH
#define DEFAULT_MAXPROPROUNDS
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
full strong LP branching rule
#define SCIP_LONGINT_FORMAT
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)
SCIP_RETCODE SCIPincludeBranchruleFullstrong(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Bool SCIPisExactSolve(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
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_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)
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)
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Bool idempotent, 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_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
SCIP_Longint SCIPgetVarStrongbranchLPAge(SCIP *scip, SCIP_VAR *var)
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)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
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_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Bool propagate
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
public methods for branching rules
public methods for message output
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SCIP_DECL_BRANCHEXECLP(x)
#define SCIP_DECL_BRANCHINIT(x)
#define SCIP_DECL_BRANCHCOPY(x)
#define SCIP_DECL_BRANCHEXIT(x)
#define SCIP_DECL_BRANCHFREE(x)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE