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