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