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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file tree.h
26  * @ingroup INTERNALAPI
27  * @brief internal methods for branch and bound tree
28  * @author Tobias Achterberg
29  * @author Timo Berthold
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #ifndef __SCIP_TREE_H__
35 #define __SCIP_TREE_H__
36 
37 
38 #include "blockmemshell/memory.h"
39 #include "scip/def.h"
40 #include "scip/nodesel.h"
41 #include "scip/type_set.h"
42 #include "scip/type_stat.h"
43 #include "scip/type_cons.h"
44 #include "scip/type_event.h"
45 #include "scip/type_lp.h"
46 #include "scip/type_var.h"
47 #include "scip/type_prob.h"
48 #include "scip/type_primal.h"
49 #include "scip/type_tree.h"
50 #include "scip/type_reopt.h"
51 #include "scip/type_branch.h"
52 #include "scip/type_prop.h"
53 #include "scip/type_implics.h"
54 #include "scip/type_history.h"
56 #include "scip/pub_tree.h"
57 
58 #ifndef NDEBUG
59 #include "scip/struct_tree.h"
60 #endif
61 
62 #ifdef __cplusplus
63 extern "C" {
64 #endif
65 
66 
67 /*
68  * Node methods
69  */
70 
71 /** creates a child node of the focus node */
73  SCIP_NODE** node, /**< pointer to node data structure */
74  BMS_BLKMEM* blkmem, /**< block memory */
75  SCIP_SET* set, /**< global SCIP settings */
76  SCIP_STAT* stat, /**< problem statistics */
77  SCIP_TREE* tree, /**< branch and bound tree */
78  SCIP_Real nodeselprio, /**< node selection priority of new node */
79  SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
80  );
81 
82 /** frees node */
84  SCIP_NODE** node, /**< node data */
85  BMS_BLKMEM* blkmem, /**< block memory buffer */
86  SCIP_SET* set, /**< global SCIP settings */
87  SCIP_STAT* stat, /**< problem statistics */
88  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
89  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
90  SCIP_TREE* tree, /**< branch and bound tree */
91  SCIP_LP* lp /**< current LP data */
92  );
93 
94 /** increases the reference counter of the LP state in the fork or subroot node */
96  SCIP_NODE* node, /**< fork/subroot node */
97  int nuses /**< number to add to the usage counter */
98  );
99 
100 /** decreases the reference counter of the LP state in the fork or subroot node */
102  SCIP_NODE* node, /**< fork/subroot node */
103  BMS_BLKMEM* blkmem, /**< block memory buffers */
104  SCIP_LP* lp /**< current LP data */
105  );
106 
107 /** installs a child, a sibling, or a leaf node as the new focus node */
109  SCIP_NODE** node, /**< pointer to node to focus (or NULL to remove focus); the node
110  * is freed, if it was cut off due to a cut off subtree */
111  BMS_BLKMEM* blkmem, /**< block memory */
112  SCIP_SET* set, /**< global SCIP settings */
113  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
114  SCIP_STAT* stat, /**< problem statistics */
115  SCIP_PROB* transprob, /**< transformed problem */
116  SCIP_PROB* origprob, /**< original problem */
117  SCIP_PRIMAL* primal, /**< primal data */
118  SCIP_TREE* tree, /**< branch and bound tree */
119  SCIP_REOPT* reopt, /**< reoptimization data structure */
120  SCIP_LP* lp, /**< current LP data */
121  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
122  SCIP_CONFLICT* conflict, /**< conflict analysis data */
123  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
124  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
125  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
126  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
127  SCIP_Bool* cutoff, /**< pointer to store whether the given node can be cut off */
128  SCIP_Bool postponed, /**< was the current focus node postponed? */
129  SCIP_Bool exitsolve /**< are we in exitsolve stage, so we only need to loose the children */
130  );
131 
132 /** cuts off node and whole sub tree from branch and bound tree */
134  SCIP_NODE* node, /**< node that should be cut off */
135  SCIP_SET* set, /**< global SCIP settings */
136  SCIP_STAT* stat, /**< problem statistics */
137  SCIP_TREE* tree, /**< branch and bound tree */
138  SCIP_PROB* transprob, /**< transformed problem after presolve */
139  SCIP_PROB* origprob, /**< original problem */
140  SCIP_REOPT* reopt, /**< reoptimization data structure */
141  SCIP_LP* lp, /**< current LP */
142  BMS_BLKMEM* blkmem /**< block memory */
143  );
144 
145 /** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
147  SCIP_NODE* node, /**< node that should be propagated again */
148  SCIP_SET* set, /**< global SCIP settings */
149  SCIP_STAT* stat, /**< problem statistics */
150  SCIP_TREE* tree /**< branch and bound tree */
151  );
152 
153 /** marks node, that it is completely propagated in the current repropagation subtree level */
155  SCIP_NODE* node, /**< node that should be propagated again */
156  SCIP_TREE* tree /**< branch and bound tree */
157  );
158 
159 /** adds constraint locally to the node and captures it; activates constraint, if node is active;
160  * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
161  */
163  SCIP_NODE* node, /**< node to add constraint to */
164  BMS_BLKMEM* blkmem, /**< block memory */
165  SCIP_SET* set, /**< global SCIP settings */
166  SCIP_STAT* stat, /**< problem statistics */
167  SCIP_TREE* tree, /**< branch and bound tree */
168  SCIP_CONS* cons /**< constraint to add */
169  );
170 
171 /** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
172  * at the node; captures constraint; disables constraint, if node is active
173  */
175  SCIP_NODE* node, /**< node to add constraint to */
176  BMS_BLKMEM* blkmem, /**< block memory */
177  SCIP_SET* set, /**< global SCIP settings */
178  SCIP_STAT* stat, /**< problem statistics */
179  SCIP_TREE* tree, /**< branch and bound tree */
180  SCIP_CONS* cons /**< constraint to locally delete */
181  );
182 
183 /** return all bound changes based on constraint propagation; stop saving the bound changes if we reach a branching
184  * decision based on a dual information
185  */
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  */
202  SCIP_NODE* node, /**< node */
203  SCIP_VAR** vars, /**< array of variables on which the branching has been performed in the parent node */
204  SCIP_Real* varbounds, /**< array of bounds which the branching in the parent node set */
205  SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes which the branching in the parent node set */
206  int start, /**< first free slot in the arrays */
207  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
208  * if this is larger than the array size, arrays should be reallocated and method
209  * should be called again */
210  int branchvarssize /**< available slots in arrays */
211  );
212 
213 /** adds bound change with inference information to focus node, child of focus node, or probing node;
214  * if possible, adjusts bound to integral value;
215  * at most one of infercons and inferprop may be non-NULL
216  */
218  SCIP_NODE* node, /**< node to add bound change to */
219  BMS_BLKMEM* blkmem, /**< block memory */
220  SCIP_SET* set, /**< global SCIP settings */
221  SCIP_STAT* stat, /**< problem statistics */
222  SCIP_PROB* transprob, /**< transformed problem after presolve */
223  SCIP_PROB* origprob, /**< original problem */
224  SCIP_TREE* tree, /**< branch and bound tree */
225  SCIP_REOPT* reopt, /**< reoptimization data structure */
226  SCIP_LP* lp, /**< current LP data */
227  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
228  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
229  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
230  SCIP_VAR* var, /**< variable to change the bounds for */
231  SCIP_Real newbound, /**< new value for bound */
232  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
233  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
234  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
235  int inferinfo, /**< user information for inference to help resolving the conflict */
236  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
237  );
238 
239 /** adds bound change to focus node, or child of focus node, or probing node;
240  * if possible, adjusts bound to integral value
241  */
243  SCIP_NODE* node, /**< node to add bound change to */
244  BMS_BLKMEM* blkmem, /**< block memory */
245  SCIP_SET* set, /**< global SCIP settings */
246  SCIP_STAT* stat, /**< problem statistics */
247  SCIP_PROB* transprob, /**< transformed problem after presolve */
248  SCIP_PROB* origprob, /**< original problem */
249  SCIP_TREE* tree, /**< branch and bound tree */
250  SCIP_REOPT* reopt, /**< reoptimization data structure */
251  SCIP_LP* lp, /**< current LP data */
252  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
253  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
254  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
255  SCIP_VAR* var, /**< variable to change the bounds for */
256  SCIP_Real newbound, /**< new value for bound */
257  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
258  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
259  );
260 
261 /** adds hole with inference information to focus node, child of focus node, or probing node;
262  * if possible, adjusts bound to integral value;
263  * at most one of infercons and inferprop may be non-NULL
264  */
266  SCIP_NODE* node, /**< node to add bound change to */
267  BMS_BLKMEM* blkmem, /**< block memory */
268  SCIP_SET* set, /**< global SCIP settings */
269  SCIP_STAT* stat, /**< problem statistics */
270  SCIP_TREE* tree, /**< branch and bound tree */
271  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
272  SCIP_VAR* var, /**< variable to change the bounds for */
273  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
274  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
275  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
276  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
277  int inferinfo, /**< user information for inference to help resolving the conflict */
278  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
279  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
280  );
281 
282 /** adds hole change to focus node, or child of focus node */
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_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
294  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
295  );
296 
297 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
299  SCIP_NODE* node, /**< node to update lower bound for */
300  SCIP_STAT* stat, /**< problem statistics */
301  SCIP_SET* set, /**< global SCIP settings */
302  SCIP_TREE* tree, /**< branch and bound tree */
303  SCIP_PROB* transprob, /**< transformed problem data */
304  SCIP_PROB* origprob, /**< original problem */
305  SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
306  );
307 
308 /** updates lower bound of node using lower bound of LP */
310  SCIP_NODE* node, /**< node to set lower bound for */
311  SCIP_SET* set, /**< global SCIP settings */
312  SCIP_STAT* stat, /**< problem statistics */
313  SCIP_TREE* tree, /**< branch and bound tree */
314  SCIP_PROB* transprob, /**< transformed problem after presolve */
315  SCIP_PROB* origprob, /**< original problem */
316  SCIP_LP* lp /**< LP data */
317  );
318 
319 /** change the node selection priority of the given child */
321  SCIP_TREE* tree, /**< branch and bound tree */
322  SCIP_NODE* child, /**< child to update the node selection priority */
323  SCIP_Real priority /**< node selection priority value */
324  );
325 
326 
327 /** sets the node's estimated bound to the new value */
329  SCIP_NODE* node, /**< node to update lower bound for */
330  SCIP_SET* set, /**< global SCIP settings */
331  SCIP_Real newestimate /**< new estimated bound for the node */
332  );
333 
334 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
336  SCIP_NODE* node, /**< node to propagate implications on */
337  BMS_BLKMEM* blkmem, /**< block memory */
338  SCIP_SET* set, /**< global SCIP settings */
339  SCIP_STAT* stat, /**< problem statistics */
340  SCIP_PROB* transprob, /**< transformed problem after presolve */
341  SCIP_PROB* origprob, /**< original problem */
342  SCIP_TREE* tree, /**< branch and bound tree */
343  SCIP_REOPT* reopt, /**< reoptimization data structure */
344  SCIP_LP* lp, /**< current LP data */
345  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
346  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
347  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
348  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
349  );
350 
351 /** returns all bound changes based on dual information.
352  *
353  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
354  * method to ensure optimality within reoptimization.
355  *
356  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
357  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
358  *
359  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
360  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
361  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
362  */
364  SCIP_NODE* node, /**< node data */
365  SCIP_VAR** vars, /**< array of variables on which the bound change is based on dual information */
366  SCIP_Real* bounds, /**< array of bounds which are based on dual information */
367  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which are based on dual information */
368  int* nvars, /**< number of variables on which the bound change is based on dual information
369  * if this is larger than the array size, arrays should be reallocated and method
370  * should be called again */
371  int varssize /**< available slots in arrays */
372  );
373 
374 /** returns the number of bound changes based on dual information.
375  *
376  * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
377  * method to ensure optimality within reoptimization.
378  *
379  * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
380  * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
381  *
382  * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
383  * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
384  * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
385  */
387  SCIP_NODE* node
388  );
389 
390 /*
391  * Tree methods
392  */
393 
394 /** creates an initialized tree data structure */
396  SCIP_TREE** tree, /**< pointer to tree data structure */
397  BMS_BLKMEM* blkmem, /**< block memory buffers */
398  SCIP_SET* set, /**< global SCIP settings */
399  SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */
400  );
401 
402 /** frees tree data structure */
404  SCIP_TREE** tree, /**< pointer to tree data structure */
405  BMS_BLKMEM* blkmem, /**< block memory buffers */
406  SCIP_SET* set, /**< global SCIP settings */
407  SCIP_STAT* stat, /**< problem statistics */
408  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
409  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
410  SCIP_LP* lp /**< current LP data */
411  );
412 
413 /** clears and resets tree data structure and deletes all nodes */
415  SCIP_TREE* tree, /**< tree data structure */
416  BMS_BLKMEM* blkmem, /**< block memory buffers */
417  SCIP_SET* set, /**< global SCIP settings */
418  SCIP_STAT* stat, /**< problem statistics */
419  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
420  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
421  SCIP_LP* lp /**< current LP data */
422  );
423 
424 /** creates the root node of the tree and puts it into the leaves queue */
426  SCIP_TREE* tree, /**< tree data structure */
427  SCIP_REOPT* reopt, /**< reoptimization data structure */
428  BMS_BLKMEM* blkmem, /**< block memory buffers */
429  SCIP_SET* set, /**< global SCIP settings */
430  SCIP_STAT* stat, /**< problem statistics */
431  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
432  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
433  SCIP_LP* lp /**< current LP data */
434  );
435 
436 /** creates a temporary presolving root node of the tree and installs it as focus node */
438  SCIP_TREE* tree, /**< tree data structure */
439  SCIP_REOPT* reopt, /**< reoptimization data structure */
440  BMS_BLKMEM* blkmem, /**< block memory buffers */
441  SCIP_SET* set, /**< global SCIP settings */
442  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
443  SCIP_STAT* stat, /**< problem statistics */
444  SCIP_PROB* transprob, /**< transformed problem */
445  SCIP_PROB* origprob, /**< original problem */
446  SCIP_PRIMAL* primal, /**< primal data */
447  SCIP_LP* lp, /**< current LP data */
448  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
449  SCIP_CONFLICT* conflict, /**< conflict analysis data */
450  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
451  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
452  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
453  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
454  );
455 
456 /** frees the temporary presolving root and resets tree data structure */
458  SCIP_TREE* tree, /**< tree data structure */
459  SCIP_REOPT* reopt, /**< reoptimization data structure */
460  BMS_BLKMEM* blkmem, /**< block memory buffers */
461  SCIP_SET* set, /**< global SCIP settings */
462  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
463  SCIP_STAT* stat, /**< problem statistics */
464  SCIP_PROB* transprob, /**< transformed problem */
465  SCIP_PROB* origprob, /**< original problem */
466  SCIP_PRIMAL* primal, /**< primal data */
467  SCIP_LP* lp, /**< current LP data */
468  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
469  SCIP_CONFLICT* conflict, /**< conflict analysis data */
470  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
471  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
472  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
473  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
474  );
475 
476 /** returns the node selector associated with the given node priority queue */
478  SCIP_TREE* tree /**< branch and bound tree */
479  );
480 
481 /** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
483  SCIP_TREE* tree, /**< branch and bound tree */
484  SCIP_SET* set, /**< global SCIP settings */
485  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
486  SCIP_STAT* stat, /**< problem statistics */
487  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
488  );
489 
490 /** cuts off nodes with lower bound not better than given upper bound */
492  SCIP_TREE* tree, /**< branch and bound tree */
493  SCIP_REOPT* reopt, /**< reoptimization data structure */
494  BMS_BLKMEM* blkmem, /**< block memory */
495  SCIP_SET* set, /**< global SCIP settings */
496  SCIP_STAT* stat, /**< dynamic problem statistics */
497  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
498  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
499  SCIP_LP* lp, /**< current LP data */
500  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
501  );
502 
503 /** constructs the LP relaxation of the focus node */
505  SCIP_TREE* tree, /**< branch and bound tree */
506  BMS_BLKMEM* blkmem, /**< block memory */
507  SCIP_SET* set, /**< global SCIP settings */
508  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
509  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
510  SCIP_LP* lp, /**< current LP data */
511  SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
512  );
513 
514 /** loads LP state for fork/subroot of the focus node */
516  SCIP_TREE* tree, /**< branch and bound tree */
517  BMS_BLKMEM* blkmem, /**< block memory buffers */
518  SCIP_SET* set, /**< global SCIP settings */
519  SCIP_PROB* prob, /**< problem data */
520  SCIP_STAT* stat, /**< dynamic problem statistics */
521  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
522  SCIP_LP* lp /**< current LP data */
523  );
524 
525 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
526  * this node selection priority can be given to the SCIPcreateChild() call
527  */
529  SCIP_TREE* tree, /**< branch and bound tree */
530  SCIP_SET* set, /**< global SCIP settings */
531  SCIP_STAT* stat, /**< dynamic problem statistics */
532  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
533  SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed
534  * fixed should only be used, when both bounds changed
535  */
536  SCIP_Real targetvalue /**< new value of the variable in the child node */
537  );
538 
539 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
540  * branching; this estimate can be given to the SCIPcreateChild() call
541  */
543  SCIP_TREE* tree, /**< branch and bound tree */
544  SCIP_SET* set, /**< global SCIP settings */
545  SCIP_STAT* stat, /**< dynamic problem statistics */
546  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
547  SCIP_Real targetvalue /**< new value of the variable in the child node */
548  );
549 
550 /** branches on a variable x
551  * if x is a continuous variable, then two child nodes will be created
552  * (x <= x', x >= x')
553  * but if the bounds of x are such that their relative difference is smaller than epsilon,
554  * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
555  * i.e., no children are created
556  * if x is not a continuous variable, then:
557  * if solution value x' is fractional, two child nodes will be created
558  * (x <= floor(x'), x >= ceil(x')),
559  * if solution value is integral, the x' is equal to lower or upper bound of the branching
560  * variable and the bounds of x are finite, then two child nodes will be created
561  * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
562  * otherwise (up to) three child nodes will be created
563  * (x <= x'-1, x == x', x >= x'+1)
564  * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
565  * will be created (the third one would be infeasible anyway)
566  */
568  SCIP_TREE* tree, /**< branch and bound tree */
569  SCIP_REOPT* reopt, /**< reoptimization data structure */
570  BMS_BLKMEM* blkmem, /**< block memory */
571  SCIP_SET* set, /**< global SCIP settings */
572  SCIP_STAT* stat, /**< problem statistics data */
573  SCIP_PROB* transprob, /**< transformed problem after presolve */
574  SCIP_PROB* origprob, /**< original problem */
575  SCIP_LP* lp, /**< current LP data */
576  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
577  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
578  SCIP_VAR* var, /**< variable to branch on */
579  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 */
580  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
581  SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
582  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
583  );
584 
585 /** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
587  SCIP_TREE* tree, /**< branch and bound tree */
588  SCIP_REOPT* reopt, /**< reoptimization data structure */
589  BMS_BLKMEM* blkmem, /**< block memory */
590  SCIP_SET* set, /**< global SCIP settings */
591  SCIP_STAT* stat, /**< problem statistics data */
592  SCIP_PROB* transprob, /**< transformed problem after presolve */
593  SCIP_PROB* origprob, /**< original problem */
594  SCIP_LP* lp, /**< current LP data */
595  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
596  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
597  SCIP_VAR* var, /**< variable to branch on */
598  SCIP_Real left, /**< left side of the domain hole */
599  SCIP_Real right, /**< right side of the domain hole */
600  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
601  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
602  );
603 
604 /** n-ary branching on a variable x
605  * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
606  * The branching value is selected as in SCIPtreeBranchVar().
607  * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
608  * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
609  * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
610  * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
611  * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
612  * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
613  * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
614  *
615  * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
616  * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
617  * results in a ternary branching where the branching variable is mostly fixed in the middle child.
618  * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
619  * (except for one child if the branching value is not in the middle).
620  */
622  SCIP_TREE* tree, /**< branch and bound tree */
623  SCIP_REOPT* reopt, /**< reoptimization data structure */
624  BMS_BLKMEM* blkmem, /**< block memory */
625  SCIP_SET* set, /**< global SCIP settings */
626  SCIP_STAT* stat, /**< problem statistics data */
627  SCIP_PROB* transprob, /**< transformed problem after presolve */
628  SCIP_PROB* origprob, /**< original problem */
629  SCIP_LP* lp, /**< current LP data */
630  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
631  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
632  SCIP_VAR* var, /**< variable to branch on */
633  SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
634  * A branching value is required for branching on continuous variables */
635  int n, /**< attempted number of children to be created, must be >= 2 */
636  SCIP_Real minwidth, /**< minimal domain width in children */
637  SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
638  int* nchildren /**< buffer to store number of created children, or NULL */
639  );
640 
641 /** adds a diving bound change to the tree together with the information if this is a bound change
642  * for the preferred direction or not
643  */
645  SCIP_TREE* tree, /**< branch and bound tree */
646  BMS_BLKMEM* blkmem, /**< block memory buffers */
647  SCIP_VAR* var, /**< variable to apply the bound change to */
648  SCIP_BRANCHDIR dir, /**< direction of the bound change */
649  SCIP_Real value, /**< value to adjust this variable bound to */
650  SCIP_Bool preferred /**< is this a bound change for the preferred child? */
651  );
652 
653 /** get the dive bound change data for the preferred or the alternative direction */
655  SCIP_TREE* tree, /**< branch and bound tree */
656  SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
657  SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
658  SCIP_Real** values, /**< pointer to store bound change values */
659  int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
660  SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
661  );
662 
663 /** clear the tree dive bound change data structure */
665  SCIP_TREE* tree /**< branch and bound tree */
666  );
667 
668 /** switches to probing mode and creates a probing root */
670  SCIP_TREE* tree, /**< branch and bound tree */
671  BMS_BLKMEM* blkmem, /**< block memory */
672  SCIP_SET* set, /**< global SCIP settings */
673  SCIP_LP* lp, /**< current LP data */
674  SCIP_RELAXATION* relaxation, /**< global relaxation data */
675  SCIP_PROB* transprob, /**< transformed problem after presolve */
676  SCIP_Bool strongbranching /**< is the probing mode used for strongbranching? */
677  );
678 
679 /** creates a new probing child node in the probing path */
681  SCIP_TREE* tree, /**< branch and bound tree */
682  BMS_BLKMEM* blkmem, /**< block memory */
683  SCIP_SET* set, /**< global SCIP settings */
684  SCIP_LP* lp /**< current LP data */
685  );
686 
687 /** sets the LP state for the current probing node
688  *
689  * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
690  * to NULL by the method
691  *
692  * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
693  * respective information should not be set
694  */
696  SCIP_TREE* tree, /**< branch and bound tree */
697  BMS_BLKMEM* blkmem, /**< block memory */
698  SCIP_LP* lp, /**< current LP data */
699  SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
700  SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
701  SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
702  SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
703  );
704 
705 /** loads the LP state for the current probing node */
707  SCIP_TREE* tree, /**< branch and bound tree */
708  BMS_BLKMEM* blkmem, /**< block memory buffers */
709  SCIP_SET* set, /**< global SCIP settings */
710  SCIP_PROB* prob, /**< problem data */
711  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
712  SCIP_LP* lp /**< current LP data */
713  );
714 
715 /** marks the probing node to have a solved LP relaxation */
717  SCIP_TREE* tree, /**< branch and bound tree */
718  BMS_BLKMEM* blkmem, /**< block memory */
719  SCIP_LP* lp /**< current LP data */
720  );
721 
722 /** undoes all changes to the problem applied in probing up to the given probing depth;
723  * the changes of the probing node of the given probing depth are the last ones that remain active;
724  * changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone
725  */
727  SCIP_TREE* tree, /**< branch and bound tree */
728  SCIP_REOPT* reopt, /**< reoptimization data structure */
729  BMS_BLKMEM* blkmem, /**< block memory buffers */
730  SCIP_SET* set, /**< global SCIP settings */
731  SCIP_STAT* stat, /**< problem statistics */
732  SCIP_PROB* transprob, /**< transformed problem */
733  SCIP_PROB* origprob, /**< original problem */
734  SCIP_LP* lp, /**< current LP data */
735  SCIP_PRIMAL* primal, /**< primal data structure */
736  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
737  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
738  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
739  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
740  int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
741  );
742 
743 /** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
744  * variables and restores active constraints arrays of focus node
745  */
747  SCIP_TREE* tree, /**< branch and bound tree */
748  SCIP_REOPT* reopt, /**< reoptimization data structure */
749  BMS_BLKMEM* blkmem, /**< block memory buffers */
750  SCIP_SET* set, /**< global SCIP settings */
751  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
752  SCIP_STAT* stat, /**< problem statistics */
753  SCIP_PROB* transprob, /**< transformed problem after presolve */
754  SCIP_PROB* origprob, /**< original problem */
755  SCIP_LP* lp, /**< current LP data */
756  SCIP_RELAXATION* relaxation, /**< global relaxation data */
757  SCIP_PRIMAL* primal, /**< primal LP data */
758  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
759  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
760  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
761  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
762  );
763 
764 /** stores relaxation solution before diving or probing */
766  SCIP_TREE* tree, /**< branch and bound tree */
767  SCIP_SET* set, /**< global SCIP settings */
768  SCIP_RELAXATION* relaxation, /**< global relaxation data */
769  SCIP_PROB* transprob /**< transformed problem after presolve */
770  );
771 
772 /** restores relaxation solution after diving or probing */
774  SCIP_TREE* tree, /**< branch and bound tree */
775  SCIP_SET* set, /**< global SCIP settings */
776  SCIP_RELAXATION* relaxation, /**< global relaxation data */
777  SCIP_PROB* transprob /**< transformed problem after presolve */
778  );
779 
780 
781 /** gets number of children of the focus node */
783  SCIP_TREE* tree /**< branch and bound tree */
784  );
785 
786 /** gets number of siblings of the focus node */
788  SCIP_TREE* tree /**< branch and bound tree */
789  );
790 
791 /** gets number of leaves in the tree (excluding children and siblings of focus nodes) */
793  SCIP_TREE* tree /**< branch and bound tree */
794  );
795 
796 /** gets number of open nodes in the tree (children + siblings + leaves) */
798  SCIP_TREE* tree /**< branch and bound tree */
799  );
800 
801 /** returns whether the active path goes completely down to the focus node */
803  SCIP_TREE* tree /**< branch and bound tree */
804  );
805 
806 /** returns whether the current node is a temporary probing node */
808  SCIP_TREE* tree /**< branch and bound tree */
809  );
810 
811 /** returns the temporary probing root node, or NULL if the we are not in probing mode */
813  SCIP_TREE* tree /**< branch and bound tree */
814  );
815 
816 /** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
818  SCIP_TREE* tree /**< branch and bound tree */
819  );
820 
821 /** gets focus node of the tree */
823  SCIP_TREE* tree /**< branch and bound tree */
824  );
825 
826 /** gets depth of focus node in the tree, or -1 if no focus node exists */
828  SCIP_TREE* tree /**< branch and bound tree */
829  );
830 
831 /** returns, whether the LP was or is to be solved in the focus node */
833  SCIP_TREE* tree /**< branch and bound tree */
834  );
835 
836 /** sets mark to solve or to ignore the LP while processing the focus node */
838  SCIP_TREE* tree, /**< branch and bound tree */
839  SCIP_Bool solvelp /**< should the LP be solved in focus node? */
840  );
841 
842 /** returns whether the LP of the focus node is already constructed */
844  SCIP_TREE* tree /**< branch and bound tree */
845  );
846 
847 /** returns whether the focus node is already solved and only propagated again */
849  SCIP_TREE* tree /**< branch and bound tree */
850  );
851 
852 /** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
854  SCIP_TREE* tree /**< branch and bound tree */
855  );
856 
857 /** 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 */
859  SCIP_TREE* tree /**< branch and bound tree */
860  );
861 
862 /** returns, whether the LP was or is to be solved in the current node */
864  SCIP_TREE* tree /**< branch and bound tree */
865  );
866 
867 /** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
869  SCIP_TREE* tree /**< branch and bound tree */
870  );
871 
872 /** gets the root node of the tree */
874  SCIP_TREE* tree /**< branch and bound tree */
875  );
876 
877 /** returns whether we are in probing and the objective value of at least one column was changed */
879  SCIP_TREE* tree /**< branch and bound tree */
880  );
881 
882 /** marks the current probing node to have a changed objective function */
884  SCIP_TREE* tree /**< branch and bound tree */
885  );
886 
887 #ifdef NDEBUG
888 
889 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
890  * speed up the algorithms.
891  */
892 
893 #define SCIPtreeGetNLeaves(tree) SCIPnodepqLen((tree)->leaves)
894 #define SCIPtreeGetNChildren(tree) ((tree)->nchildren)
895 #define SCIPtreeGetNSiblings(tree) ((tree)->nsiblings)
896 #define SCIPtreeGetNNodes(tree) \
897  (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree))
898 #define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
899 #define SCIPtreeProbing(tree) ((tree)->probingroot != NULL)
900 #define SCIPtreeGetProbingRoot(tree) (tree)->probingroot
901 #define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
902 #define SCIPtreeGetFocusNode(tree) (tree)->focusnode
903 #define SCIPtreeGetFocusDepth(tree) ((tree)->focusnode != NULL ? (int)(tree)->focusnode->depth : -1)
904 #define SCIPtreeHasFocusNodeLP(tree) (tree)->focusnodehaslp
905 #define SCIPtreeSetFocusNodeLP(tree,solvelp) ((tree)->focusnodehaslp = solvelp)
906 #define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed
907 #define SCIPtreeInRepropagation(tree) ((tree)->focusnode != NULL \
908  && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
909 #define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
910 #define SCIPtreeGetCurrentDepth(tree) ((tree)->pathlen-1)
911 #define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
912 #define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth)
913 #define SCIPtreeGetRootNode(tree) ((tree)->root)
914 #define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged)
915 #define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE)
916 
917 #endif
918 
919 
920 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
922  SCIP_TREE* tree /**< branch and bound tree */
923  );
924 
925 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
927  SCIP_TREE* tree /**< branch and bound tree */
928  );
929 
930 /** gets the best child of the focus node w.r.t. the node selection strategy */
932  SCIP_TREE* tree, /**< branch and bound tree */
933  SCIP_SET* set /**< global SCIP settings */
934  );
935 
936 /** gets the best sibling of the focus node w.r.t. the node selection strategy */
938  SCIP_TREE* tree, /**< branch and bound tree */
939  SCIP_SET* set /**< global SCIP settings */
940  );
941 
942 /** gets the best leaf from the node queue w.r.t. the node selection strategy */
944  SCIP_TREE* tree /**< branch and bound tree */
945  );
946 
947 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
949  SCIP_TREE* tree, /**< branch and bound tree */
950  SCIP_SET* set /**< global SCIP settings */
951  );
952 
953 /** gets the minimal lower bound of all nodes in the tree */
955  SCIP_TREE* tree, /**< branch and bound tree */
956  SCIP_SET* set /**< global SCIP settings */
957  );
958 
959 /** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */
961  SCIP_TREE* tree, /**< branch and bound tree */
962  SCIP_SET* set /**< global SCIP settings */
963  );
964 
965 /** gets the average lower bound of all nodes in the tree */
967  SCIP_TREE* tree, /**< branch and bound tree */
968  SCIP_Real cutoffbound /**< global cutoff bound */
969  );
970 
971 /** query if focus node was already branched on */
973  SCIP_TREE* tree, /**< branch and bound tree */
974  SCIP_NODE* node /**< tree node, or NULL to check focus node */
975  );
976 
977 #ifdef __cplusplus
978 }
979 #endif
980 
981 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: tree.c:6499
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
Definition: tree.c:5107
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6274
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:5013
void SCIPnodeGetDualBoundchgs(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_BOUNDTYPE *boundtypes, int *nvars, int varssize)
Definition: tree.c:7645
SCIP_RETCODE SCIPnodeFree(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: tree.c:1055
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8431
SCIP_RETCODE SCIPnodeDelCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition: tree.c:1651
public methods for branch and bound tree
SCIP_RETCODE SCIPtreeLoadProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:6578
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7294
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:993
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:6524
type definitions for implications, variable bounds, and cliques
SCIP_RETCODE SCIPtreeCutoff(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: tree.c:5135
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:5430
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
Definition: tree.c:8345
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7158
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition: tree.c:8355
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:6834
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:1812
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8311
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7222
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPtreeCreate(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: tree.c:4776
type definitions for global SCIP settings
SCIP_NODE * SCIPtreeGetProbingRoot(SCIP_TREE *tree)
Definition: tree.c:8298
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8328
type definitions for collecting reoptimization information
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8403
type definitions for branching rules
type definitions for problem statistics
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition: tree.c:8228
SCIP_Bool SCIPtreeIsPathComplete(SCIP_TREE *tree)
Definition: tree.c:8268
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8366
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:1188
type definitions for LP management
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition: tree.c:8285
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
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:4309
void SCIPnodeMarkPropagated(SCIP_NODE *node, SCIP_TREE *tree)
Definition: tree.c:1274
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: tree.c:5221
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7185
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:3417
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition: tree.c:7212
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
Definition: tree.c:1042
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition: tree.c:8376
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:2365
data structures for branch and bound tree
internal methods for node selectors and node priority queues
SCIP_RETCODE SCIPtreeCreateRoot(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4967
type definitions for problem variables
int SCIPnodeGetNDualBndchgs(SCIP_NODE *node)
Definition: tree.c:7600
type definitions for managing events
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1248
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:2237
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8420
#define SCIP_Bool
Definition: def.h:93
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8442
SCIP_RETCODE SCIPtreeLoadLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:3545
SCIP_Real SCIPtreeGetAvgLowerbound(SCIP_TREE *tree, SCIP_Real cutoffbound)
Definition: tree.c:7346
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6329
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: tree.c:6306
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
Definition: tree.c:2461
void SCIPnodeGetBdChgsAfterDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int start, int *nbranchvars, int branchvarssize)
Definition: tree.c:7963
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:5903
SCIP_RETCODE SCIPnodeReleaseLPIState(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:275
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:6434
SCIP_RETCODE SCIPtreeFree(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4857
SCIP_RETCODE SCIPnodeCaptureLPIState(SCIP_NODE *node, int nuses)
Definition: tree.c:247
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8386
type definitions for storing and manipulating the main problem
SCIP_NODESEL * SCIPtreeGetNodesel(SCIP_TREE *tree)
Definition: tree.c:5097
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition: tree.c:8238
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8464
SCIP_RETCODE SCIPtreeClear(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:4906
type definitions for propagators
SCIP_RETCODE SCIPtreeStoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:7029
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:5054
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:2087
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:6660
#define SCIP_Real
Definition: def.h:186
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:1608
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8453
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:2116
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
Definition: tree.c:7106
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
Definition: tree.c:8248
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:2409
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8475
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:2477
type definitions for collecting primal CIP solutions and primal informations
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition: tree.c:8258
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
void SCIPchildChgNodeselPrio(SCIP_TREE *tree, SCIP_NODE *child, SCIP_Real priority)
Definition: tree.c:2443
SCIP_RETCODE SCIPtreeRestoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition: tree.c:7073
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:6868
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition: tree.c:7132
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7256
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:7875
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5371
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:5761
memory allocation routines