SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
scip_tree.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-2023 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 scip_tree.c
26 * @ingroup OTHER_CFILES
27 * @brief public methods for the branch-and-bound tree
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Gerald Gamrath
31 * @author Leona Gottwald
32 * @author Stefan Heinz
33 * @author Gregor Hendel
34 * @author Thorsten Koch
35 * @author Alexander Martin
36 * @author Marc Pfetsch
37 * @author Michael Winkler
38 * @author Kati Wolter
39 *
40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
41 */
42
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44
46#include "scip/debug.h"
47#include "scip/nodesel.h"
48#include "scip/pub_message.h"
49#include "scip/pub_tree.h"
50#include "scip/pub_var.h"
51#include "scip/scip_mem.h"
52#include "scip/scip_tree.h"
53#include "scip/scip_numerics.h"
54#include "scip/struct_mem.h"
55#include "scip/struct_scip.h"
56#include "scip/struct_stat.h"
57#include "scip/struct_tree.h"
58#include "scip/tree.h"
59
60/** gets focus node in the tree
61 *
62 * if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started.
63 *
64 * @return the current node of the search tree
65 *
66 * @pre This method can be called if @p scip is in one of the following stages:
67 * - \ref SCIP_STAGE_INITPRESOLVE
68 * - \ref SCIP_STAGE_PRESOLVING
69 * - \ref SCIP_STAGE_EXITPRESOLVE
70 * - \ref SCIP_STAGE_SOLVING
71 */
73 SCIP* scip /**< SCIP data structure */
74 )
75{
77
78 return SCIPtreeGetFocusNode(scip->tree);
79}
80
81/** gets current node in the tree
82 *
83 * @return the current node of the search tree
84 *
85 * @pre This method can be called if @p scip is in one of the following stages:
86 * - \ref SCIP_STAGE_INITPRESOLVE
87 * - \ref SCIP_STAGE_PRESOLVING
88 * - \ref SCIP_STAGE_EXITPRESOLVE
89 * - \ref SCIP_STAGE_SOLVING
90 */
92 SCIP* scip /**< SCIP data structure */
93 )
94{
96
97 return SCIPtreeGetCurrentNode(scip->tree);
98}
99
100/** gets the root node of the tree
101 *
102 * @return the root node of the search tree
103 *
104 * @pre This method can be called if @p scip is in one of the following stages:
105 * - \ref SCIP_STAGE_INITPRESOLVE
106 * - \ref SCIP_STAGE_PRESOLVING
107 * - \ref SCIP_STAGE_EXITPRESOLVE
108 * - \ref SCIP_STAGE_SOLVING
109 */
111 SCIP* scip /**< SCIP data structure */
112 )
113{
115
116 return SCIPtreeGetRootNode(scip->tree);
117}
118
119/** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node
120 * to the unprocessed nodes.
121 *
122 * @return effective root depth
123 *
124 * @pre This method can be called if @p scip is in one of the following stages:
125 * - \ref SCIP_STAGE_SOLVING
126 */
128 SCIP* scip /**< SCIP data structure */
129 )
130{
131 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetEffectiveRootDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
132
134}
135
136/** returns whether the current node is already solved and only propagated again
137 *
138 * @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE.
139 *
140 * @pre This method can be called if @p scip is in one of the following stages:
141 * - \ref SCIP_STAGE_INITPRESOLVE
142 * - \ref SCIP_STAGE_PRESOLVING
143 * - \ref SCIP_STAGE_EXITPRESOLVE
144 * - \ref SCIP_STAGE_SOLVING
145 */
147 SCIP* scip /**< SCIP data structure */
148 )
149{
151
152 return SCIPtreeInRepropagation(scip->tree);
153}
154
155/** gets children of focus node along with the number of children
156 *
157 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
158 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
159 *
160 * @pre This method can be called if @p scip is in one of the following stages:
161 * - \ref SCIP_STAGE_SOLVING
162 * - \ref SCIP_STAGE_SOLVED
163 */
165 SCIP* scip, /**< SCIP data structure */
166 SCIP_NODE*** children, /**< pointer to store children array, or NULL if not needed */
167 int* nchildren /**< pointer to store number of children, or NULL if not needed */
168 )
169{
171
172 if( children != NULL )
173 *children = scip->tree->children;
174 if( nchildren != NULL )
175 *nchildren = scip->tree->nchildren;
176
177 return SCIP_OKAY;
178}
179
180/** gets number of children of focus node
181 *
182 * @return number of children of the focus node
183 *
184 * @pre This method can be called if @p scip is in one of the following stages:
185 * - \ref SCIP_STAGE_SOLVING
186 * - \ref SCIP_STAGE_SOLVED
187 */
189 SCIP* scip /**< SCIP data structure */
190 )
191{
193
194 return scip->tree->nchildren;
195}
196
197/** gets siblings of focus node along with the number of siblings
198 *
199 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
200 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
201 *
202 * @pre This method can be called if @p scip is in one of the following stages:
203 * - \ref SCIP_STAGE_SOLVING
204 * - \ref SCIP_STAGE_SOLVED
205 */
207 SCIP* scip, /**< SCIP data structure */
208 SCIP_NODE*** siblings, /**< pointer to store siblings array, or NULL if not needed */
209 int* nsiblings /**< pointer to store number of siblings, or NULL if not needed */
210 )
211{
213
214 if( siblings != NULL )
215 *siblings = scip->tree->siblings;
216 if( nsiblings != NULL )
217 *nsiblings = scip->tree->nsiblings;
218
219 return SCIP_OKAY;
220}
221
222/** gets number of siblings of focus node
223 *
224 * @return the number of siblings of focus node
225 *
226 * @pre This method can be called if @p scip is in one of the following stages:
227 * - \ref SCIP_STAGE_SOLVING
228 * - \ref SCIP_STAGE_SOLVED
229 */
231 SCIP* scip /**< SCIP data structure */
232 )
233{
235
236 return scip->tree->nsiblings;
237}
238
239/** gets leaves of the tree along with the number of leaves
240 *
241 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
242 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
243 *
244 * @pre This method can be called if @p scip is in one of the following stages:
245 * - \ref SCIP_STAGE_SOLVING
246 * - \ref SCIP_STAGE_SOLVED
247 */
249 SCIP* scip, /**< SCIP data structure */
250 SCIP_NODE*** leaves, /**< pointer to store leaves array, or NULL if not needed */
251 int* nleaves /**< pointer to store number of leaves, or NULL if not needed */
252 )
253{
255
256 if( leaves != NULL )
257 *leaves = SCIPnodepqNodes(scip->tree->leaves);
258 if( nleaves != NULL )
259 *nleaves = SCIPnodepqLen(scip->tree->leaves);
260
261 return SCIP_OKAY;
262}
263
264/** gets number of leaves in the tree
265 *
266 * @return the number of leaves in the tree
267 *
268 * @pre This method can be called if @p scip is in one of the following stages:
269 * - \ref SCIP_STAGE_SOLVING
270 * - \ref SCIP_STAGE_SOLVED
271 */
273 SCIP* scip /**< SCIP data structure */
274 )
275{
277
278 return SCIPnodepqLen(scip->tree->leaves);
279}
280
281/** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
282 *
283 * @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
284 *
285 * @pre This method can be called if @p scip is in one of the following stages:
286 * - \ref SCIP_STAGE_SOLVING
287 */
289 SCIP* scip /**< SCIP data structure */
290 )
291{
293
294 return SCIPtreeGetPrioChild(scip->tree);
295}
296
297/** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
298 *
299 * @return the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
300 *
301 * @pre This method can be called if @p scip is in one of the following stages:
302 * - \ref SCIP_STAGE_SOLVING
303 */
305 SCIP* scip /**< SCIP data structure */
306 )
307{
309
310 return SCIPtreeGetPrioSibling(scip->tree);
311}
312
313/** gets the best child of the focus node w.r.t. the node selection strategy
314 *
315 * @return the best child of the focus node w.r.t. the node selection strategy
316 *
317 * @pre This method can be called if @p scip is in one of the following stages:
318 * - \ref SCIP_STAGE_SOLVING
319 */
321 SCIP* scip /**< SCIP data structure */
322 )
323{
325
326 return SCIPtreeGetBestChild(scip->tree, scip->set);
327}
328
329/** gets the best sibling of the focus node w.r.t. the node selection strategy
330 *
331 * @return the best sibling of the focus node w.r.t. the node selection strategy
332 *
333 * @pre This method can be called if @p scip is in one of the following stages:
334 * - \ref SCIP_STAGE_SOLVING
335 */
337 SCIP* scip /**< SCIP data structure */
338 )
339{
341
342 return SCIPtreeGetBestSibling(scip->tree, scip->set);
343}
344
345/** gets the best leaf from the node queue w.r.t. the node selection strategy
346 *
347 * @return the best leaf from the node queue w.r.t. the node selection strategy
348 *
349 * @pre This method can be called if @p scip is in one of the following stages:
350 * - \ref SCIP_STAGE_SOLVING
351 */
353 SCIP* scip /**< SCIP data structure */
354 )
355{
357
358 return SCIPtreeGetBestLeaf(scip->tree);
359}
360
361/** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
362 *
363 * @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
364 *
365 * @pre This method can be called if @p scip is in one of the following stages:
366 * - \ref SCIP_STAGE_SOLVING
367 */
369 SCIP* scip /**< SCIP data structure */
370 )
371{
373
374 return SCIPtreeGetBestNode(scip->tree, scip->set);
375}
376
377/** gets the node with smallest lower bound from the tree (child, sibling, or leaf)
378 *
379 * @return the node with smallest lower bound from the tree (child, sibling, or leaf)
380 *
381 * @pre This method can be called if @p scip is in one of the following stages:
382 * - \ref SCIP_STAGE_SOLVING
383 */
385 SCIP* scip /**< SCIP data structure */
386 )
387{
389
390 return SCIPtreeGetLowerboundNode(scip->tree, scip->set);
391}
392
393/** access to all data of open nodes (leaves, children, and siblings)
394 *
395 * @pre This method can be called if @p scip is in one of the following stages:
396 * - \ref SCIP_STAGE_SOLVING
397 */
399 SCIP* scip, /**< SCIP data structure */
400 SCIP_NODE*** leaves, /**< pointer to store the leaves, or NULL if not needed */
401 SCIP_NODE*** children, /**< pointer to store the children, or NULL if not needed */
402 SCIP_NODE*** siblings, /**< pointer to store the siblings, or NULL if not needed */
403 int* nleaves, /**< pointer to store the number of leaves, or NULL */
404 int* nchildren, /**< pointer to store the number of children, or NULL */
405 int* nsiblings /**< pointer to store the number of siblings, or NULL */
406 )
407{
408 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetOpenNodesData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
409
410 if( leaves != NULL )
411 *leaves = SCIPnodepqNodes(scip->tree->leaves);
412 if( children != NULL )
413 *children = scip->tree->children;
414 if( siblings != NULL )
415 *siblings = scip->tree->siblings;
416 if( nleaves != NULL )
417 *nleaves = SCIPnodepqLen(scip->tree->leaves);
418 if( nchildren != NULL )
419 *nchildren = SCIPtreeGetNChildren(scip->tree);
420 if( nsiblings != NULL )
421 *nsiblings = SCIPtreeGetNSiblings(scip->tree);
422
423 return SCIP_OKAY;
424}
425
426/** cuts off node and whole sub tree from branch and bound tree
427 *
428 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
429 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
430 *
431 * @pre This method can be called if @p scip is in one of the following stages:
432 * - \ref SCIP_STAGE_SOLVING
433 */
435 SCIP* scip, /**< SCIP data structure */
436 SCIP_NODE* node /**< node that should be cut off */
437 )
438{
440
441 SCIP_CALL( SCIPnodeCutoff(node, scip->set, scip->stat, scip->tree, scip->transprob, scip->origprob, scip->reopt,
442 scip->lp, scip->mem->probmem) );
443
444 return SCIP_OKAY;
445}
446
447/** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode()
448 *
449 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
450 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
451 *
452 * @pre This method can be called if @p scip is in one of the following stages:
453 * - \ref SCIP_STAGE_SOLVING
454 *
455 * @note In diving mode, the removal of nodes is delayed until diving ends.
456 */
458 SCIP* scip /**< SCIP data structure */
459 )
460{
462
463 SCIP_CALL( SCIPtreeCutoff(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
464 scip->eventqueue, scip->lp, SCIPinfinity(scip)) );
465
466 return SCIP_OKAY;
467}
468
469/** marks the given node to be propagated again the next time a node of its subtree is processed
470 *
471 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
472 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
473 *
474 * @pre This method can be called if @p scip is in one of the following stages:
475 * - \ref SCIP_STAGE_SOLVING
476 */
478 SCIP* scip, /**< SCIP data structure */
479 SCIP_NODE* node /**< node that should be propagated again */
480 )
481{
483
484 SCIPnodePropagateAgain(node, scip->set, scip->stat, scip->tree);
485
486 return SCIP_OKAY;
487}
488
489/** returns depth of first node in active path that is marked being cutoff
490 *
491 * @return depth of first node in active path that is marked being cutoff
492 *
493 * @pre This method can be called if @p scip is in one of the following stages:
494 * - \ref SCIP_STAGE_SOLVING
495 */
497 SCIP* scip /**< SCIP data structure */
498 )
499{
501
502 return scip->tree->cutoffdepth;
503}
504
505/** returns depth of first node in active path that has to be propagated again
506 *
507 * @return depth of first node in active path that has to be propagated again
508 *
509 * @pre This method can be called if @p scip is in one of the following stages:
510 * - \ref SCIP_STAGE_SOLVING
511 */
513 SCIP* scip /**< SCIP data structure */
514 )
515{
517
518 return scip->tree->repropdepth;
519}
520
521/** prints all branching decisions on variables from the root to the given node
522 *
523 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
524 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
525 *
526 * @pre This method can be called if @p scip is in one of the following stages:
527 * - \ref SCIP_STAGE_SOLVING
528 */
530 SCIP* scip, /**< SCIP data structure */
531 SCIP_NODE* node, /**< node data */
532 FILE* file /**< output file (or NULL for standard output) */
533 )
534{
535 SCIP_VAR** branchvars; /* array of variables on which the branchings has been performed in all ancestors */
536 SCIP_Real* branchbounds; /* array of bounds which the branchings in all ancestors set */
537 SCIP_BOUNDTYPE* boundtypes; /* array of boundtypes which the branchings in all ancestors set */
538 int* nodeswitches; /* marks, where in the arrays the branching decisions of the next node on the path start
539 * branchings performed at the parent of node always start at position 0. For single variable branching,
540 * nodeswitches[i] = i holds */
541 int nbranchvars; /* number of variables on which branchings have been performed in all ancestors
542 * if this is larger than the array size, arrays should be reallocated and method should be called again */
543 int branchvarssize; /* available slots in arrays */
544 int nnodes; /* number of nodes in the nodeswitch array */
545 int nodeswitchsize; /* available slots in node switch array */
546
549
550 /* memory allocation */
555
557
558 /* if the arrays were to small, we have to reallocate them and recall SCIPnodeGetAncestorBranchingPath */
560 {
563
564 /* memory reallocation */
569
572 }
573
574 /* we only want to create output, if branchings were performed */
575 if( nbranchvars >= 1 )
576 {
577 int i;
578 int j;
579
580 /* print all nodes, starting from the root, which is last in the arrays */
581 for( j = nnodes-1; j >= 0; --j)
582 {
583 int end;
584 if(j == nnodes-1)
586 else
587 end = nodeswitches[j+1];
588
589 for( i = nodeswitches[j]; i < end; ++i )
590 {
591 if( i > nodeswitches[j] )
592 SCIPmessageFPrintInfo(scip->messagehdlr, file, " AND ");
593 SCIPmessageFPrintInfo(scip->messagehdlr, file, "<%s> %s %.1f",SCIPvarGetName(branchvars[i]), boundtypes[i] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbounds[i]);
594 }
595 SCIPmessageFPrintInfo(scip->messagehdlr, file, "\n");
596 if( j > 0 )
597 {
598 if( nodeswitches[j]-nodeswitches[j-1] != 1 )
599 SCIPmessageFPrintInfo(scip->messagehdlr, file, " |\n |\n");
600 else if( boundtypes[i-1] == SCIP_BOUNDTYPE_LOWER )
601 SCIPmessageFPrintInfo(scip->messagehdlr, file, "\\ \n \\\n");
602 else
603 SCIPmessageFPrintInfo(scip->messagehdlr, file, " /\n/ \n");
604 }
605 }
606 }
607
608 /* free all local memory */
610 SCIPfreeBufferArray(scip, &boundtypes);
613
614 return SCIP_OKAY;
615}
616
617/** sets whether the LP should be solved at the focus node
618 *
619 * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
620 * solved.
621 *
622 * @pre This method can be called if @p scip is in one of the following stages:
623 * - \ref SCIP_STAGE_SOLVING
624 */
626 SCIP* scip, /**< SCIP data structure */
627 SCIP_Bool solvelp /**< should the LP be solved? */
628 )
629{
631
633}
634
635/** gets number of nodes left in the tree (children + siblings + leaves)
636 *
637 * @return the number of nodes left in the tree (children + siblings + leaves)
638 *
639 * @pre This method can be called if SCIP is in one of the following stages:
640 * - \ref SCIP_STAGE_PRESOLVED
641 * - \ref SCIP_STAGE_SOLVING
642 * - \ref SCIP_STAGE_SOLVED
643 */
645 SCIP* scip /**< SCIP data structure */
646 )
647{
649
650 return SCIPtreeGetNNodes(scip->tree);
651}
652
653/** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
654 * such that the depth includes the probing path
655 *
656 * @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
657 * such that the depth includes the probing path
658 *
659 * @pre This method can be called if SCIP is in one of the following stages:
660 * - \ref SCIP_STAGE_TRANSFORMED
661 * - \ref SCIP_STAGE_INITPRESOLVE
662 * - \ref SCIP_STAGE_PRESOLVING
663 * - \ref SCIP_STAGE_EXITPRESOLVE
664 * - \ref SCIP_STAGE_PRESOLVED
665 * - \ref SCIP_STAGE_INITSOLVE
666 * - \ref SCIP_STAGE_SOLVING
667 * - \ref SCIP_STAGE_SOLVED
668 * - \ref SCIP_STAGE_EXITSOLVE
669 */
671 SCIP* scip /**< SCIP data structure */
672 )
673{
675
676 return SCIPtreeGetCurrentDepth(scip->tree);
677}
678
679/** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
680 * branching tree, excluding the nodes of the probing path
681 *
682 * @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
683 * branching tree, excluding the nodes of the probing path
684 *
685 * @pre This method can be called if SCIP is in one of the following stages:
686 * - \ref SCIP_STAGE_TRANSFORMED
687 * - \ref SCIP_STAGE_INITPRESOLVE
688 * - \ref SCIP_STAGE_PRESOLVING
689 * - \ref SCIP_STAGE_EXITPRESOLVE
690 * - \ref SCIP_STAGE_PRESOLVED
691 * - \ref SCIP_STAGE_INITSOLVE
692 * - \ref SCIP_STAGE_SOLVING
693 * - \ref SCIP_STAGE_SOLVED
694 * - \ref SCIP_STAGE_EXITSOLVE
695 */
697 SCIP* scip /**< SCIP data structure */
698 )
699{
701
702 return SCIPtreeGetFocusDepth(scip->tree);
703}
704
705/** gets current plunging depth (successive times, a child was selected as next node)
706 *
707 * @return the current plunging depth (successive times, a child was selected as next node)
708 *
709 * @pre This method can be called if SCIP is in one of the following stages:
710 * - \ref SCIP_STAGE_PRESOLVED
711 * - \ref SCIP_STAGE_SOLVING
712 */
714 SCIP* scip /**< SCIP data structure */
715 )
716{
718
719 return scip->stat->plungedepth;
720}
721
722/** query if node was the last parent of a branching of the tree
723 *
724 * @return TRUE if node was the last parent of a branching of the tree
725 *
726 * @pre This method can be called if SCIP is in one of the following stages:
727 * - \ref SCIP_STAGE_PRESOLVED
728 * - \ref SCIP_STAGE_SOLVING
729 * - \ref SCIP_STAGE_SOLVED
730 */
732 SCIP* scip, /**< SCIP data structure */
733 SCIP_NODE* node /**< tree node, or NULL to check focus node */
734 )
735{
736 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPwasNodeLastBranchParent", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
737
738 return SCIPtreeWasNodeLastBranchParent(scip->tree, node);
739}
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition debug.c:2208
methods for debugging
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL_ABORT(x)
Definition def.h:367
#define SCIP_CALL(x)
Definition def.h:388
#define nnodes
Definition gastrans.c:74
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
void SCIPnodeGetAncestorBranchingPath(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize, int *nodeswitches, int *nnodes, int nodeswitchsize)
Definition tree.c:8095
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition tree.c:7454
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPpruneTree(SCIP *scip)
Definition scip_tree.c:457
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition scip_tree.c:127
int SCIPgetNSiblings(SCIP *scip)
Definition scip_tree.c:230
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition scip_tree.c:477
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition scip_tree.c:336
int SCIPgetNChildren(SCIP *scip)
Definition scip_tree.c:188
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition scip_tree.c:398
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition scip_tree.c:146
void SCIPsetFocusnodeLP(SCIP *scip, SCIP_Bool solvelp)
Definition scip_tree.c:625
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition scip_tree.c:164
int SCIPgetNNodesLeft(SCIP *scip)
Definition scip_tree.c:644
int SCIPgetFocusDepth(SCIP *scip)
Definition scip_tree.c:696
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition scip_tree.c:72
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition scip_tree.c:248
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition scip_tree.c:320
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition scip_tree.c:304
int SCIPgetCutoffdepth(SCIP *scip)
Definition scip_tree.c:496
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition scip_tree.c:529
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
int SCIPgetNLeaves(SCIP *scip)
Definition scip_tree.c:272
SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition scip_tree.c:731
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition scip_tree.c:368
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition scip_tree.c:206
int SCIPgetPlungeDepth(SCIP *scip)
Definition scip_tree.c:713
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition scip_tree.c:384
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition scip_tree.c:288
int SCIPgetRepropdepth(SCIP *scip)
Definition scip_tree.c:512
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition scip_tree.c:434
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition scip_tree.c:352
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition scip_tree.c:110
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition message.c:618
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
Definition nodesel.c:571
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
Definition nodesel.c:561
internal methods for node selectors and node priority queues
public methods for message output
public methods for branch and bound tree
public methods for problem variables
public methods for memory management
public methods for numerical tolerances
public methods for the branch-and-bound tree
datastructures for block memory pools and memory buffers
SCIP main data structure.
datastructures for problem statistics
data structures for branch and bound tree
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7186
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition tree.c:1188
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition tree.c:8312
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition tree.c:8329
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition tree.c:1248
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition tree.c:8229
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition tree.c:8387
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition tree.c:8454
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7159
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition tree.c:8443
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition tree.c:7133
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition tree.c:8356
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition tree.c:8259
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition tree.c:8239
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7223
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition tree.c:7213
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition tree.c:8404
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
Definition tree.c:7107
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
Definition tree.c:1042
SCIP_RETCODE SCIPtreeCutoff(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition tree.c:5136
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition tree.c:8377
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7295
internal methods for branch and bound tree
@ SCIP_BOUNDTYPE_LOWER
Definition type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition type_lp.h:59
enum SCIP_Retcode SCIP_RETCODE