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