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 (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