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.c
26   	 * @ingroup DEFPLUGINS_NODESEL
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   	#include "blockmemshell/memory.h"
71   	#include "scip/nodesel_uct.h"
72   	#include "scip/pub_message.h"
73   	#include "scip/pub_nodesel.h"
74   	#include "scip/pub_tree.h"
75   	#include "scip/scip_mem.h"
76   	#include "scip/scip_message.h"
77   	#include "scip/scip_nodesel.h"
78   	#include "scip/scip_numerics.h"
79   	#include "scip/scip_param.h"
80   	#include "scip/scip_solvingstats.h"
81   	#include "scip/scip_tree.h"
82   	#include <string.h>
83   	
84   	#define NODESEL_NAME            "uct"
85   	#define NODESEL_DESC            "node selector which balances exploration and exploitation "
86   	#define NODESEL_STDPRIORITY     10
87   	#define NODESEL_MEMSAVEPRIORITY 0
88   	
89   	/** default values for user parameters */
90   	#define DEFAULT_WEIGHT          0.1     /**< weight of node visits in UCT score */
91   	#define DEFAULT_NODELIMIT       31      /**< limit of node selections after which UCT node selection is turned off */
92   	#define DEFAULT_USEESTIMATE     FALSE   /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
93   	#define INITIALSIZE             1024    /**< initial size of node visits array (increased dynamically if required) */
94   	#define MAXNODELIMIT            1000000 /**< the maximum value for user parameter nodelimit */
95   	/*
96   	 * Data structures
97   	 */
98   	
99   	/** node selector data */
100  	struct SCIP_NodeselData
101  	{
102  	   int*                  nodevisits;         /**< array to store the number of node visits so far for every node */
103  	   SCIP_Real             weight;             /**< weight of node visits in UCT score */
104  	   int                   nodelimit;          /**< limit of node selections after which UCT node selection is turned off */
105  	   int                   sizenodevisits;     /**< the size of the visits array */
106  	   int                   nselections;        /**< counter for the number of node selections */
107  	   int                   origstdpriority;    /**< priority of node selector when starting branch and bound */
108  	   SCIP_Bool             useestimate;        /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
109  	};
110  	
111  	/*
112  	 * Local methods
113  	 */
114  	
115  	/** get the number times @p node has been visited so far */
116  	static
117  	int nodeGetVisits(
118  	   SCIP_NODESELDATA*     nodeseldata,        /**< node selector data */
119  	   SCIP_NODE*            node                /**< the node in question */
120  	   )
121  	{
122  	   int nodenumber;
123  	
124  	   assert(nodeseldata != NULL);
125  	   assert(node != NULL);
126  	
127  	   /* nodes numbers start with 1 for the root node */
128  	   nodenumber = (int)(SCIPnodeGetNumber(node) - 1);
129  	   assert(nodenumber >= 0);
130  	
131  	   if( nodenumber >= nodeseldata->sizenodevisits )
132  	      return 0;
133  	   else
134  	      return nodeseldata->nodevisits[nodenumber];
135  	}
136  	
137  	/** increases the visits counter along the path from @p node to the root node */
138  	static
139  	void updateVisits(
140  	   SCIP_NODESELDATA*     nodeseldata,        /**< node selector data */
141  	   SCIP_NODE*            node                /**< leaf node of path along which the visits are backpropagated */
142  	   )
143  	{
144  	   int* visits;
145  	
146  	   assert(nodeseldata != NULL);
147  	   assert(node != NULL);
148  	
149  	   visits = nodeseldata->nodevisits;
150  	   assert(visits != NULL);
151  	
152  	   /* increase visits counter of all nodes along the path until root node is reached (which has NULL as parent) */
153  	   do
154  	   {
155  	      int nodenumber;
156  	
157  	      nodenumber = (int)(SCIPnodeGetNumber(node) - 1);
158  	      if( nodenumber < nodeseldata->sizenodevisits )
159  	         ++(visits[nodenumber]);
160  	
161  	      assert(SCIPnodeGetParent(node) == NULL || SCIPnodeGetDepth(node) >= 1);
162  	      node = SCIPnodeGetParent(node);
163  	   }
164  	   while( node != NULL );
165  	}
166  	
167  	/** switches to a different node selection rule by assigning the lowest priority of all node selectors to uct */
168  	static
169  	SCIP_RETCODE turnoffNodeSelector(
170  	   SCIP*                 scip,               /**< SCIP data structure */
171  	   SCIP_NODESEL*         nodesel             /**< the node selector to be turned off */
172  	   )
173  	{
174  	   SCIP_NODESEL** nodesels;
175  	   int nnodesels;
176  	   int newpriority;
177  	   int prio;
178  	   int n;
179  	
180  	   nodesels = SCIPgetNodesels(scip);
181  	   nnodesels = SCIPgetNNodesels(scip);
182  	   newpriority = SCIPnodeselGetStdPriority(nodesel);
183  	
184  	   /* loop over node selectors to find minimum priority */
185  	   for( n = 0; n < nnodesels; ++n )
186  	   {
187  	      prio = SCIPnodeselGetStdPriority(nodesels[n]);
188  	      newpriority = MIN(newpriority, prio);
189  	   }
190  	   newpriority = MAX(newpriority, INT_MIN + 1);
191  	
192  	   SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Reached node limit of UCT node selection rule -> switching to default\n");
193  	   SCIP_CALL( SCIPsetNodeselStdPriority(scip, nodesel, newpriority - 1) );
194  	
195  	   return SCIP_OKAY;
196  	}
197  	
198  	/** returns UCT score of @p node; the UCT score is a mixture of the node's lower bound or estimate and the number of times
199  	 *  it has been visited so far in relation with the number of times its parent has been visited so far
200  	 */
201  	static
202  	SCIP_Real nodeGetUctScore(
203  	   SCIP*                 scip,               /**< SCIP data structure */
204  	   SCIP_NODE*            node,               /**< the node for which UCT score is requested */
205  	   SCIP_NODESELDATA*     nodeseldata         /**< node selector data */
206  	   )
207  	{
208  	   SCIP_NODE* parent;
209  	   SCIP_Real rootlowerbound;
210  	   SCIP_Real score;
211  	   int parentvisits;
212  	
213  	   rootlowerbound = SCIPgetLowerboundRoot(scip);
214  	
215  	   /* the objective part of the UCT score uses the (negative) gap between node estimate and root lower bound */
216  	   score = nodeseldata->useestimate ? SCIPnodeGetEstimate(node) : SCIPnodeGetLowerbound(node);
217  	
218  	   /* if the root lower bound is infinite due to LP errors, we ignore the gap part of the UCT score */
219  	   if( !SCIPisInfinity(scip, REALABS(rootlowerbound)) && !SCIPisEQ(scip, score, rootlowerbound) )
220  	   {
221  	      SCIP_Real absscore;
222  	      SCIP_Real absrootlowerbound;
223  	      SCIP_Real minabs;
224  	
225  	      assert(SCIPisGE(scip, score, rootlowerbound));
226  	      absscore = REALABS(score);
227  	      absrootlowerbound = REALABS(rootlowerbound);
228  	      minabs = MIN(absscore, absrootlowerbound);
229  	      minabs = MAX(minabs, 1.0);
230  	
231  	      score = (rootlowerbound - score) / minabs;
232  	   }
233  	   else
234  	      score = 0.0;
235  	
236  	   /* the visits part of the UCT score function */
237  	   parent = SCIPnodeGetParent(node);
238  	   assert(parent != NULL);
239  	   parentvisits = nodeGetVisits(nodeseldata, parent);
240  	
241  	   if( parentvisits > 0 )
242  	   {
243  	      int visits;
244  	
245  	      visits = nodeGetVisits(nodeseldata, node);
246  	      score += nodeseldata->weight * parentvisits / (SCIP_Real)(1 + visits);
247  	   }
248  	
249  	   return score;
250  	}
251  	
252  	/** compares two leaf nodes by comparing the UCT scores of the two children of their deepest common ancestor */
253  	static
254  	int compareNodes(
255  	   SCIP*                 scip,               /**< SCIP data structure */
256  	   SCIP_NODESELDATA*     nodeseldata,        /**< node selector data */
257  	   SCIP_NODE*            node1,              /**< first node for comparison */
258  	   SCIP_NODE*            node2               /**< second node for comparisons */
259  	   )
260  	{
261  	   SCIP_Real score1;
262  	   SCIP_Real score2;
263  	
264  	   assert(node1 != node2);
265  	
266  	   /* go back in the tree to find the two shallowest ancestors of node1 and node2 which share the same parent */
267  	   while( SCIPnodeGetParent(node1) != SCIPnodeGetParent(node2) )
268  	   {
269  	      /* if the nodes have the same depth but not the same parent both pointers can be updated, otherwise only the deeper
270  	       * node pointer is moved
271  	       */
272  	      if( SCIPnodeGetDepth(node1) == SCIPnodeGetDepth(node2) )
273  	      {
274  	         node1 = SCIPnodeGetParent(node1);
275  	         node2 = SCIPnodeGetParent(node2);
276  	      }
277  	      else if( SCIPnodeGetDepth(node1) > SCIPnodeGetDepth(node2) )
278  	         node1 = SCIPnodeGetParent(node1);
279  	      else if( SCIPnodeGetDepth(node1) < SCIPnodeGetDepth(node2) )
280  	         node2 = SCIPnodeGetParent(node2);
281  	
282  	      assert(node1 != NULL);
283  	      assert(node2 != NULL);
284  	   }
285  	
286  	   /* get UCT scores for both nodes */
287  	   score1 = nodeGetUctScore(scip, node1, nodeseldata);
288  	   score2 = nodeGetUctScore(scip, node2, nodeseldata);
289  	
290  	   if( (SCIPisInfinity(scip, score1) && SCIPisInfinity(scip, score2)) ||
291  	      (SCIPisInfinity(scip, -score1) && SCIPisInfinity(scip, -score2)) ||
292  	      SCIPisEQ(scip, score1, score2) )
293  	   {
294  	      return 0;
295  	   }
296  	   else if( SCIPisLT(scip, score1, score2) )
297  	      return -1;
298  	   else
299  	   {
300  	      assert(SCIPisGT(scip, score1, score2));
301  	      return 1;
302  	   }
303  	}
304  	
305  	/** selects the best node among @p nodes with respect to UCT score */
306  	static
307  	void selectBestNode(
308  	   SCIP*                 scip,               /**< SCIP data structure */
309  	   SCIP_NODE**           selnode,            /**< pointer to store the selected node, needs not be empty */
310  	   SCIP_NODESELDATA*     nodeseldata,        /**< node selector data */
311  	   SCIP_NODE**           nodes,              /**< array of nodes to select from */
312  	   int                   nnodes              /**< size of the nodes array */
313  	   )
314  	{
315  	   int n;
316  	
317  	   assert(nnodes == 0 || nodes != NULL);
318  	   assert(nnodes >= 0);
319  	   assert(selnode != NULL);
320  	
321  	   if( nnodes == 0 )
322  	      return;
323  	
324  	   /* loop over nodes, always keeping reference to the best found node so far */
325  	   for( n = 0; n < nnodes; ++n )
326  	   {
327  	      assert(nodes[n] != NULL);
328  	      /* update the selected node if the current node has a higher score */
329  	      if( *selnode == NULL || compareNodes(scip, nodeseldata, *selnode, nodes[n]) < 0 )
330  	         *selnode = nodes[n];
331  	   }
332  	}
333  	
334  	/** keeps visits array large enough to save visits for all nodes in the branch and bound tree */
335  	static
336  	SCIP_RETCODE ensureMemorySize(
337  	   SCIP*                 scip,               /**< SCIP data structure */
338  	   SCIP_NODESELDATA*     nodeseldata         /**< node selector data */
339  	   )
340  	{
341  	   assert(nodeseldata != NULL);
342  	
343  	   /* if array has not been allocated yet, do this now with default initial capacity */
344  	   if( nodeseldata->nodevisits == NULL )
345  	   {
346  	      SCIP_CALL( SCIPallocClearMemoryArray(scip, &nodeseldata->nodevisits, INITIALSIZE) ); /*lint !e506*/
347  	      nodeseldata->sizenodevisits = INITIALSIZE;
348  	   }
349  	
350  	   assert(nodeseldata->nodelimit >= SCIPgetNNodes(scip));
351  	
352  	   /* if user node limit has not been reached yet, resize the visits array if necessary */
353  	   if( nodeseldata->sizenodevisits < 2 * nodeseldata->nodelimit && nodeseldata->sizenodevisits < (int)(2 * SCIPgetNNodes(scip)))
354  	   {
355  	      int newcapacity;
356  	      newcapacity = MIN(2 * nodeseldata->sizenodevisits, 2 * nodeseldata->nodelimit);
357  	
358  	      SCIPdebugMsg(scip, "Resizing node visits array, old capacity: %d new capacity : %d\n", nodeseldata->sizenodevisits, newcapacity);
359  	      assert(newcapacity > nodeseldata->sizenodevisits);
360  	
361  	      SCIP_CALL( SCIPreallocMemoryArray(scip, &nodeseldata->nodevisits, newcapacity) );
362  	      BMSclearMemoryArray(&(nodeseldata->nodevisits[nodeseldata->sizenodevisits]), newcapacity - nodeseldata->sizenodevisits); /*lint !e866*/
363  	
364  	      nodeseldata->sizenodevisits = newcapacity;
365  	   }
366  	
367  	   return SCIP_OKAY;
368  	}
369  	
370  	/*
371  	 * Callback methods of node selector
372  	 */
373  	
374  	/** copy method for node selector plugins (called when SCIP copies plugins) */
375  	static
376  	SCIP_DECL_NODESELCOPY(nodeselCopyUct)
377  	{  /*lint --e{715}*/
378  	   assert(scip != NULL);
379  	   SCIP_CALL( SCIPincludeNodeselUct(scip) );
380  	
381  	   return SCIP_OKAY;
382  	}
383  	
384  	/** solving process initialization method of node selector (called when branch and bound process is about to begin) */
385  	static
386  	SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
387  	{
388  	   SCIP_NODESELDATA* nodeseldata;
389  	   assert(scip != NULL);
390  	   assert(nodesel != NULL);
391  	
392  	   nodeseldata = SCIPnodeselGetData(nodesel);
393  	
394  	   assert(nodeseldata != NULL);
395  	   nodeseldata->nselections = 0;
396  	   nodeseldata->sizenodevisits = 0;
397  	   nodeseldata->origstdpriority = SCIPnodeselGetStdPriority(nodesel);
398  	
399  	   return SCIP_OKAY;
400  	}
401  	
402  	/** solving process deinitialization method of node selector (called when branch and bound process data gets freed) */
403  	static
404  	SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
405  	{
406  	   SCIP_NODESELDATA* nodeseldata;
407  	   assert(scip != NULL);
408  	   assert(nodesel != NULL);
409  	
410  	   nodeseldata = SCIPnodeselGetData(nodesel);
411  	
412  	   assert(nodeseldata != NULL);
413  	
414  	   if( nodeseldata->sizenodevisits > 0 )
415  	   {
416  	      assert(nodeseldata->nodevisits != NULL);
417  	      SCIPfreeMemoryArray(scip, &nodeseldata->nodevisits);
418  	   }
419  	   nodeseldata->sizenodevisits = 0;
420  	   nodeseldata->nselections = 0;
421  	
422  	   /* reset node selector priority to its original value (before turning it off) */
423  	   SCIP_CALL( SCIPsetNodeselStdPriority(scip, nodesel, nodeseldata->origstdpriority) );
424  	
425  	   return SCIP_OKAY;
426  	}
427  	
428  	/** destructor of node selector to free user data (called when SCIP is exiting) */
429  	static
430  	SCIP_DECL_NODESELFREE(nodeselFreeUct)
431  	{
432  	   SCIP_NODESELDATA* nodeseldata;
433  	   assert(scip != NULL);
434  	   assert(nodesel != NULL);
435  	
436  	   nodeseldata = SCIPnodeselGetData(nodesel);
437  	   if( nodeseldata->sizenodevisits > 0 )
438  	   {
439  	      assert(nodeseldata->nodevisits != NULL);
440  	      SCIPfreeMemoryArray(scip, &nodeseldata->nodevisits);
441  	   }
442  	   SCIPfreeBlockMemory(scip, &nodeseldata);
443  	
444  	   SCIPnodeselSetData(nodesel, NULL);
445  	
446  	   return SCIP_OKAY;
447  	}
448  	
449  	/** node selection method of node selector */
450  	static
451  	SCIP_DECL_NODESELSELECT(nodeselSelectUct)
452  	{
453  	   SCIP_NODESELDATA* nodeseldata;
454  	   SCIP_NODE** leaves;
455  	   SCIP_NODE** children;
456  	   SCIP_NODE** siblings;
457  	   int nleaves;
458  	   int nsiblings;
459  	   int nchildren;
460  	
461  	   assert(nodesel != NULL);
462  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
463  	   assert(scip != NULL);
464  	   assert(selnode != NULL);
465  	
466  	   *selnode = NULL;
467  	
468  	   nodeseldata = SCIPnodeselGetData(nodesel);
469  	   assert(nodeseldata != NULL);
470  	
471  	   if( nodeseldata->nodelimit < SCIPgetNNodes(scip) )
472  	   {
473  	      SCIPerrorMessage("UCT node limit exceeded\n");
474  	      return SCIP_INVALIDCALL;
475  	   }
476  	
477  	   /* collect leaves, children and siblings data */
478  	   SCIP_CALL( SCIPgetOpenNodesData(scip, &leaves, &children, &siblings, &nleaves, &nchildren, &nsiblings) );
479  	   assert(nleaves + nchildren + nsiblings == SCIPgetNNodesLeft(scip));
480  	
481  	   if( SCIPgetNNodesLeft(scip) == 0 )
482  	      return SCIP_OKAY;
483  	
484  	   /* make sure that UCT node selection data is large enough to store node visits */
485  	   SCIP_CALL( ensureMemorySize(scip, nodeseldata) );
486  	
487  	   /* select next node as best node with respect to UCT-based comparison method */
488  	   selectBestNode(scip, selnode, nodeseldata, children, nchildren);
489  	   selectBestNode(scip, selnode, nodeseldata, siblings, nsiblings);
490  	   selectBestNode(scip, selnode, nodeseldata, leaves, nleaves);
491  	
492  	   if( *selnode == NULL )
493  	   {
494  	      SCIPerrorMessage("Node selection rule UCT could not select a node.\n");
495  	      return SCIP_INVALIDCALL;
496  	   }
497  	
498  	   /* increase the number of selections */
499  	   ++nodeseldata->nselections;
500  	
501  	   /* switch back to default node selection rule if the node limit is exceeded */
502  	   if( nodeseldata->nselections == nodeseldata->nodelimit )
503  	   {
504  	      SCIP_CALL( turnoffNodeSelector(scip, nodesel) );
505  	   }
506  	   else
507  	   {
508  	      /* trigger update of visits along the path from the selected node to the root node */
509  	      SCIPdebugMsg(scip, "updating node visits from node number %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(*selnode));
510  	      updateVisits(nodeseldata, *selnode);
511  	   }
512  	
513  	   return SCIP_OKAY;
514  	}
515  	
516  	/** node comparison method of UCT node selector */
517  	static
518  	SCIP_DECL_NODESELCOMP(nodeselCompUct)
519  	{  /*lint --e{715}*/
520  	   SCIP_Real lowerbound1;
521  	   SCIP_Real lowerbound2;
522  	
523  	   lowerbound1 = SCIPnodeGetLowerbound(node1);
524  	   lowerbound2 = SCIPnodeGetLowerbound(node2);
525  	
526  	   if( SCIPisLT(scip, lowerbound1, lowerbound2) )
527  	      return -1;
528  	   else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
529  	      return 1;
530  	   else
531  	      return 0;
532  	}
533  	
534  	/*
535  	 * node selector specific interface methods
536  	 */
537  	
538  	/** creates the uct node selector and includes it in SCIP */
539  	SCIP_RETCODE SCIPincludeNodeselUct(
540  	   SCIP*                 scip                /**< SCIP data structure */
541  	   )
542  	{
543  	   SCIP_NODESELDATA* nodeseldata;
544  	   SCIP_NODESEL* nodesel;
545  	
546  	   /* create uct node selector data */
547  	   SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
548  	
549  	   nodesel = NULL;
550  	   nodeseldata->nodevisits = NULL;
551  	   nodeseldata->nselections = 0;
552  	   nodeseldata->sizenodevisits = 0;
553  	   nodeseldata->origstdpriority = NODESEL_STDPRIORITY;
554  	
555  	   /* use SCIPincludeNodeselBasic() plus setter functions if you want to set callbacks one-by-one and your code should
556  	    * compile independent of new callbacks being added in future SCIP versions
557  	    */
558  	   SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY,
559  	          NODESEL_MEMSAVEPRIORITY, nodeselSelectUct, nodeselCompUct, nodeseldata) );
560  	
561  	   assert(nodesel != NULL);
562  	
563  	   /* set non fundamental callbacks via setter functions */
564  	   SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyUct) );
565  	   SCIP_CALL( SCIPsetNodeselInitsol(scip, nodesel, nodeselInitsolUct) );
566  	   SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeUct) );
567  	   SCIP_CALL( SCIPsetNodeselExitsol(scip, nodesel, nodeselExitsolUct) );
568  	
569  	   /* add uct node selector parameters */
570  	   SCIP_CALL( SCIPaddIntParam(scip, "nodeselection/" NODESEL_NAME "/nodelimit",
571  	         "maximum number of nodes before switching to default rule",
572  	         &nodeseldata->nodelimit, TRUE, DEFAULT_NODELIMIT, 0, MAXNODELIMIT, NULL, NULL) );
573  	   SCIP_CALL( SCIPaddRealParam(scip, "nodeselection/" NODESEL_NAME "/weight",
574  	         "weight for visit quotient of node selection rule",
575  	         &nodeseldata->weight, TRUE, DEFAULT_WEIGHT, 0.0, 1.0, NULL, NULL) );
576  	   SCIP_CALL( SCIPaddBoolParam(scip, "nodeselection/" NODESEL_NAME "/useestimate",
577  	         "should the estimate (TRUE) or lower bound of a node be used for UCT score?",
578  	         &nodeseldata->useestimate, TRUE, DEFAULT_USEESTIMATE, NULL, NULL) );
579  	
580  	   return SCIP_OKAY;
581  	}
582