Scippy

SCIP

Solving Constraint Integer Programs

tree.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file tree.h
17  * @ingroup INTERNALAPI
18  * @brief internal methods for branch and bound tree
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_TREE_H__
26 #define __SCIP_TREE_H__
27 
28 
29 #include "blockmemshell/memory.h"
30 #include "scip/def.h"
31 #include "scip/nodesel.h"
32 #include "scip/type_set.h"
33 #include "scip/type_stat.h"
34 #include "scip/type_cons.h"
35 #include "scip/type_event.h"
36 #include "scip/type_lp.h"
37 #include "scip/type_var.h"
38 #include "scip/type_prob.h"
39 #include "scip/type_primal.h"
40 #include "scip/type_tree.h"
41 #include "scip/type_reopt.h"
42 #include "scip/type_branch.h"
43 #include "scip/type_prop.h"
44 #include "scip/type_implics.h"
45 #include "scip/type_history.h"
47 #include "scip/pub_tree.h"
48 
49 #ifndef NDEBUG
50 #include "scip/struct_tree.h"
51 #endif
52 
53 #ifdef __cplusplus
54 extern "C" {
55 #endif
56 
57 
58 /*
59  * Node methods
60  */
61 
62 /** creates a child node of the focus node */
64  SCIP_NODE** node, /**< pointer to node data structure */
65  BMS_BLKMEM* blkmem, /**< block memory */
66  SCIP_SET* set, /**< global SCIP settings */
67  SCIP_STAT* stat, /**< problem statistics */
68  SCIP_TREE* tree, /**< branch and bound tree */
69  SCIP_Real nodeselprio, /**< node selection priority of new node */
70  SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
71  );
72 
73 /** frees node */
75  SCIP_NODE** node, /**< node data */
76  BMS_BLKMEM* blkmem, /**< block memory buffer */
77  SCIP_SET* set, /**< global SCIP settings */
78  SCIP_STAT* stat, /**< problem statistics */
79  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
80  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
81  SCIP_TREE* tree, /**< branch and bound tree */
82  SCIP_LP* lp /**< current LP data */
83  );
84 
85 /** increases the reference counter of the LP state in the fork or subroot node */
87  SCIP_NODE* node, /**< fork/subroot node */
88  int nuses /**< number to add to the usage counter */
89  );
90 
91 /** decreases the reference counter of the LP state in the fork or subroot node */
93  SCIP_NODE* node, /**< fork/subroot node */
94  BMS_BLKMEM* blkmem, /**< block memory buffers */
95  SCIP_LP* lp /**< current LP data */
96  );
97 
98 /** installs a child, a sibling, or a leaf node as the new focus node */
100  SCIP_NODE** node, /**< pointer to node to focus (or NULL to remove focus); the node
101  * is freed, if it was cut off due to a cut off subtree */
102  BMS_BLKMEM* blkmem, /**< block memory */
103  SCIP_SET* set, /**< global SCIP settings */
104  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
105  SCIP_STAT* stat, /**< problem statistics */
106  SCIP_PROB* transprob, /**< transformed problem */
107  SCIP_PROB* origprob, /**< original problem */
108  SCIP_PRIMAL* primal, /**< primal data */
109  SCIP_TREE* tree, /**< branch and bound tree */
110  SCIP_REOPT* reopt, /**< reoptimization data structure */
111  SCIP_LP* lp, /**< current LP data */
112  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
113  SCIP_CONFLICT* conflict, /**< conflict analysis data */
114  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
115  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
116  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
117  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
118  SCIP_Bool* cutoff, /**< pointer to store whether the given node can be cut off */
119  SCIP_Bool postponed, /**< was the current focus node postponed? */
120  SCIP_Bool exitsolve /**< are we in exitsolve stage, so we only need to loose the children */
121  );
122 
123 /** cuts off node and whole sub tree from branch and bound tree */
125  SCIP_NODE* node, /**< node that should be cut off */
126  SCIP_SET* set, /**< global SCIP settings */
127  SCIP_STAT* stat, /**< problem statistics */
128  SCIP_TREE* tree, /**< branch and bound tree */
129  SCIP_PROB* transprob, /**< transformed problem after presolve */
130  SCIP_PROB* origprob, /**< original problem */
131  SCIP_REOPT* reopt, /**< reoptimization data structure */
132  SCIP_LP* lp, /**< current LP */
133  BMS_BLKMEM* blkmem /**< block memory */
134  );
135 
136 /** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
138  SCIP_NODE* node, /**< node that should be propagated again */
139  SCIP_SET* set, /**< global SCIP settings */
140  SCIP_STAT* stat, /**< problem statistics */
141  SCIP_TREE* tree /**< branch and bound tree */
142  );
143 
144 /** marks node, that it is completely propagated in the current repropagation subtree level */
146  SCIP_NODE* node, /**< node that should be propagated again */
147  SCIP_TREE* tree /**< branch and bound tree */
148  );
149 
150 /** adds constraint locally to the node and captures it; activates constraint, if node is active;
151  * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
152  */
154  SCIP_NODE* node, /**< node to add constraint to */
155  BMS_BLKMEM* blkmem, /**< block memory */
156  SCIP_SET* set, /**< global SCIP settings */
157  SCIP_STAT* stat, /**< problem statistics */
158  SCIP_TREE* tree, /**< branch and bound tree */
159  SCIP_CONS* cons /**< constraint to add */
160  );
161 
162 /** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
163  * at the node; captures constraint; disables constraint, if node is active
164  */
166  SCIP_NODE* node, /**< node to add constraint to */
167  BMS_BLKMEM* blkmem, /**< block memory */
168  SCIP_SET* set, /**< global SCIP settings */
169  SCIP_STAT* stat, /**< problem statistics */
170  SCIP_TREE* tree, /**< branch and bound tree */
171  SCIP_CONS* cons /**< constraint to locally delete */
172  );
173 
174 /** return all bound changes based on constraint propagation; stop saving the bound changes if we reach a branching
175  * decision based on a dual information
176  */
178  SCIP_NODE* node, /**< node */
179  SCIP_VAR** vars, /**< array of variables on which constraint propagation triggers a bound change */
180  SCIP_Real* varbounds, /**< array of bounds set by constraint propagation */
181  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes set by constraint propagation */
182  int* nconspropvars, /**< number of variables on which constraint propagation triggers a bound change
183  * if this is larger than the array size, arrays should be reallocated and method
184  * should be called again */
185  int conspropvarssize /**< available slots in arrays */
186  );
187 
188 /** gets all bound changes applied after the first bound change based on dual information.
189  *
190  * @note: currently, we can only detect bound changes based in dual information if they arise from strong branching.
191  */
193  SCIP_NODE* node, /**< node */
194  SCIP_VAR** vars, /**< array of variables on which the branching has been performed in the parent node */
195  SCIP_Real* varbounds, /**< array of bounds which the branching in the parent node set */
196  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes which the branching in the parent node set */
197  int start, /**< first free slot in the arrays */
198  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
199  * if this is larger than the array size, arrays should be reallocated and method
200  * should be called again */
201  int branchvarssize /**< available slots in arrays */
202  );
203 
204 /** adds bound change with inference information to focus node, child of focus node, or probing node;
205  * if possible, adjusts bound to integral value;
206  * at most one of infercons and inferprop may be non-NULL
207  */
209  SCIP_NODE* node, /**< node to add bound change to */
210  BMS_BLKMEM* blkmem, /**< block memory */
211  SCIP_SET* set, /**< global SCIP settings */
212  SCIP_STAT* stat, /**< problem statistics */
213  SCIP_PROB* transprob, /**< transformed problem after presolve */
214  SCIP_PROB* origprob, /**< original problem */
215  SCIP_TREE* tree, /**< branch and bound tree */
216  SCIP_REOPT* reopt, /**< reoptimization data structure */
217  SCIP_LP* lp, /**< current LP data */
218  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
219  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
220  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
221  SCIP_VAR* var, /**< variable to change the bounds for */
222  SCIP_Real newbound, /**< new value for bound */
223  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
224  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
225  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
226  int inferinfo, /**< user information for inference to help resolving the conflict */
227  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
228  );
229 
230 /** adds bound change to focus node, or child of focus node, or probing node;
231  * if possible, adjusts bound to integral value
232  */
234  SCIP_NODE* node, /**< node to add bound change to */
235  BMS_BLKMEM* blkmem, /**< block memory */
236  SCIP_SET* set, /**< global SCIP settings */
237  SCIP_STAT* stat, /**< problem statistics */
238  SCIP_PROB* transprob, /**< transformed problem after presolve */
239  SCIP_PROB* origprob, /**< original problem */
240  SCIP_TREE* tree, /**< branch and bound tree */
241  SCIP_REOPT* reopt, /**< reoptimization data structure */
242  SCIP_LP* lp, /**< current LP data */
243  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
244  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
245  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
246  SCIP_VAR* var, /**< variable to change the bounds for */
247  SCIP_Real newbound, /**< new value for bound */
248  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
249  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
250  );
251 
252 /** adds hole with inference information to focus node, child of focus node, or probing node;
253  * if possible, adjusts bound to integral value;
254  * at most one of infercons and inferprop may be non-NULL
255  */
257  SCIP_NODE* node, /**< node to add bound change to */
258  BMS_BLKMEM* blkmem, /**< block memory */
259  SCIP_SET* set, /**< global SCIP settings */
260  SCIP_STAT* stat, /**< problem statistics */
261  SCIP_TREE* tree, /**< branch and bound tree */
262  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
263  SCIP_VAR* var, /**< variable to change the bounds for */
264  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
265  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
266  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
267  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
268  int inferinfo, /**< user information for inference to help resolving the conflict */
269  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
270  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
271  );
272 
273 /** adds hole change to focus node, or child of focus node */
275  SCIP_NODE* node, /**< node to add bound change to */
276  BMS_BLKMEM* blkmem, /**< block memory */
277  SCIP_SET* set, /**< global SCIP settings */
278  SCIP_STAT* stat, /**< problem statistics */
279  SCIP_TREE* tree, /**< branch and bound tree */
280  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
281  SCIP_VAR* var, /**< variable to change the bounds for */
282  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
283  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
284  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
285  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
286  );
287 
288 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
290  SCIP_NODE* node, /**< node to update lower bound for */
291  SCIP_STAT* stat, /**< problem statistics */
292  SCIP_SET* set, /**< global SCIP settings */
293  SCIP_TREE* tree, /**< branch and bound tree */
294  SCIP_PROB* transprob, /**< transformed problem data */
295  SCIP_PROB* origprob, /**< original problem */
296  SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
297  );
298 
299 /** updates lower bound of node using lower bound of LP */
301  SCIP_NODE* node, /**< node to set lower bound for */
302  SCIP_SET* set, /**< global SCIP settings */
303  SCIP_STAT* stat, /**< problem statistics */
304  SCIP_TREE* tree, /**< branch and bound tree */
305  SCIP_PROB* transprob, /**< transformed problem after presolve */
306  SCIP_PROB* origprob, /**< original problem */
307  SCIP_LP* lp /**< LP data */
308  );
309 
310 /** change the node selection priority of the given child */
312  SCIP_TREE* tree, /**< branch and bound tree */
313  SCIP_NODE* child, /**< child to update the node selection priority */
314  SCIP_Real priority /**< node selection priority value */
315  );
316 
317 
318 /** sets the node's estimated bound to the new value */
320  SCIP_NODE* node, /**< node to update lower bound for */
321  SCIP_SET* set, /**< global SCIP settings */
322  SCIP_Real newestimate /**< new estimated bound for the node */
323  );
324 
325 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
327  SCIP_NODE* node, /**< node to propagate implications on */
328  BMS_BLKMEM* blkmem, /**< block memory */
329  SCIP_SET* set, /**< global SCIP settings */
330  SCIP_STAT* stat, /**< problem statistics */
331  SCIP_PROB* transprob, /**< transformed problem after presolve */
332  SCIP_PROB* origprob, /**< original problem */
333  SCIP_TREE* tree, /**< branch and bound tree */
334  SCIP_REOPT* reopt, /**< reoptimization data structure */
335  SCIP_LP* lp, /**< current LP data */
336  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
337  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
338  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
339  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
340  );
341 
342 /** returns all bound changes based on dual information.
343  *
344  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
345  * method to ensure optimality within reoptimization.
346  *
347  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
348  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
349  *
350  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
351  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
352  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
353  */
355  SCIP_NODE* node, /**< node data */
356  SCIP_VAR** vars, /**< array of variables on which the bound change is based on dual information */
357  SCIP_Real* bounds, /**< array of bounds which are based on dual information */
358  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which are based on dual information */
359  int* nvars, /**< number of variables on which the bound change is based on dual information
360  * if this is larger than the array size, arrays should be reallocated and method
361  * should be called again */
362  int varssize /**< available slots in arrays */
363  );
364 
365 /** returns the number of bound changes based on dual information.
366  *
367  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
368  * method to ensure optimality within reoptimization.
369  *
370  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
371  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
372  *
373  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
374  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
375  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
376  */
378  SCIP_NODE* node
379  );
380 
381 /*
382  * Tree methods
383  */
384 
385 /** creates an initialized tree data structure */
387  SCIP_TREE** tree, /**< pointer to tree data structure */
388  BMS_BLKMEM* blkmem, /**< block memory buffers */
389  SCIP_SET* set, /**< global SCIP settings */
390  SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */
391  );
392 
393 /** frees tree data structure */
395  SCIP_TREE** tree, /**< pointer to tree data structure */
396  BMS_BLKMEM* blkmem, /**< block memory buffers */
397  SCIP_SET* set, /**< global SCIP settings */
398  SCIP_STAT* stat, /**< problem statistics */
399  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
400  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
401  SCIP_LP* lp /**< current LP data */
402  );
403 
404 /** clears and resets tree data structure and deletes all nodes */
406  SCIP_TREE* tree, /**< tree data structure */
407  BMS_BLKMEM* blkmem, /**< block memory buffers */
408  SCIP_SET* set, /**< global SCIP settings */
409  SCIP_STAT* stat, /**< problem statistics */
410  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
411  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
412  SCIP_LP* lp /**< current LP data */
413  );
414 
415 /** creates the root node of the tree and puts it into the leaves queue */
417  SCIP_TREE* tree, /**< tree data structure */
418  SCIP_REOPT* reopt, /**< reoptimization data structure */
419  BMS_BLKMEM* blkmem, /**< block memory buffers */
420  SCIP_SET* set, /**< global SCIP settings */
421  SCIP_STAT* stat, /**< problem statistics */
422  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
423  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
424  SCIP_LP* lp /**< current LP data */
425  );
426 
427 /** creates a temporary presolving root node of the tree and installs it as focus node */
429  SCIP_TREE* tree, /**< tree data structure */
430  SCIP_REOPT* reopt, /**< reoptimization data structure */
431  BMS_BLKMEM* blkmem, /**< block memory buffers */
432  SCIP_SET* set, /**< global SCIP settings */
433  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
434  SCIP_STAT* stat, /**< problem statistics */
435  SCIP_PROB* transprob, /**< transformed problem */
436  SCIP_PROB* origprob, /**< original problem */
437  SCIP_PRIMAL* primal, /**< primal data */
438  SCIP_LP* lp, /**< current LP data */
439  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
440  SCIP_CONFLICT* conflict, /**< conflict analysis data */
441  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
442  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
443  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
444  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
445  );
446 
447 /** frees the temporary presolving root and resets tree data structure */
449  SCIP_TREE* tree, /**< tree data structure */
450  SCIP_REOPT* reopt, /**< reoptimization data structure */
451  BMS_BLKMEM* blkmem, /**< block memory buffers */
452  SCIP_SET* set, /**< global SCIP settings */
453  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
454  SCIP_STAT* stat, /**< problem statistics */
455  SCIP_PROB* transprob, /**< transformed problem */
456  SCIP_PROB* origprob, /**< original problem */
457  SCIP_PRIMAL* primal, /**< primal data */
458  SCIP_LP* lp, /**< current LP data */
459  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
460  SCIP_CONFLICT* conflict, /**< conflict analysis data */
461  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
462  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
463  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
464  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
465  );
466 
467 /** returns the node selector associated with the given node priority queue */
469  SCIP_TREE* tree /**< branch and bound tree */
470  );
471 
472 /** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
474  SCIP_TREE* tree, /**< branch and bound tree */
475  SCIP_SET* set, /**< global SCIP settings */
476  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
477  SCIP_STAT* stat, /**< problem statistics */
478  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
479  );
480 
481 /** cuts off nodes with lower bound not better than given upper bound */
483  SCIP_TREE* tree, /**< branch and bound tree */
484  SCIP_REOPT* reopt, /**< reoptimization data structure */
485  BMS_BLKMEM* blkmem, /**< block memory */
486  SCIP_SET* set, /**< global SCIP settings */
487  SCIP_STAT* stat, /**< dynamic problem statistics */
488  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
489  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
490  SCIP_LP* lp, /**< current LP data */
491  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
492  );
493 
494 /** constructs the LP relaxation of the focus node */
496  SCIP_TREE* tree, /**< branch and bound tree */
497  BMS_BLKMEM* blkmem, /**< block memory */
498  SCIP_SET* set, /**< global SCIP settings */
499  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
500  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
501  SCIP_LP* lp, /**< current LP data */
502  SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
503  );
504 
505 /** loads LP state for fork/subroot of the focus node */
507  SCIP_TREE* tree, /**< branch and bound tree */
508  BMS_BLKMEM* blkmem, /**< block memory buffers */
509  SCIP_SET* set, /**< global SCIP settings */
510  SCIP_STAT* stat, /**< dynamic problem statistics */
511  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
512  SCIP_LP* lp /**< current LP data */
513  );
514 
515 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
516  * this node selection priority can be given to the SCIPcreateChild() call
517  */
519  SCIP_TREE* tree, /**< branch and bound tree */
520  SCIP_SET* set, /**< global SCIP settings */
521  SCIP_STAT* stat, /**< dynamic problem statistics */
522  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
523  SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed
524  * fixed should only be used, when both bounds changed
525  */
526  SCIP_Real targetvalue /**< new value of the variable in the child node */
527  );
528 
529 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
530  * branching; this estimate can be given to the SCIPcreateChild() call
531  */
533  SCIP_TREE* tree, /**< branch and bound tree */
534  SCIP_SET* set, /**< global SCIP settings */
535  SCIP_STAT* stat, /**< dynamic problem statistics */
536  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
537  SCIP_Real targetvalue /**< new value of the variable in the child node */
538  );
539 
540 /** branches on a variable x
541  * if x is a continuous variable, then two child nodes will be created
542  * (x <= x', x >= x')
543  * but if the bounds of x are such that their relative difference is smaller than epsilon,
544  * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
545  * i.e., no children are created
546  * if x is not a continuous variable, then:
547  * if solution value x' is fractional, two child nodes will be created
548  * (x <= floor(x'), x >= ceil(x')),
549  * if solution value is integral, the x' is equal to lower or upper bound of the branching
550  * variable and the bounds of x are finite, then two child nodes will be created
551  * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
552  * otherwise (up to) three child nodes will be created
553  * (x <= x'-1, x == x', x >= x'+1)
554  * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
555  * will be created (the third one would be infeasible anyway)
556  */
558  SCIP_TREE* tree, /**< branch and bound tree */
559  SCIP_REOPT* reopt, /**< reoptimization data structure */
560  BMS_BLKMEM* blkmem, /**< block memory */
561  SCIP_SET* set, /**< global SCIP settings */
562  SCIP_STAT* stat, /**< problem statistics data */
563  SCIP_PROB* transprob, /**< transformed problem after presolve */
564  SCIP_PROB* origprob, /**< original problem */
565  SCIP_LP* lp, /**< current LP data */
566  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
567  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
568  SCIP_VAR* var, /**< variable to branch on */
569  SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution. A branching value is required for branching on continuous variables */
570  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
571  SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
572  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
573  );
574 
575 /** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
577  SCIP_TREE* tree, /**< branch and bound tree */
578  SCIP_REOPT* reopt, /**< reoptimization data structure */
579  BMS_BLKMEM* blkmem, /**< block memory */
580  SCIP_SET* set, /**< global SCIP settings */
581  SCIP_STAT* stat, /**< problem statistics data */
582  SCIP_PROB* transprob, /**< transformed problem after presolve */
583  SCIP_PROB* origprob, /**< original problem */
584  SCIP_LP* lp, /**< current LP data */
585  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
586  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
587  SCIP_VAR* var, /**< variable to branch on */
588  SCIP_Real left, /**< left side of the domain hole */
589  SCIP_Real right, /**< right side of the domain hole */
590  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
591  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
592  );
593 
594 /** n-ary branching on a variable x
595  * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
596  * The branching value is selected as in SCIPtreeBranchVar().
597  * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
598  * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
599  * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
600  * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
601  * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
602  * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
603  * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
604  *
605  * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
606  * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
607  * results in a ternary branching where the branching variable is mostly fixed in the middle child.
608  * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
609  * (except for one child if the branching value is not in the middle).
610  */
612  SCIP_TREE* tree, /**< branch and bound tree */
613  SCIP_REOPT* reopt, /**< reoptimization data structure */
614  BMS_BLKMEM* blkmem, /**< block memory */
615  SCIP_SET* set, /**< global SCIP settings */
616  SCIP_STAT* stat, /**< problem statistics data */
617  SCIP_PROB* transprob, /**< transformed problem after presolve */
618  SCIP_PROB* origprob, /**< original problem */
619  SCIP_LP* lp, /**< current LP data */
620  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
621  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
622  SCIP_VAR* var, /**< variable to branch on */
623  SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
624  * A branching value is required for branching on continuous variables */
625  int n, /**< attempted number of children to be created, must be >= 2 */
626  SCIP_Real minwidth, /**< minimal domain width in children */
627  SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
628  int* nchildren /**< buffer to store number of created children, or NULL */
629  );
630 
631 /** adds a diving bound change to the tree together with the information if this is a bound change
632  * for the preferred direction or not
633  */
635  SCIP_TREE* tree, /**< branch and bound tree */
636  BMS_BLKMEM* blkmem, /**< block memory buffers */
637  SCIP_VAR* var, /**< variable to apply the bound change to */
638  SCIP_BRANCHDIR dir, /**< direction of the bound change */
639  SCIP_Real value, /**< value to adjust this variable bound to */
640  SCIP_Bool preferred /**< is this a bound change for the preferred child? */
641  );
642 
643 /** get the dive bound change data for the preferred or the alternative direction */
645  SCIP_TREE* tree, /**< branch and bound tree */
646  SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
647  SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
648  SCIP_Real** values, /**< pointer to store bound change values */
649  int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
650  SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
651  );
652 
653 /** clear the tree dive bound change data structure */
655  SCIP_TREE* tree /**< branch and bound tree */
656  );
657 
658 /** switches to probing mode and creates a probing root */
660  SCIP_TREE* tree, /**< branch and bound tree */
661  BMS_BLKMEM* blkmem, /**< block memory */
662  SCIP_SET* set, /**< global SCIP settings */
663  SCIP_LP* lp, /**< current LP data */
664  SCIP_RELAXATION* relaxation, /**< global relaxation data */
665  SCIP_PROB* transprob, /**< transformed problem after presolve */
666  SCIP_Bool strongbranching /**< is the probing mode used for strongbranching? */
667  );
668 
669 /** creates a new probing child node in the probing path */
671  SCIP_TREE* tree, /**< branch and bound tree */
672  BMS_BLKMEM* blkmem, /**< block memory */
673  SCIP_SET* set, /**< global SCIP settings */
674  SCIP_LP* lp /**< current LP data */
675  );
676 
677 /** sets the LP state for the current probing node
678  *
679  * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
680  * to NULL by the method
681  *
682  * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
683  * respective information should not be set
684  */
686  SCIP_TREE* tree, /**< branch and bound tree */
687  BMS_BLKMEM* blkmem, /**< block memory */
688  SCIP_LP* lp, /**< current LP data */
689  SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
690  SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
691  SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
692  SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
693  );
694 
695 /** loads the LP state for the current probing node */
697  SCIP_TREE* tree, /**< branch and bound tree */
698  BMS_BLKMEM* blkmem, /**< block memory buffers */
699  SCIP_SET* set, /**< global SCIP settings */
700  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
701  SCIP_LP* lp /**< current LP data */
702  );
703 
704 /** marks the probing node to have a solved LP relaxation */
706  SCIP_TREE* tree, /**< branch and bound tree */
707  BMS_BLKMEM* blkmem, /**< block memory */
708  SCIP_LP* lp /**< current LP data */
709  );
710 
711 /** undoes all changes to the problem applied in probing up to the given probing depth;
712  * the changes of the probing node of the given probing depth are the last ones that remain active;
713  * changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone
714  */
716  SCIP_TREE* tree, /**< branch and bound tree */
717  SCIP_REOPT* reopt, /**< reoptimization data structure */
718  BMS_BLKMEM* blkmem, /**< block memory buffers */
719  SCIP_SET* set, /**< global SCIP settings */
720  SCIP_STAT* stat, /**< problem statistics */
721  SCIP_PROB* transprob, /**< transformed problem */
722  SCIP_PROB* origprob, /**< original problem */
723  SCIP_LP* lp, /**< current LP data */
724  SCIP_PRIMAL* primal, /**< primal data structure */
725  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
726  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
727  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
728  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
729  int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
730  );
731 
732 /** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
733  * variables and restores active constraints arrays of focus node
734  */
736  SCIP_TREE* tree, /**< branch and bound tree */
737  SCIP_REOPT* reopt, /**< reoptimization data structure */
738  BMS_BLKMEM* blkmem, /**< block memory buffers */
739  SCIP_SET* set, /**< global SCIP settings */
740  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
741  SCIP_STAT* stat, /**< problem statistics */
742  SCIP_PROB* transprob, /**< transformed problem after presolve */
743  SCIP_PROB* origprob, /**< original problem */
744  SCIP_LP* lp, /**< current LP data */
745  SCIP_RELAXATION* relaxation, /**< global relaxation data */
746  SCIP_PRIMAL* primal, /**< primal LP data */
747  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
748  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
749  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
750  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
751  );
752 
753 /** stores relaxation solution before diving or probing */
755  SCIP_TREE* tree, /**< branch and bound tree */
756  SCIP_SET* set, /**< global SCIP settings */
757  SCIP_RELAXATION* relaxation, /**< global relaxation data */
758  SCIP_PROB* transprob /**< transformed problem after presolve */
759  );
760 
761 /** restores relaxation solution after diving or probing */
763  SCIP_TREE* tree, /**< branch and bound tree */
764  SCIP_SET* set, /**< global SCIP settings */
765  SCIP_RELAXATION* relaxation, /**< global relaxation data */
766  SCIP_PROB* transprob /**< transformed problem after presolve */
767  );
768 
769 
770 /** gets number of children of the focus node */
772  SCIP_TREE* tree /**< branch and bound tree */
773  );
774 
775 /** gets number of siblings of the focus node */
777  SCIP_TREE* tree /**< branch and bound tree */
778  );
779 
780 /** gets number of leaves in the tree (excluding children and siblings of focus nodes) */
782  SCIP_TREE* tree /**< branch and bound tree */
783  );
784 
785 /** gets number of open nodes in the tree (children + siblings + leaves) */
787  SCIP_TREE* tree /**< branch and bound tree */
788  );
789 
790 /** returns whether the active path goes completely down to the focus node */
792  SCIP_TREE* tree /**< branch and bound tree */
793  );
794 
795 /** returns whether the current node is a temporary probing node */
797  SCIP_TREE* tree /**< branch and bound tree */
798  );
799 
800 /** returns the temporary probing root node, or NULL if the we are not in probing mode */
802  SCIP_TREE* tree /**< branch and bound tree */
803  );
804 
805 /** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
807  SCIP_TREE* tree /**< branch and bound tree */
808  );
809 
810 /** gets focus node of the tree */
812  SCIP_TREE* tree /**< branch and bound tree */
813  );
814 
815 /** gets depth of focus node in the tree, or -1 if no focus node exists */
817  SCIP_TREE* tree /**< branch and bound tree */
818  );
819 
820 /** returns, whether the LP was or is to be solved in the focus node */
822  SCIP_TREE* tree /**< branch and bound tree */
823  );
824 
825 /** sets mark to solve or to ignore the LP while processing the focus node */
827  SCIP_TREE* tree, /**< branch and bound tree */
828  SCIP_Bool solvelp /**< should the LP be solved in focus node? */
829  );
830 
831 /** returns whether the LP of the focus node is already constructed */
833  SCIP_TREE* tree /**< branch and bound tree */
834  );
835 
836 /** returns whether the focus node is already solved and only propagated again */
838  SCIP_TREE* tree /**< branch and bound tree */
839  );
840 
841 /** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
843  SCIP_TREE* tree /**< branch and bound tree */
844  );
845 
846 /** gets depth of current node in the tree, i.e. the length of the active path minus 1, or -1 if no current node exists */
848  SCIP_TREE* tree /**< branch and bound tree */
849  );
850 
851 /** returns, whether the LP was or is to be solved in the current node */
853  SCIP_TREE* tree /**< branch and bound tree */
854  );
855 
856 /** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
858  SCIP_TREE* tree /**< branch and bound tree */
859  );
860 
861 /** gets the root node of the tree */
863  SCIP_TREE* tree /**< branch and bound tree */
864  );
865 
866 /** returns whether we are in probing and the objective value of at least one column was changed */
868  SCIP_TREE* tree /**< branch and bound tree */
869  );
870 
871 /** marks the current probing node to have a changed objective function */
873  SCIP_TREE* tree /**< branch and bound tree */
874  );
875 
876 #ifdef NDEBUG
877 
878 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
879  * speed up the algorithms.
880  */
881 
882 #define SCIPtreeGetNLeaves(tree) SCIPnodepqLen((tree)->leaves)
883 #define SCIPtreeGetNChildren(tree) ((tree)->nchildren)
884 #define SCIPtreeGetNSiblings(tree) ((tree)->nsiblings)
885 #define SCIPtreeGetNNodes(tree) \
886  (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree))
887 #define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
888 #define SCIPtreeProbing(tree) ((tree)->probingroot != NULL)
889 #define SCIPtreeGetProbingRoot(tree) (tree)->probingroot
890 #define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
891 #define SCIPtreeGetFocusNode(tree) (tree)->focusnode
892 #define SCIPtreeGetFocusDepth(tree) ((tree)->focusnode != NULL ? (int)(tree)->focusnode->depth : -1)
893 #define SCIPtreeHasFocusNodeLP(tree) (tree)->focusnodehaslp
894 #define SCIPtreeSetFocusNodeLP(tree,solvelp) ((tree)->focusnodehaslp = solvelp)
895 #define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed
896 #define SCIPtreeInRepropagation(tree) ((tree)->focusnode != NULL \
897  && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
898 #define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
899 #define SCIPtreeGetCurrentDepth(tree) ((tree)->pathlen-1)
900 #define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
901 #define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth)
902 #define SCIPtreeGetRootNode(tree) ((tree)->root)
903 #define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged)
904 #define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE)
905 
906 #endif
907 
908 
909 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
911  SCIP_TREE* tree /**< branch and bound tree */
912  );
913 
914 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
916  SCIP_TREE* tree /**< branch and bound tree */
917  );
918 
919 /** gets the best child of the focus node w.r.t. the node selection strategy */
921  SCIP_TREE* tree, /**< branch and bound tree */
922  SCIP_SET* set /**< global SCIP settings */
923  );
924 
925 /** gets the best sibling of the focus node w.r.t. the node selection strategy */
927  SCIP_TREE* tree, /**< branch and bound tree */
928  SCIP_SET* set /**< global SCIP settings */
929  );
930 
931 /** gets the best leaf from the node queue w.r.t. the node selection strategy */
933  SCIP_TREE* tree /**< branch and bound tree */
934  );
935 
936 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
938  SCIP_TREE* tree, /**< branch and bound tree */
939  SCIP_SET* set /**< global SCIP settings */
940  );
941 
942 /** gets the minimal lower bound of all nodes in the tree */
944  SCIP_TREE* tree, /**< branch and bound tree */
945  SCIP_SET* set /**< global SCIP settings */
946  );
947 
948 /** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */
950  SCIP_TREE* tree, /**< branch and bound tree */
951  SCIP_SET* set /**< global SCIP settings */
952  );
953 
954 /** gets the average lower bound of all nodes in the tree */
956  SCIP_TREE* tree, /**< branch and bound tree */
957  SCIP_Real cutoffbound /**< global cutoff bound */
958  );
959 
960 /** query if focus node was already branched on */
962  SCIP_TREE* tree, /**< branch and bound tree */
963  SCIP_NODE* node /**< tree node, or NULL to check focus node */
964  );
965 
966 #ifdef __cplusplus
967 }
968 #endif
969 
970 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: tree.c:6489
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
Definition: tree.c:5097
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6264
SCIP_RETCODE SCIPtreeCreatePresolvingRoot(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable)
Definition: tree.c:5003
void SCIPnodeGetDualBoundchgs(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_BOUNDTYPE *boundtypes, int *nvars, int varssize)
Definition: tree.c:7634
SCIP_RETCODE SCIPnodeFree(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: tree.c:1046
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8420
SCIP_RETCODE SCIPnodeDelCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition: tree.c:1642
public methods for branch and bound tree
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7283
SCIP_RETCODE SCIPnodeCreateChild(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: tree.c:984
SCIP_RETCODE SCIPtreeSetProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp, SCIP_LPISTATE **lpistate, SCIP_LPINORMS **lpinorms, SCIP_Bool primalfeas, SCIP_Bool dualfeas)
Definition: tree.c:6514
type definitions for implications, variable bounds, and cliques
SCIP_RETCODE SCIPtreeCutoff(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: tree.c:5125
SCIP_RETCODE SCIPtreeBranchVar(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: tree.c:5420
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
Definition: tree.c:8334
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7147
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition: tree.c:8344
type definitions for conflict store
SCIP_RETCODE SCIPtreeBacktrackProbing(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_PRIMAL *primal, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, int probingdepth)
Definition: tree.c:6823
SCIP_RETCODE SCIPnodeAddBoundinfer(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_CONS *infercons, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool probingchange)
Definition: tree.c:1803
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8300
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7211
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPtreeCreate(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: tree.c:4766
type definitions for global SCIP settings
SCIP_NODE * SCIPtreeGetProbingRoot(SCIP_TREE *tree)
Definition: tree.c:8287
SCIP_RETCODE SCIPtreeLoadLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:3536
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8317
type definitions for collecting reoptimization information
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8392
type definitions for branching rules
type definitions for problem statistics
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition: tree.c:8217
SCIP_Bool SCIPtreeIsPathComplete(SCIP_TREE *tree)
Definition: tree.c:8257
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8355
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition: tree.c:1179
type definitions for LP management
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition: tree.c:8274
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
SCIP_RETCODE SCIPnodeFocus(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *cutoff, SCIP_Bool postponed, SCIP_Bool exitsolve)
Definition: tree.c:4299
void SCIPnodeMarkPropagated(SCIP_NODE *node, SCIP_TREE *tree)
Definition: tree.c:1265
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: tree.c:5211
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7174
SCIP_RETCODE SCIPtreeLoadLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool *initroot)
Definition: tree.c:3408
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition: tree.c:7201
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
Definition: tree.c:1033
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition: tree.c:8365
void SCIPnodeUpdateLowerbound(SCIP_NODE *node, SCIP_STAT *stat, SCIP_SET *set, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_Real newbound)
Definition: tree.c:2356
data structures for branch and bound tree
internal methods for node selectors and node priority queues
SCIP_RETCODE SCIPtreeCreateRoot(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4957
type definitions for problem variables
int SCIPnodeGetNDualBndchgs(SCIP_NODE *node)
Definition: tree.c:7589
type definitions for managing events
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1239
SCIP_RETCODE SCIPnodeAddHolechg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_Bool probingchange, SCIP_Bool *added)
Definition: tree.c:2228
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8409
#define SCIP_Bool
Definition: def.h:84
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8431
SCIP_Real SCIPtreeGetAvgLowerbound(SCIP_TREE *tree, SCIP_Real cutoffbound)
Definition: tree.c:7335
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6319
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: tree.c:6296
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
Definition: tree.c:2452
void SCIPnodeGetBdChgsAfterDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int start, int *nbranchvars, int branchvarssize)
Definition: tree.c:7952
type definitions for branch and bound tree
SCIP_RETCODE SCIPtreeBranchVarNary(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: tree.c:5893
SCIP_RETCODE SCIPnodeReleaseLPIState(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:266
SCIP_RETCODE SCIPtreeStartProbing(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob, SCIP_Bool strongbranching)
Definition: tree.c:6424
SCIP_RETCODE SCIPtreeFree(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4847
SCIP_RETCODE SCIPnodeCaptureLPIState(SCIP_NODE *node, int nuses)
Definition: tree.c:238
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8375
type definitions for storing and manipulating the main problem
SCIP_NODESEL * SCIPtreeGetNodesel(SCIP_TREE *tree)
Definition: tree.c:5087
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition: tree.c:8227
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8453
SCIP_RETCODE SCIPtreeClear(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4896
type definitions for propagators
SCIP_RETCODE SCIPtreeStoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:7018
SCIP_RETCODE SCIPtreeFreePresolvingRoot(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable)
Definition: tree.c:5044
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2078
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:6649
#define SCIP_Real
Definition: def.h:177
type definitions for branching and inference history
SCIP_RETCODE SCIPnodeAddCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition: tree.c:1599
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8442
SCIP_RETCODE SCIPnodeAddHoleinfer(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_CONS *infercons, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool probingchange, SCIP_Bool *added)
Definition: tree.c:2107
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
Definition: tree.c:7095
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
Definition: tree.c:8237
SCIP_RETCODE SCIPnodeUpdateLowerboundLP(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp)
Definition: tree.c:2400
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8464
SCIP_RETCODE SCIPnodePropagateImplics(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *cutoff)
Definition: tree.c:2468
type definitions for collecting primal CIP solutions and primal informations
SCIP_RETCODE SCIPtreeLoadProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:6568
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition: tree.c:8247
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
void SCIPchildChgNodeselPrio(SCIP_TREE *tree, SCIP_NODE *child, SCIP_Real priority)
Definition: tree.c:2434
SCIP_RETCODE SCIPtreeRestoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:7062
SCIP_RETCODE SCIPtreeEndProbing(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRIMAL *primal, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable)
Definition: tree.c:6857
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition: tree.c:7121
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7245
type definitions for constraints and constraint handlers
void SCIPnodeGetConsProps(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int *nconspropvars, int conspropvarssize)
Definition: tree.c:7864
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5361
SCIP_RETCODE SCIPtreeBranchVarHole(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: tree.c:5751
memory allocation routines