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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file 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 "scip/def.h"
30 #include "blockmemshell/memory.h"
31 #include "scip/type_set.h"
32 #include "scip/type_stat.h"
33 #include "scip/type_cons.h"
34 #include "scip/type_event.h"
35 #include "scip/type_lp.h"
36 #include "scip/type_var.h"
37 #include "scip/type_prob.h"
38 #include "scip/type_primal.h"
39 #include "scip/type_tree.h"
40 #include "scip/type_reopt.h"
41 #include "scip/type_branch.h"
42 #include "scip/type_prop.h"
43 #include "scip/type_implics.h"
44 #include "scip/type_history.h"
46 #include "scip/pub_tree.h"
47 
48 #ifndef NDEBUG
49 #include "scip/struct_tree.h"
50 #endif
51 
52 #ifdef __cplusplus
53 extern "C" {
54 #endif
55 
56 
57 /*
58  * Node methods
59  */
60 
61 /** creates a child node of the focus node */
62 extern
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 */
74 extern
76  SCIP_NODE** node, /**< node data */
77  BMS_BLKMEM* blkmem, /**< block memory buffer */
78  SCIP_SET* set, /**< global SCIP settings */
79  SCIP_STAT* stat, /**< problem statistics */
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 */
86 extern
88  SCIP_NODE* node, /**< fork/subroot node */
89  int nuses /**< number to add to the usage counter */
90  );
91 
92 /** decreases the reference counter of the LP state in the fork or subroot node */
93 extern
95  SCIP_NODE* node, /**< fork/subroot node */
96  BMS_BLKMEM* blkmem, /**< block memory buffers */
97  SCIP_LP* lp /**< current LP data */
98  );
99 
100 /** installs a child, a sibling, or a leaf node as the new focus node */
101 extern
103  SCIP_NODE** node, /**< pointer to node to focus (or NULL to remove focus); the node
104  * is freed, if it was cut off due to a cut off subtree */
105  BMS_BLKMEM* blkmem, /**< block memory */
106  SCIP_SET* set, /**< global SCIP settings */
107  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
108  SCIP_STAT* stat, /**< problem statistics */
109  SCIP_PROB* transprob, /**< transformed problem */
110  SCIP_PROB* origprob, /**< original problem */
111  SCIP_PRIMAL* primal, /**< primal data */
112  SCIP_TREE* tree, /**< branch and bound tree */
113  SCIP_REOPT* reopt, /**< reoptimization data structure */
114  SCIP_LP* lp, /**< current LP data */
115  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
116  SCIP_CONFLICT* conflict, /**< conflict analysis data */
117  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
118  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
119  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
120  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
121  SCIP_Bool* cutoff, /**< pointer to store whether the given node can be cut off */
122  SCIP_Bool postponed, /**< was the current focus node postponed? */
123  SCIP_Bool exitsolve /**< are we in exitsolve stage, so we only need to loose the children */
124  );
125 
126 /** cuts off node and whole sub tree from branch and bound tree */
127 extern
129  SCIP_NODE* node, /**< node that should be cut off */
130  SCIP_SET* set, /**< global SCIP settings */
131  SCIP_STAT* stat, /**< problem statistics */
132  SCIP_TREE* tree, /**< branch and bound tree */
133  SCIP_PROB* transprob, /**< transformed problem after presolve */
134  SCIP_PROB* origprob, /**< original problem */
135  SCIP_REOPT* reopt, /**< reoptimization data structure */
136  SCIP_LP* lp, /**< current LP */
137  BMS_BLKMEM* blkmem /**< block memory */
138  );
139 
140 /** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
141 extern
143  SCIP_NODE* node, /**< node that should be propagated again */
144  SCIP_SET* set, /**< global SCIP settings */
145  SCIP_STAT* stat, /**< problem statistics */
146  SCIP_TREE* tree /**< branch and bound tree */
147  );
148 
149 /** marks node, that it is completely propagated in the current repropagation subtree level */
150 extern
152  SCIP_NODE* node, /**< node that should be propagated again */
153  SCIP_TREE* tree /**< branch and bound tree */
154  );
155 
156 /** adds constraint locally to the node and captures it; activates constraint, if node is active;
157  * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
158  */
159 extern
161  SCIP_NODE* node, /**< node to add constraint to */
162  BMS_BLKMEM* blkmem, /**< block memory */
163  SCIP_SET* set, /**< global SCIP settings */
164  SCIP_STAT* stat, /**< problem statistics */
165  SCIP_TREE* tree, /**< branch and bound tree */
166  SCIP_CONS* cons /**< constraint to add */
167  );
168 
169 /** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
170  * at the node; captures constraint; disables constraint, if node is active
171  */
172 extern
174  SCIP_NODE* node, /**< node to add constraint to */
175  BMS_BLKMEM* blkmem, /**< block memory */
176  SCIP_SET* set, /**< global SCIP settings */
177  SCIP_STAT* stat, /**< problem statistics */
178  SCIP_TREE* tree, /**< branch and bound tree */
179  SCIP_CONS* cons /**< constraint to locally delete */
180  );
181 
182 /** return all bound changes based on constraint propagation; stop saving the bound changes if we reach a branching
183  * decision based on a dual information
184  */
185 extern
187  SCIP_NODE* node, /**< node */
188  SCIP_VAR** vars, /**< array of variables on which constraint propagation triggers a bound change */
189  SCIP_Real* varbounds, /**< array of bounds set by constraint propagation */
190  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes set by constraint propagation */
191  int* nconspropvars, /**< number of variables on which constraint propagation triggers a bound change
192  * if this is larger than the array size, arrays should be reallocated and method
193  * should be called again */
194  int conspropvarssize /**< available slots in arrays */
195  );
196 
197 /** gets all bound changes applied after the first bound change based on dual information.
198  *
199  * @note: currently, we can only detect bound changes based in dual information if they arise from strong branching.
200  */
201 extern
203  SCIP_NODE* node, /**< node */
204  SCIP_VAR** vars, /**< array of variables on which the branching has been performed in the parent node */
205  SCIP_Real* varbounds, /**< array of bounds which the branching in the parent node set */
206  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes which the branching in the parent node set */
207  int start, /**< first free slot in the arrays */
208  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
209  * if this is larger than the array size, arrays should be reallocated and method
210  * should be called again */
211  int branchvarssize /**< available slots in arrays */
212  );
213 
214 /** adds bound change with inference information to focus node, child of focus node, or probing node;
215  * if possible, adjusts bound to integral value;
216  * at most one of infercons and inferprop may be non-NULL
217  */
218 extern
220  SCIP_NODE* node, /**< node to add bound change to */
221  BMS_BLKMEM* blkmem, /**< block memory */
222  SCIP_SET* set, /**< global SCIP settings */
223  SCIP_STAT* stat, /**< problem statistics */
224  SCIP_PROB* transprob, /**< transformed problem after presolve */
225  SCIP_PROB* origprob, /**< original problem */
226  SCIP_TREE* tree, /**< branch and bound tree */
227  SCIP_REOPT* reopt, /**< reoptimization data structure */
228  SCIP_LP* lp, /**< current LP data */
229  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
230  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
231  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
232  SCIP_VAR* var, /**< variable to change the bounds for */
233  SCIP_Real newbound, /**< new value for bound */
234  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
235  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
236  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
237  int inferinfo, /**< user information for inference to help resolving the conflict */
238  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
239  );
240 
241 /** adds bound change to focus node, or child of focus node, or probing node;
242  * if possible, adjusts bound to integral value
243  */
244 extern
246  SCIP_NODE* node, /**< node to add bound change to */
247  BMS_BLKMEM* blkmem, /**< block memory */
248  SCIP_SET* set, /**< global SCIP settings */
249  SCIP_STAT* stat, /**< problem statistics */
250  SCIP_PROB* transprob, /**< transformed problem after presolve */
251  SCIP_PROB* origprob, /**< original problem */
252  SCIP_TREE* tree, /**< branch and bound tree */
253  SCIP_REOPT* reopt, /**< reoptimization data structure */
254  SCIP_LP* lp, /**< current LP data */
255  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
256  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
257  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
258  SCIP_VAR* var, /**< variable to change the bounds for */
259  SCIP_Real newbound, /**< new value for bound */
260  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
261  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
262  );
263 
264 /** adds hole with inference information to focus node, child of focus node, or probing node;
265  * if possible, adjusts bound to integral value;
266  * at most one of infercons and inferprop may be non-NULL
267  */
269  SCIP_NODE* node, /**< node to add bound change to */
270  BMS_BLKMEM* blkmem, /**< block memory */
271  SCIP_SET* set, /**< global SCIP settings */
272  SCIP_STAT* stat, /**< problem statistics */
273  SCIP_TREE* tree, /**< branch and bound tree */
274  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
275  SCIP_VAR* var, /**< variable to change the bounds for */
276  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
277  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
278  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
279  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
280  int inferinfo, /**< user information for inference to help resolving the conflict */
281  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
282  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
283  );
284 
285 /** adds hole change to focus node, or child of focus node */
286 extern
288  SCIP_NODE* node, /**< node to add bound change to */
289  BMS_BLKMEM* blkmem, /**< block memory */
290  SCIP_SET* set, /**< global SCIP settings */
291  SCIP_STAT* stat, /**< problem statistics */
292  SCIP_TREE* tree, /**< branch and bound tree */
293  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
294  SCIP_VAR* var, /**< variable to change the bounds for */
295  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
296  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
297  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
298  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
299  );
300 
301 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
302 extern
304  SCIP_NODE* node, /**< node to update lower bound for */
305  SCIP_STAT* stat, /**< problem statistics */
306  SCIP_SET* set, /**< global SCIP settings */
307  SCIP_TREE* tree, /**< branch and bound tree */
308  SCIP_PROB* transprob, /**< transformed problem data */
309  SCIP_PROB* origprob, /**< original problem */
310  SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
311  );
312 
313 /** updates lower bound of node using lower bound of LP */
314 extern
316  SCIP_NODE* node, /**< node to set lower bound for */
317  SCIP_SET* set, /**< global SCIP settings */
318  SCIP_STAT* stat, /**< problem statistics */
319  SCIP_TREE* tree, /**< branch and bound tree */
320  SCIP_PROB* transprob, /**< transformed problem after presolve */
321  SCIP_PROB* origprob, /**< original problem */
322  SCIP_LP* lp /**< LP data */
323  );
324 
325 /** change the node selection priority of the given child */
326 extern
328  SCIP_TREE* tree, /**< branch and bound tree */
329  SCIP_NODE* child, /**< child to update the node selection priority */
330  SCIP_Real priority /**< node selection priority value */
331  );
332 
333 
334 /** sets the node's estimated bound to the new value */
335 extern
337  SCIP_NODE* node, /**< node to update lower bound for */
338  SCIP_SET* set, /**< global SCIP settings */
339  SCIP_Real newestimate /**< new estimated bound for the node */
340  );
341 
342 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
343 extern
345  SCIP_NODE* node, /**< node to propagate implications on */
346  BMS_BLKMEM* blkmem, /**< block memory */
347  SCIP_SET* set, /**< global SCIP settings */
348  SCIP_STAT* stat, /**< problem statistics */
349  SCIP_PROB* transprob, /**< transformed problem after presolve */
350  SCIP_PROB* origprob, /**< original problem */
351  SCIP_TREE* tree, /**< branch and bound tree */
352  SCIP_REOPT* reopt, /**< reoptimization data structure */
353  SCIP_LP* lp, /**< current LP data */
354  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
355  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
356  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
357  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
358  );
359 
360 /** returns all bound changes based on dual information.
361  *
362  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
363  * method to ensure optimality within reoptimization.
364  *
365  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
366  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
367  *
368  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
369  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
370  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
371  */
372 extern
374  SCIP_NODE* node, /**< node data */
375  SCIP_VAR** vars, /**< array of variables on which the bound change is based on dual information */
376  SCIP_Real* bounds, /**< array of bounds which are based on dual information */
377  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which are based on dual information */
378  int* nvars, /**< number of variables on which the bound change is based on dual information
379  * if this is larger than the array size, arrays should be reallocated and method
380  * should be called again */
381  int varssize /**< available slots in arrays */
382  );
383 
384 /** returns the number of bound changes based on dual information.
385  *
386  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
387  * method to ensure optimality within reoptimization.
388  *
389  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
390  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
391  *
392  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
393  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
394  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
395  */
396 extern
398  SCIP_NODE* node
399  );
400 
401 /*
402  * Tree methods
403  */
404 
405 /** creates an initialized tree data structure */
406 extern
408  SCIP_TREE** tree, /**< pointer to tree data structure */
409  BMS_BLKMEM* blkmem, /**< block memory buffers */
410  SCIP_SET* set, /**< global SCIP settings */
411  SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */
412  );
413 
414 /** frees tree data structure */
415 extern
417  SCIP_TREE** tree, /**< pointer to tree data structure */
418  BMS_BLKMEM* blkmem, /**< block memory buffers */
419  SCIP_SET* set, /**< global SCIP settings */
420  SCIP_STAT* stat, /**< problem statistics */
421  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
422  SCIP_LP* lp /**< current LP data */
423  );
424 
425 /** clears and resets tree data structure and deletes all nodes */
426 extern
428  SCIP_TREE* tree, /**< tree data structure */
429  BMS_BLKMEM* blkmem, /**< block memory buffers */
430  SCIP_SET* set, /**< global SCIP settings */
431  SCIP_STAT* stat, /**< problem statistics */
432  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
433  SCIP_LP* lp /**< current LP data */
434  );
435 
436 /** creates the root node of the tree and puts it into the leaves queue */
437 extern
439  SCIP_TREE* tree, /**< tree data structure */
440  SCIP_REOPT* reopt, /**< reoptimization data structure */
441  BMS_BLKMEM* blkmem, /**< block memory buffers */
442  SCIP_SET* set, /**< global SCIP settings */
443  SCIP_STAT* stat, /**< problem statistics */
444  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
445  SCIP_LP* lp /**< current LP data */
446  );
447 
448 /** creates a temporary presolving root node of the tree and installs it as focus node */
449 extern
451  SCIP_TREE* tree, /**< tree data structure */
452  SCIP_REOPT* reopt, /**< reoptimization data structure */
453  BMS_BLKMEM* blkmem, /**< block memory buffers */
454  SCIP_SET* set, /**< global SCIP settings */
455  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
456  SCIP_STAT* stat, /**< problem statistics */
457  SCIP_PROB* transprob, /**< transformed problem */
458  SCIP_PROB* origprob, /**< original problem */
459  SCIP_PRIMAL* primal, /**< primal data */
460  SCIP_LP* lp, /**< current LP data */
461  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
462  SCIP_CONFLICT* conflict, /**< conflict analysis data */
463  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
464  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
465  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
466  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
467  );
468 
469 /** frees the temporary presolving root and resets tree data structure */
470 extern
472  SCIP_TREE* tree, /**< tree data structure */
473  SCIP_REOPT* reopt, /**< reoptimization data structure */
474  BMS_BLKMEM* blkmem, /**< block memory buffers */
475  SCIP_SET* set, /**< global SCIP settings */
476  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
477  SCIP_STAT* stat, /**< problem statistics */
478  SCIP_PROB* transprob, /**< transformed problem */
479  SCIP_PROB* origprob, /**< original problem */
480  SCIP_PRIMAL* primal, /**< primal data */
481  SCIP_LP* lp, /**< current LP data */
482  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
483  SCIP_CONFLICT* conflict, /**< conflict analysis data */
484  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
485  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
486  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
487  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
488  );
489 
490 /** returns the node selector associated with the given node priority queue */
491 extern
493  SCIP_TREE* tree /**< branch and bound tree */
494  );
495 
496 /** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
497 extern
499  SCIP_TREE* tree, /**< branch and bound tree */
500  SCIP_SET* set, /**< global SCIP settings */
501  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
502  SCIP_STAT* stat, /**< problem statistics */
503  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
504  );
505 
506 /** cuts off nodes with lower bound not better than given upper bound */
507 extern
509  SCIP_TREE* tree, /**< branch and bound tree */
510  SCIP_REOPT* reopt, /**< reoptimization data structure */
511  BMS_BLKMEM* blkmem, /**< block memory */
512  SCIP_SET* set, /**< global SCIP settings */
513  SCIP_STAT* stat, /**< dynamic problem statistics */
514  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
515  SCIP_LP* lp, /**< current LP data */
516  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
517  );
518 
519 /** constructs the LP relaxation of the focus node */
520 extern
522  SCIP_TREE* tree, /**< branch and bound tree */
523  BMS_BLKMEM* blkmem, /**< block memory */
524  SCIP_SET* set, /**< global SCIP settings */
525  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
526  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
527  SCIP_LP* lp, /**< current LP data */
528  SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
529  );
530 
531 /** loads LP state for fork/subroot of the focus node */
532 extern
534  SCIP_TREE* tree, /**< branch and bound tree */
535  BMS_BLKMEM* blkmem, /**< block memory buffers */
536  SCIP_SET* set, /**< global SCIP settings */
537  SCIP_STAT* stat, /**< dynamic problem statistics */
538  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
539  SCIP_LP* lp /**< current LP data */
540  );
541 
542 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
543  * this node selection priority can be given to the SCIPcreateChild() call
544  */
545 extern
547  SCIP_TREE* tree, /**< branch and bound tree */
548  SCIP_SET* set, /**< global SCIP settings */
549  SCIP_STAT* stat, /**< dynamic problem statistics */
550  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
551  SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed
552  * fixed should only be used, when both bounds changed
553  */
554  SCIP_Real targetvalue /**< new value of the variable in the child node */
555  );
556 
557 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
558  * branching; this estimate can be given to the SCIPcreateChild() call
559  */
560 extern
562  SCIP_TREE* tree, /**< branch and bound tree */
563  SCIP_SET* set, /**< global SCIP settings */
564  SCIP_STAT* stat, /**< dynamic problem statistics */
565  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
566  SCIP_Real targetvalue /**< new value of the variable in the child node */
567  );
568 
569 /** branches on a variable x
570  * if x is a continuous variable, then two child nodes will be created
571  * (x <= x', x >= x')
572  * but if the bounds of x are such that their relative difference is smaller than epsilon,
573  * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
574  * i.e., no children are created
575  * if x is not a continuous variable, then:
576  * if solution value x' is fractional, two child nodes will be created
577  * (x <= floor(x'), x >= ceil(x')),
578  * if solution value is integral, the x' is equal to lower or upper bound of the branching
579  * variable and the bounds of x are finite, then two child nodes will be created
580  * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
581  * otherwise (up to) three child nodes will be created
582  * (x <= x'-1, x == x', x >= x'+1)
583  * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
584  * will be created (the third one would be infeasible anyway)
585  */
586 extern
588  SCIP_TREE* tree, /**< branch and bound tree */
589  SCIP_REOPT* reopt, /**< reoptimization data structure */
590  BMS_BLKMEM* blkmem, /**< block memory */
591  SCIP_SET* set, /**< global SCIP settings */
592  SCIP_STAT* stat, /**< problem statistics data */
593  SCIP_PROB* transprob, /**< transformed problem after presolve */
594  SCIP_PROB* origprob, /**< original problem */
595  SCIP_LP* lp, /**< current LP data */
596  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
597  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
598  SCIP_VAR* var, /**< variable to branch on */
599  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 */
600  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
601  SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
602  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
603  );
604 
605 /** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
606 extern
608  SCIP_TREE* tree, /**< branch and bound tree */
609  SCIP_REOPT* reopt, /**< reoptimization data structure */
610  BMS_BLKMEM* blkmem, /**< block memory */
611  SCIP_SET* set, /**< global SCIP settings */
612  SCIP_STAT* stat, /**< problem statistics data */
613  SCIP_PROB* transprob, /**< transformed problem after presolve */
614  SCIP_PROB* origprob, /**< original problem */
615  SCIP_LP* lp, /**< current LP data */
616  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
617  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
618  SCIP_VAR* var, /**< variable to branch on */
619  SCIP_Real left, /**< left side of the domain hole */
620  SCIP_Real right, /**< right side of the domain hole */
621  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
622  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
623  );
624 
625 /** n-ary branching on a variable x
626  * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
627  * The branching value is selected as in SCIPtreeBranchVar().
628  * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
629  * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
630  * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
631  * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
632  * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
633  * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
634  * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
635  *
636  * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
637  * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
638  * results in a ternary branching where the branching variable is mostly fixed in the middle child.
639  * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
640  * (except for one child if the branching value is not in the middle).
641  */
642 extern
644  SCIP_TREE* tree, /**< branch and bound tree */
645  SCIP_REOPT* reopt, /**< reoptimization data structure */
646  BMS_BLKMEM* blkmem, /**< block memory */
647  SCIP_SET* set, /**< global SCIP settings */
648  SCIP_STAT* stat, /**< problem statistics data */
649  SCIP_PROB* transprob, /**< transformed problem after presolve */
650  SCIP_PROB* origprob, /**< original problem */
651  SCIP_LP* lp, /**< current LP data */
652  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
653  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
654  SCIP_VAR* var, /**< variable to branch on */
655  SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
656  * A branching value is required for branching on continuous variables */
657  int n, /**< attempted number of children to be created, must be >= 2 */
658  SCIP_Real minwidth, /**< minimal domain width in children */
659  SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
660  int* nchildren /**< buffer to store number of created children, or NULL */
661  );
662 
663 /** adds a diving bound change to the tree together with the information if this is a bound change
664  * for the preferred direction or not
665  */
666 extern
668  SCIP_TREE* tree, /**< branch and bound tree */
669  BMS_BLKMEM* blkmem, /**< block memory buffers */
670  SCIP_VAR* var, /**< variable to apply the bound change to */
671  SCIP_BRANCHDIR dir, /**< direction of the bound change */
672  SCIP_Real value, /**< value to adjust this variable bound to */
673  SCIP_Bool preferred /**< is this a bound change for the preferred child? */
674  );
675 
676 /** get the dive bound change data for the preferred or the alternative direction */
677 extern
679  SCIP_TREE* tree, /**< branch and bound tree */
680  SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
681  SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
682  SCIP_Real** values, /**< pointer to store bound change values */
683  int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
684  SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
685  );
686 
687 /** clear the tree dive bound change data structure */
688 extern
690  SCIP_TREE* tree /**< branch and bound tree */
691  );
692 
693 /** switches to probing mode and creates a probing root */
694 extern
696  SCIP_TREE* tree, /**< branch and bound tree */
697  BMS_BLKMEM* blkmem, /**< block memory */
698  SCIP_SET* set, /**< global SCIP settings */
699  SCIP_LP* lp, /**< current LP data */
700  SCIP_RELAXATION* relaxation, /**< global relaxation data */
701  SCIP_PROB* transprob, /**< transformed problem after presolve */
702  SCIP_Bool strongbranching /**< is the probing mode used for strongbranching? */
703  );
704 
705 /** creates a new probing child node in the probing path */
706 extern
708  SCIP_TREE* tree, /**< branch and bound tree */
709  BMS_BLKMEM* blkmem, /**< block memory */
710  SCIP_SET* set, /**< global SCIP settings */
711  SCIP_LP* lp /**< current LP data */
712  );
713 
714 /** sets the LP state for the current probing node
715  *
716  * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
717  * to NULL by the method
718  *
719  * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
720  * respective information should not be set
721  */
722 extern
724  SCIP_TREE* tree, /**< branch and bound tree */
725  BMS_BLKMEM* blkmem, /**< block memory */
726  SCIP_LP* lp, /**< current LP data */
727  SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
728  SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
729  SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
730  SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
731  );
732 
733 /** loads the LP state for the current probing node */
734 extern
736  SCIP_TREE* tree, /**< branch and bound tree */
737  BMS_BLKMEM* blkmem, /**< block memory buffers */
738  SCIP_SET* set, /**< global SCIP settings */
739  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
740  SCIP_LP* lp /**< current LP data */
741  );
742 
743 /** marks the probing node to have a solved LP relaxation */
744 extern
746  SCIP_TREE* tree, /**< branch and bound tree */
747  BMS_BLKMEM* blkmem, /**< block memory */
748  SCIP_LP* lp /**< current LP data */
749  );
750 
751 /** undoes all changes to the problem applied in probing up to the given probing depth;
752  * the changes of the probing node of the given probing depth are the last ones that remain active;
753  * changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone
754  */
755 extern
757  SCIP_TREE* tree, /**< branch and bound tree */
758  SCIP_REOPT* reopt, /**< reoptimization data structure */
759  BMS_BLKMEM* blkmem, /**< block memory buffers */
760  SCIP_SET* set, /**< global SCIP settings */
761  SCIP_STAT* stat, /**< problem statistics */
762  SCIP_PROB* transprob, /**< transformed problem */
763  SCIP_PROB* origprob, /**< original problem */
764  SCIP_LP* lp, /**< current LP data */
765  SCIP_PRIMAL* primal, /**< primal data structure */
766  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
767  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
768  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
769  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
770  int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
771  );
772 
773 /** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
774  * variables and restores active constraints arrays of focus node
775  */
776 extern
778  SCIP_TREE* tree, /**< branch and bound tree */
779  SCIP_REOPT* reopt, /**< reoptimization data structure */
780  BMS_BLKMEM* blkmem, /**< block memory buffers */
781  SCIP_SET* set, /**< global SCIP settings */
782  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
783  SCIP_STAT* stat, /**< problem statistics */
784  SCIP_PROB* transprob, /**< transformed problem after presolve */
785  SCIP_PROB* origprob, /**< original problem */
786  SCIP_LP* lp, /**< current LP data */
787  SCIP_RELAXATION* relaxation, /**< global relaxation data */
788  SCIP_PRIMAL* primal, /**< primal LP data */
789  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
790  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
791  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
792  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
793  );
794 
795 /** stores relaxation solution before diving or probing */
796 extern
798  SCIP_TREE* tree, /**< branch and bound tree */
799  SCIP_SET* set, /**< global SCIP settings */
800  SCIP_RELAXATION* relaxation, /**< global relaxation data */
801  SCIP_PROB* transprob /**< transformed problem after presolve */
802  );
803 
804 /** restores relaxation solution after diving or probing */
805 extern
807  SCIP_TREE* tree, /**< branch and bound tree */
808  SCIP_SET* set, /**< global SCIP settings */
809  SCIP_RELAXATION* relaxation, /**< global relaxation data */
810  SCIP_PROB* transprob /**< transformed problem after presolve */
811  );
812 
813 
814 /** gets number of children of the focus node */
815 extern
817  SCIP_TREE* tree /**< branch and bound tree */
818  );
819 
820 /** gets number of siblings of the focus node */
821 extern
823  SCIP_TREE* tree /**< branch and bound tree */
824  );
825 
826 /** gets number of leaves in the tree (excluding children and siblings of focus nodes) */
827 extern
829  SCIP_TREE* tree /**< branch and bound tree */
830  );
831 
832 /** gets number of open nodes in the tree (children + siblings + leaves) */
833 extern
835  SCIP_TREE* tree /**< branch and bound tree */
836  );
837 
838 /** returns whether the active path goes completely down to the focus node */
839 extern
841  SCIP_TREE* tree /**< branch and bound tree */
842  );
843 
844 /** returns whether the current node is a temporary probing node */
845 extern
847  SCIP_TREE* tree /**< branch and bound tree */
848  );
849 
850 /** returns the temporary probing root node, or NULL if the we are not in probing mode */
851 extern
853  SCIP_TREE* tree /**< branch and bound tree */
854  );
855 
856 /** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
857 extern
859  SCIP_TREE* tree /**< branch and bound tree */
860  );
861 
862 /** gets focus node of the tree */
863 extern
865  SCIP_TREE* tree /**< branch and bound tree */
866  );
867 
868 /** gets depth of focus node in the tree, or -1 if no focus node exists */
869 extern
871  SCIP_TREE* tree /**< branch and bound tree */
872  );
873 
874 /** returns, whether the LP was or is to be solved in the focus node */
875 extern
877  SCIP_TREE* tree /**< branch and bound tree */
878  );
879 
880 /** sets mark to solve or to ignore the LP while processing the focus node */
881 extern
883  SCIP_TREE* tree, /**< branch and bound tree */
884  SCIP_Bool solvelp /**< should the LP be solved in focus node? */
885  );
886 
887 /** returns whether the LP of the focus node is already constructed */
888 extern
890  SCIP_TREE* tree /**< branch and bound tree */
891  );
892 
893 /** returns whether the focus node is already solved and only propagated again */
894 extern
896  SCIP_TREE* tree /**< branch and bound tree */
897  );
898 
899 /** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
900 extern
902  SCIP_TREE* tree /**< branch and bound tree */
903  );
904 
905 /** 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 */
906 extern
908  SCIP_TREE* tree /**< branch and bound tree */
909  );
910 
911 /** returns, whether the LP was or is to be solved in the current node */
912 extern
914  SCIP_TREE* tree /**< branch and bound tree */
915  );
916 
917 /** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
918 extern
920  SCIP_TREE* tree /**< branch and bound tree */
921  );
922 
923 /** gets the root node of the tree */
924 extern
926  SCIP_TREE* tree /**< branch and bound tree */
927  );
928 
929 /** returns whether we are in probing and the objective value of at least one column was changed */
930 extern
932  SCIP_TREE* tree /**< branch and bound tree */
933  );
934 
935 /** marks the current probing node to have a changed objective function */
936 extern
938  SCIP_TREE* tree /**< branch and bound tree */
939  );
940 
941 #ifdef NDEBUG
942 
943 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
944  * speed up the algorithms.
945  */
946 
947 #define SCIPtreeGetNLeaves(tree) SCIPnodepqLen((tree)->leaves)
948 #define SCIPtreeGetNChildren(tree) ((tree)->nchildren)
949 #define SCIPtreeGetNSiblings(tree) ((tree)->nsiblings)
950 #define SCIPtreeGetNNodes(tree) \
951  (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree))
952 #define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
953 #define SCIPtreeProbing(tree) ((tree)->probingroot != NULL)
954 #define SCIPtreeGetProbingRoot(tree) (tree)->probingroot
955 #define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
956 #define SCIPtreeGetFocusNode(tree) (tree)->focusnode
957 #define SCIPtreeGetFocusDepth(tree) ((tree)->focusnode != NULL ? (tree)->focusnode->depth : -1)
958 #define SCIPtreeHasFocusNodeLP(tree) (tree)->focusnodehaslp
959 #define SCIPtreeSetFocusNodeLP(tree,solvelp) ((tree)->focusnodehaslp = solvelp)
960 #define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed
961 #define SCIPtreeInRepropagation(tree) ((tree)->focusnode != NULL \
962  && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
963 #define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
964 #define SCIPtreeGetCurrentDepth(tree) ((tree)->pathlen-1)
965 #define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
966 #define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth)
967 #define SCIPtreeGetRootNode(tree) ((tree)->root)
968 #define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged)
969 #define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE)
970 
971 #endif
972 
973 
974 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
975 extern
977  SCIP_TREE* tree /**< branch and bound tree */
978  );
979 
980 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
981 extern
983  SCIP_TREE* tree /**< branch and bound tree */
984  );
985 
986 /** gets the best child of the focus node w.r.t. the node selection strategy */
987 extern
989  SCIP_TREE* tree, /**< branch and bound tree */
990  SCIP_SET* set /**< global SCIP settings */
991  );
992 
993 /** gets the best sibling of the focus node w.r.t. the node selection strategy */
994 extern
996  SCIP_TREE* tree, /**< branch and bound tree */
997  SCIP_SET* set /**< global SCIP settings */
998  );
999 
1000 /** gets the best leaf from the node queue w.r.t. the node selection strategy */
1001 extern
1003  SCIP_TREE* tree /**< branch and bound tree */
1004  );
1005 
1006 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
1007 extern
1009  SCIP_TREE* tree, /**< branch and bound tree */
1010  SCIP_SET* set /**< global SCIP settings */
1011  );
1012 
1013 /** gets the minimal lower bound of all nodes in the tree */
1014 extern
1016  SCIP_TREE* tree, /**< branch and bound tree */
1017  SCIP_SET* set /**< global SCIP settings */
1018  );
1019 
1020 /** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */
1021 extern
1023  SCIP_TREE* tree, /**< branch and bound tree */
1024  SCIP_SET* set /**< global SCIP settings */
1025  );
1026 
1027 /** gets the average lower bound of all nodes in the tree */
1028 extern
1030  SCIP_TREE* tree, /**< branch and bound tree */
1031  SCIP_Real cutoffbound /**< global cutoff bound */
1032  );
1033 
1034 #ifdef __cplusplus
1035 }
1036 #endif
1037 
1038 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_RETCODE SCIPnodeFree(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: tree.c:1027
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: tree.c:6412
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
Definition: tree.c:5027
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6193
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:4933
void SCIPnodeGetDualBoundchgs(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_BOUNDTYPE *boundtypes, int *nvars, int varssize)
Definition: tree.c:7549
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8335
SCIP_RETCODE SCIPnodeDelCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition: tree.c:1608
public methods for branch and bound tree
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7198
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:980
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:6437
type definitions for implications, variable bounds, and cliques
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:5349
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
Definition: tree.c:8249
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7062
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition: tree.c:8259
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:6746
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:1769
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8215
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7126
struct SCIP_LPiNorms SCIP_LPINORMS
Definition: type_lpi.h:98
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPtreeCreate(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: tree.c:4701
type definitions for global SCIP settings
SCIP_NODE * SCIPtreeGetProbingRoot(SCIP_TREE *tree)
Definition: tree.c:8202
SCIP_RETCODE SCIPtreeLoadLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:3475
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8232
type definitions for collecting reoptimization information
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8307
type definitions for branching rules
type definitions for problem statistics
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition: tree.c:8132
SCIP_Bool SCIPtreeIsPathComplete(SCIP_TREE *tree)
Definition: tree.c:8172
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8270
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition: tree.c:1146
type definitions for LP management
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition: tree.c:8189
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:4241
void SCIPnodeMarkPropagated(SCIP_NODE *node, SCIP_TREE *tree)
Definition: tree.c:1232
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: tree.c:5140
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7089
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:3347
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition: tree.c:7116
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition: tree.c:8280
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:2299
struct SCIP_LPiState SCIP_LPISTATE
Definition: type_lpi.h:97
data structures for branch and bound tree
type definitions for problem variables
int SCIPnodeGetNDualBndchgs(SCIP_NODE *node)
Definition: tree.c:7504
type definitions for managing events
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1206
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:2171
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8324
#define SCIP_Bool
Definition: def.h:69
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8346
SCIP_Real SCIPtreeGetAvgLowerbound(SCIP_TREE *tree, SCIP_Real cutoffbound)
Definition: tree.c:7250
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6248
SCIP_RETCODE SCIPtreeFree(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4780
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: tree.c:6225
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
Definition: tree.c:2395
void SCIPnodeGetBdChgsAfterDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int start, int *nbranchvars, int branchvarssize)
Definition: tree.c:7867
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:5822
SCIP_RETCODE SCIPnodeReleaseLPIState(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:263
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:6347
SCIP_RETCODE SCIPtreeCreateRoot(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4888
SCIP_RETCODE SCIPnodeCaptureLPIState(SCIP_NODE *node, int nuses)
Definition: tree.c:235
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8290
type definitions for storing and manipulating the main problem
SCIP_NODESEL * SCIPtreeGetNodesel(SCIP_TREE *tree)
Definition: tree.c:5017
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition: tree.c:8142
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8368
type definitions for propagators
SCIP_RETCODE SCIPtreeStoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:6941
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:4974
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:2021
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:6572
#define SCIP_Real
Definition: def.h:157
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:1565
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8357
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:2050
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
Definition: tree.c:7010
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
Definition: tree.c:8152
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:2343
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8379
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:2409
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:6491
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition: tree.c:8162
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:426
void SCIPchildChgNodeselPrio(SCIP_TREE *tree, SCIP_NODE *child, SCIP_Real priority)
Definition: tree.c:2377
SCIP_RETCODE SCIPtreeRestoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:6978
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:6780
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition: tree.c:7036
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7160
SCIP_RETCODE SCIPtreeCutoff(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: tree.c:5055
SCIP_RETCODE SCIPtreeClear(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4828
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:7779
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5290
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:5680
memory allocation routines