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