1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file nodesel_uct.h 26 * @ingroup NODESELECTORS 27 * @brief uct node selector which balances exploration and exploitation by considering node visits 28 * @author Gregor Hendel 29 * 30 * the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound 31 * and the number of times it has been visited so far compared to its parent node. 32 * 33 * The idea of UCT node selection for MIP appeared in: 34 * Ashish Sabharwal and Horst Samulowitz 35 * Guiding Combinatorial Optimization with UCT (2011) 36 * 37 * The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node, 38 * the algorithm selects the current node's child \f$N_i\f$ which maximizes the UCT score 39 * 40 * \f$ \mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)} 41 * \f$ 42 * 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. 45 * 46 * The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion. 47 * 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$ 55 * with higher UCT score is a candidate for the next selected leaf. 56 * 57 * The node selector features several parameters: 58 * 59 * the nodelimit delimits the number of explored nodes before UCT selection is turned off 60 * the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula) 61 * useestimate determines whether the node's estimate or lower bound is taken as estimate 62 * 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 65 * UCT is to switch it on before SCIP starts optimization. 66 */ 67 68 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 69 70 #ifndef __SCIP_NODESEL_UCT_H__ 71 #define __SCIP_NODESEL_UCT_H__ 72 73 #include "scip/def.h" 74 #include "scip/type_retcode.h" 75 #include "scip/type_scip.h" 76 77 #ifdef __cplusplus 78 extern "C" { 79 #endif 80 81 /** creates the uct node selector and includes it in SCIP 82 * 83 * @ingroup NodeSelectorIncludes 84 */ 85 SCIP_EXPORT 86 SCIP_RETCODE SCIPincludeNodeselUct( 87 SCIP* scip /**< SCIP data structure */ 88 ); 89 90 #ifdef __cplusplus 91 } 92 #endif 93 94 #endif 95