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-2019 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 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 /** internal method for creating a node selector */
753 static
755  SCIP_NODESEL** nodesel, /**< pointer to store node selector */
756  SCIP_SET* set, /**< global SCIP settings */
757  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
758  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
759  const char* name, /**< name of node selector */
760  const char* desc, /**< description of node selector */
761  int stdpriority, /**< priority of the node selector in standard mode */
762  int memsavepriority, /**< priority of the node selector in memory saving mode */
763  SCIP_DECL_NODESELCOPY ((*nodeselcopy)), /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
764  SCIP_DECL_NODESELFREE ((*nodeselfree)), /**< destructor of node selector */
765  SCIP_DECL_NODESELINIT ((*nodeselinit)), /**< initialize node selector */
766  SCIP_DECL_NODESELEXIT ((*nodeselexit)), /**< deinitialize node selector */
767  SCIP_DECL_NODESELINITSOL((*nodeselinitsol)),/**< solving process initialization method of node selector */
768  SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)),/**< solving process deinitialization method of node selector */
769  SCIP_DECL_NODESELSELECT((*nodeselselect)),/**< node selection method */
770  SCIP_DECL_NODESELCOMP ((*nodeselcomp)), /**< node comparison method */
771  SCIP_NODESELDATA* nodeseldata /**< node selector data */
772  )
773 {
774  char paramname[SCIP_MAXSTRLEN];
775  char paramdesc[SCIP_MAXSTRLEN];
776 
777  assert(nodesel != NULL);
778  assert(name != NULL);
779  assert(desc != NULL);
780  assert(nodeselselect != NULL);
781  assert(nodeselcomp != NULL);
782 
783  SCIP_ALLOC( BMSallocMemory(nodesel) );
784  BMSclearMemory(*nodesel);
785 
786  SCIP_ALLOC( BMSduplicateMemoryArray(&(*nodesel)->name, name, strlen(name)+1) );
787  SCIP_ALLOC( BMSduplicateMemoryArray(&(*nodesel)->desc, desc, strlen(desc)+1) );
788  (*nodesel)->stdpriority = stdpriority;
789  (*nodesel)->memsavepriority = memsavepriority;
790  (*nodesel)->nodeselcopy = nodeselcopy;
791  (*nodesel)->nodeselfree = nodeselfree;
792  (*nodesel)->nodeselinit = nodeselinit;
793  (*nodesel)->nodeselexit = nodeselexit;
794  (*nodesel)->nodeselinitsol = nodeselinitsol;
795  (*nodesel)->nodeselexitsol = nodeselexitsol;
796  (*nodesel)->nodeselselect = nodeselselect;
797  (*nodesel)->nodeselcomp = nodeselcomp;
798  (*nodesel)->nodeseldata = nodeseldata;
799  (*nodesel)->initialized = FALSE;
800  /* create clocks */
801  SCIP_CALL( SCIPclockCreate(&(*nodesel)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
802  SCIP_CALL( SCIPclockCreate(&(*nodesel)->nodeseltime, SCIP_CLOCKTYPE_DEFAULT) );
803 
804  /* add parameters */
805  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "nodeselection/%s/stdpriority", name);
806  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of node selection rule <%s> in standard mode", name);
807  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
808  &(*nodesel)->stdpriority, FALSE, stdpriority, INT_MIN/4, INT_MAX/2,
809  paramChgdNodeselStdPriority, (SCIP_PARAMDATA*)(*nodesel)) ); /*lint !e740*/
810 
811  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "nodeselection/%s/memsavepriority", name);
812  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of node selection rule <%s> in memory saving mode", name);
813  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
814  &(*nodesel)->memsavepriority, TRUE, memsavepriority, INT_MIN/4, INT_MAX/4,
815  paramChgdNodeselMemsavePriority, (SCIP_PARAMDATA*)(*nodesel)) ); /*lint !e740*/
816 
817  return SCIP_OKAY;
818 }
819 
820 /** creates a node selector */
822  SCIP_NODESEL** nodesel, /**< pointer to store node selector */
823  SCIP_SET* set, /**< global SCIP settings */
824  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
825  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
826  const char* name, /**< name of node selector */
827  const char* desc, /**< description of node selector */
828  int stdpriority, /**< priority of the node selector in standard mode */
829  int memsavepriority, /**< priority of the node selector in memory saving mode */
830  SCIP_DECL_NODESELCOPY ((*nodeselcopy)), /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
831  SCIP_DECL_NODESELFREE ((*nodeselfree)), /**< destructor of node selector */
832  SCIP_DECL_NODESELINIT ((*nodeselinit)), /**< initialize node selector */
833  SCIP_DECL_NODESELEXIT ((*nodeselexit)), /**< deinitialize node selector */
834  SCIP_DECL_NODESELINITSOL((*nodeselinitsol)),/**< solving process initialization method of node selector */
835  SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)),/**< solving process deinitialization method of node selector */
836  SCIP_DECL_NODESELSELECT((*nodeselselect)),/**< node selection method */
837  SCIP_DECL_NODESELCOMP ((*nodeselcomp)), /**< node comparison method */
838  SCIP_NODESELDATA* nodeseldata /**< node selector data */
839  )
840 {
841  assert(nodesel != NULL);
842  assert(name != NULL);
843  assert(desc != NULL);
844  assert(nodeselselect != NULL);
845  assert(nodeselcomp != NULL);
846 
847  SCIP_CALL_FINALLY( doNodeselCreate(nodesel, set, messagehdlr, blkmem, name, desc, stdpriority, memsavepriority,
848  nodeselcopy, nodeselfree, nodeselinit, nodeselexit, nodeselinitsol, nodeselexitsol, nodeselselect, nodeselcomp,
849  nodeseldata), (void) SCIPnodeselFree(nodesel, set) );
850 
851  return SCIP_OKAY;
852 }
853 
854 /** frees memory of node selector */
856  SCIP_NODESEL** nodesel, /**< pointer to node selector data structure */
857  SCIP_SET* set /**< global SCIP settings */
858  )
859 {
860  assert(nodesel != NULL);
861  if( *nodesel == NULL )
862  return SCIP_OKAY;
863  assert(!(*nodesel)->initialized);
864  assert(set != NULL);
865 
866  /* call destructor of node selector */
867  if( (*nodesel)->nodeselfree != NULL )
868  {
869  SCIP_CALL( (*nodesel)->nodeselfree(set->scip, *nodesel) );
870  }
871 
872  /* free clocks */
873  SCIPclockFree(&(*nodesel)->nodeseltime);
874  SCIPclockFree(&(*nodesel)->setuptime);
875 
876  BMSfreeMemoryArrayNull(&(*nodesel)->name);
877  BMSfreeMemoryArrayNull(&(*nodesel)->desc);
878  BMSfreeMemory(nodesel);
879 
880  return SCIP_OKAY;
881 }
882 
883 /** initializes node selector */
885  SCIP_NODESEL* nodesel, /**< node selector */
886  SCIP_SET* set /**< global SCIP settings */
887  )
888 {
889  assert(nodesel != NULL);
890  assert(set != NULL);
891 
892  if( nodesel->initialized )
893  {
894  SCIPerrorMessage("node selector <%s> already initialized", nodesel->name);
895  return SCIP_INVALIDCALL;
896  }
897 
898  if( set->misc_resetstat )
899  {
900  SCIPclockReset(nodesel->setuptime);
901  SCIPclockReset(nodesel->nodeseltime);
902  }
903 
904  if( nodesel->nodeselinit != NULL )
905  {
906  /* start timing */
907  SCIPclockStart(nodesel->setuptime, set);
908 
909  SCIP_CALL( nodesel->nodeselinit(set->scip, nodesel) );
910 
911  /* stop timing */
912  SCIPclockStop(nodesel->setuptime, set);
913  }
914  nodesel->initialized = TRUE;
915 
916  return SCIP_OKAY;
917 }
918 
919 /** deinitializes node selector */
921  SCIP_NODESEL* nodesel, /**< node selector */
922  SCIP_SET* set /**< global SCIP settings */
923  )
924 {
925  assert(nodesel != NULL);
926  assert(set != NULL);
927 
928  if( !nodesel->initialized )
929  {
930  SCIPerrorMessage("node selector <%s> not initialized", nodesel->name);
931  return SCIP_INVALIDCALL;
932  }
933 
934  if( nodesel->nodeselexit != NULL )
935  {
936  /* start timing */
937  SCIPclockStart(nodesel->setuptime, set);
938 
939  SCIP_CALL( nodesel->nodeselexit(set->scip, nodesel) );
940 
941  /* stop timing */
942  SCIPclockStop(nodesel->setuptime, set);
943  }
944  nodesel->initialized = FALSE;
945 
946  return SCIP_OKAY;
947 }
948 
949 /** informs node selector that the branch and bound process is being started */
951  SCIP_NODESEL* nodesel, /**< node selector */
952  SCIP_SET* set /**< global SCIP settings */
953  )
954 {
955  assert(nodesel != NULL);
956  assert(set != NULL);
957 
958  /* call solving process initialization method of node selector */
959  if( nodesel->nodeselinitsol != NULL )
960  {
961  /* start timing */
962  SCIPclockStart(nodesel->setuptime, set);
963 
964  SCIP_CALL( nodesel->nodeselinitsol(set->scip, nodesel) );
965 
966  /* stop timing */
967  SCIPclockStop(nodesel->setuptime, set);
968  }
969 
970  return SCIP_OKAY;
971 }
972 
973 /** informs node selector that the branch and bound process data is being freed */
975  SCIP_NODESEL* nodesel, /**< node selector */
976  SCIP_SET* set /**< global SCIP settings */
977  )
978 {
979  assert(nodesel != NULL);
980  assert(set != NULL);
981 
982  /* call solving process deinitialization method of node selector */
983  if( nodesel->nodeselexitsol != NULL )
984  {
985  /* start timing */
986  SCIPclockStart(nodesel->setuptime, set);
987 
988  SCIP_CALL( nodesel->nodeselexitsol(set->scip, nodesel) );
989 
990  /* stop timing */
991  SCIPclockStop(nodesel->setuptime, set);
992  }
993 
994  return SCIP_OKAY;
995 }
996 
997 /** select next node to be processed */
999  SCIP_NODESEL* nodesel, /**< node selector */
1000  SCIP_SET* set, /**< global SCIP settings */
1001  SCIP_NODE** selnode /**< pointer to store node to be processed next */
1002  )
1003 {
1004  assert(nodesel != NULL);
1005  assert(nodesel->nodeselselect != NULL);
1006  assert(set != NULL);
1007  assert(selnode != NULL);
1008 
1009  /* start timing */
1010  SCIPclockStart(nodesel->nodeseltime, set);
1011 
1012  SCIP_CALL( nodesel->nodeselselect(set->scip, nodesel, selnode) );
1013 
1014  /* stop timing */
1015  SCIPclockStop(nodesel->nodeseltime, set);
1016 
1017  return SCIP_OKAY;
1018 }
1019 
1020 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */
1022  SCIP_NODESEL* nodesel, /**< node selector */
1023  SCIP_SET* set, /**< global SCIP settings */
1024  SCIP_NODE* node1, /**< first node to compare */
1025  SCIP_NODE* node2 /**< second node to compare */
1026  )
1027 {
1028  assert(nodesel != NULL);
1029  assert(nodesel->nodeselcomp != NULL);
1030  assert(set != NULL);
1031  assert(node1 != NULL);
1032  assert(node2 != NULL);
1033 
1034  return nodesel->nodeselcomp(set->scip, nodesel, node1, node2);
1035 }
1036 
1037 /** gets name of node selector */
1039  SCIP_NODESEL* nodesel /**< node selector */
1040  )
1041 {
1042  assert(nodesel != NULL);
1043 
1044  return nodesel->name;
1045 }
1046 
1047 /** gets description of node selector */
1049  SCIP_NODESEL* nodesel /**< node selector */
1050  )
1051 {
1052  assert(nodesel != NULL);
1053 
1054  return nodesel->desc;
1055 }
1056 
1057 /** gets priority of node selector in standard mode */
1059  SCIP_NODESEL* nodesel /**< node selector */
1060  )
1061 {
1062  assert(nodesel != NULL);
1063 
1064  return nodesel->stdpriority;
1065 }
1066 
1067 /** gets priority of node selector in standard mode */
1069  SCIP_NODESEL* nodesel, /**< node selector */
1070  SCIP_SET* set, /**< global SCIP settings */
1071  int priority /**< new priority of the node selector */
1072  )
1073 {
1074  assert(nodesel != NULL);
1075  assert(set != NULL);
1076 
1077  nodesel->stdpriority = priority;
1078  set->nodesel = NULL;
1079 }
1080 
1081 /** gets priority of node selector in memory saving mode */
1083  SCIP_NODESEL* nodesel /**< node selector */
1084  )
1085 {
1086  assert(nodesel != NULL);
1087 
1088  return nodesel->memsavepriority;
1089 }
1090 
1091 /** sets priority of node selector in memory saving mode */
1093  SCIP_NODESEL* nodesel, /**< node selector */
1094  SCIP_SET* set, /**< global SCIP settings */
1095  int priority /**< new priority of the node selector */
1096  )
1097 {
1098  assert(nodesel != NULL);
1099  assert(set != NULL);
1100 
1101  nodesel->memsavepriority = priority;
1102  set->nodesel = NULL;
1103 }
1104 
1105 /** gets user data of node selector */
1107  SCIP_NODESEL* nodesel /**< node selector */
1108  )
1109 {
1110  assert(nodesel != NULL);
1111 
1112  return nodesel->nodeseldata;
1113 }
1114 
1115 /** sets user data of node selector; user has to free old data in advance! */
1117  SCIP_NODESEL* nodesel, /**< node selector */
1118  SCIP_NODESELDATA* nodeseldata /**< new node selector user data */
1119  )
1120 {
1121  assert(nodesel != NULL);
1122 
1123  nodesel->nodeseldata = nodeseldata;
1124 }
1125 
1126 /* new callback/method setter methods */
1127 
1128 /** sets copy method of node selector */
1130  SCIP_NODESEL* nodesel, /**< node selector */
1131  SCIP_DECL_NODESELCOPY ((*nodeselcopy)) /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
1132  )
1133 {
1134  assert(nodesel != NULL);
1135 
1136  nodesel->nodeselcopy = nodeselcopy;
1137 }
1138 
1139 /** sets destructor method of node selector */
1141  SCIP_NODESEL* nodesel, /**< node selector */
1142  SCIP_DECL_NODESELFREE ((*nodeselfree)) /**< destructor of node selector */
1143  )
1144 {
1145  assert(nodesel != NULL);
1146 
1147  nodesel->nodeselfree = nodeselfree;
1148 }
1149 
1150 /** sets initialization method of node selector */
1152  SCIP_NODESEL* nodesel, /**< node selector */
1153  SCIP_DECL_NODESELINIT ((*nodeselinit)) /**< initialize node selector */
1154  )
1155 {
1156  assert(nodesel != NULL);
1157 
1158  nodesel->nodeselinit = nodeselinit;
1159 }
1160 
1161 /** sets deinitialization method of node selector */
1163  SCIP_NODESEL* nodesel, /**< node selector */
1164  SCIP_DECL_NODESELEXIT ((*nodeselexit)) /**< deinitialize node selector */
1165  )
1166 {
1167  assert(nodesel != NULL);
1168 
1169  nodesel->nodeselexit = nodeselexit;
1170 }
1171 
1172 /** sets solving process initialization method of node selector */
1174  SCIP_NODESEL* nodesel, /**< node selector */
1175  SCIP_DECL_NODESELINITSOL ((*nodeselinitsol))/**< solving process initialization method of node selector */
1176  )
1177 {
1178  assert(nodesel != NULL);
1179 
1180  nodesel->nodeselinitsol = nodeselinitsol;
1181 }
1182 
1183 /** sets solving process deinitialization method of node selector */
1185  SCIP_NODESEL* nodesel, /**< node selector */
1186  SCIP_DECL_NODESELEXITSOL ((*nodeselexitsol))/**< solving process deinitialization method of node selector */
1187  )
1188 {
1189  assert(nodesel != NULL);
1190 
1191  nodesel->nodeselexitsol = nodeselexitsol;
1192 }
1193 
1194 /** is node selector initialized? */
1196  SCIP_NODESEL* nodesel /**< node selector */
1197  )
1198 {
1199  assert(nodesel != NULL);
1200 
1201  return nodesel->initialized;
1202 }
1203 
1204 /** enables or disables all clocks of \p nodesel, depending on the value of the flag */
1206  SCIP_NODESEL* nodesel, /**< the node selector for which all clocks should be enabled or disabled */
1207  SCIP_Bool enable /**< should the clocks of the node selector be enabled? */
1208  )
1209 {
1210  assert(nodesel != NULL);
1211 
1212  SCIPclockEnableOrDisable(nodesel->setuptime, enable);
1213  SCIPclockEnableOrDisable(nodesel->nodeseltime, enable);
1214 }
1215 
1216 /** gets time in seconds used in this node selector for setting up for next stages */
1218  SCIP_NODESEL* nodesel /**< node selector */
1219  )
1220 {
1221  assert(nodesel != NULL);
1222 
1223  return SCIPclockGetTime(nodesel->setuptime);
1224 }
1225 
1226 /** gets time in seconds used in this node selector */
1228  SCIP_NODESEL* nodesel /**< node selector */
1229  )
1230 {
1231  assert(nodesel != NULL);
1232 
1233  return SCIPclockGetTime(nodesel->nodeseltime);
1234 }
void SCIPnodeselSetFree(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: nodesel.c:1140
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
#define NULL
Definition: def.h:253
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
SCIP_RETCODE SCIPsetNodeselMemsavePriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:274
void SCIPnodeselEnableOrDisableClocks(SCIP_NODESEL *nodesel, SCIP_Bool enable)
Definition: nodesel.c:1205
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:138
internal methods for branch and bound tree
void SCIPnodeselSetInit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINIT((*nodeselinit)))
Definition: nodesel.c:1151
SCIP_RETCODE SCIPnodeselExitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:974
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:274
internal methods for clocks and timing issues
SCIP_Real lowerboundsum
const char * SCIPnodeselGetDesc(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1048
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:76
#define SCIP_DECL_NODESELINITSOL(x)
Definition: type_nodesel.h:83
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:407
static SCIP_DECL_PARAMCHGD(paramChgdNodeselStdPriority)
Definition: nodesel.c:706
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:5813
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:558
static SCIP_DECL_SORTPTRCOMP(nodeCompNumber)
Definition: nodesel.c:55
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:350
#define FALSE
Definition: def.h:73
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:280
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7357
#define TRUE
Definition: def.h:72
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:950
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8215
internal methods for handling parameter settings
SCIP_Bool initialized
methods for creating output for visualization tools (VBC, BAK)
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:250
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7367
#define BMSfreeMemory(ptr)
Definition: memory.h:135
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:12902
SCIP_VISUAL * visual
Definition: struct_stat.h:168
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
Definition: scip_nodesel.c:259
internal methods for LP management
SCIP_RETCODE SCIPnodeselExit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:920
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
Definition: nodesel.c:998
#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:6047
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:5993
#define PQ_LEFTCHILD(p)
Definition: nodesel.c:49
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_NODE ** slots
SCIP_CLOCK * nodeseltime
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_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1106
SCIP_EXPORT void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
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:855
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:754
internal methods for node selectors and node priority queues
SCIP_Bool SCIPnodeselIsInitialized(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1195
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:365
SCIP main data structure.
int SCIPnodeselCompare(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:1021
int SCIPsetCalcTreeGrowSize(SCIP_SET *set, int num)
Definition: set.c:5512
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:2879
SCIP_RETCODE SCIPnodeselInit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:884
void SCIPnodeselSetInitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: nodesel.c:1173
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:133
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
SCIP_Real SCIPnodeselGetTime(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1227
public data structures and miscellaneous methods
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8346
#define SCIP_Bool
Definition: def.h:70
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:821
#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:5973
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:1092
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:1720
void SCIPnodeselSetExit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXIT((*nodeselexit)))
Definition: nodesel.c:1162
#define SCIP_EVENTTYPE_NODEINFEASIBLE
Definition: type_event.h:79
SCIP_NODE * SCIPnodepqFirst(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:532
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1116
static long * number
#define BMSclearMemory(ptr)
Definition: memory.h:119
SCIP_NODESELDATA * nodeseldata
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:716
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1038
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1058
void SCIPnodeselSetStdPriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1068
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
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10263
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
#define SCIP_Real
Definition: def.h:164
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
Definition: visual.c:523
internal methods for problem statistics
#define SCIP_DECL_NODESELCOPY(x)
Definition: type_nodesel.h:47
#define PQ_RIGHTCHILD(p)
Definition: nodesel.c:50
SCIP_Real SCIPnodeselGetSetupTime(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1217
#define BMSallocMemory(ptr)
Definition: memory.h:109
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:117
void SCIPnodeselSetCopy(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: nodesel.c:1129
SCIP_EXPORT SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7337
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:427
SCIP_NODESEL * nodesel
#define SCIP_ALLOC(x)
Definition: def.h:376
#define SCIP_DECL_NODESELSELECT(x)
Definition: type_nodesel.h:109
void SCIPnodeselSetExitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: nodesel.c:1184
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 callable library.
int SCIPnodeselGetMemsavePriority(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1082