nodesel_uct.c
Go to the documentation of this file.
27 * @brief uct node selector which balances exploration and exploitation by considering node visits
30 * the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound
37 * The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node,
40 * \f$ \mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)}
43 * where \f$\mbox{estimate}\f$ is the node's lower bound normalized by the root lower bound, and \f$\mbox{visits}\f$
44 * denotes the number of times a leaf in the subtree rooted at this node has been explored so far.
46 * The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion.
48 * The authors suggest that this node selection rule is particularly useful at the beginning of the solving process, but
49 * to switch to a different node selection after a number of nodes has been explored to reduce computational overhead.
50 * Our implementation uses only information available from the original SCIP tree which does not support the
51 * forward path mechanism needed for the most efficient node selection. Instead, the algorithm selects the next leaf
52 * 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
53 * by following their paths back upwards until their deepest common ancestor \f$a\f$ is reached, together with the two
54 * children of \f$a\f$ representing the two paths to l_1, l_2. The leaf represented by the child of \f$a\f$
60 * the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula)
63 * @note It should be avoided to switch to uct node selection after the branch and bound process has begun because
64 * the central UCT score information how often a path was taken is not collected if UCT is inactive. A safe use of
68/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
91#define DEFAULT_NODELIMIT 31 /**< limit of node selections after which UCT node selection is turned off */
92#define DEFAULT_USEESTIMATE FALSE /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
93#define INITIALSIZE 1024 /**< initial size of node visits array (increased dynamically if required) */
108 SCIP_Bool useestimate; /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
152 /* increase visits counter of all nodes along the path until root node is reached (which has NULL as parent) */
167/** switches to a different node selection rule by assigning the lowest priority of all node selectors to uct */
192 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Reached node limit of UCT node selection rule -> switching to default\n");
198/** 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
199 * it has been visited so far in relation with the number of times its parent has been visited so far
215 /* the objective part of the UCT score uses the (negative) gap between node estimate and root lower bound */
218 /* if the root lower bound is infinite due to LP errors, we ignore the gap part of the UCT score */
252/** compares two leaf nodes by comparing the UCT scores of the two children of their deepest common ancestor */
266 /* go back in the tree to find the two shallowest ancestors of node1 and node2 which share the same parent */
269 /* if the nodes have the same depth but not the same parent both pointers can be updated, otherwise only the deeper
346 SCIP_CALL( SCIPallocClearMemoryArray(scip, &nodeseldata->nodevisits, INITIALSIZE) ); /*lint !e506*/
353 if( nodeseldata->sizenodevisits < 2 * nodeseldata->nodelimit && nodeseldata->sizenodevisits < (int)(2 * SCIPgetNNodes(scip)))
358 SCIPdebugMsg(scip, "Resizing node visits array, old capacity: %d new capacity : %d\n", nodeseldata->sizenodevisits, newcapacity);
362 BMSclearMemoryArray(&(nodeseldata->nodevisits[nodeseldata->sizenodevisits]), newcapacity - nodeseldata->sizenodevisits); /*lint !e866*/
384/** solving process initialization method of node selector (called when branch and bound process is about to begin) */
402/** solving process deinitialization method of node selector (called when branch and bound process data gets freed) */
478 SCIP_CALL( SCIPgetOpenNodesData(scip, &leaves, &children, &siblings, &nleaves, &nchildren, &nsiblings) );
509 SCIPdebugMsg(scip, "updating node visits from node number %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(*selnode));
555 /* use SCIPincludeNodeselBasic() plus setter functions if you want to set callbacks one-by-one and your code should
558 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY,
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
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:83
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:139
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:57
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:103
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:269
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1130
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:154
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1120
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1072
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:138
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: scip_nodesel.c:218
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: scip_nodesel.c:202
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
Definition: scip_solvingstats.c:1450
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:398
memory allocation routines
Definition: objbenders.h:44
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel_uct.c:254
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:117
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:202
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:139
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
Definition: nodesel_uct.c:169
static SCIP_DECL_NODESELSELECT(nodeselSelectUct)
Definition: nodesel_uct.c:451
static SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
Definition: nodesel_uct.c:404
static SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
Definition: nodesel_uct.c:386
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:336
static void selectBestNode(SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes)
Definition: nodesel_uct.c:307
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
Definition: struct_tree.h:142
Definition: struct_nodesel.h:62
Definition: struct_scip.h:70