Scippy

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