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
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"
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 */
100struct 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 */
116static
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 */
138static
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 */
168static
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 */
201static
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 */
253static
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 */
306static
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 */
335static
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) */
375static
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) */
385static
386SCIP_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) */
403static
404SCIP_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) */
429static
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 */
450static
451SCIP_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 {
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 */
517static
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}
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNodeselUct(SCIP *scip)
Definition: nodesel_uct.c:539
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
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 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
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:66
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:80
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7773
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7523
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_NODESEL ** SCIPgetNodesels(SCIP *scip)
Definition: scip_nodesel.c:247
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_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:269
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1130
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:154
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1120
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1072
int SCIPgetNNodesels(SCIP *scip)
Definition: scip_nodesel.c:258
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:138
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1052
SCIP_RETCODE SCIPsetNodeselExitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: scip_nodesel.c:218
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: scip_nodesel.c:202
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:644
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
#define DEFAULT_WEIGHT
Definition: nodesel_uct.c:90
static int compareNodes(SCIP *scip, SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel_uct.c:254
static int nodeGetVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:117
static SCIP_Real nodeGetUctScore(SCIP *scip, SCIP_NODE *node, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:202
static void updateVisits(SCIP_NODESELDATA *nodeseldata, SCIP_NODE *node)
Definition: nodesel_uct.c:139
#define INITIALSIZE
Definition: nodesel_uct.c:93
#define DEFAULT_USEESTIMATE
Definition: nodesel_uct.c:92
static SCIP_DECL_NODESELFREE(nodeselFreeUct)
Definition: nodesel_uct.c:430
#define NODESEL_NAME
Definition: nodesel_uct.c:84
static SCIP_RETCODE turnoffNodeSelector(SCIP *scip, SCIP_NODESEL *nodesel)
Definition: nodesel_uct.c:169
#define DEFAULT_NODELIMIT
Definition: nodesel_uct.c:91
static SCIP_DECL_NODESELSELECT(nodeselSelectUct)
Definition: nodesel_uct.c:451
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_uct.c:87
static SCIP_DECL_NODESELEXITSOL(nodeselExitsolUct)
Definition: nodesel_uct.c:404
#define NODESEL_STDPRIORITY
Definition: nodesel_uct.c:86
static SCIP_DECL_NODESELINITSOL(nodeselInitsolUct)
Definition: nodesel_uct.c:386
#define NODESEL_DESC
Definition: nodesel_uct.c:85
static SCIP_RETCODE ensureMemorySize(SCIP *scip, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel_uct.c:336
static void selectBestNode(SCIP *scip, SCIP_NODE **selnode, SCIP_NODESELDATA *nodeseldata, SCIP_NODE **nodes, int nnodes)
Definition: nodesel_uct.c:307
static SCIP_DECL_NODESELCOPY(nodeselCopyUct)
Definition: nodesel_uct.c:376
#define MAXNODELIMIT
Definition: nodesel_uct.c:94
static SCIP_DECL_NODESELCOMP(nodeselCompUct)
Definition: nodesel_uct.c:518
uct node selector which balances exploration and exploitation by considering node visits
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public methods for node selectors
public methods for branch and bound tree
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for querying solving statistics
public methods for the branch-and-bound tree
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63