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-2024 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
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
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
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
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
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
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
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);
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 */
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  */
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 }
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:138
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:117
#define DEFAULT_USEESTIMATE
Definition: nodesel_uct.c:92
#define INITIALSIZE
Definition: nodesel_uct.c:93
#define NULL
Definition: def.h:267
public methods for SCIP parameter handling
SCIP_NODESEL ** SCIPgetNodesels(SCIP *scip)
Definition: scip_nodesel.c:247
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:7510
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:80
#define NODESEL_STDPRIORITY
Definition: nodesel_uct.c:86
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:103
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7770
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:398
#define NODESEL_DESC
Definition: nodesel_uct.c:85
#define DEFAULT_NODELIMIT
Definition: nodesel_uct.c:91
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:644
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel_uct.c:254
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7500
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:66
#define SCIPdebugMsg
Definition: scip_message.h:78
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:83
static SCIP_DECL_NODESELCOMP(nodeselCompUct)
Definition: nodesel_uct.c:518
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
public methods for numerical tolerances
public methods for querying solving statistics
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_uct.c:87
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
Definition: nodesel_uct.c:169
public methods for the branch-and-bound tree
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7490
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:52
static SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
Definition: nodesel_uct.c:404
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: scip_nodesel.c:218
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_WEIGHT
Definition: nodesel_uct.c:90
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip)
Definition: nodesel_uct.c:539
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:202
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1120
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:380
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
public methods for node selectors
#define SCIP_Bool
Definition: def.h:91
#define MAXNODELIMIT
Definition: nodesel_uct.c:94
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:139
static SCIP_DECL_NODESELCOPY(nodeselCopyUct)
Definition: nodesel_uct.c:376
static SCIP_DECL_NODESELFREE(nodeselFreeUct)
Definition: nodesel_uct.c:430
#define MIN(x, y)
Definition: def.h:243
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1052
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: scip_nodesel.c:202
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:307
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7520
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define MAX(x, y)
Definition: def.h:239
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNNodesels(SCIP *scip)
Definition: scip_nodesel.c:258
static SCIP_DECL_NODESELSELECT(nodeselSelectUct)
Definition: nodesel_uct.c:451
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:154
public methods for message output
#define SCIP_Real
Definition: def.h:173
public methods for message handling
static SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
Definition: nodesel_uct.c:386
#define NODESEL_NAME
Definition: nodesel_uct.c:84
#define nnodes
Definition: gastrans.c:74
uct node selector which balances exploration and exploitation by considering node visits ...
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
SCIP_Longint SCIPgetNNodes(SCIP *scip)
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:336
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1072
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1130
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:139
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:269
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:57
memory allocation routines