65#define BRANCHRULE_NAME "cloud"
66#define BRANCHRULE_DESC "branching rule that considers several alternative LP optima"
67#define BRANCHRULE_PRIORITY 0
68#define BRANCHRULE_MAXDEPTH -1
69#define BRANCHRULE_MAXBOUNDDIST 1.0
71#define DEFAULT_USECLOUD TRUE
72#define DEFAULT_USEUNION FALSE
73#define DEFAULT_MAXPOINTS -1
74#define DEFAULT_MINSUCCESSRATE 0.0
75#define DEFAULT_MINSUCCESSUNION 0.0
76#define DEFAULT_MAXDEPTHUNION 65000
77#define DEFAULT_ONLYF2 FALSE
84struct SCIP_BranchruleData
91 SCIP_Real minsuccessrate;
92 SCIP_Real minsuccessunion;
119 if( branchruledata->cloudclock !=
NULL)
127 ntried = branchruledata->ntried;
128 nuseful = branchruledata->nuseful;
129 ncloudpoints = branchruledata->ncloudpoints;
130 nsavedlps = branchruledata->nsavedlps;
135 SCIPstatisticMessage(
"cloud success rates useful/tried: %8.6g points/useful: %8.6g saved/useful: %8.6g \n",
136 ntried == 0 ? -1 : (
SCIP_Real)nuseful / ntried, nuseful == 0 ? -1 : (
SCIP_Real)ncloudpoints / nuseful, nuseful == 0 ? -1 : (
SCIP_Real)nsavedlps / nuseful);
160 branchruledata->lastcand = 0;
161 branchruledata->nuseful = 0;
162 branchruledata->nusefulunions = 0;
163 branchruledata->ntried = 0;
164 branchruledata->ntriedunions = 0;
165 branchruledata->ncloudpoints = 0;
166 branchruledata->nsavedlps = 0;
168 if( branchruledata->cloudclock !=
NULL)
242 if( branchruledata->skipdown ==
NULL )
246 branchruledata->skipsize =
nvars;
263 if( branchruledata->useunion &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion && !branchruledata->onlyF2)
275 branchruledata->ntried++;
321 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion )
324 for(
i = 0;
i < ndiscvars; ++
i)
338 while(
newpoint && branchruledata->usecloud )
417 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion )
420 for(
i = 0;
i < ndiscvars; ++
i)
436 if( branchruledata->maxpoints != -1 && counter >= branchruledata->maxpoints )
440 SCIPdebugMsg(
scip,
"considered %d additional points in the cloud\n",counter);
450 branchruledata->ncloudpoints += (counter+1);
451 branchruledata->nuseful++;
474 for(
i = 0;
i <
nlpcands && !branchruledata->onlyF2; ++
i)
484 branchruledata->skipdown[counter] =
TRUE;
486 branchruledata->skipup[counter] =
TRUE;
487 assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
500 if( branchruledata->usecloud &&
501 branchruledata->ntried > 100 &&
502 (SCIP_Real)branchruledata->nuseful / branchruledata->ntried < branchruledata->minsuccessrate )
505 branchruledata->usecloud =
FALSE;
508 if( branchruledata->onlyF2 )
509 counter =
MAX(counter,1);
513 branchruledata->skipup, counter, counter,
ncomplete, &branchruledata->lastcand, 0,
FALSE,
FALSE,
516 if( branchruledata->lastcand <=
ncomplete )
545 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion && branchruledata->lastcand >
ncomplete )
557 for(
i = 0;
i < ndiscvars; ++
i)
570 branchruledata->skipdown[counter] =
TRUE;
572 branchruledata->skipup[counter] =
TRUE;
573 assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
590 branchruledata->ntriedunions++;
611 branchruledata->nusefulunions++;
621 SCIPdebugMsg(
scip,
" -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
626 SCIPdebugMsg(
scip,
" -> selected from %d new candidates, candidate %d: variable <%s> (down=%g, up=%g, score=%g)\n",
657 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion )
669 if( branchruledata->useunion &&
670 branchruledata->ntriedunions > 10 &&
671 (SCIP_Real)branchruledata->nusefulunions / branchruledata->ntriedunions < branchruledata->minsuccessunion )
674 branchruledata->useunion =
FALSE;
694 branchruledata->lastcand = 0;
695 branchruledata->skipsize = 0;
696 branchruledata->skipup =
NULL;
697 branchruledata->skipdown =
NULL;
714 "should a cloud of points be used?",
718 "should only F2 be used?",
722 "should the union of candidates be used?",
726 "maximum number of points for the cloud (-1 means no limit)",
730 "minimum success rate for the cloud",
734 "minimum success rate for the union",
738 "maximum depth for the union",
SCIP_RETCODE SCIPselectVarPseudoStrongBranching(SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, int *bestpseudocand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
all variables full strong LP branching rule
#define BRANCHRULE_PRIORITY
#define DEFAULT_MAXPOINTS
#define DEFAULT_MINSUCCESSUNION
#define DEFAULT_MAXDEPTHUNION
#define DEFAULT_MINSUCCESSRATE
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
full strong LP branching rule
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 SCIPincludeBranchruleCloud(SCIP *scip)
SCIP_Bool SCIPisExactSolve(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNBinVars(SCIP *scip)
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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 SCIPaddRealParam(SCIP *scip, 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)
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_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 SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgRowLhsDive(SCIP *scip, SCIP_ROW *row, SCIP_Real newlhs)
SCIP_RETCODE SCIPchgRowRhsDive(SCIP *scip, SCIP_ROW *row, SCIP_Real newrhs)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#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_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
public methods for branching rules
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
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 solutions
public methods for querying solving statistics
public methods for timing
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_BRANCHFREE(x)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
enum SCIP_Retcode SCIP_RETCODE