nodesel_uct.c
Go to the documentation of this file.
18 * @brief uct node selector which balances exploration and exploitation by considering node visits
21 * the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound
28 * The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node,
31 * \f$ \mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)}
34 * where \f$\mbox{estimate}\f$ is the node's lower bound normalized by the root lower bound, and \f$\mbox{visits}\f$
35 * denotes the number of times a leaf in the subtree rooted at this node has been explored so far.
37 * The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion.
39 * The authors suggest that this node selection rule is particularly useful at the beginning of the solving process, but
40 * to switch to a different node selection after a number of nodes has been explored to reduce computational overhead.
41 * Our implementation uses only information available from the original SCIP tree which does not support the
42 * forward path mechanism needed for the most efficient node selection. Instead, the algorithm selects the next leaf
43 * 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
44 * by following their paths back upwards until their deepest common ancestor \f$a\f$ is reached, together with the two
45 * children of \f$a\f$ representing the two paths to l_1, l_2. The leaf represented by the child of \f$a\f$
51 * the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula)
54 * @note It should be avoided to switch to uct node selection after the branch and bound process has begun because
55 * the central UCT score information how often a path was taken is not collected if UCT is inactive. A safe use of
59 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
82 #define DEFAULT_NODELIMIT 31 /**< limit of node selections after which UCT node selection is turned off */
83 #define DEFAULT_USEESTIMATE FALSE /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
84 #define INITIALSIZE 1024 /**< initial size of node visits array (increased dynamically if required) */
99 SCIP_Bool useestimate; /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
143 /* increase visits counter of all nodes along the path until root node is reached (which has NULL as parent) */
158 /** switches to a different node selection rule by assigning the lowest priority of all node selectors to uct */
183 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Reached node limit of UCT node selection rule -> switching to default\n");
189 /** returns UCT score of @p node; the UCT score is a mixture of the node's lower bound or estimate and the number of times
190 * it has been visited so far in relation with the number of times its parent has been visited so far
206 /* the objective part of the UCT score uses the (negative) gap between node estimate and root lower bound */
209 /* if the root lower bound is infinite due to LP errors, we ignore the gap part of the UCT score */
243 /** compares two leaf nodes by comparing the UCT scores of the two children of their deepest common ancestor */
257 /* go back in the tree to find the two shallowest ancestors of node1 and node2 which share the same parent */
260 /* if the nodes have the same depth but not the same parent both pointers can be updated, otherwise only the deeper
325 /** keeps visits array large enough to save visits for all nodes in the branch and bound tree */
337 SCIP_CALL( SCIPallocClearMemoryArray(scip, &nodeseldata->nodevisits, INITIALSIZE) ); /*lint !e506*/
344 if( nodeseldata->sizenodevisits < 2 * nodeseldata->nodelimit && nodeseldata->sizenodevisits < (int)(2 * SCIPgetNNodes(scip)))
349 SCIPdebugMsg(scip, "Resizing node visits array, old capacity: %d new capacity : %d\n", nodeseldata->sizenodevisits, newcapacity);
353 BMSclearMemoryArray(&(nodeseldata->nodevisits[nodeseldata->sizenodevisits]), newcapacity - nodeseldata->sizenodevisits); /*lint !e866*/
375 /** solving process initialization method of node selector (called when branch and bound process is about to begin) */
393 /** solving process deinitialization method of node selector (called when branch and bound process data gets freed) */
469 SCIP_CALL( SCIPgetOpenNodesData(scip, &leaves, &children, &siblings, &nleaves, &nchildren, &nsiblings) );
500 SCIPdebugMsg(scip, "updating node visits from node number %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(*selnode));
546 /* use SCIPincludeNodeselBasic() plus setter functions if you want to set callbacks one-by-one and your code should
549 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY,
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:129
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:108
Definition: struct_nodesel.h:52
public methods for SCIP parameter handling
public methods for branch and bound tree
Definition: struct_scip.h:59
public methods for node selector plugins
public methods for memory management
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)
Definition: scip_nodesel.c:94
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:389
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel_uct.c:245
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
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)
Definition: scip_param.c:74
Definition: struct_tree.h:132
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
Definition: scip_solvingstats.c:1442
public methods for numerical tolerances
public methods for querying solving statistics
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
Definition: nodesel_uct.c:160
public methods for the branch-and-bound tree
static SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
Definition: nodesel_uct.c:395
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: scip_nodesel.c:209
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
Definition: type_retcode.h:42
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:193
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1111
Definition: type_retcode.h:33
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
public methods for node selectors
Definition: type_message.h:44
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:130
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: scip_nodesel.c:193
static void selectBestNode(SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes)
Definition: nodesel_uct.c:298
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
static SCIP_DECL_NODESELSELECT(nodeselSelectUct)
Definition: nodesel_uct.c:442
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:145
public methods for message output
public methods for message handling
static SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
Definition: nodesel_uct.c:377
uct node selector which balances exploration and exploitation by considering node visits ...
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:327
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1063
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1121
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)
Definition: scip_param.c:130
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:260
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)
Definition: scip_param.c:48
memory allocation routines