64 #define NODESEL_NAME "uct" 65 #define NODESEL_DESC "node selector which balances exploration and exploitation " 66 #define NODESEL_STDPRIORITY 10 67 #define NODESEL_MEMSAVEPRIORITY 0 70 #define DEFAULT_WEIGHT 0.1 71 #define DEFAULT_NODELIMIT 31 72 #define DEFAULT_USEESTIMATE FALSE 73 #define INITIALSIZE 1024 74 #define MAXNODELIMIT 1000000 80 struct SCIP_NodeselData
104 assert(nodeseldata !=
NULL);
105 assert(node !=
NULL);
109 assert(nodenumber >= 0);
111 if( nodenumber >= nodeseldata->sizenodevisits )
114 return nodeseldata->nodevisits[nodenumber];
126 assert(nodeseldata !=
NULL);
127 assert(node !=
NULL);
129 visits = nodeseldata->nodevisits;
130 assert(visits !=
NULL);
138 if( nodenumber < nodeseldata->sizenodevisits )
139 ++(visits[nodenumber]);
144 while( node !=
NULL );
165 for( n = 0; n < nnodesels; ++n )
168 newpriority =
MIN(newpriority, prio);
170 newpriority =
MAX(newpriority, INT_MIN + 1);
205 assert(
SCIPisGE(scip, score, rootlowerbound));
207 absrootlowerbound =
REALABS(rootlowerbound);
208 minabs =
MIN(absscore, absrootlowerbound);
209 minabs =
MAX(minabs, 1.0);
211 score = (rootlowerbound - score) / minabs;
218 assert(parent !=
NULL);
221 if( parentvisits > 0 )
226 score += nodeseldata->weight * parentvisits / (
SCIP_Real)(1 + visits);
244 assert(node1 != node2);
262 assert(node1 !=
NULL);
263 assert(node2 !=
NULL);
276 else if(
SCIPisLT(scip, score1, score2) )
280 assert(
SCIPisGT(scip, score1, score2));
297 assert(nnodes == 0 || nodes !=
NULL);
299 assert(selnode !=
NULL);
305 for( n = 0; n <
nnodes; ++n )
307 assert(nodes[n] !=
NULL);
309 if( *selnode ==
NULL ||
compareNodes(scip, nodeseldata, *selnode, nodes[n]) < 0 )
321 assert(nodeseldata !=
NULL);
324 if( nodeseldata->nodevisits ==
NULL )
333 if( nodeseldata->sizenodevisits < 2 * nodeseldata->nodelimit && nodeseldata->sizenodevisits < (
int)(2 *
SCIPgetNNodes(scip)))
336 newcapacity =
MIN(2 * nodeseldata->sizenodevisits, 2 * nodeseldata->nodelimit);
338 SCIPdebugMsg(scip,
"Resizing node visits array, old capacity: %d new capacity : %d\n", nodeseldata->sizenodevisits, newcapacity);
339 assert(newcapacity > nodeseldata->sizenodevisits);
342 BMSclearMemoryArray(&(nodeseldata->nodevisits[nodeseldata->sizenodevisits]), newcapacity - nodeseldata->sizenodevisits);
344 nodeseldata->sizenodevisits = newcapacity;
370 assert(nodesel !=
NULL);
374 assert(nodeseldata !=
NULL);
375 nodeseldata->nselections = 0;
376 nodeseldata->sizenodevisits = 0;
388 assert(nodesel !=
NULL);
392 assert(nodeseldata !=
NULL);
394 if( nodeseldata->sizenodevisits > 0 )
396 assert(nodeseldata->nodevisits !=
NULL);
399 nodeseldata->sizenodevisits = 0;
400 nodeseldata->nselections = 0;
414 assert(nodesel !=
NULL);
417 if( nodeseldata->sizenodevisits > 0 )
419 assert(nodeseldata->nodevisits !=
NULL);
441 assert(nodesel !=
NULL);
444 assert(selnode !=
NULL);
449 assert(nodeseldata !=
NULL);
471 assert(*selnode !=
NULL);
474 ++nodeseldata->nselections;
477 if( nodeseldata->nselections == nodeseldata->nodelimit )
525 nodeseldata->nodevisits =
NULL;
526 nodeseldata->nselections = 0;
527 nodeseldata->sizenodevisits = 0;
536 assert(nodesel !=
NULL);
546 "maximum number of nodes before switching to default rule",
549 "weight for visit quotient of node selection rule",
552 "should the estimate (TRUE) or lower bound of a node be used for UCT score?",
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
#define DEFAULT_USEESTIMATE
SCIP_NODESEL ** SCIPgetNodesels(SCIP *scip)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
#define NODESEL_STDPRIORITY
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_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
#define DEFAULT_NODELIMIT
enum SCIP_Retcode SCIP_RETCODE
int SCIPgetNNodesLeft(SCIP *scip)
#define SCIPfreeBlockMemory(scip, ptr)
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
#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)
static SCIP_DECL_NODESELCOMP(nodeselCompUct)
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
#define NODESEL_MEMSAVEPRIORITY
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
struct SCIP_NodeselData SCIP_NODESELDATA
static SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip)
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
static SCIP_DECL_NODESELCOPY(nodeselCopyUct)
static SCIP_DECL_NODESELFREE(nodeselFreeUct)
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define SCIPallocClearMemoryArray(scip, ptr, num)
static void selectBestNode(SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes)
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNNodesels(SCIP *scip)
static SCIP_DECL_NODESELSELECT(nodeselSelectUct)
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
static SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
uct node selector which balances exploration and exploitation by considering node visits ...
#define BMSclearMemoryArray(ptr, num)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
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 SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
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)