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
133 if( branchruledata->cloudclock !=
NULL)
141 ntried = branchruledata->ntried;
142 nuseful = branchruledata->nuseful;
143 ncloudpoints = branchruledata->ncloudpoints;
144 nsavedlps = branchruledata->nsavedlps;
149 SCIPstatisticMessage(
"cloud success rates useful/tried: %8.6g points/useful: %8.6g saved/useful: %8.6g \n",
150 ntried == 0 ? -1 : (
SCIP_Real)nuseful / ntried, nuseful == 0 ? -1 : (
SCIP_Real)ncloudpoints / nuseful, nuseful == 0 ? -1 : (
SCIP_Real)nsavedlps / nuseful);
174 branchruledata->lastcand = 0;
175 branchruledata->nuseful = 0;
176 branchruledata->nusefulunions = 0;
177 branchruledata->ntried = 0;
178 branchruledata->ntriedunions = 0;
179 branchruledata->ncloudpoints = 0;
180 branchruledata->nsavedlps = 0;
182 if( branchruledata->cloudclock !=
NULL)
256 if( branchruledata->skipdown ==
NULL )
260 branchruledata->skipsize =
nvars;
275 newlpcandsmin =
NULL;
276 newlpcandsmax =
NULL;
277 if( branchruledata->useunion &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion && !branchruledata->onlyF2)
289 branchruledata->ntried++;
335 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion )
338 for(
i = 0;
i < ndiscvars; ++
i)
346 newlpcandsmin[
i] = solval;
347 newlpcandsmax[
i] = solval;
352 while( newpoint && branchruledata->usecloud )
427 lpcandsmin[
i] =
MIN(lpcandsmin[
i], solval);
428 lpcandsmax[
i] =
MAX(lpcandsmax[
i], solval);
431 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion )
434 for(
i = 0;
i < ndiscvars; ++
i)
442 newlpcandsmin[
i] =
MIN(newlpcandsmin[
i], solval);
443 newlpcandsmax[
i] =
MAX(newlpcandsmax[
i], solval);
450 if( branchruledata->maxpoints != -1 && counter >= branchruledata->maxpoints )
454 SCIPdebugMsg(
scip,
"considered %d additional points in the cloud\n",counter);
464 branchruledata->ncloudpoints += (counter+1);
465 branchruledata->nuseful++;
475 lpcandscopy[counter] = lpcandscopy[
i];
476 lpcandssolcopy[counter] = lpcandssolcopy[
i];
477 lpcandsfraccopy[counter] = lpcandsfraccopy[
i];
488 for(
i = 0;
i <
nlpcands && !branchruledata->onlyF2; ++
i)
493 lpcandscopy[counter] = lpcandscopy[
i];
494 lpcandssolcopy[counter] = lpcandssolcopy[
i];
495 lpcandsfraccopy[counter] = lpcandsfraccopy[
i];
498 branchruledata->skipdown[counter] =
TRUE;
500 branchruledata->skipup[counter] =
TRUE;
501 assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
514 if( branchruledata->usecloud &&
515 branchruledata->ntried > 100 &&
516 (
SCIP_Real)branchruledata->nuseful / branchruledata->ntried < branchruledata->minsuccessrate )
519 branchruledata->usecloud =
FALSE;
522 if( branchruledata->onlyF2 )
523 counter =
MAX(counter,1);
527 branchruledata->skipup, counter, counter, ncomplete, &branchruledata->lastcand, 0,
FALSE,
FALSE,
528 &
bestcand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound,
result) );
530 if( branchruledata->lastcand <= ncomplete )
533 branchruledata->nsavedlps += 2*(
nlpcands - ncomplete);
538 branchruledata->nsavedlps += 2*(
nlpcands - counter)+counter - ncomplete;
559 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion && branchruledata->lastcand > ncomplete )
571 for(
i = 0;
i < ndiscvars; ++
i)
581 newlpcands[counter] =
vars[
i];
584 branchruledata->skipdown[counter] =
TRUE;
586 branchruledata->skipup[counter] =
TRUE;
587 assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
604 branchruledata->ntriedunions++;
607 &newcand, &newdown, &newup, &newscore, &newdownvalid, &newupvalid, &newbound,
result) );
615 if( newscore > bestscore )
618 var = newlpcands[newcand];
621 bestdownvalid = newdownvalid;
622 bestupvalid = newupvalid;
623 bestscore = newscore;
625 branchruledata->nusefulunions++;
635 SCIPdebugMsg(
scip,
" -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
640 SCIPdebugMsg(
scip,
" -> selected from %d new candidates, candidate %d: variable <%s> (down=%g, up=%g, score=%g)\n",
659 if( allcolsinlp && !exactsolve )
671 if( branchruledata->useunion && !branchruledata->onlyF2 &&
SCIPgetDepth(
scip) < branchruledata->maxdepthunion )
683 if( branchruledata->useunion &&
684 branchruledata->ntriedunions > 10 &&
685 (
SCIP_Real)branchruledata->nusefulunions / branchruledata->ntriedunions < branchruledata->minsuccessunion )
688 branchruledata->useunion =
FALSE;
708 branchruledata->lastcand = 0;
709 branchruledata->skipsize = 0;
710 branchruledata->skipup =
NULL;
711 branchruledata->skipdown =
NULL;
729 "should a cloud of points be used?",
733 "should only F2 be used?",
737 "should the union of candidates be used?",
741 "maximum number of points for the cloud (-1 means no limit)",
745 "minimum success rate for the cloud",
749 "minimum success rate for the union",
753 "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)
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
all variables full strong LP branching rule
#define DEFAULT_MAXPOINTS
#define DEFAULT_MINSUCCESSUNION
#define DEFAULT_MAXDEPTHUNION
#define DEFAULT_MINSUCCESSRATE
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 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 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_BRANCHCOPY(x)
#define SCIP_DECL_BRANCHFREE(x)
struct SCIP_Branchrule SCIP_BRANCHRULE
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
struct SCIP_Clock SCIP_CLOCK
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_Node SCIP_NODE