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