84#define NODESEL_NAME "uct"
85#define NODESEL_DESC "node selector which balances exploration and exploitation "
86#define NODESEL_STDPRIORITY 10
87#define NODESEL_MEMSAVEPRIORITY 0
90#define DEFAULT_WEIGHT 0.1
91#define DEFAULT_NODELIMIT 31
92#define DEFAULT_USEESTIMATE FALSE
93#define INITIALSIZE 1024
94#define MAXNODELIMIT 1000000
100struct SCIP_NodeselData
108 SCIP_Bool useestimate;
131 if( nodenumber >= nodeseldata->sizenodevisits )
134 return nodeseldata->nodevisits[nodenumber];
149 visits = nodeseldata->nodevisits;
164 while( node !=
NULL );
185 for( n = 0; n < nnodesels; ++n )
209 SCIP_Real rootlowerbound;
231 score = (rootlowerbound - score) /
minabs;
325 for( n = 0; n <
nnodes; ++n )
344 if( nodeseldata->nodevisits ==
NULL )
353 if( nodeseldata->sizenodevisits < 2 * nodeseldata->nodelimit && nodeseldata->sizenodevisits < (
int)(2 *
SCIPgetNNodes(
scip)))
356 newcapacity =
MIN(2 * nodeseldata->sizenodevisits, 2 * nodeseldata->nodelimit);
395 nodeseldata->nselections = 0;
396 nodeseldata->sizenodevisits = 0;
414 if( nodeseldata->sizenodevisits > 0 )
419 nodeseldata->sizenodevisits = 0;
420 nodeseldata->nselections = 0;
437 if( nodeseldata->sizenodevisits > 0 )
499 ++nodeseldata->nselections;
502 if( nodeseldata->nselections == nodeseldata->nodelimit )
550 nodeseldata->nodevisits =
NULL;
551 nodeseldata->nselections = 0;
552 nodeseldata->sizenodevisits = 0;
571 "maximum number of nodes before switching to default rule",
574 "weight for visit quotient of node selection rule",
577 "should the estimate (TRUE) or lower bound of a node be used for UCT score?",
#define SCIP_LONGINT_FORMAT
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip)
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)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocClearMemoryArray(scip, ptr, num)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
int SCIPnodeGetDepth(SCIP_NODE *node)
SCIP_NODESEL ** SCIPgetNodesels(SCIP *scip)
SCIP_RETCODE SCIPincludeNodeselBasic(SCIP *scip, SCIP_NODESEL **nodesel, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel,)
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel,)
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel,)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel,)
int SCIPgetNNodesels(SCIP *scip)
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
int SCIPgetNNodesLeft(SCIP *scip)
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
#define DEFAULT_USEESTIMATE
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
#define DEFAULT_NODELIMIT
#define NODESEL_MEMSAVEPRIORITY
#define NODESEL_STDPRIORITY
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
static void selectBestNode(SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes)
uct node selector which balances exploration and exploitation by considering node visits
public methods for message output
public methods for node selectors
public methods for branch and bound tree
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for querying solving statistics
public methods for the branch-and-bound tree
#define SCIP_DECL_NODESELCOMP(x)
#define SCIP_DECL_NODESELINITSOL(x)
#define SCIP_DECL_NODESELCOPY(x)
#define SCIP_DECL_NODESELEXITSOL(x)
#define SCIP_DECL_NODESELSELECT(x)
#define SCIP_DECL_NODESELFREE(x)
struct SCIP_NodeselData SCIP_NODESELDATA
enum SCIP_Retcode SCIP_RETCODE