uct node selector which balances exploration and exploitation by considering node visits
the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound and the number of times it has been visited so far compared to its parent node.
The idea of UCT node selection for MIP appeared in: Ashish Sabharwal and Horst Samulowitz Guiding Combinatorial Optimization with UCT (2011)
The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node, the algorithm selects the current node's child \(N_i\) which maximizes the UCT score
\( \mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)} \)
where \(\mbox{estimate}\) is the node's lower bound normalized by the root lower bound, and \(\mbox{visits}\) denotes the number of times a leaf in the subtree rooted at this node has been explored so far.
The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion.
The authors suggest that this node selection rule is particularly useful at the beginning of the solving process, but to switch to a different node selection after a number of nodes has been explored to reduce computational overhead. Our implementation uses only information available from the original SCIP tree which does not support the forward path mechanism needed for the most efficient node selection. Instead, the algorithm selects the next leaf by looping over all leaves and comparing the best leaf found so far with the next one. Two leaves l_1, l_2 are compared by following their paths back upwards until their deepest common ancestor \(a\) is reached, together with the two children of \(a\) representing the two paths to l_1, l_2. The leaf represented by the child of \(a\) with higher UCT score is a candidate for the next selected leaf.
The node selector features several parameters:
the nodelimit delimits the number of explored nodes before UCT selection is turned off the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula) useestimate determines whether the node's estimate or lower bound is taken as estimate
Definition in file nodesel_uct.c.
Go to the source code of this file.
Macros | |
#define | NODESEL_NAME "uct" |
#define | NODESEL_DESC "node selector which balances exploration and exploitation " |
#define | NODESEL_STDPRIORITY 10 |
#define | NODESEL_MEMSAVEPRIORITY 0 |
#define | DEFAULT_WEIGHT 0.1 |
#define | DEFAULT_NODELIMIT 31 |
#define | DEFAULT_USEESTIMATE FALSE |
#define | INITIALSIZE 1024 |
#define | MAXNODELIMIT 1000000 |
Functions | |
static int | nodeGetVisits (SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node) |
static void | updateVisits (SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node) |
static SCIP_RETCODE | turnoffNodeSelector (SCIP *scip, SCIP_NODESEL *nodesel) |
static SCIP_Real | nodeGetUctScore (SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata) |
static int | compareNodes (SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2) |
static void | selectBestNode (SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes) |
static SCIP_RETCODE | ensureMemorySize (SCIP *scip, SCIP_NODESELDATA *nodeseldata) |
static | SCIP_DECL_NODESELCOPY (nodeselCopyUct) |
static | SCIP_DECL_NODESELINITSOL (nodeselInitsolUct) |
static | SCIP_DECL_NODESELEXITSOL (nodeselExitsolUct) |
static | SCIP_DECL_NODESELFREE (nodeselFreeUct) |
static | SCIP_DECL_NODESELSELECT (nodeselSelectUct) |
static | SCIP_DECL_NODESELCOMP (nodeselCompUct) |
SCIP_RETCODE | SCIPincludeNodeselUct (SCIP *scip) |
#define NODESEL_NAME "uct" |
Definition at line 64 of file nodesel_uct.c.
Referenced by SCIP_DECL_NODESELSELECT(), and SCIPincludeNodeselUct().
#define NODESEL_DESC "node selector which balances exploration and exploitation " |
Definition at line 65 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
#define NODESEL_STDPRIORITY 10 |
Definition at line 66 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
#define NODESEL_MEMSAVEPRIORITY 0 |
Definition at line 67 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
#define DEFAULT_WEIGHT 0.1 |
default values for user parameters weight of node visits in UCT score
Definition at line 70 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
#define DEFAULT_NODELIMIT 31 |
limit of node selections after which UCT node selection is turned off
Definition at line 71 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
#define DEFAULT_USEESTIMATE FALSE |
should the estimate (TRUE) or the lower bound of a node be used for UCT score?
Definition at line 72 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
#define INITIALSIZE 1024 |
initial size of node visits array (increased dynamically if required)
Definition at line 73 of file nodesel_uct.c.
Referenced by ensureMemorySize().
#define MAXNODELIMIT 1000000 |
the maximum value for user parameter nodelimit
Definition at line 74 of file nodesel_uct.c.
Referenced by SCIPincludeNodeselUct().
|
static |
get the number times node
has been visited so far
nodeseldata | node selector data |
node | the node in question |
Definition at line 97 of file nodesel_uct.c.
References SCIPnodeGetNumber().
Referenced by nodeGetUctScore().
|
static |
increases the visits counter along the path from node
to the root node
nodeseldata | node selector data |
node | leaf node of path along which the visits are backpropagated |
Definition at line 119 of file nodesel_uct.c.
References SCIPnodeGetDepth(), SCIPnodeGetNumber(), and SCIPnodeGetParent().
Referenced by SCIP_DECL_NODESELSELECT().
|
static |
switches to a different node selection rule by assigning the lowest priority of all node selectors to uct
scip | SCIP data structure |
nodesel | the node selector to be turned off |
Definition at line 149 of file nodesel_uct.c.
References MAX, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_NORMAL, SCIPgetNNodesels(), SCIPgetNodesels(), SCIPnodeselGetStdPriority(), SCIPsetNodeselStdPriority(), and SCIPverbMessage().
Referenced by SCIP_DECL_NODESELSELECT().
|
static |
returns UCT score of node
; the UCT score is a mixture of the node's lower bound or estimate and the number of times it has been visited so far in relation with the number of times its parent has been visited so far
scip | SCIP data structure |
node | the node for which UCT score is requested |
nodeseldata | node selector data |
Definition at line 182 of file nodesel_uct.c.
References MAX, nodeGetVisits(), REALABS, SCIP_Real, SCIPgetLowerboundRoot(), SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPnodeGetEstimate(), SCIPnodeGetLowerbound(), and SCIPnodeGetParent().
Referenced by compareNodes().
|
static |
compares two leaf nodes by comparing the UCT scores of the two children of their deepest common ancestor
scip | SCIP data structure |
nodeseldata | node selector data |
node1 | first node for comparison |
node2 | second node for comparisons |
Definition at line 234 of file nodesel_uct.c.
References nodeGetUctScore(), SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPnodeGetDepth(), and SCIPnodeGetParent().
Referenced by selectBestNode().
|
static |
selects the best node among nodes
with respect to UCT score
scip | SCIP data structure |
selnode | pointer to store the selected node, needs not be empty |
nodeseldata | node selector data |
nodes | array of nodes to select from |
nnodes | size of the nodes array |
Definition at line 287 of file nodesel_uct.c.
References compareNodes(), and nnodes.
Referenced by SCIP_DECL_NODESELSELECT().
|
static |
keeps visits array large enough to save visits for all nodes in the branch and bound tree
scip | SCIP data structure |
nodeseldata | node selector data |
Definition at line 316 of file nodesel_uct.c.
References BMSclearMemoryArray, INITIALSIZE, SCIP_CALL, SCIP_OKAY, SCIPallocClearMemoryArray, SCIPdebugMsg, SCIPgetNNodes(), and SCIPreallocMemoryArray.
Referenced by SCIP_DECL_NODESELSELECT().
|
static |
copy method for node selector plugins (called when SCIP copies plugins)
Definition at line 356 of file nodesel_uct.c.
References SCIP_CALL, SCIP_OKAY, and SCIPincludeNodeselUct().
|
static |
solving process initialization method of node selector (called when branch and bound process is about to begin)
Definition at line 366 of file nodesel_uct.c.
References SCIP_OKAY, SCIPnodeselGetData(), and SCIPnodeselGetStdPriority().
|
static |
solving process deinitialization method of node selector (called when branch and bound process data gets freed)
Definition at line 384 of file nodesel_uct.c.
References SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArray, SCIPnodeselGetData(), and SCIPsetNodeselStdPriority().
|
static |
destructor of node selector to free user data (called when SCIP is exiting)
Definition at line 410 of file nodesel_uct.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeMemoryArray, SCIPnodeselGetData(), and SCIPnodeselSetData().
|
static |
node selection method of node selector
Definition at line 431 of file nodesel_uct.c.
References ensureMemorySize(), NODESEL_NAME, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPdebugMsg, SCIPerrorMessage, SCIPgetNNodes(), SCIPgetNNodesLeft(), SCIPgetOpenNodesData(), SCIPnodeGetNumber(), SCIPnodeselGetData(), SCIPnodeselGetName(), selectBestNode(), turnoffNodeSelector(), and updateVisits().
|
static |
node comparison method of UCT node selector
Definition at line 498 of file nodesel_uct.c.
References SCIP_Real, SCIPisGT(), SCIPisLT(), and SCIPnodeGetLowerbound().