Scippy

SCIP

Solving Constraint Integer Programs

nodesel.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-2021 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.c
17  * @ingroup OTHER_CFILES
18  * @brief methods for node selectors
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include <assert.h>
26 #include <string.h>
27 
28 #include "scip/def.h"
29 #include "scip/set.h"
30 #include "scip/clock.h"
31 #include "scip/stat.h"
32 #include "scip/visual.h"
33 #include "scip/paramset.h"
34 #include "scip/tree.h"
35 #include "scip/reopt.h"
36 #include "scip/lp.h"
37 #include "scip/scip.h"
38 #include "scip/nodesel.h"
39 #include "scip/pub_message.h"
40 #include "scip/pub_misc.h"
41 
42 #include "scip/struct_nodesel.h"
43 #include "scip/struct_scip.h"
44 
45 /*
46  * node priority queue methods
47  */
48 
49 #define PQ_PARENT(q) (((q)+1)/2-1)
50 #define PQ_LEFTCHILD(p) (2*(p)+1)
51 #define PQ_RIGHTCHILD(p) (2*(p)+2)
52 
53 
54 /** node comparator for node numbers */
55 static
56 SCIP_DECL_SORTPTRCOMP(nodeCompNumber)
57 { /*lint --e{715}*/
58  assert(elem1 != NULL);
59  assert(elem2 != NULL);
60 
61  if( ((SCIP_NODE*)elem1)->number < ((SCIP_NODE*)elem2)->number )
62  return -1;
63  else if( ((SCIP_NODE*)elem1)->number > ((SCIP_NODE*)elem2)->number )
64  return +1;
65  else
66  {
67  /* no such two nodes should have the same node number */
68  assert(elem1 == elem2);
69  return 0;
70  }
71 }
72 
73 
74 /** resizes node memory to hold at least the given number of nodes */
75 static
77  SCIP_NODEPQ* nodepq, /**< node priority queue */
78  SCIP_SET* set, /**< global SCIP settings */
79  int minsize /**< minimal number of storable nodes */
80  )
81 {
82  assert(nodepq != NULL);
83 
84  if( minsize <= nodepq->size )
85  return SCIP_OKAY;
86 
87  nodepq->size = SCIPsetCalcTreeGrowSize(set, minsize);
88  SCIP_ALLOC( BMSreallocMemoryArray(&nodepq->slots, nodepq->size) );
89  SCIP_ALLOC( BMSreallocMemoryArray(&nodepq->bfsposs, nodepq->size) );
90  SCIP_ALLOC( BMSreallocMemoryArray(&nodepq->bfsqueue, nodepq->size) );
91 
92  return SCIP_OKAY;
93 }
94 
95 /** creates node priority queue */
97  SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */
98  SCIP_SET* set, /**< global SCIP settings */
99  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
100  )
101 { /*lint --e{715}*/
102  assert(nodepq != NULL);
103  assert(set != NULL);
104 
105  SCIP_ALLOC( BMSallocMemory(nodepq) );
106  (*nodepq)->nodesel = nodesel;
107  (*nodepq)->slots = NULL;
108  (*nodepq)->bfsposs = NULL;
109  (*nodepq)->bfsqueue = NULL;
110  (*nodepq)->len = 0;
111  (*nodepq)->size = 0;
112  (*nodepq)->lowerboundsum = 0.0;
113 
114  return SCIP_OKAY;
115 }
116 
117 /** frees node priority queue, but not the data nodes themselves */
119  SCIP_NODEPQ** nodepq /**< pointer to a node priority queue */
120  )
121 {
122  assert(nodepq != NULL);
123  assert(*nodepq != NULL);
124 
125  BMSfreeMemoryArrayNull(&(*nodepq)->slots);
126  BMSfreeMemoryArrayNull(&(*nodepq)->bfsposs);
127  BMSfreeMemoryArrayNull(&(*nodepq)->bfsqueue);
128  BMSfreeMemory(nodepq);
129 }
130 
131 /** frees node priority queue and all nodes in the queue */
133  SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */
134  BMS_BLKMEM* blkmem, /**< block memory buffers */
135  SCIP_SET* set, /**< global SCIP settings */
136  SCIP_STAT* stat, /**< problem statistics */
137  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
138  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
139  SCIP_TREE* tree, /**< branch and bound tree */
140  SCIP_LP* lp /**< current LP data */
141  )
142 {
143  assert(nodepq != NULL);
144  assert(*nodepq != NULL);
145 
146  /* free the nodes of the queue */
147  SCIP_CALL( SCIPnodepqClear(*nodepq, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
148 
149  /* free the queue data structure */
150  SCIPnodepqDestroy(nodepq);
151 
152  return SCIP_OKAY;
153 }
154 
155 /** deletes all nodes in the node priority queue */
157  SCIP_NODEPQ* nodepq, /**< node priority queue */
158  BMS_BLKMEM* blkmem, /**< block memory buffers */
159  SCIP_SET* set, /**< global SCIP settings */
160  SCIP_STAT* stat, /**< problem statistics */
161  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
162  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
163  SCIP_TREE* tree, /**< branch and bound tree */
164  SCIP_LP* lp /**< current LP data */
165  )
166 {
167  int i;
168 
169  assert(nodepq != NULL);
170 
171  if( nodepq->len > 0 )
172  {
173  /* sort the sorts downwards after their number to increase speed when freeing in debug mode */
174  /* @todo: if a node is freed, the parent will also be freed, if no children are left; maybe we want to free all
175  * nodes in the order of decreasing node numbers
176  */
177  SCIPsortDownPtr((void**)nodepq->slots, nodeCompNumber, nodepq->len);
178 
179  /* free the nodes of the queue */
180  for( i = 0; i < nodepq->len; ++i )
181  {
182  assert(nodepq->slots[i] != NULL);
183  assert(SCIPnodeGetType(nodepq->slots[i]) == SCIP_NODETYPE_LEAF);
184 
185  SCIP_CALL( SCIPnodeFree(&nodepq->slots[i], blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
186  }
187  }
188 
189  /* reset data */
190  nodepq->len = 0;
191  nodepq->lowerboundsum = 0.0;
192 
193  return SCIP_OKAY;
194 }
195 
196 /** returns the node selector associated with the given node priority queue */
198  SCIP_NODEPQ* nodepq /**< node priority queue */
199  )
200 {
201  assert(nodepq != NULL);
202 
203  return nodepq->nodesel;
204 }
205 
206 /** sets the node selector used for sorting the nodes in the queue, and resorts the queue if necessary */
208  SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */
209  SCIP_SET* set, /**< global SCIP settings */
210  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
211  )
212 {
213  SCIP_NODEPQ* newnodepq;
214  SCIP_RETCODE retcode;
215  int i;
216 
217  assert(nodepq != NULL);
218  assert(*nodepq != NULL);
219  assert((*nodepq)->len >= 0);
220  assert(nodesel != NULL);
221  assert(nodesel->nodeselcomp != NULL);
222 
223  if( (*nodepq)->nodesel == nodesel )
224  return SCIP_OKAY;
225 
226  /* create new node priority queue */
227  SCIP_CALL( SCIPnodepqCreate(&newnodepq, set, nodesel) );
228 
229  /* resize the new node priority queue to be able to store all nodes */
230  retcode = nodepqResize(newnodepq, set, (*nodepq)->len);
231 
232  /* insert all nodes in the new node priority queue */
233  for( i = 0; i < (*nodepq)->len && retcode == SCIP_OKAY; ++i )
234  {
235  retcode = SCIPnodepqInsert(newnodepq, set, (*nodepq)->slots[i]);
236  }
237 
238  if( retcode != SCIP_OKAY )
239  {
240  SCIPnodepqDestroy(&newnodepq);
241 
242  return retcode;
243  }
244 
245  /* destroy the old node priority queue without freeing the nodes */
246  SCIPnodepqDestroy(nodepq);
247 
248  /* use the new node priority queue */
249  *nodepq = newnodepq;
250 
251  return SCIP_OKAY;
252 }
253 
254 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */
256  SCIP_NODEPQ* nodepq, /**< node priority queue */
257  SCIP_SET* set, /**< global SCIP settings */
258  SCIP_NODE* node1, /**< first node to compare */
259  SCIP_NODE* node2 /**< second node to compare */
260  )
261 {
262  assert(nodepq != NULL);
263  assert(nodepq->nodesel != NULL);
264  assert(nodepq->nodesel->nodeselcomp != NULL);
265  assert(set != NULL);
266 
267  return SCIPnodeselCompare(nodepq->nodesel, set, node1, node2);
268 }
269 
270 /** inserts node into node priority queue */
272  SCIP_NODEPQ* nodepq, /**< node priority queue */
273  SCIP_SET* set, /**< global SCIP settings */
274  SCIP_NODE* node /**< node to be inserted */
275  )
276 {
277  SCIP_NODESEL* nodesel;
278  SCIP_NODE** slots;
279  int* bfsposs;
280  int* bfsqueue;
281  SCIP_Real lowerbound;
282  int pos;
283  int bfspos;
284 
285  assert(nodepq != NULL);
286  assert(nodepq->len >= 0);
287  assert(set != NULL);
288  assert(node != NULL);
289 
290  nodesel = nodepq->nodesel;
291  assert(nodesel != NULL);
292  assert(nodesel->nodeselcomp != NULL);
293 
294  SCIP_CALL( nodepqResize(nodepq, set, nodepq->len+1) );
295  slots = nodepq->slots;
296  bfsposs = nodepq->bfsposs;
297  bfsqueue = nodepq->bfsqueue;
298 
299  /* insert node as leaf in the tree, move it towards the root as long it is better than its parent */
300  nodepq->len++;
301  nodepq->lowerboundsum += SCIPnodeGetLowerbound(node);
302  pos = nodepq->len-1;
303  while( pos > 0 && nodesel->nodeselcomp(set->scip, nodesel, node, slots[PQ_PARENT(pos)]) < 0 )
304  {
305  slots[pos] = slots[PQ_PARENT(pos)];
306  bfsposs[pos] = bfsposs[PQ_PARENT(pos)];
307  bfsqueue[bfsposs[pos]] = pos;
308  pos = PQ_PARENT(pos);
309  }
310  slots[pos] = node;
311 
312  /* insert the final position into the bfs index queue */
313  lowerbound = SCIPnodeGetLowerbound(node);
314  bfspos = nodepq->len-1;
315  while( bfspos > 0 && lowerbound < SCIPnodeGetLowerbound(slots[bfsqueue[PQ_PARENT(bfspos)]]) )
316  {
317  bfsqueue[bfspos] = bfsqueue[PQ_PARENT(bfspos)];
318  bfsposs[bfsqueue[bfspos]] = bfspos;
319  bfspos = PQ_PARENT(bfspos);
320  }
321  bfsqueue[bfspos] = pos;
322  bfsposs[pos] = bfspos;
323 
324  SCIPsetDebugMsg(set, "inserted node %p[%g] at pos %d and bfspos %d of node queue\n", (void*)node, lowerbound, pos, bfspos);
325 
326  return SCIP_OKAY;
327 }
328 
329 /** deletes node at given position from the node priority queue; returns TRUE, if the parent fell down to the
330  * free position
331  */
332 static
334  SCIP_NODEPQ* nodepq, /**< node priority queue */
335  SCIP_SET* set, /**< global SCIP settings */
336  int rempos /**< queue position of node to remove */
337  )
338 {
339  SCIP_NODESEL* nodesel;
340  SCIP_NODE** slots;
341  int* bfsposs;
342  int* bfsqueue;
343  SCIP_NODE* lastnode;
344  int lastbfspos;
345  int lastbfsqueueidx;
346  int freepos;
347  int freebfspos;
348  SCIP_Bool parentfelldown;
349  SCIP_Bool bfsparentfelldown;
350 
351  assert(nodepq != NULL);
352  assert(nodepq->len > 0);
353  assert(set != NULL);
354  assert(0 <= rempos && rempos < nodepq->len);
355 
356  nodesel = nodepq->nodesel;
357  assert(nodesel != NULL);
358  assert(nodesel->nodeselcomp != NULL);
359 
360  slots = nodepq->slots;
361  bfsposs = nodepq->bfsposs;
362  bfsqueue = nodepq->bfsqueue;
363 
364  nodepq->lowerboundsum -= SCIPnodeGetLowerbound(slots[rempos]);
365  freepos = rempos;
366  freebfspos = bfsposs[rempos];
367  assert(0 <= freebfspos && freebfspos < nodepq->len);
368 
369  SCIPsetDebugMsg(set, "delete node %p[%g] at pos %d and bfspos %d of node queue\n",
370  (void*)slots[freepos], SCIPnodeGetLowerbound(slots[freepos]), freepos, freebfspos);
371 
372  /* remove node of the tree and get a free slot,
373  * if the removed node was the last node of the queue
374  * - do nothing
375  * if the last node of the queue is better than the parent of the removed node:
376  * - move the parent to the free slot, until the last node can be placed in the free slot
377  * if the last node of the queue is not better than the parent of the free slot:
378  * - move the better child to the free slot until the last node can be placed in the free slot
379  */
380  nodepq->len--;
381 
382  /* process the slots queue ordered by the node selection comparator */
383  lastnode = slots[nodepq->len];
384  lastbfspos = bfsposs[nodepq->len];
385  parentfelldown = FALSE;
386  if( freepos < nodepq->len )
387  {
388  int parentpos;
389 
390  /* try to move parents downwards to insert last node */
391  parentpos = PQ_PARENT(freepos);
392  while( freepos > 0 && nodesel->nodeselcomp(set->scip, nodesel, lastnode, slots[parentpos]) < 0 )
393  {
394  slots[freepos] = slots[parentpos];
395  bfsposs[freepos] = bfsposs[parentpos];
396  bfsqueue[bfsposs[freepos]] = freepos;
397  freepos = parentpos;
398  parentpos = PQ_PARENT(freepos);
399  parentfelldown = TRUE;
400  }
401  if( !parentfelldown )
402  {
403  /* downward moving of parents was not successful -> move children upwards */
404  while( freepos <= PQ_PARENT(nodepq->len-1) ) /* as long as free slot has children... */
405  {
406  int childpos;
407  int brotherpos;
408 
409  /* select the better child of free slot */
410  childpos = PQ_LEFTCHILD(freepos);
411  assert(childpos < nodepq->len);
412  brotherpos = PQ_RIGHTCHILD(freepos);
413  if( brotherpos < nodepq->len
414  && nodesel->nodeselcomp(set->scip, nodesel, slots[brotherpos], slots[childpos]) < 0 )
415  childpos = brotherpos;
416 
417  /* exit search loop if better child is not better than last node */
418  if( nodesel->nodeselcomp(set->scip, nodesel, lastnode, slots[childpos]) <= 0 )
419  break;
420 
421  /* move better child upwards, free slot is now the better child's slot */
422  slots[freepos] = slots[childpos];
423  bfsposs[freepos] = bfsposs[childpos];
424  bfsqueue[bfsposs[freepos]] = freepos;
425  freepos = childpos;
426  }
427  }
428  assert(0 <= freepos && freepos < nodepq->len);
429  assert(!parentfelldown || PQ_LEFTCHILD(freepos) < nodepq->len);
430  slots[freepos] = lastnode;
431  bfsposs[freepos] = lastbfspos;
432  bfsqueue[lastbfspos] = freepos;
433  }
434 
435  /* process the bfs queue ordered by the lower bound */
436  lastbfsqueueidx = bfsqueue[nodepq->len];
437  bfsparentfelldown = FALSE;
438  if( freebfspos < nodepq->len )
439  {
440  SCIP_Real lastlowerbound;
441  int parentpos;
442 
443  /* try to move parents downwards to insert last queue index */
444  lastlowerbound = SCIPnodeGetLowerbound(slots[lastbfsqueueidx]);
445  parentpos = PQ_PARENT(freebfspos);
446  while( freebfspos > 0 && lastlowerbound < SCIPnodeGetLowerbound(slots[bfsqueue[parentpos]]) )
447  {
448  bfsqueue[freebfspos] = bfsqueue[parentpos];
449  bfsposs[bfsqueue[freebfspos]] = freebfspos;
450  freebfspos = parentpos;
451  parentpos = PQ_PARENT(freebfspos);
452  bfsparentfelldown = TRUE;
453  }
454  if( !bfsparentfelldown )
455  {
456  /* downward moving of parents was not successful -> move children upwards */
457  while( freebfspos <= PQ_PARENT(nodepq->len-1) ) /* as long as free slot has children... */
458  {
459  int childpos;
460  int brotherpos;
461 
462  /* select the better child of free slot */
463  childpos = PQ_LEFTCHILD(freebfspos);
464  assert(childpos < nodepq->len);
465  brotherpos = PQ_RIGHTCHILD(freebfspos);
466  if( brotherpos < nodepq->len
467  && SCIPnodeGetLowerbound(slots[bfsqueue[brotherpos]]) < SCIPnodeGetLowerbound(slots[bfsqueue[childpos]]) )
468  childpos = brotherpos;
469 
470  /* exit search loop if better child is not better than last node */
471  if( lastlowerbound <= SCIPnodeGetLowerbound(slots[bfsqueue[childpos]]) )
472  break;
473 
474  /* move better child upwards, free slot is now the better child's slot */
475  bfsqueue[freebfspos] = bfsqueue[childpos];
476  bfsposs[bfsqueue[freebfspos]] = freebfspos;
477  freebfspos = childpos;
478  }
479  }
480  assert(0 <= freebfspos && freebfspos < nodepq->len);
481  assert(!bfsparentfelldown || PQ_LEFTCHILD(freebfspos) < nodepq->len);
482  bfsqueue[freebfspos] = lastbfsqueueidx;
483  bfsposs[lastbfsqueueidx] = freebfspos;
484  }
485 
486  return parentfelldown;
487 }
488 
489 /** returns the position of given node in the priority queue, or -1 if not existing */
490 static
492  SCIP_NODEPQ* nodepq, /**< node priority queue */
493  SCIP_SET* set, /**< global SCIP settings */
494  SCIP_NODE* node /**< node to find */
495  )
496 {
497  int pos;
498 
499  assert(nodepq != NULL);
500  assert(nodepq->len >= 0);
501  assert(set != NULL);
502  assert(node != NULL);
503 
504  /* search the node in the queue */
505  for( pos = 0; pos < nodepq->len && node != nodepq->slots[pos]; ++pos )
506  {}
507 
508  if( pos == nodepq->len )
509  pos = -1;
510 
511  return pos;
512 }
513 
514 /** removes node from the node priority queue */
516  SCIP_NODEPQ* nodepq, /**< node priority queue */
517  SCIP_SET* set, /**< global SCIP settings */
518  SCIP_NODE* node /**< node to remove */
519  )
520 {
521  int pos;
522 
523  pos = nodepqFindNode(nodepq, set, node);
524  if( pos == -1 )
525  {
526  SCIPerrorMessage("node doesn't exist in node priority queue\n");
527  return SCIP_INVALIDDATA;
528  }
529 
530  (void)nodepqDelPos(nodepq, set, pos);
531 
532  return SCIP_OKAY;
533 }
534 
535 /** returns the best node of the queue without removing it */
537  const SCIP_NODEPQ* nodepq /**< node priority queue */
538  )
539 {
540  assert(nodepq != NULL);
541  assert(nodepq->len >= 0);
542 
543  if( nodepq->len == 0 )
544  return NULL;
545 
546  assert(nodepq->slots[0] != NULL);
547 
548  return nodepq->slots[0];
549 }
550 
551 /** returns the nodes array of the queue */
553  const SCIP_NODEPQ* nodepq /**< node priority queue */
554  )
555 {
556  assert(nodepq != NULL);
557 
558  return nodepq->slots;
559 }
560 
561 /** returns the number of nodes stored in the node priority queue */
563  const SCIP_NODEPQ* nodepq /**< node priority queue */
564  )
565 {
566  assert(nodepq != NULL);
567  assert(nodepq->len >= 0);
568 
569  return nodepq->len;
570 }
571 
572 /** gets the minimal lower bound of all nodes in the queue */
574  SCIP_NODEPQ* nodepq, /**< node priority queue */
575  SCIP_SET* set /**< global SCIP settings */
576  )
577 {
578  assert(nodepq != NULL);
579  assert(nodepq->nodesel != NULL);
580  assert(set != NULL);
581 
582  if( nodepq->len > 0 )
583  {
584  int bfspos;
585 
586  bfspos = nodepq->bfsqueue[0];
587  assert(0 <= bfspos && bfspos < nodepq->len);
588  assert(nodepq->slots[bfspos] != NULL);
589  return SCIPnodeGetLowerbound(nodepq->slots[bfspos]);
590  }
591  else
592  return SCIPsetInfinity(set);
593 }
594 
595 /** gets the node with minimal lower bound of all nodes in the queue */
597  SCIP_NODEPQ* nodepq, /**< node priority queue */
598  SCIP_SET* set /**< global SCIP settings */
599  )
600 {
601  assert(nodepq != NULL);
602  assert(nodepq->nodesel != NULL);
603  assert(set != NULL);
604 
605  /* the node selector's compare method sorts the minimal lower bound to the front */
606  if( nodepq->len > 0 )
607  {
608  int bfspos;
609 
610  bfspos = nodepq->bfsqueue[0];
611  assert(0 <= bfspos && bfspos < nodepq->len);
612  assert(nodepq->slots[bfspos] != NULL);
613  return nodepq->slots[bfspos];
614  }
615  else
616  return NULL;
617 }
618 
619 /** gets the sum of lower bounds of all nodes in the queue */
621  SCIP_NODEPQ* nodepq /**< node priority queue */
622  )
623 {
624  assert(nodepq != NULL);
625 
626  return nodepq->lowerboundsum;
627 }
628 
629 /** free all nodes from the queue that are cut off by the given upper bound */
631  SCIP_NODEPQ* nodepq, /**< node priority queue */
632  BMS_BLKMEM* blkmem, /**< block memory buffer */
633  SCIP_SET* set, /**< global SCIP settings */
634  SCIP_STAT* stat, /**< dynamic problem statistics */
635  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
636  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
637  SCIP_TREE* tree, /**< branch and bound tree */
638  SCIP_REOPT* reopt, /**< reoptimization data structure */
639  SCIP_LP* lp, /**< current LP data */
640  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
641  )
642 {
643  SCIP_NODE* node;
644  int pos;
645  SCIP_Bool parentfelldown;
646 
647  assert(nodepq != NULL);
648 
649  SCIPsetDebugMsg(set, "bounding node queue of length %d with cutoffbound=%g\n", nodepq->len, cutoffbound);
650  pos = nodepq->len-1;
651  while( pos >= 0 )
652  {
653  assert(pos < nodepq->len);
654  node = nodepq->slots[pos];
655  assert(node != NULL);
656  assert(SCIPnodeGetType(node) == SCIP_NODETYPE_LEAF);
657  if( SCIPsetIsInfinity(set, SCIPnodeGetLowerbound(node)) || SCIPsetIsGE(set, SCIPnodeGetLowerbound(node), cutoffbound) )
658  {
659  SCIPsetDebugMsg(set, "free node in slot %d (len=%d) at depth %d with lowerbound=%g\n",
660  pos, nodepq->len, SCIPnodeGetDepth(node), SCIPnodeGetLowerbound(node));
661 
662  /* cut off node; because we looped from back to front, the existing children of the node must have a smaller
663  * lower bound than the cut off value
664  */
665  assert(PQ_LEFTCHILD(pos) >= nodepq->len
666  || SCIPsetIsLT(set, SCIPnodeGetLowerbound(nodepq->slots[PQ_LEFTCHILD(pos)]), cutoffbound));
667  assert(PQ_RIGHTCHILD(pos) >= nodepq->len
668  || SCIPsetIsLT(set, SCIPnodeGetLowerbound(nodepq->slots[PQ_RIGHTCHILD(pos)]), cutoffbound));
669 
670  /* free the slot in the node PQ */
671  parentfelldown = nodepqDelPos(nodepq, set, pos);
672 
673  /* - if the slot was occupied by the parent, we have to check this slot (the parent) again; unfortunately,
674  * we will check the node which occupied the parent's slot again, even though it cannot be cut off;
675  * - otherwise, the slot was the last slot or it was occupied by a node with a position greater than
676  * the current position; this node was already checked and we can decrease the position
677  */
678  if( !parentfelldown )
679  pos--;
680 
681  SCIPvisualCutoffNode(stat->visual, set, stat, node, FALSE);
682 
683  if( set->reopt_enable )
684  {
685  assert(reopt != NULL);
686  SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, node, SCIP_EVENTTYPE_NODEINFEASIBLE, lp,
687  SCIPlpGetSolstat(lp), SCIPnodeGetDepth(node) == 0, SCIPtreeGetFocusNode(tree) == node,
689  }
690 
691  /* free memory of the node */
692  SCIP_CALL( SCIPnodeFree(&node, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
693  }
694  else
695  pos--;
696  }
697  SCIPsetDebugMsg(set, " -> bounded node queue has length %d\n", nodepq->len);
698 
699  return SCIP_OKAY;
700 }
701 
702 
703 
704 
705 /*
706  * node selector methods
707  */
708 
709 /** method to call, when the standard mode priority of a node selector was changed */
710 static
711 SCIP_DECL_PARAMCHGD(paramChgdNodeselStdPriority)
712 { /*lint --e{715}*/
713  SCIP_PARAMDATA* paramdata;
714 
715  paramdata = SCIPparamGetData(param);
716  assert(paramdata != NULL);
717 
718  /* use SCIPsetNodeselStdPriority() to mark the nodesels unsorted */
719  SCIP_CALL( SCIPsetNodeselStdPriority(scip, (SCIP_NODESEL*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
720 
721  return SCIP_OKAY;
722 }
723 
724 /** method to call, when the memory saving mode priority of a node selector was changed */
725 static
726 SCIP_DECL_PARAMCHGD(paramChgdNodeselMemsavePriority)
727 { /*lint --e{715}*/
728  SCIP_PARAMDATA* paramdata;
729 
730  paramdata = SCIPparamGetData(param);
731  assert(paramdata != NULL);
732 
733  /* use SCIPsetNodeselMemsavePriority() to mark the nodesels unsorted */
734  SCIP_CALL( SCIPsetNodeselMemsavePriority(scip, (SCIP_NODESEL*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
735 
736  return SCIP_OKAY;
737 }
738 
739 /** copies the given node selector to a new scip */
741  SCIP_NODESEL* nodesel, /**< node selector */
742  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
743  )
744 {
745  assert(nodesel != NULL);
746  assert(set != NULL);
747  assert(set->scip != NULL);
748 
749  if( nodesel->nodeselcopy != NULL )
750  {
751  SCIPsetDebugMsg(set, "including node selector %s in subscip %p\n", SCIPnodeselGetName(nodesel), (void*)set->scip);
752  SCIP_CALL( nodesel->nodeselcopy(set->scip, nodesel) );
753  }
754  return SCIP_OKAY;
755 }
756 
757 /** internal method for creating a node selector */
758 static
760  SCIP_NODESEL** nodesel, /**< pointer to store node selector */
761  SCIP_SET* set, /**< global SCIP settings */
762  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
763  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
764  const char* name, /**< name of node selector */
765  const char* desc, /**< description of node selector */
766  int stdpriority, /**< priority of the node selector in standard mode */
767  int memsavepriority, /**< priority of the node selector in memory saving mode */
768  SCIP_DECL_NODESELCOPY ((*nodeselcopy)), /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
769  SCIP_DECL_NODESELFREE ((*nodeselfree)), /**< destructor of node selector */
770  SCIP_DECL_NODESELINIT ((*nodeselinit)), /**< initialize node selector */
771  SCIP_DECL_NODESELEXIT ((*nodeselexit)), /**< deinitialize node selector */
772  SCIP_DECL_NODESELINITSOL((*nodeselinitsol)),/**< solving process initialization method of node selector */
773  SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)),/**< solving process deinitialization method of node selector */
774  SCIP_DECL_NODESELSELECT((*nodeselselect)),/**< node selection method */
775  SCIP_DECL_NODESELCOMP ((*nodeselcomp)), /**< node comparison method */
776  SCIP_NODESELDATA* nodeseldata /**< node selector data */
777  )
778 {
780  char paramdesc[SCIP_MAXSTRLEN];
781 
782  assert(nodesel != NULL);
783  assert(name != NULL);
784  assert(desc != NULL);
785  assert(nodeselselect != NULL);
786  assert(nodeselcomp != NULL);
787 
788  SCIP_ALLOC( BMSallocMemory(nodesel) );
789  BMSclearMemory(*nodesel);
790 
791  SCIP_ALLOC( BMSduplicateMemoryArray(&(*nodesel)->name, name, strlen(name)+1) );
792  SCIP_ALLOC( BMSduplicateMemoryArray(&(*nodesel)->desc, desc, strlen(desc)+1) );
793  (*nodesel)->stdpriority = stdpriority;
794  (*nodesel)->memsavepriority = memsavepriority;
795  (*nodesel)->nodeselcopy = nodeselcopy;
796  (*nodesel)->nodeselfree = nodeselfree;
797  (*nodesel)->nodeselinit = nodeselinit;
798  (*nodesel)->nodeselexit = nodeselexit;
799  (*nodesel)->nodeselinitsol = nodeselinitsol;
800  (*nodesel)->nodeselexitsol = nodeselexitsol;
801  (*nodesel)->nodeselselect = nodeselselect;
802  (*nodesel)->nodeselcomp = nodeselcomp;
803  (*nodesel)->nodeseldata = nodeseldata;
804  (*nodesel)->initialized = FALSE;
805  /* create clocks */
806  SCIP_CALL( SCIPclockCreate(&(*nodesel)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
807  SCIP_CALL( SCIPclockCreate(&(*nodesel)->nodeseltime, SCIP_CLOCKTYPE_DEFAULT) );
808 
809  /* add parameters */
810  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "nodeselection/%s/stdpriority", name);
811  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of node selection rule <%s> in standard mode", name);
812  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
813  &(*nodesel)->stdpriority, FALSE, stdpriority, INT_MIN/4, INT_MAX/2,
814  paramChgdNodeselStdPriority, (SCIP_PARAMDATA*)(*nodesel)) ); /*lint !e740*/
815 
816  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "nodeselection/%s/memsavepriority", name);
817  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of node selection rule <%s> in memory saving mode", name);
818  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
819  &(*nodesel)->memsavepriority, TRUE, memsavepriority, INT_MIN/4, INT_MAX/4,
820  paramChgdNodeselMemsavePriority, (SCIP_PARAMDATA*)(*nodesel)) ); /*lint !e740*/
821 
822  return SCIP_OKAY;
823 }
824 
825 /** creates a node selector */
827  SCIP_NODESEL** nodesel, /**< pointer to store node selector */
828  SCIP_SET* set, /**< global SCIP settings */
829  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
830  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
831  const char* name, /**< name of node selector */
832  const char* desc, /**< description of node selector */
833  int stdpriority, /**< priority of the node selector in standard mode */
834  int memsavepriority, /**< priority of the node selector in memory saving mode */
835  SCIP_DECL_NODESELCOPY ((*nodeselcopy)), /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
836  SCIP_DECL_NODESELFREE ((*nodeselfree)), /**< destructor of node selector */
837  SCIP_DECL_NODESELINIT ((*nodeselinit)), /**< initialize node selector */
838  SCIP_DECL_NODESELEXIT ((*nodeselexit)), /**< deinitialize node selector */
839  SCIP_DECL_NODESELINITSOL((*nodeselinitsol)),/**< solving process initialization method of node selector */
840  SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)),/**< solving process deinitialization method of node selector */
841  SCIP_DECL_NODESELSELECT((*nodeselselect)),/**< node selection method */
842  SCIP_DECL_NODESELCOMP ((*nodeselcomp)), /**< node comparison method */
843  SCIP_NODESELDATA* nodeseldata /**< node selector data */
844  )
845 {
846  assert(nodesel != NULL);
847  assert(name != NULL);
848  assert(desc != NULL);
849  assert(nodeselselect != NULL);
850  assert(nodeselcomp != NULL);
851 
852  SCIP_CALL_FINALLY( doNodeselCreate(nodesel, set, messagehdlr, blkmem, name, desc, stdpriority, memsavepriority,
853  nodeselcopy, nodeselfree, nodeselinit, nodeselexit, nodeselinitsol, nodeselexitsol, nodeselselect, nodeselcomp,
854  nodeseldata), (void) SCIPnodeselFree(nodesel, set) );
855 
856  return SCIP_OKAY;
857 }
858 
859 /** frees memory of node selector */
861  SCIP_NODESEL** nodesel, /**< pointer to node selector data structure */
862  SCIP_SET* set /**< global SCIP settings */
863  )
864 {
865  assert(nodesel != NULL);
866  if( *nodesel == NULL )
867  return SCIP_OKAY;
868  assert(!(*nodesel)->initialized);
869  assert(set != NULL);
870 
871  /* call destructor of node selector */
872  if( (*nodesel)->nodeselfree != NULL )
873  {
874  SCIP_CALL( (*nodesel)->nodeselfree(set->scip, *nodesel) );
875  }
876 
877  /* free clocks */
878  SCIPclockFree(&(*nodesel)->nodeseltime);
879  SCIPclockFree(&(*nodesel)->setuptime);
880 
881  BMSfreeMemoryArrayNull(&(*nodesel)->name);
882  BMSfreeMemoryArrayNull(&(*nodesel)->desc);
883  BMSfreeMemory(nodesel);
884 
885  return SCIP_OKAY;
886 }
887 
888 /** initializes node selector */
890  SCIP_NODESEL* nodesel, /**< node selector */
891  SCIP_SET* set /**< global SCIP settings */
892  )
893 {
894  assert(nodesel != NULL);
895  assert(set != NULL);
896 
897  if( nodesel->initialized )
898  {
899  SCIPerrorMessage("node selector <%s> already initialized", nodesel->name);
900  return SCIP_INVALIDCALL;
901  }
902 
903  if( set->misc_resetstat )
904  {
905  SCIPclockReset(nodesel->setuptime);
906  SCIPclockReset(nodesel->nodeseltime);
907  }
908 
909  if( nodesel->nodeselinit != NULL )
910  {
911  /* start timing */
912  SCIPclockStart(nodesel->setuptime, set);
913 
914  SCIP_CALL( nodesel->nodeselinit(set->scip, nodesel) );
915 
916  /* stop timing */
917  SCIPclockStop(nodesel->setuptime, set);
918  }
919  nodesel->initialized = TRUE;
920 
921  return SCIP_OKAY;
922 }
923 
924 /** deinitializes node selector */
926  SCIP_NODESEL* nodesel, /**< node selector */
927  SCIP_SET* set /**< global SCIP settings */
928  )
929 {
930  assert(nodesel != NULL);
931  assert(set != NULL);
932 
933  if( !nodesel->initialized )
934  {
935  SCIPerrorMessage("node selector <%s> not initialized", nodesel->name);
936  return SCIP_INVALIDCALL;
937  }
938 
939  if( nodesel->nodeselexit != NULL )
940  {
941  /* start timing */
942  SCIPclockStart(nodesel->setuptime, set);
943 
944  SCIP_CALL( nodesel->nodeselexit(set->scip, nodesel) );
945 
946  /* stop timing */
947  SCIPclockStop(nodesel->setuptime, set);
948  }
949  nodesel->initialized = FALSE;
950 
951  return SCIP_OKAY;
952 }
953 
954 /** informs node selector that the branch and bound process is being started */
956  SCIP_NODESEL* nodesel, /**< node selector */
957  SCIP_SET* set /**< global SCIP settings */
958  )
959 {
960  assert(nodesel != NULL);
961  assert(set != NULL);
962 
963  /* call solving process initialization method of node selector */
964  if( nodesel->nodeselinitsol != NULL )
965  {
966  /* start timing */
967  SCIPclockStart(nodesel->setuptime, set);
968 
969  SCIP_CALL( nodesel->nodeselinitsol(set->scip, nodesel) );
970 
971  /* stop timing */
972  SCIPclockStop(nodesel->setuptime, set);
973  }
974 
975  return SCIP_OKAY;
976 }
977 
978 /** informs node selector that the branch and bound process data is being freed */
980  SCIP_NODESEL* nodesel, /**< node selector */
981  SCIP_SET* set /**< global SCIP settings */
982  )
983 {
984  assert(nodesel != NULL);
985  assert(set != NULL);
986 
987  /* call solving process deinitialization method of node selector */
988  if( nodesel->nodeselexitsol != NULL )
989  {
990  /* start timing */
991  SCIPclockStart(nodesel->setuptime, set);
992 
993  SCIP_CALL( nodesel->nodeselexitsol(set->scip, nodesel) );
994 
995  /* stop timing */
996  SCIPclockStop(nodesel->setuptime, set);
997  }
998 
999  return SCIP_OKAY;
1000 }
1001 
1002 /** select next node to be processed */
1004  SCIP_NODESEL* nodesel, /**< node selector */
1005  SCIP_SET* set, /**< global SCIP settings */
1006  SCIP_NODE** selnode /**< pointer to store node to be processed next */
1007  )
1008 {
1009  assert(nodesel != NULL);
1010  assert(nodesel->nodeselselect != NULL);
1011  assert(set != NULL);
1012  assert(selnode != NULL);
1013 
1014  /* start timing */
1015  SCIPclockStart(nodesel->nodeseltime, set);
1016 
1017  SCIP_CALL( nodesel->nodeselselect(set->scip, nodesel, selnode) );
1018 
1019  /* stop timing */
1020  SCIPclockStop(nodesel->nodeseltime, set);
1021 
1022  return SCIP_OKAY;
1023 }
1024 
1025 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */
1027  SCIP_NODESEL* nodesel, /**< node selector */
1028  SCIP_SET* set, /**< global SCIP settings */
1029  SCIP_NODE* node1, /**< first node to compare */
1030  SCIP_NODE* node2 /**< second node to compare */
1031  )
1032 {
1033  assert(nodesel != NULL);
1034  assert(nodesel->nodeselcomp != NULL);
1035  assert(set != NULL);
1036  assert(node1 != NULL);
1037  assert(node2 != NULL);
1038 
1039  return nodesel->nodeselcomp(set->scip, nodesel, node1, node2);
1040 }
1041 
1042 /** gets name of node selector */
1044  SCIP_NODESEL* nodesel /**< node selector */
1045  )
1046 {
1047  assert(nodesel != NULL);
1048 
1049  return nodesel->name;
1050 }
1051 
1052 /** gets description of node selector */
1054  SCIP_NODESEL* nodesel /**< node selector */
1055  )
1056 {
1057  assert(nodesel != NULL);
1058 
1059  return nodesel->desc;
1060 }
1061 
1062 /** gets priority of node selector in standard mode */
1064  SCIP_NODESEL* nodesel /**< node selector */
1065  )
1066 {
1067  assert(nodesel != NULL);
1068 
1069  return nodesel->stdpriority;
1070 }
1071 
1072 /** gets priority of node selector in standard mode */
1074  SCIP_NODESEL* nodesel, /**< node selector */
1075  SCIP_SET* set, /**< global SCIP settings */
1076  int priority /**< new priority of the node selector */
1077  )
1078 {
1079  assert(nodesel != NULL);
1080  assert(set != NULL);
1081 
1082  nodesel->stdpriority = priority;
1083  set->nodesel = NULL;
1084 }
1085 
1086 /** gets priority of node selector in memory saving mode */
1088  SCIP_NODESEL* nodesel /**< node selector */
1089  )
1090 {
1091  assert(nodesel != NULL);
1092 
1093  return nodesel->memsavepriority;
1094 }
1095 
1096 /** sets priority of node selector in memory saving mode */
1098  SCIP_NODESEL* nodesel, /**< node selector */
1099  SCIP_SET* set, /**< global SCIP settings */
1100  int priority /**< new priority of the node selector */
1101  )
1102 {
1103  assert(nodesel != NULL);
1104  assert(set != NULL);
1105 
1106  nodesel->memsavepriority = priority;
1107  set->nodesel = NULL;
1108 }
1109 
1110 /** gets user data of node selector */
1112  SCIP_NODESEL* nodesel /**< node selector */
1113  )
1114 {
1115  assert(nodesel != NULL);
1116 
1117  return nodesel->nodeseldata;
1118 }
1119 
1120 /** sets user data of node selector; user has to free old data in advance! */
1122  SCIP_NODESEL* nodesel, /**< node selector */
1123  SCIP_NODESELDATA* nodeseldata /**< new node selector user data */
1124  )
1125 {
1126  assert(nodesel != NULL);
1127 
1128  nodesel->nodeseldata = nodeseldata;
1129 }
1130 
1131 /* new callback/method setter methods */
1132 
1133 /** sets copy method of node selector */
1135  SCIP_NODESEL* nodesel, /**< node selector */
1136  SCIP_DECL_NODESELCOPY ((*nodeselcopy)) /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
1137  )
1138 {
1139  assert(nodesel != NULL);
1140 
1141  nodesel->nodeselcopy = nodeselcopy;
1142 }
1143 
1144 /** sets destructor method of node selector */
1146  SCIP_NODESEL* nodesel, /**< node selector */
1147  SCIP_DECL_NODESELFREE ((*nodeselfree)) /**< destructor of node selector */
1148  )
1149 {
1150  assert(nodesel != NULL);
1151 
1152  nodesel->nodeselfree = nodeselfree;
1153 }
1154 
1155 /** sets initialization method of node selector */
1157  SCIP_NODESEL* nodesel, /**< node selector */
1158  SCIP_DECL_NODESELINIT ((*nodeselinit)) /**< initialize node selector */
1159  )
1160 {
1161  assert(nodesel != NULL);
1162 
1163  nodesel->nodeselinit = nodeselinit;
1164 }
1165 
1166 /** sets deinitialization method of node selector */
1168  SCIP_NODESEL* nodesel, /**< node selector */
1169  SCIP_DECL_NODESELEXIT ((*nodeselexit)) /**< deinitialize node selector */
1170  )
1171 {
1172  assert(nodesel != NULL);
1173 
1174  nodesel->nodeselexit = nodeselexit;
1175 }
1176 
1177 /** sets solving process initialization method of node selector */
1179  SCIP_NODESEL* nodesel, /**< node selector */
1180  SCIP_DECL_NODESELINITSOL ((*nodeselinitsol))/**< solving process initialization method of node selector */
1181  )
1182 {
1183  assert(nodesel != NULL);
1184 
1185  nodesel->nodeselinitsol = nodeselinitsol;
1186 }
1187 
1188 /** sets solving process deinitialization method of node selector */
1190  SCIP_NODESEL* nodesel, /**< node selector */
1191  SCIP_DECL_NODESELEXITSOL ((*nodeselexitsol))/**< solving process deinitialization method of node selector */
1192  )
1193 {
1194  assert(nodesel != NULL);
1195 
1196  nodesel->nodeselexitsol = nodeselexitsol;
1197 }
1198 
1199 /** is node selector initialized? */
1201  SCIP_NODESEL* nodesel /**< node selector */
1202  )
1203 {
1204  assert(nodesel != NULL);
1205 
1206  return nodesel->initialized;
1207 }
1208 
1209 /** enables or disables all clocks of \p nodesel, depending on the value of the flag */
1211  SCIP_NODESEL* nodesel, /**< the node selector for which all clocks should be enabled or disabled */
1212  SCIP_Bool enable /**< should the clocks of the node selector be enabled? */
1213  )
1214 {
1215  assert(nodesel != NULL);
1216 
1217  SCIPclockEnableOrDisable(nodesel->setuptime, enable);
1218  SCIPclockEnableOrDisable(nodesel->nodeseltime, enable);
1219 }
1220 
1221 /** gets time in seconds used in this node selector for setting up for next stages */
1223  SCIP_NODESEL* nodesel /**< node selector */
1224  )
1225 {
1226  assert(nodesel != NULL);
1227 
1228  return SCIPclockGetTime(nodesel->setuptime);
1229 }
1230 
1231 /** gets time in seconds used in this node selector */
1233  SCIP_NODESEL* nodesel /**< node selector */
1234  )
1235 {
1236  assert(nodesel != NULL);
1237 
1238  return SCIPclockGetTime(nodesel->nodeseltime);
1239 }
void SCIPnodeselSetFree(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: nodesel.c:1145
void SCIPnodepqDestroy(SCIP_NODEPQ **nodepq)
Definition: nodesel.c:118
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:552
#define SCIP_DECL_NODESELCOMP(x)
Definition: type_nodesel.h:131
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6200
int SCIPnodeselGetMemsavePriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1087
void SCIPnodeselEnableOrDisableClocks(SCIP_NODESEL *nodesel, SCIP_Bool enable)
Definition: nodesel.c:1210
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:141
internal methods for branch and bound tree
void SCIPnodeselSetInit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINIT((*nodeselinit)))
Definition: nodesel.c:1156
SCIP_RETCODE SCIPnodeselExitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:979
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7452
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:670
int SCIPnodepqCompare(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:255
#define SCIP_MAXSTRLEN
Definition: def.h:293
internal methods for clocks and timing issues
SCIP_Real lowerboundsum
SCIP_RETCODE SCIPnodeFree(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: tree.c:1046
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:78
#define SCIP_DECL_NODESELINITSOL(x)
Definition: type_nodesel.h:88
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:426
static SCIP_DECL_PARAMCHGD(paramChgdNodeselStdPriority)
Definition: nodesel.c:711
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6065
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:562
static SCIP_DECL_SORTPTRCOMP(nodeCompNumber)
Definition: nodesel.c:56
const char * SCIPnodeselGetDesc(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1053
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:351
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPsetNodeselMemsavePriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:275
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:281
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
SCIP_NODE * SCIPnodepqGetLowerboundNode(SCIP_NODEPQ *nodepq, SCIP_SET *set)
Definition: nodesel.c:596
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Real SCIPnodepqGetLowerboundSum(SCIP_NODEPQ *nodepq)
Definition: nodesel.c:620
SCIP_RETCODE SCIPnodeselInitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:955
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8300
internal methods for handling parameter settings
SCIP_Bool initialized
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7442
methods for creating output for visualization tools (VBC, BAK)
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:251
#define BMSfreeMemory(ptr)
Definition: memory.h:138
SCIP_NODESEL * SCIPnodepqGetNodesel(SCIP_NODEPQ *nodepq)
Definition: nodesel.c:197
static int nodepqFindNode(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:491
static SCIP_RETCODE nodepqResize(SCIP_NODEPQ *nodepq, SCIP_SET *set, int minsize)
Definition: nodesel.c:76
#define SCIP_DECL_NODESELEXITSOL(x)
Definition: type_nodesel.h:99
SCIP_CLOCK * setuptime
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13081
SCIP_VISUAL * visual
Definition: struct_stat.h:175
internal methods for LP management
Definition: heur_padm.c:123
SCIP_RETCODE SCIPnodeselExit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:925
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
Definition: nodesel.c:1003
#define SCIP_DECL_NODESELINIT(x)
Definition: type_nodesel.h:69
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6294
SCIP_RETCODE SCIPnodeselCopyInclude(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:740
SCIP_RETCODE SCIPnodepqInsert(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:271
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:43
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6240
#define PQ_LEFTCHILD(p)
Definition: nodesel.c:50
SCIP_RETCODE SCIPnodepqBound(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: nodesel.c:630
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_NODE ** slots
SCIP_CLOCK * nodeseltime
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:200
SCIP_RETCODE SCIPnodepqSetNodesel(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: nodesel.c:207
SCIP_RETCODE SCIPnodepqFree(SCIP_NODEPQ **nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: nodesel.c:132
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:429
#define SCIP_DECL_NODESELFREE(x)
Definition: type_nodesel.h:61
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPnodeselFree(SCIP_NODESEL **nodesel, SCIP_SET *set)
Definition: nodesel.c:860
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1111
static SCIP_RETCODE doNodeselCreate(SCIP_NODESEL **nodesel, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELCOPY((*nodeselcopy)), SCIP_DECL_NODESELFREE((*nodeselfree)), SCIP_DECL_NODESELINIT((*nodeselinit)), SCIP_DECL_NODESELEXIT((*nodeselexit)), SCIP_DECL_NODESELINITSOL((*nodeselinitsol)), SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)), SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:759
internal methods for node selectors and node priority queues
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
SCIP main data structure.
SCIP_Real SCIPnodeselGetTime(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1232
int SCIPnodeselCompare(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:1026
int SCIPsetCalcTreeGrowSize(SCIP_SET *set, int num)
Definition: set.c:5788
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, 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: set.c:3014
SCIP_RETCODE SCIPnodeselInit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:889
void SCIPnodeselSetInitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: nodesel.c:1178
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:136
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:161
data structures and methods for collecting reoptimization information
public data structures and miscellaneous methods
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8431
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPnodeselCreate(SCIP_NODESEL **nodesel, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELCOPY((*nodeselcopy)), SCIP_DECL_NODESELFREE((*nodeselfree)), SCIP_DECL_NODESELINIT((*nodeselinit)), SCIP_DECL_NODESELEXIT((*nodeselexit)), SCIP_DECL_NODESELINITSOL((*nodeselinitsol)), SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)), SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:826
#define SCIP_DECL_NODESELEXIT(x)
Definition: type_nodesel.h:77
SCIP_RETCODE SCIPreoptCheckCutoff(SCIP_REOPT *reopt, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_NODE *node, SCIP_EVENTTYPE eventtype, SCIP_LP *lp, SCIP_LPSOLSTAT lpsolstat, SCIP_Bool isrootnode, SCIP_Bool isfocusnode, SCIP_Real lowerbound, int effectiverootdepth)
Definition: reopt.c:6024
static const char * paramname[]
Definition: lpi_msk.c:4998
SCIP_RETCODE SCIPnodepqRemove(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:515
void SCIPnodeselSetMemsavePriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1097
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:176
SCIP_RETCODE SCIPnodepqCreate(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: nodesel.c:96
#define SCIPsetDebugMsg
Definition: set.h:1755
void SCIPnodeselSetExit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXIT((*nodeselexit)))
Definition: nodesel.c:1167
#define SCIP_EVENTTYPE_NODEINFEASIBLE
Definition: type_event.h:85
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1043
SCIP_NODE * SCIPnodepqFirst(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:536
static long * number
#define BMSclearMemory(ptr)
Definition: memory.h:122
SCIP_NODESELDATA * nodeseldata
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:725
SCIP_Real SCIPnodeselGetSetupTime(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1222
void SCIPnodeselSetStdPriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1073
SCIP_Real SCIPnodepqGetLowerbound(SCIP_NODEPQ *nodepq, SCIP_SET *set)
Definition: nodesel.c:573
static SCIP_Bool nodepqDelPos(SCIP_NODEPQ *nodepq, SCIP_SET *set, int rempos)
Definition: nodesel.c:333
#define PQ_PARENT(q)
Definition: nodesel.c:49
public methods for message output
data structures for node selectors and node priority queues
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7422
#define SCIP_Real
Definition: def.h:177
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
Definition: visual.c:524
internal methods for problem statistics
#define SCIP_DECL_NODESELCOPY(x)
Definition: type_nodesel.h:52
#define PQ_RIGHTCHILD(p)
Definition: nodesel.c:51
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:120
void SCIPnodeselSetCopy(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: nodesel.c:1134
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
SCIP_NODESEL * nodesel
#define SCIP_ALLOC(x)
Definition: def.h:395
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1063
#define SCIP_DECL_NODESELSELECT(x)
Definition: type_nodesel.h:114
void SCIPnodeselSetExitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: nodesel.c:1189
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1121
SCIP_Bool SCIPnodeselIsInitialized(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1200
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:260
SCIP callable library.
SCIP_RETCODE SCIPnodepqClear(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: nodesel.c:156