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-2017 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 email to 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 /** returns all constraints added to a given node */
183 extern
185  SCIP_NODE* node, /**< node */
186  SCIP_CONS** addedconss, /**< array to store the constraints */
187  int* naddedconss, /**< number of added constraints */
188  int addedconsssize /**< size of the constraint array */
189  );
190 
191 /** return all bound changes based on constraint propagation; stop saving the bound changes if we reach a branching
192  * decision based on a dual information
193  */
194 extern
196  SCIP_NODE* node, /**< node */
197  SCIP_VAR** vars, /**< array of variables on which constraint propagation triggers a bound change */
198  SCIP_Real* varbounds, /**< array of bounds set by constraint propagation */
199  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes set by constraint propagation */
200  int* nconspropvars, /**< number of variables on which constraint propagation triggers a bound change
201  * if this is larger than the array size, arrays should be reallocated and method
202  * should be called again */
203  int conspropvarssize /**< available slots in arrays */
204  );
205 
206 /** gets all bound changes applied after the first bound change based on dual information.
207  *
208  * @note: currently, we can only detect bound changes based in dual information if they arise from strong branching.
209  */
210 extern
212  SCIP_NODE* node, /**< node */
213  SCIP_VAR** vars, /**< array of variables on which the branching has been performed in the parent node */
214  SCIP_Real* varbounds, /**< array of bounds which the branching in the parent node set */
215  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes which the branching in the parent node set */
216  int start, /**< first free slot in the arrays */
217  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
218  * if this is larger than the array size, arrays should be reallocated and method
219  * should be called again */
220  int branchvarssize /**< available slots in arrays */
221  );
222 
223 /** returns the number of added constraints to the given node */
224 extern
226  SCIP_NODE* node
227  );
228 
229 /** adds bound change with inference information to focus node, child of focus node, or probing node;
230  * if possible, adjusts bound to integral value;
231  * at most one of infercons and inferprop may be non-NULL
232  */
233 extern
235  SCIP_NODE* node, /**< node to add bound change to */
236  BMS_BLKMEM* blkmem, /**< block memory */
237  SCIP_SET* set, /**< global SCIP settings */
238  SCIP_STAT* stat, /**< problem statistics */
239  SCIP_PROB* transprob, /**< transformed problem after presolve */
240  SCIP_PROB* origprob, /**< original problem */
241  SCIP_TREE* tree, /**< branch and bound tree */
242  SCIP_REOPT* reopt, /**< reoptimization data structure */
243  SCIP_LP* lp, /**< current LP data */
244  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
245  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
246  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
247  SCIP_VAR* var, /**< variable to change the bounds for */
248  SCIP_Real newbound, /**< new value for bound */
249  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
250  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
251  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
252  int inferinfo, /**< user information for inference to help resolving the conflict */
253  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
254  );
255 
256 /** adds bound change to focus node, or child of focus node, or probing node;
257  * if possible, adjusts bound to integral value
258  */
259 extern
261  SCIP_NODE* node, /**< node to add bound change to */
262  BMS_BLKMEM* blkmem, /**< block memory */
263  SCIP_SET* set, /**< global SCIP settings */
264  SCIP_STAT* stat, /**< problem statistics */
265  SCIP_PROB* transprob, /**< transformed problem after presolve */
266  SCIP_PROB* origprob, /**< original problem */
267  SCIP_TREE* tree, /**< branch and bound tree */
268  SCIP_REOPT* reopt, /**< reoptimization data structure */
269  SCIP_LP* lp, /**< current LP data */
270  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
271  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
272  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
273  SCIP_VAR* var, /**< variable to change the bounds for */
274  SCIP_Real newbound, /**< new value for bound */
275  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
276  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
277  );
278 
279 /** adds hole with inference information to focus node, child of focus node, or probing node;
280  * if possible, adjusts bound to integral value;
281  * at most one of infercons and inferprop may be non-NULL
282  */
284  SCIP_NODE* node, /**< node to add bound change to */
285  BMS_BLKMEM* blkmem, /**< block memory */
286  SCIP_SET* set, /**< global SCIP settings */
287  SCIP_STAT* stat, /**< problem statistics */
288  SCIP_TREE* tree, /**< branch and bound tree */
289  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
290  SCIP_VAR* var, /**< variable to change the bounds for */
291  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
292  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
293  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
294  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
295  int inferinfo, /**< user information for inference to help resolving the conflict */
296  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
297  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
298  );
299 
300 /** adds hole change to focus node, or child of focus node */
301 extern
303  SCIP_NODE* node, /**< node to add bound change to */
304  BMS_BLKMEM* blkmem, /**< block memory */
305  SCIP_SET* set, /**< global SCIP settings */
306  SCIP_STAT* stat, /**< problem statistics */
307  SCIP_TREE* tree, /**< branch and bound tree */
308  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
309  SCIP_VAR* var, /**< variable to change the bounds for */
310  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
311  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
312  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
313  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
314  );
315 
316 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
317 extern
319  SCIP_NODE* node, /**< node to update lower bound for */
320  SCIP_STAT* stat, /**< problem statistics */
321  SCIP_SET* set, /**< global SCIP settings */
322  SCIP_TREE* tree, /**< branch and bound tree */
323  SCIP_PROB* transprob, /**< transformed problem data */
324  SCIP_PROB* origprob, /**< original problem */
325  SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
326  );
327 
328 /** updates lower bound of node using lower bound of LP */
329 extern
331  SCIP_NODE* node, /**< node to set lower bound for */
332  SCIP_SET* set, /**< global SCIP settings */
333  SCIP_STAT* stat, /**< problem statistics */
334  SCIP_TREE* tree, /**< branch and bound tree */
335  SCIP_PROB* transprob, /**< transformed problem after presolve */
336  SCIP_PROB* origprob, /**< original problem */
337  SCIP_LP* lp /**< LP data */
338  );
339 
340 /** change the node selection priority of the given child */
341 extern
343  SCIP_TREE* tree, /**< branch and bound tree */
344  SCIP_NODE* child, /**< child to update the node selection priority */
345  SCIP_Real priority /**< node selection priority value */
346  );
347 
348 
349 /** sets the node's estimated bound to the new value */
350 extern
352  SCIP_NODE* node, /**< node to update lower bound for */
353  SCIP_SET* set, /**< global SCIP settings */
354  SCIP_Real newestimate /**< new estimated bound for the node */
355  );
356 
357 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
358 extern
360  SCIP_NODE* node, /**< node to propagate implications on */
361  BMS_BLKMEM* blkmem, /**< block memory */
362  SCIP_SET* set, /**< global SCIP settings */
363  SCIP_STAT* stat, /**< problem statistics */
364  SCIP_PROB* transprob, /**< transformed problem after presolve */
365  SCIP_PROB* origprob, /**< original problem */
366  SCIP_TREE* tree, /**< branch and bound tree */
367  SCIP_REOPT* reopt, /**< reoptimization data structure */
368  SCIP_LP* lp, /**< current LP data */
369  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
370  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
371  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
372  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
373  );
374 
375 /** returns all bound changes based on dual information.
376  *
377  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
378  * method to ensure optimality within reoptimization.
379  *
380  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
381  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
382  *
383  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
384  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
385  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
386  */
387 extern
389  SCIP_NODE* node, /**< node data */
390  SCIP_VAR** vars, /**< array of variables on which the bound change is based on dual information */
391  SCIP_Real* bounds, /**< array of bounds which are based on dual information */
392  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which are based on dual information */
393  int* nvars, /**< number of variables on which the bound change is based on dual information
394  * if this is larger than the array size, arrays should be reallocated and method
395  * should be called again */
396  int varssize /**< available slots in arrays */
397  );
398 
399 /** returns the number of bound changes based on dual information.
400  *
401  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
402  * method to ensure optimality within reoptimization.
403  *
404  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
405  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
406  *
407  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
408  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
409  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
410  */
411 extern
413  SCIP_NODE* node
414  );
415 
416 /*
417  * Tree methods
418  */
419 
420 /** creates an initialized tree data structure */
421 extern
423  SCIP_TREE** tree, /**< pointer to tree data structure */
424  BMS_BLKMEM* blkmem, /**< block memory buffers */
425  SCIP_SET* set, /**< global SCIP settings */
426  SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */
427  );
428 
429 /** frees tree data structure */
430 extern
432  SCIP_TREE** tree, /**< pointer to tree data structure */
433  BMS_BLKMEM* blkmem, /**< block memory buffers */
434  SCIP_SET* set, /**< global SCIP settings */
435  SCIP_STAT* stat, /**< problem statistics */
436  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
437  SCIP_LP* lp /**< current LP data */
438  );
439 
440 /** clears and resets tree data structure and deletes all nodes */
441 extern
443  SCIP_TREE* tree, /**< tree data structure */
444  BMS_BLKMEM* blkmem, /**< block memory buffers */
445  SCIP_SET* set, /**< global SCIP settings */
446  SCIP_STAT* stat, /**< problem statistics */
447  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
448  SCIP_LP* lp /**< current LP data */
449  );
450 
451 /** creates the root node of the tree and puts it into the leaves queue */
452 extern
454  SCIP_TREE* tree, /**< tree data structure */
455  SCIP_REOPT* reopt, /**< reoptimization data structure */
456  BMS_BLKMEM* blkmem, /**< block memory buffers */
457  SCIP_SET* set, /**< global SCIP settings */
458  SCIP_STAT* stat, /**< problem statistics */
459  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
460  SCIP_LP* lp /**< current LP data */
461  );
462 
463 /** creates a temporary presolving root node of the tree and installs it as focus node */
464 extern
466  SCIP_TREE* tree, /**< tree data structure */
467  SCIP_REOPT* reopt, /**< reoptimization data structure */
468  BMS_BLKMEM* blkmem, /**< block memory buffers */
469  SCIP_SET* set, /**< global SCIP settings */
470  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
471  SCIP_STAT* stat, /**< problem statistics */
472  SCIP_PROB* transprob, /**< transformed problem */
473  SCIP_PROB* origprob, /**< original problem */
474  SCIP_PRIMAL* primal, /**< primal data */
475  SCIP_LP* lp, /**< current LP data */
476  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
477  SCIP_CONFLICT* conflict, /**< conflict analysis data */
478  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
479  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
480  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
481  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
482  );
483 
484 /** frees the temporary presolving root and resets tree data structure */
485 extern
487  SCIP_TREE* tree, /**< tree data structure */
488  SCIP_REOPT* reopt, /**< reoptimization data structure */
489  BMS_BLKMEM* blkmem, /**< block memory buffers */
490  SCIP_SET* set, /**< global SCIP settings */
491  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
492  SCIP_STAT* stat, /**< problem statistics */
493  SCIP_PROB* transprob, /**< transformed problem */
494  SCIP_PROB* origprob, /**< original problem */
495  SCIP_PRIMAL* primal, /**< primal data */
496  SCIP_LP* lp, /**< current LP data */
497  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
498  SCIP_CONFLICT* conflict, /**< conflict analysis data */
499  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
500  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
501  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
502  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
503  );
504 
505 /** returns the node selector associated with the given node priority queue */
506 extern
508  SCIP_TREE* tree /**< branch and bound tree */
509  );
510 
511 /** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
512 extern
514  SCIP_TREE* tree, /**< branch and bound tree */
515  SCIP_SET* set, /**< global SCIP settings */
516  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
517  SCIP_STAT* stat, /**< problem statistics */
518  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
519  );
520 
521 /** cuts off nodes with lower bound not better than given upper bound */
522 extern
524  SCIP_TREE* tree, /**< branch and bound tree */
525  SCIP_REOPT* reopt, /**< reoptimization data structure */
526  BMS_BLKMEM* blkmem, /**< block memory */
527  SCIP_SET* set, /**< global SCIP settings */
528  SCIP_STAT* stat, /**< dynamic problem statistics */
529  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
530  SCIP_LP* lp, /**< current LP data */
531  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
532  );
533 
534 /** constructs the LP relaxation of the focus node */
535 extern
537  SCIP_TREE* tree, /**< branch and bound tree */
538  BMS_BLKMEM* blkmem, /**< block memory */
539  SCIP_SET* set, /**< global SCIP settings */
540  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
541  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
542  SCIP_LP* lp, /**< current LP data */
543  SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
544  );
545 
546 /** loads LP state for fork/subroot of the focus node */
547 extern
549  SCIP_TREE* tree, /**< branch and bound tree */
550  BMS_BLKMEM* blkmem, /**< block memory buffers */
551  SCIP_SET* set, /**< global SCIP settings */
552  SCIP_STAT* stat, /**< dynamic problem statistics */
553  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
554  SCIP_LP* lp /**< current LP data */
555  );
556 
557 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
558  * this node selection priority 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_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed
567  * fixed should only be used, when both bounds changed
568  */
569  SCIP_Real targetvalue /**< new value of the variable in the child node */
570  );
571 
572 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
573  * branching; this estimate can be given to the SCIPcreateChild() call
574  */
575 extern
577  SCIP_TREE* tree, /**< branch and bound tree */
578  SCIP_SET* set, /**< global SCIP settings */
579  SCIP_STAT* stat, /**< dynamic problem statistics */
580  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
581  SCIP_Real targetvalue /**< new value of the variable in the child node */
582  );
583 
584 /** branches on a variable x
585  * if x is a continuous variable, then two child nodes will be created
586  * (x <= x', x >= x')
587  * but if the bounds of x are such that their relative difference is smaller than epsilon,
588  * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
589  * i.e., no children are created
590  * if x is not a continuous variable, then:
591  * if solution value x' is fractional, two child nodes will be created
592  * (x <= floor(x'), x >= ceil(x')),
593  * if solution value is integral, the x' is equal to lower or upper bound of the branching
594  * variable and the bounds of x are finite, then two child nodes will be created
595  * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
596  * otherwise (up to) three child nodes will be created
597  * (x <= x'-1, x == x', x >= x'+1)
598  * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
599  * will be created (the third one would be infeasible anyway)
600  */
601 extern
603  SCIP_TREE* tree, /**< branch and bound tree */
604  SCIP_REOPT* reopt, /**< reoptimization data structure */
605  BMS_BLKMEM* blkmem, /**< block memory */
606  SCIP_SET* set, /**< global SCIP settings */
607  SCIP_STAT* stat, /**< problem statistics data */
608  SCIP_PROB* transprob, /**< transformed problem after presolve */
609  SCIP_PROB* origprob, /**< original problem */
610  SCIP_LP* lp, /**< current LP data */
611  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
612  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
613  SCIP_VAR* var, /**< variable to branch on */
614  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 */
615  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
616  SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
617  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
618  );
619 
620 /** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
621 extern
623  SCIP_TREE* tree, /**< branch and bound tree */
624  SCIP_REOPT* reopt, /**< reoptimization data structure */
625  BMS_BLKMEM* blkmem, /**< block memory */
626  SCIP_SET* set, /**< global SCIP settings */
627  SCIP_STAT* stat, /**< problem statistics data */
628  SCIP_PROB* transprob, /**< transformed problem after presolve */
629  SCIP_PROB* origprob, /**< original problem */
630  SCIP_LP* lp, /**< current LP data */
631  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
632  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
633  SCIP_VAR* var, /**< variable to branch on */
634  SCIP_Real left, /**< left side of the domain hole */
635  SCIP_Real right, /**< right side of the domain hole */
636  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
637  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
638  );
639 
640 /** n-ary branching on a variable x
641  * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
642  * The branching value is selected as in SCIPtreeBranchVar().
643  * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
644  * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
645  * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
646  * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
647  * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
648  * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
649  * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
650  *
651  * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
652  * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
653  * results in a ternary branching where the branching variable is mostly fixed in the middle child.
654  * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
655  * (except for one child if the branching value is not in the middle).
656  */
657 extern
659  SCIP_TREE* tree, /**< branch and bound tree */
660  SCIP_REOPT* reopt, /**< reoptimization data structure */
661  BMS_BLKMEM* blkmem, /**< block memory */
662  SCIP_SET* set, /**< global SCIP settings */
663  SCIP_STAT* stat, /**< problem statistics data */
664  SCIP_PROB* transprob, /**< transformed problem after presolve */
665  SCIP_PROB* origprob, /**< original problem */
666  SCIP_LP* lp, /**< current LP data */
667  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
668  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
669  SCIP_VAR* var, /**< variable to branch on */
670  SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
671  * A branching value is required for branching on continuous variables */
672  int n, /**< attempted number of children to be created, must be >= 2 */
673  SCIP_Real minwidth, /**< minimal domain width in children */
674  SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
675  int* nchildren /**< buffer to store number of created children, or NULL */
676  );
677 
678 /** adds a diving bound change to the tree together with the information if this is a bound change
679  * for the preferred direction or not
680  */
681 extern
683  SCIP_TREE* tree, /**< branch and bound tree */
684  BMS_BLKMEM* blkmem, /**< block memory buffers */
685  SCIP_VAR* var, /**< variable to apply the bound change to */
686  SCIP_BRANCHDIR dir, /**< direction of the bound change */
687  SCIP_Real value, /**< value to adjust this variable bound to */
688  SCIP_Bool preferred /**< is this a bound change for the preferred child? */
689  );
690 
691 /** get the dive bound change data for the preferred or the alternative direction */
692 extern
694  SCIP_TREE* tree, /**< branch and bound tree */
695  SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
696  SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
697  SCIP_Real** values, /**< pointer to store bound change values */
698  int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
699  SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
700  );
701 
702 /** clear the tree dive bound change data structure */
703 extern
705  SCIP_TREE* tree /**< branch and bound tree */
706  );
707 
708 /** switches to probing mode and creates a probing root */
709 extern
711  SCIP_TREE* tree, /**< branch and bound tree */
712  BMS_BLKMEM* blkmem, /**< block memory */
713  SCIP_SET* set, /**< global SCIP settings */
714  SCIP_LP* lp, /**< current LP data */
715  SCIP_RELAXATION* relaxation, /**< global relaxation data */
716  SCIP_PROB* transprob, /**< transformed problem after presolve */
717  SCIP_Bool strongbranching /**< is the probing mode used for strongbranching? */
718  );
719 
720 /** creates a new probing child node in the probing path */
721 extern
723  SCIP_TREE* tree, /**< branch and bound tree */
724  BMS_BLKMEM* blkmem, /**< block memory */
725  SCIP_SET* set, /**< global SCIP settings */
726  SCIP_LP* lp /**< current LP data */
727  );
728 
729 /** sets the LP state for the current probing node
730  *
731  * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
732  * to NULL by the method
733  *
734  * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
735  * respective information should not be set
736  */
737 extern
739  SCIP_TREE* tree, /**< branch and bound tree */
740  BMS_BLKMEM* blkmem, /**< block memory */
741  SCIP_LP* lp, /**< current LP data */
742  SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
743  SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
744  SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
745  SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
746  );
747 
748 /** loads the LP state for the current probing node */
749 extern
751  SCIP_TREE* tree, /**< branch and bound tree */
752  BMS_BLKMEM* blkmem, /**< block memory buffers */
753  SCIP_SET* set, /**< global SCIP settings */
754  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
755  SCIP_LP* lp /**< current LP data */
756  );
757 
758 /** marks the probing node to have a solved LP relaxation */
759 extern
761  SCIP_TREE* tree, /**< branch and bound tree */
762  BMS_BLKMEM* blkmem, /**< block memory */
763  SCIP_LP* lp /**< current LP data */
764  );
765 
766 /** undoes all changes to the problem applied in probing up to the given probing depth;
767  * the changes of the probing node of the given probing depth are the last ones that remain active;
768  * changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone
769  */
770 extern
772  SCIP_TREE* tree, /**< branch and bound tree */
773  SCIP_REOPT* reopt, /**< reoptimization data structure */
774  BMS_BLKMEM* blkmem, /**< block memory buffers */
775  SCIP_SET* set, /**< global SCIP settings */
776  SCIP_STAT* stat, /**< problem statistics */
777  SCIP_PROB* transprob, /**< transformed problem */
778  SCIP_PROB* origprob, /**< original problem */
779  SCIP_LP* lp, /**< current LP data */
780  SCIP_PRIMAL* primal, /**< primal data structure */
781  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
782  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
783  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
784  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
785  int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
786  );
787 
788 /** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
789  * variables and restores active constraints arrays of focus node
790  */
791 extern
793  SCIP_TREE* tree, /**< branch and bound tree */
794  SCIP_REOPT* reopt, /**< reoptimization data structure */
795  BMS_BLKMEM* blkmem, /**< block memory buffers */
796  SCIP_SET* set, /**< global SCIP settings */
797  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
798  SCIP_STAT* stat, /**< problem statistics */
799  SCIP_PROB* transprob, /**< transformed problem after presolve */
800  SCIP_PROB* origprob, /**< original problem */
801  SCIP_LP* lp, /**< current LP data */
802  SCIP_RELAXATION* relaxation, /**< global relaxation data */
803  SCIP_PRIMAL* primal, /**< primal LP data */
804  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
805  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
806  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
807  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
808  );
809 
810 /** stores relaxation solution before diving or probing */
811 extern
813  SCIP_TREE* tree, /**< branch and bound tree */
814  SCIP_SET* set, /**< global SCIP settings */
815  SCIP_RELAXATION* relaxation, /**< global relaxation data */
816  SCIP_PROB* transprob /**< transformed problem after presolve */
817  );
818 
819 /** restores relaxation solution after diving or probing */
820 extern
822  SCIP_TREE* tree, /**< branch and bound tree */
823  SCIP_SET* set, /**< global SCIP settings */
824  SCIP_RELAXATION* relaxation, /**< global relaxation data */
825  SCIP_PROB* transprob /**< transformed problem after presolve */
826  );
827 
828 
829 /** gets number of children of the focus node */
830 extern
832  SCIP_TREE* tree /**< branch and bound tree */
833  );
834 
835 /** gets number of siblings of the focus node */
836 extern
838  SCIP_TREE* tree /**< branch and bound tree */
839  );
840 
841 /** gets number of leaves in the tree (excluding children and siblings of focus nodes) */
842 extern
844  SCIP_TREE* tree /**< branch and bound tree */
845  );
846 
847 /** gets number of open nodes in the tree (children + siblings + leaves) */
848 extern
850  SCIP_TREE* tree /**< branch and bound tree */
851  );
852 
853 /** returns whether the active path goes completely down to the focus node */
854 extern
856  SCIP_TREE* tree /**< branch and bound tree */
857  );
858 
859 /** returns whether the current node is a temporary probing node */
860 extern
862  SCIP_TREE* tree /**< branch and bound tree */
863  );
864 
865 /** returns the temporary probing root node, or NULL if the we are not in probing mode */
866 extern
868  SCIP_TREE* tree /**< branch and bound tree */
869  );
870 
871 /** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
872 extern
874  SCIP_TREE* tree /**< branch and bound tree */
875  );
876 
877 /** gets focus node of the tree */
878 extern
880  SCIP_TREE* tree /**< branch and bound tree */
881  );
882 
883 /** gets depth of focus node in the tree, or -1 if no focus node exists */
884 extern
886  SCIP_TREE* tree /**< branch and bound tree */
887  );
888 
889 /** returns, whether the LP was or is to be solved in the focus node */
890 extern
892  SCIP_TREE* tree /**< branch and bound tree */
893  );
894 
895 /** sets mark to solve or to ignore the LP while processing the focus node */
896 extern
898  SCIP_TREE* tree, /**< branch and bound tree */
899  SCIP_Bool solvelp /**< should the LP be solved in focus node? */
900  );
901 
902 /** returns whether the LP of the focus node is already constructed */
903 extern
905  SCIP_TREE* tree /**< branch and bound tree */
906  );
907 
908 /** returns whether the focus node is already solved and only propagated again */
909 extern
911  SCIP_TREE* tree /**< branch and bound tree */
912  );
913 
914 /** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
915 extern
917  SCIP_TREE* tree /**< branch and bound tree */
918  );
919 
920 /** 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 */
921 extern
923  SCIP_TREE* tree /**< branch and bound tree */
924  );
925 
926 /** returns, whether the LP was or is to be solved in the current node */
927 extern
929  SCIP_TREE* tree /**< branch and bound tree */
930  );
931 
932 /** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
933 extern
935  SCIP_TREE* tree /**< branch and bound tree */
936  );
937 
938 /** gets the root node of the tree */
939 extern
941  SCIP_TREE* tree /**< branch and bound tree */
942  );
943 
944 /** returns whether we are in probing and the objective value of at least one column was changed */
945 extern
947  SCIP_TREE* tree /**< branch and bound tree */
948  );
949 
950 /** marks the current probing node to have a changed objective function */
951 extern
953  SCIP_TREE* tree /**< branch and bound tree */
954  );
955 
956 #ifdef NDEBUG
957 
958 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
959  * speed up the algorithms.
960  */
961 
962 #define SCIPtreeGetNLeaves(tree) SCIPnodepqLen((tree)->leaves)
963 #define SCIPtreeGetNChildren(tree) ((tree)->nchildren)
964 #define SCIPtreeGetNSiblings(tree) ((tree)->nsiblings)
965 #define SCIPtreeGetNNodes(tree) \
966  (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree))
967 #define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
968 #define SCIPtreeProbing(tree) ((tree)->probingroot != NULL)
969 #define SCIPtreeGetProbingRoot(tree) (tree)->probingroot
970 #define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
971 #define SCIPtreeGetFocusNode(tree) (tree)->focusnode
972 #define SCIPtreeGetFocusDepth(tree) ((tree)->focusnode != NULL ? (tree)->focusnode->depth : -1)
973 #define SCIPtreeHasFocusNodeLP(tree) (tree)->focusnodehaslp
974 #define SCIPtreeSetFocusNodeLP(tree,solvelp) ((tree)->focusnodehaslp = solvelp)
975 #define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed
976 #define SCIPtreeInRepropagation(tree) ((tree)->focusnode != NULL \
977  && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
978 #define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
979 #define SCIPtreeGetCurrentDepth(tree) ((tree)->pathlen-1)
980 #define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
981 #define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth)
982 #define SCIPtreeGetRootNode(tree) ((tree)->root)
983 #define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged)
984 #define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE)
985 
986 #endif
987 
988 
989 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
990 extern
992  SCIP_TREE* tree /**< branch and bound tree */
993  );
994 
995 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
996 extern
998  SCIP_TREE* tree /**< branch and bound tree */
999  );
1000 
1001 /** gets the best child of the focus node w.r.t. the node selection strategy */
1002 extern
1004  SCIP_TREE* tree, /**< branch and bound tree */
1005  SCIP_SET* set /**< global SCIP settings */
1006  );
1007 
1008 /** gets the best sibling of the focus node w.r.t. the node selection strategy */
1009 extern
1011  SCIP_TREE* tree, /**< branch and bound tree */
1012  SCIP_SET* set /**< global SCIP settings */
1013  );
1014 
1015 /** gets the best leaf from the node queue w.r.t. the node selection strategy */
1016 extern
1018  SCIP_TREE* tree /**< branch and bound tree */
1019  );
1020 
1021 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
1022 extern
1024  SCIP_TREE* tree, /**< branch and bound tree */
1025  SCIP_SET* set /**< global SCIP settings */
1026  );
1027 
1028 /** gets the minimal lower bound of all nodes in the tree */
1029 extern
1031  SCIP_TREE* tree, /**< branch and bound tree */
1032  SCIP_SET* set /**< global SCIP settings */
1033  );
1034 
1035 /** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */
1036 extern
1038  SCIP_TREE* tree, /**< branch and bound tree */
1039  SCIP_SET* set /**< global SCIP settings */
1040  );
1041 
1042 /** gets the average lower bound of all nodes in the tree */
1043 extern
1045  SCIP_TREE* tree, /**< branch and bound tree */
1046  SCIP_Real cutoffbound /**< global cutoff bound */
1047  );
1048 
1049 #ifdef __cplusplus
1050 }
1051 #endif
1052 
1053 #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:6405
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
Definition: tree.c:5019
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6186
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:4925
void SCIPnodeGetDualBoundchgs(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_BOUNDTYPE *boundtypes, int *nvars, int varssize)
Definition: tree.c:7542
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8328
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:7191
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:6430
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:5341
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
Definition: tree.c:8242
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7055
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition: tree.c:8252
type definitions for conflict store
void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1638
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:6739
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:8208
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7119
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:4693
type definitions for global SCIP settings
SCIP_NODE * SCIPtreeGetProbingRoot(SCIP_TREE *tree)
Definition: tree.c:8195
SCIP_RETCODE SCIPtreeLoadLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:3469
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8225
type definitions for collecting reoptimization information
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8300
type definitions for branching rules
type definitions for problem statistics
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition: tree.c:8125
SCIP_Bool SCIPtreeIsPathComplete(SCIP_TREE *tree)
Definition: tree.c:8165
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8263
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:8182
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:4236
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:5132
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7082
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:3341
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition: tree.c:7109
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition: tree.c:8273
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:7497
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:8317
#define SCIP_Bool
Definition: def.h:61
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8339
SCIP_Real SCIPtreeGetAvgLowerbound(SCIP_TREE *tree, SCIP_Real cutoffbound)
Definition: tree.c:7243
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6241
SCIP_RETCODE SCIPtreeFree(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4772
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: tree.c:6218
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
Definition: tree.c:2391
void SCIPnodeGetBdChgsAfterDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int start, int *nbranchvars, int branchvarssize)
Definition: tree.c:7860
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:5815
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:6340
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:4880
SCIP_RETCODE SCIPnodeCaptureLPIState(SCIP_NODE *node, int nuses)
Definition: tree.c:235
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8283
type definitions for storing and manipulating the main problem
SCIP_NODESEL * SCIPtreeGetNodesel(SCIP_TREE *tree)
Definition: tree.c:5009
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition: tree.c:8135
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8361
type definitions for propagators
SCIP_RETCODE SCIPtreeStoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:6934
int SCIPnodeGetNAddedConss(SCIP_NODE *node)
Definition: tree.c:1668
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:4966
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:6565
#define SCIP_Real
Definition: def.h:149
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:8350
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:7003
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
Definition: tree.c:8145
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:2339
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8372
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:2405
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:6484
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition: tree.c:8155
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
void SCIPchildChgNodeselPrio(SCIP_TREE *tree, SCIP_NODE *child, SCIP_Real priority)
Definition: tree.c:2373
SCIP_RETCODE SCIPtreeRestoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:6971
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:6773
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition: tree.c:7029
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7153
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:5047
SCIP_RETCODE SCIPtreeClear(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4820
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:7772
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5282
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:5673
memory allocation routines