# SCIP

Solving Constraint Integer Programs

 nodesel_uct.h Go to the documentation of this file. 1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15  16 /**@file nodesel_uct.h 17  * @ingroup NODESELECTORS 18  * @brief uct node selector which balances exploration and exploitation by considering node visits 19  * @author Gregor Hendel 20  * 21  * the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound 22  * and the number of times it has been visited so far compared to its parent node. 23  * 24  * The idea of UCT node selection for MIP appeared in: 25  * Ashish Sabharwal and Horst Samulowitz 26  * Guiding Combinatorial Optimization with UCT (2011) 27  * 28  * The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node, 29  * the algorithm selects the current node's child \f$N_i\f$ which maximizes the UCT score 30  * 31  * \f$\mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)} 32 * \f$ 33  * 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. 36  * 37  * The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion. 38  * 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$ 46  * with higher UCT score is a candidate for the next selected leaf. 47  * 48  * The node selector features several parameters: 49  * 50  * the nodelimit delimits the number of explored nodes before UCT selection is turned off 51  * the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula) 52  * useestimate determines whether the node's estimate or lower bound is taken as estimate 53  * 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 56  * UCT is to switch it on before SCIP starts optimization. 57  */ 58  59 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 60  61 #ifndef __SCIP_NODESEL_UCT_H__ 62 #define __SCIP_NODESEL_UCT_H__ 63  64  65 #include "scip/scip.h" 66  67 #ifdef __cplusplus 68 extern "C" { 69 #endif 70  71 /** creates the uct node selector and includes it in SCIP */ 72 extern 74  SCIP* scip /**< SCIP data structure */ 75  ); 76  77 #ifdef __cplusplus 78 } 79 #endif 80  81 #endif 82  Generated on Wed Apr 2 2014 for SCIP Doxygen Documentation by doxygen (1.8.2) © 2020 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap