Scippy

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 2002-2022 Zuse Institute Berlin */
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
87  SCIP* scip /**< SCIP data structure */
88  );
89 
90 #ifdef __cplusplus
91 }
92 #endif
93 
94 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip)
Definition: nodesel_uct.c:539
common defines and data types used in all packages of SCIP