Scippy

SCIP

Solving Constraint Integer Programs

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