All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
nodesel_uct.h
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*/
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip) SCIP callable library. |