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