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-2020 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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
263  SCIP* scip /**< SCIP data structure */
264  )
265 {
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  */
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  */
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  */
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  */
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  */
343  SCIP* scip /**< SCIP data structure */
344  )
345 {
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  */
359  SCIP* scip /**< SCIP data structure */
360  )
361 {
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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 }
SCIP_STAT * stat
Definition: struct_scip.h:70
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:552
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:310
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:497
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:8332
public methods for memory management
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7271
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:342
void SCIPsetFocusnodeLP(SCIP *scip, SCIP_Bool solvelp)
Definition: scip_tree.c:593
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:464
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7199
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7135
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:388
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:562
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:294
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
#define FALSE
Definition: def.h:73
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7430
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8380
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:154
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:424
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8288
public methods for problem variables
SCIP_PROB * transprob
Definition: struct_scip.h:89
SCIP_NODE ** siblings
Definition: struct_tree.h:191
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:326
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:136
SCIP_PROB * origprob
Definition: struct_scip.h:71
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:117
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:62
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8305
public methods for the branch-and-bound tree
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition: tree.c:8205
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition: tree.c:7189
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:1176
SCIP_MEM * mem
Definition: struct_scip.h:62
int nsiblings
Definition: struct_tree.h:215
int cutoffdepth
Definition: struct_tree.h:221
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:358
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
Definition: tree.c:1033
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition: tree.c:8353
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:238
int repropdepth
Definition: struct_tree.h:222
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:2011
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:100
int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:178
SCIP_REOPT * reopt
Definition: struct_scip.h:76
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7162
#define NULL
Definition: lpi_spx1.cpp:155
data structures for branch and bound tree
internal methods for node selectors and node priority queues
SCIP_NODEPQ * leaves
Definition: struct_tree.h:178
#define SCIP_CALL(x)
Definition: def.h:364
SCIP main data structure.
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:278
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:681
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1236
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8419
#define SCIP_Bool
Definition: def.h:70
SCIP_NODE ** children
Definition: struct_tree.h:190
methods for debugging
datastructures for block memory pools and memory buffers
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:612
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:374
datastructures for problem statistics
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition: tree.c:8215
BMS_BLKMEM * probmem
Definition: struct_mem.h:40
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8430
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8363
int SCIPgetNLeaves(SCIP *scip)
Definition: scip_tree.c:262
SCIP_SET * set
Definition: struct_scip.h:63
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:163
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:196
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:445
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
Definition: tree.c:7083
int SCIPgetRepropdepth(SCIP *scip)
Definition: scip_tree.c:480
SCIP_TREE * tree
Definition: struct_scip.h:86
SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:699
int nchildren
Definition: struct_tree.h:213
#define nnodes
Definition: gastrans.c:65
int plungedepth
Definition: struct_stat.h:226
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
SCIP_LP * lp
Definition: struct_scip.h:82
SCIP_EXPORT 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:8071
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition: tree.c:8235
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition: tree.c:7109
int SCIPgetFocusDepth(SCIP *scip)
Definition: scip_tree.c:664
int SCIPgetNSiblings(SCIP *scip)
Definition: scip_tree.c:220
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
memory allocation routines