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