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