SCIP

Solving Constraint Integer Programs

nodesel_uct.c
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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file nodesel_uct.c
17  * @brief uct node selector which balances exploration and exploitation by considering node visits
18  * @author Gregor Hendel
19  *
20  * the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound
21  * and the number of times it has been visited so far compared to its parent node.
22  *
23  * The idea of UCT node selection for MIP appeared in:
24  * Ashish Sabharwal and Horst Samulowitz
25  * Guiding Combinatorial Optimization with UCT (2011)
26  *
27  * The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node,
28  * the algorithm selects the current node's child \f$N_i\f$ which maximizes the UCT score
29  *
30  * \f$\mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)} 31 * \f$
32  *
33  * where \f$\mbox{estimate}\f$ is the node's lower bound normalized by the root lower bound, and \f$\mbox{visits}\f$
34  * denotes the number of times a leaf in the subtree rooted at this node has been explored so far.
35  *
36  * The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion.
37  *
38  * The authors suggest that this node selection rule is particularly useful at the beginning of the solving process, but
39  * to switch to a different node selection after a number of nodes has been explored to reduce computational overhead.
40  * Our implementation uses only information available from the original SCIP tree which does not support the
41  * forward path mechanism needed for the most efficient node selection. Instead, the algorithm selects the next leaf
42  * 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
43  * by following their paths back upwards until their deepest common ancestor \f$a\f$ is reached, together with the two
44  * children of \f$a\f$ representing the two paths to l_1, l_2. The leaf represented by the child of \f$a\f$
45  * with higher UCT score is a candidate for the next selected leaf.
46  *
47  * The node selector features several parameters:
48  *
49  * the nodelimit delimits the number of explored nodes before UCT selection is turned off
50  * the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula)
51  * useestimate determines whether the node's estimate or lower bound is taken as estimate
52  *
53  * @note It should be avoided to switch to uct node selection after the branch and bound process has begun because
54  * the central UCT score information how often a path was taken is not collected if UCT is inactive. A safe use of
55  * UCT is to switch it on before SCIP starts optimization.
56  */
57
58 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
59
60 #include "blockmemshell/memory.h"
61 #include "scip/nodesel_uct.h"
62 #include "scip/pub_message.h"
63 #include "scip/pub_nodesel.h"
64 #include "scip/pub_tree.h"
65 #include "scip/scip_mem.h"
66 #include "scip/scip_message.h"
67 #include "scip/scip_nodesel.h"
68 #include "scip/scip_numerics.h"
69 #include "scip/scip_param.h"
70 #include "scip/scip_solvingstats.h"
71 #include "scip/scip_tree.h"
72 #include <string.h>
73
74 #define NODESEL_NAME "uct"
75 #define NODESEL_DESC "node selector which balances exploration and exploitation "
76 #define NODESEL_STDPRIORITY 10
77 #define NODESEL_MEMSAVEPRIORITY 0
78
79 /** default values for user parameters */
80 #define DEFAULT_WEIGHT 0.1 /**< weight of node visits in UCT score */
81 #define DEFAULT_NODELIMIT 31 /**< limit of node selections after which UCT node selection is turned off */
82 #define DEFAULT_USEESTIMATE FALSE /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
83 #define INITIALSIZE 1024 /**< initial size of node visits array (increased dynamically if required) */
84 #define MAXNODELIMIT 1000000 /**< the maximum value for user parameter nodelimit */
85 /*
86  * Data structures
87  */
88
89 /** node selector data */
90 struct SCIP_NodeselData
91 {
92  int* nodevisits; /**< array to store the number of node visits so far for every node */
93  SCIP_Real weight; /**< weight of node visits in UCT score */
94  int nodelimit; /**< limit of node selections after which UCT node selection is turned off */
95  int sizenodevisits; /**< the size of the visits array */
96  int nselections; /**< counter for the number of node selections */
97  int origstdpriority; /**< priority of node selector when starting branch and bound */
98  SCIP_Bool useestimate; /**< should the estimate (TRUE) or the lower bound of a node be used for UCT score? */
99 };
100
101 /*
102  * Local methods
103  */
104
105 /** get the number times @p node has been visited so far */
106 static
108  SCIP_NODESELDATA* nodeseldata, /**< node selector data */
109  SCIP_NODE* node /**< the node in question */
110  )
111 {
112  int nodenumber;
113
114  assert(nodeseldata != NULL);
115  assert(node != NULL);
116
117  /* nodes numbers start with 1 for the root node */
118  nodenumber = (int)(SCIPnodeGetNumber(node) - 1);
119  assert(nodenumber >= 0);
120
121  if( nodenumber >= nodeseldata->sizenodevisits )
122  return 0;
123  else
124  return nodeseldata->nodevisits[nodenumber];
125 }
126
127 /** increases the visits counter along the path from @p node to the root node */
128 static
130  SCIP_NODESELDATA* nodeseldata, /**< node selector data */
131  SCIP_NODE* node /**< leaf node of path along which the visits are backpropagated */
132  )
133 {
134  int* visits;
135
136  assert(nodeseldata != NULL);
137  assert(node != NULL);
138
139  visits = nodeseldata->nodevisits;
140  assert(visits != NULL);
141
142  /* increase visits counter of all nodes along the path until root node is reached (which has NULL as parent) */
143  do
144  {
145  int nodenumber;
146
147  nodenumber = (int)(SCIPnodeGetNumber(node) - 1);
148  if( nodenumber < nodeseldata->sizenodevisits )
149  ++(visits[nodenumber]);
150
151  assert(SCIPnodeGetParent(node) == NULL || SCIPnodeGetDepth(node) >= 1);
152  node = SCIPnodeGetParent(node);
153  }
154  while( node != NULL );
155 }
156
157 /** switches to a different node selection rule by assigning the lowest priority of all node selectors to uct */
158 static
160  SCIP* scip, /**< SCIP data structure */
161  SCIP_NODESEL* nodesel /**< the node selector to be turned off */
162  )
163 {
164  SCIP_NODESEL** nodesels;
165  int nnodesels;
166  int newpriority;
167  int prio;
168  int n;
169
170  nodesels = SCIPgetNodesels(scip);
171  nnodesels = SCIPgetNNodesels(scip);
172  newpriority = SCIPnodeselGetStdPriority(nodesel);
173
174  /* loop over node selectors to find minimum priority */
175  for( n = 0; n < nnodesels; ++n )
176  {
177  prio = SCIPnodeselGetStdPriority(nodesels[n]);
178  newpriority = MIN(newpriority, prio);
179  }
180  newpriority = MAX(newpriority, INT_MIN + 1);
181
182  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Reached node limit of UCT node selection rule -> switching to default\n");
183  SCIP_CALL( SCIPsetNodeselStdPriority(scip, nodesel, newpriority - 1) );
184
185  return SCIP_OKAY;
186 }
187
188 /** 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
189  * it has been visited so far in relation with the number of times its parent has been visited so far
190  */
191 static
193  SCIP* scip, /**< SCIP data structure */
194  SCIP_NODE* node, /**< the node for which UCT score is requested */
195  SCIP_NODESELDATA* nodeseldata /**< node selector data */
196  )
197 {
198  SCIP_NODE* parent;
199  SCIP_Real rootlowerbound;
200  SCIP_Real score;
201  int parentvisits;
202
203  rootlowerbound = SCIPgetLowerboundRoot(scip);
204
205  /* the objective part of the UCT score uses the (negative) gap between node estimate and root lower bound */
206  score = nodeseldata->useestimate ? SCIPnodeGetEstimate(node) : SCIPnodeGetLowerbound(node);
207
208  /* if the root lower bound is infinite due to LP errors, we ignore the gap part of the UCT score */
209  if( !SCIPisInfinity(scip, REALABS(rootlowerbound)) && !SCIPisEQ(scip, score, rootlowerbound) )
210  {
211  SCIP_Real absscore;
212  SCIP_Real absrootlowerbound;
213  SCIP_Real minabs;
214
215  assert(SCIPisGE(scip, score, rootlowerbound));
216  absscore = REALABS(score);
217  absrootlowerbound = REALABS(rootlowerbound);
218  minabs = MIN(absscore, absrootlowerbound);
219  minabs = MAX(minabs, 1.0);
220
221  score = (rootlowerbound - score) / minabs;
222  }
223  else
224  score = 0.0;
225
226  /* the visits part of the UCT score function */
227  parent = SCIPnodeGetParent(node);
228  assert(parent != NULL);
229  parentvisits = nodeGetVisits(nodeseldata, parent);
230
231  if( parentvisits > 0 )
232  {
233  int visits;
234
235  visits = nodeGetVisits(nodeseldata, node);
236  score += nodeseldata->weight * parentvisits / (SCIP_Real)(1 + visits);
237  }
238
239  return score;
240 }
241
242 /** compares two leaf nodes by comparing the UCT scores of the two children of their deepest common ancestor */
243 static
245  SCIP* scip, /**< SCIP data structure */
246  SCIP_NODESELDATA* nodeseldata, /**< node selector data */
247  SCIP_NODE* node1, /**< first node for comparison */
248  SCIP_NODE* node2 /**< second node for comparisons */
249  )
250 {
251  SCIP_Real score1;
252  SCIP_Real score2;
253
254  assert(node1 != node2);
255
256  /* go back in the tree to find the two shallowest ancestors of node1 and node2 which share the same parent */
257  while( SCIPnodeGetParent(node1) != SCIPnodeGetParent(node2) )
258  {
259  /* if the nodes have the same depth but not the same parent both pointers can be updated, otherwise only the deeper
260  * node pointer is moved
261  */
262  if( SCIPnodeGetDepth(node1) == SCIPnodeGetDepth(node2) )
263  {
264  node1 = SCIPnodeGetParent(node1);
265  node2 = SCIPnodeGetParent(node2);
266  }
267  else if( SCIPnodeGetDepth(node1) > SCIPnodeGetDepth(node2) )
268  node1 = SCIPnodeGetParent(node1);
269  else if( SCIPnodeGetDepth(node1) < SCIPnodeGetDepth(node2) )
270  node2 = SCIPnodeGetParent(node2);
271
272  assert(node1 != NULL);
273  assert(node2 != NULL);
274  }
275
276  /* get UCT scores for both nodes */
277  score1 = nodeGetUctScore(scip, node1, nodeseldata);
278  score2 = nodeGetUctScore(scip, node2, nodeseldata);
279
280  if( (SCIPisInfinity(scip, score1) && SCIPisInfinity(scip, score2)) ||
281  (SCIPisInfinity(scip, -score1) && SCIPisInfinity(scip, -score2)) ||
282  SCIPisEQ(scip, score1, score2) )
283  {
284  return 0;
285  }
286  else if( SCIPisLT(scip, score1, score2) )
287  return -1;
288  else
289  {
290  assert(SCIPisGT(scip, score1, score2));
291  return 1;
292  }
293 }
294
295 /** selects the best node among @p nodes with respect to UCT score */
296 static
298  SCIP* scip, /**< SCIP data structure */
299  SCIP_NODE** selnode, /**< pointer to store the selected node, needs not be empty */
300  SCIP_NODESELDATA* nodeseldata, /**< node selector data */
301  SCIP_NODE** nodes, /**< array of nodes to select from */
302  int nnodes /**< size of the nodes array */
303  )
304 {
305  int n;
306
307  assert(nnodes == 0 || nodes != NULL);
308  assert(nnodes >= 0);
309  assert(selnode != NULL);
310
311  if( nnodes == 0 )
312  return;
313
314  /* loop over nodes, always keeping reference to the best found node so far */
315  for( n = 0; n < nnodes; ++n )
316  {
317  assert(nodes[n] != NULL);
318  /* update the selected node if the current node has a higher score */
319  if( *selnode == NULL || compareNodes(scip, nodeseldata, *selnode, nodes[n]) < 0 )
320  *selnode = nodes[n];
321  }
322 }
323
324 /** keeps visits array large enough to save visits for all nodes in the branch and bound tree */
325 static
327  SCIP* scip, /**< SCIP data structure */
328  SCIP_NODESELDATA* nodeseldata /**< node selector data */
329  )
330 {
331  assert(nodeseldata != NULL);
332
333  /* if array has not been allocated yet, do this now with default initial capacity */
334  if( nodeseldata->nodevisits == NULL )
335  {
336  SCIP_CALL( SCIPallocClearMemoryArray(scip, &nodeseldata->nodevisits, INITIALSIZE) ); /*lint !e506*/
337  nodeseldata->sizenodevisits = INITIALSIZE;
338  }
339
340  assert(nodeseldata->nodelimit >= SCIPgetNNodes(scip));
341
342  /* if user node limit has not been reached yet, resize the visits array if necessary */
343  if( nodeseldata->sizenodevisits < 2 * nodeseldata->nodelimit && nodeseldata->sizenodevisits < (int)(2 * SCIPgetNNodes(scip)))
344  {
345  int newcapacity;
346  newcapacity = MIN(2 * nodeseldata->sizenodevisits, 2 * nodeseldata->nodelimit);
347
348  SCIPdebugMsg(scip, "Resizing node visits array, old capacity: %d new capacity : %d\n", nodeseldata->sizenodevisits, newcapacity);
349  assert(newcapacity > nodeseldata->sizenodevisits);
350
351  SCIP_CALL( SCIPreallocMemoryArray(scip, &nodeseldata->nodevisits, newcapacity) );
352  BMSclearMemoryArray(&(nodeseldata->nodevisits[nodeseldata->sizenodevisits]), newcapacity - nodeseldata->sizenodevisits); /*lint !e866*/
353
354  nodeseldata->sizenodevisits = newcapacity;
355  }
356
357  return SCIP_OKAY;
358 }
359
360 /*
361  * Callback methods of node selector
362  */
363
364 /** copy method for node selector plugins (called when SCIP copies plugins) */
365 static
366 SCIP_DECL_NODESELCOPY(nodeselCopyUct)
367 { /*lint --e{715}*/
368  assert(scip != NULL);
370
371  return SCIP_OKAY;
372 }
373
374 /** solving process initialization method of node selector (called when branch and bound process is about to begin) */
375 static
376 SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
377 {
378  SCIP_NODESELDATA* nodeseldata;
379  assert(scip != NULL);
380  assert(nodesel != NULL);
381
382  nodeseldata = SCIPnodeselGetData(nodesel);
383
384  assert(nodeseldata != NULL);
385  nodeseldata->nselections = 0;
386  nodeseldata->sizenodevisits = 0;
387  nodeseldata->origstdpriority = SCIPnodeselGetStdPriority(nodesel);
388
389  return SCIP_OKAY;
390 }
391
392 /** solving process deinitialization method of node selector (called when branch and bound process data gets freed) */
393 static
394 SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
395 {
396  SCIP_NODESELDATA* nodeseldata;
397  assert(scip != NULL);
398  assert(nodesel != NULL);
399
400  nodeseldata = SCIPnodeselGetData(nodesel);
401
402  assert(nodeseldata != NULL);
403
404  if( nodeseldata->sizenodevisits > 0 )
405  {
406  assert(nodeseldata->nodevisits != NULL);
407  SCIPfreeMemoryArray(scip, &nodeseldata->nodevisits);
408  }
409  nodeseldata->sizenodevisits = 0;
410  nodeseldata->nselections = 0;
411
412  /* reset node selector priority to its original value (before turning it off) */
413  SCIP_CALL( SCIPsetNodeselStdPriority(scip, nodesel, nodeseldata->origstdpriority) );
414
415  return SCIP_OKAY;
416 }
417
418 /** destructor of node selector to free user data (called when SCIP is exiting) */
419 static
420 SCIP_DECL_NODESELFREE(nodeselFreeUct)
421 {
422  SCIP_NODESELDATA* nodeseldata;
423  assert(scip != NULL);
424  assert(nodesel != NULL);
425
426  nodeseldata = SCIPnodeselGetData(nodesel);
427  if( nodeseldata->sizenodevisits > 0 )
428  {
429  assert(nodeseldata->nodevisits != NULL);
430  SCIPfreeMemoryArray(scip, &nodeseldata->nodevisits);
431  }
432  SCIPfreeBlockMemory(scip, &nodeseldata);
433
434  SCIPnodeselSetData(nodesel, NULL);
435
436  return SCIP_OKAY;
437 }
438
439 /** node selection method of node selector */
440 static
441 SCIP_DECL_NODESELSELECT(nodeselSelectUct)
442 {
443  SCIP_NODESELDATA* nodeseldata;
444  SCIP_NODE** leaves;
445  SCIP_NODE** children;
446  SCIP_NODE** siblings;
447  int nleaves;
448  int nsiblings;
449  int nchildren;
450
451  assert(nodesel != NULL);
452  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
453  assert(scip != NULL);
454  assert(selnode != NULL);
455
456  *selnode = NULL;
457
458  nodeseldata = SCIPnodeselGetData(nodesel);
459  assert(nodeseldata != NULL);
460
461  if( nodeseldata->nodelimit < SCIPgetNNodes(scip) )
462  {
463  SCIPerrorMessage("UCT node limit exceeded\n");
464  return SCIP_INVALIDCALL;
465  }
466
467  /* collect leaves, children and siblings data */
468  SCIP_CALL( SCIPgetOpenNodesData(scip, &leaves, &children, &siblings, &nleaves, &nchildren, &nsiblings) );
469  assert(nleaves + nchildren + nsiblings == SCIPgetNNodesLeft(scip));
470
471  if( SCIPgetNNodesLeft(scip) == 0 )
472  return SCIP_OKAY;
473
474  /* make sure that UCT node selection data is large enough to store node visits */
475  SCIP_CALL( ensureMemorySize(scip, nodeseldata) );
476
477  /* select next node as best node with respect to UCT-based comparison method */
478  selectBestNode(scip, selnode, nodeseldata, children, nchildren);
479  selectBestNode(scip, selnode, nodeseldata, siblings, nsiblings);
480  selectBestNode(scip, selnode, nodeseldata, leaves, nleaves);
481
482  if( *selnode == NULL )
483  {
484  SCIPerrorMessage("Node selection rule UCT could not select a node.\n");
485  return SCIP_INVALIDCALL;
486  }
487
488  /* increase the number of selections */
489  ++nodeseldata->nselections;
490
491  /* switch back to default node selection rule if the node limit is exceeded */
492  if( nodeseldata->nselections == nodeseldata->nodelimit )
493  {
494  SCIP_CALL( turnoffNodeSelector(scip, nodesel) );
495  }
496  else
497  {
498  /* trigger update of visits along the path from the selected node to the root node */
499  SCIPdebugMsg(scip, "updating node visits from node number %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(*selnode));
500  updateVisits(nodeseldata, *selnode);
501  }
502
503  return SCIP_OKAY;
504 }
505
506 /** node comparison method of UCT node selector */
507 static
508 SCIP_DECL_NODESELCOMP(nodeselCompUct)
509 { /*lint --e{715}*/
510  SCIP_Real lowerbound1;
511  SCIP_Real lowerbound2;
512
513  lowerbound1 = SCIPnodeGetLowerbound(node1);
514  lowerbound2 = SCIPnodeGetLowerbound(node2);
515
516  if( SCIPisLT(scip, lowerbound1, lowerbound2) )
517  return -1;
518  else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
519  return 1;
520  else
521  return 0;
522 }
523
524 /*
525  * node selector specific interface methods
526  */
527
528 /** creates the uct node selector and includes it in SCIP */
530  SCIP* scip /**< SCIP data structure */
531  )
532 {
533  SCIP_NODESELDATA* nodeseldata;
534  SCIP_NODESEL* nodesel;
535
536  /* create uct node selector data */
537  SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
538
539  nodesel = NULL;
540  nodeseldata->nodevisits = NULL;
541  nodeseldata->nselections = 0;
542  nodeseldata->sizenodevisits = 0;
543  nodeseldata->origstdpriority = NODESEL_STDPRIORITY;
544
545  /* use SCIPincludeNodeselBasic() plus setter functions if you want to set callbacks one-by-one and your code should
546  * compile independent of new callbacks being added in future SCIP versions
547  */
549  NODESEL_MEMSAVEPRIORITY, nodeselSelectUct, nodeselCompUct, nodeseldata) );
550
551  assert(nodesel != NULL);
552
553  /* set non fundamental callbacks via setter functions */
554  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyUct) );
555  SCIP_CALL( SCIPsetNodeselInitsol(scip, nodesel, nodeselInitsolUct) );
556  SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeUct) );
557  SCIP_CALL( SCIPsetNodeselExitsol(scip, nodesel, nodeselExitsolUct) );
558
559  /* add uct node selector parameters */
560  SCIP_CALL( SCIPaddIntParam(scip, "nodeselection/" NODESEL_NAME "/nodelimit",
561  "maximum number of nodes before switching to default rule",
562  &nodeseldata->nodelimit, TRUE, DEFAULT_NODELIMIT, 0, MAXNODELIMIT, NULL, NULL) );
563  SCIP_CALL( SCIPaddRealParam(scip, "nodeselection/" NODESEL_NAME "/weight",
564  "weight for visit quotient of node selection rule",
565  &nodeseldata->weight, TRUE, DEFAULT_WEIGHT, 0.0, 1.0, NULL, NULL) );
566  SCIP_CALL( SCIPaddBoolParam(scip, "nodeselection/" NODESEL_NAME "/useestimate",
567  "should the estimate (TRUE) or lower bound of a node be used for UCT score?",
568  &nodeseldata->useestimate, TRUE, DEFAULT_USEESTIMATE, NULL, NULL) );
569
570  return SCIP_OKAY;
571 }
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:208
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:107
#define DEFAULT_USEESTIMATE
Definition: nodesel_uct.c:82
#define INITIALSIZE
Definition: nodesel_uct.c:83
#define NULL
Definition: def.h:246
public methods for SCIP parameter handling
SCIP_NODESEL ** SCIPgetNodesels(SCIP *scip)
Definition: scip_nodesel.c:317
public methods for branch and bound tree
public methods for node selector plugins
public methods for memory management
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7367
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:88
#define NODESEL_STDPRIORITY
Definition: nodesel_uct.c:76
SCIP_RETCODE SCIPincludeNodeselBasic(SCIP *scip, SCIP_NODESEL **nodesel, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: scip_nodesel.c:173
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7627
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:465
#define NODESEL_DESC
Definition: nodesel_uct.c:75
#define DEFAULT_NODELIMIT
Definition: nodesel_uct.c:81
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:689
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel_uct.c:244
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7357
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:74
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:155
static SCIP_DECL_NODESELCOMP(nodeselCompUct)
Definition: nodesel_uct.c:508
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
public methods for numerical tolerances
public methods for querying solving statistics
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_uct.c:77
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
Definition: nodesel_uct.c:159
public methods for the branch-and-bound tree
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7347
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:38
static SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
Definition: nodesel_uct.c:394
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: scip_nodesel.c:288
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_WEIGHT
Definition: nodesel_uct.c:80
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip)
Definition: nodesel_uct.c:529
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:192
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1106
#define REALABS(x)
Definition: def.h:181
#define SCIP_CALL(x)
Definition: def.h:358
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
public methods for node selectors
#define SCIP_Bool
Definition: def.h:69
#define MAXNODELIMIT
Definition: nodesel_uct.c:84
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:129
static SCIP_DECL_NODESELCOPY(nodeselCopyUct)
Definition: nodesel_uct.c:366
static SCIP_DECL_NODESELFREE(nodeselFreeUct)
Definition: nodesel_uct.c:420
#define MIN(x, y)
Definition: def.h:216
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1038
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: scip_nodesel.c:272
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static void selectBestNode(SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes)
Definition: nodesel_uct.c:297
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7377
#define SCIP_LONGINT_FORMAT
Definition: def.h:149
#define MAX(x, y)
Definition: def.h:215
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNNodesels(SCIP *scip)
Definition: scip_nodesel.c:328
static SCIP_DECL_NODESELSELECT(nodeselSelectUct)
Definition: nodesel_uct.c:441
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:224
public methods for message output
#define SCIP_Real
Definition: def.h:157
public methods for message handling
static SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
Definition: nodesel_uct.c:376
#define NODESEL_NAME
Definition: nodesel_uct.c:74
#define nnodes
Definition: gastrans.c:65
uct node selector which balances exploration and exploitation by considering node visits ...
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
SCIP_Longint SCIPgetNNodes(SCIP *scip)
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:326
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1058
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1116
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:211
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:339
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129
memory allocation routines