SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file 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
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
63extern "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 on non-continuous variables based on constraint and propagator propagation
184 *
185 * Stop saving the bound changes when a propagation based on a dual information is reached.
186 */
188 SCIP_NODE* node, /**< node */
189 SCIP_VAR** vars, /**< array of variables on which propagation triggers a bound change */
190 SCIP_Real* varbounds, /**< array of bounds set by propagation */
191 SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes set by propagation */
192 int* npropvars, /**< number of variables on which propagation triggers a bound change
193 * if this is larger than the array size, arrays should be reallocated and method
194 * should be called again */
195 int propvarssize /**< available slots in arrays */
196 );
197
198/** return bound changes on non-continuous variables based on constraint and propagator propagation
199 *
200 * Start saving the bound changes when a propagation based on a dual information is reached.
201 *
202 * @note Currently, we can only detect bound changes based in dual information if they arise from strong branching.
203 */
205 SCIP_NODE* node, /**< node */
206 SCIP_VAR** vars, /**< array where to store variables with bound changes */
207 SCIP_Real* varbounds, /**< array where to store changed bounds */
208 SCIP_BOUNDTYPE* varboundtypes, /**< array where to store type of changed bound*/
209 int* nvars, /**< buffer to store number of bound changes;
210 * if this is larger than varssize, arrays should be reallocated and method
211 * should be called again */
212 int varssize /**< available slots in provided arrays */
213 );
214
215/** adds bound change with inference information to focus node, child of focus node, or probing node;
216 * if possible, adjusts bound to integral value;
217 * at most one of infercons and inferprop may be non-NULL
218 */
220 SCIP_NODE* node, /**< node to add bound change to */
221 BMS_BLKMEM* blkmem, /**< block memory */
222 SCIP_SET* set, /**< global SCIP settings */
223 SCIP_STAT* stat, /**< problem statistics */
224 SCIP_PROB* transprob, /**< transformed problem after presolve */
225 SCIP_PROB* origprob, /**< original problem */
226 SCIP_TREE* tree, /**< branch and bound tree */
227 SCIP_REOPT* reopt, /**< reoptimization data structure */
228 SCIP_LP* lp, /**< current LP data */
229 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
230 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
231 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
232 SCIP_VAR* var, /**< variable to change the bounds for */
233 SCIP_Real newbound, /**< new value for bound */
234 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
235 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
236 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
237 int inferinfo, /**< user information for inference to help resolving the conflict */
238 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
239 );
240
241/** adds bound change to focus node, or child of focus node, or probing node;
242 * if possible, adjusts bound to integral value
243 */
245 SCIP_NODE* node, /**< node to add bound change to */
246 BMS_BLKMEM* blkmem, /**< block memory */
247 SCIP_SET* set, /**< global SCIP settings */
248 SCIP_STAT* stat, /**< problem statistics */
249 SCIP_PROB* transprob, /**< transformed problem after presolve */
250 SCIP_PROB* origprob, /**< original problem */
251 SCIP_TREE* tree, /**< branch and bound tree */
252 SCIP_REOPT* reopt, /**< reoptimization data structure */
253 SCIP_LP* lp, /**< current LP data */
254 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
255 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
256 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
257 SCIP_VAR* var, /**< variable to change the bounds for */
258 SCIP_Real newbound, /**< new value for bound */
259 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
260 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
261 );
262
263/** adds hole with inference information to focus node, child of focus node, or probing node;
264 * if possible, adjusts bound to integral value;
265 * at most one of infercons and inferprop may be non-NULL
266 */
268 SCIP_NODE* node, /**< node to add bound change to */
269 BMS_BLKMEM* blkmem, /**< block memory */
270 SCIP_SET* set, /**< global SCIP settings */
271 SCIP_STAT* stat, /**< problem statistics */
272 SCIP_TREE* tree, /**< branch and bound tree */
273 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
274 SCIP_VAR* var, /**< variable to change the bounds for */
275 SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
276 SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
277 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
278 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
279 int inferinfo, /**< user information for inference to help resolving the conflict */
280 SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
281 SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
282 );
283
284/** adds hole change to focus node, or child of focus node */
286 SCIP_NODE* node, /**< node to add bound change to */
287 BMS_BLKMEM* blkmem, /**< block memory */
288 SCIP_SET* set, /**< global SCIP settings */
289 SCIP_STAT* stat, /**< problem statistics */
290 SCIP_TREE* tree, /**< branch and bound tree */
291 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
292 SCIP_VAR* var, /**< variable to change the bounds for */
293 SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
294 SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
295 SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
296 SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
297 );
298
299/** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
301 SCIP_NODE* node, /**< node to update lower bound for */
302 SCIP_STAT* stat, /**< problem statistics */
303 SCIP_SET* set, /**< global SCIP settings */
304 SCIP_TREE* tree, /**< branch and bound tree */
305 SCIP_PROB* transprob, /**< transformed problem data */
306 SCIP_PROB* origprob, /**< original problem */
307 SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
308 );
309
310/** updates lower bound of node using lower bound of LP */
312 SCIP_NODE* node, /**< node to set lower bound for */
313 SCIP_SET* set, /**< global SCIP settings */
314 SCIP_STAT* stat, /**< problem statistics */
315 SCIP_TREE* tree, /**< branch and bound tree */
316 SCIP_PROB* transprob, /**< transformed problem after presolve */
317 SCIP_PROB* origprob, /**< original problem */
318 SCIP_LP* lp /**< LP data */
319 );
320
321/** change the node selection priority of the given child */
323 SCIP_TREE* tree, /**< branch and bound tree */
324 SCIP_NODE* child, /**< child to update the node selection priority */
325 SCIP_Real priority /**< node selection priority value */
326 );
327
328
329/** sets the node's estimated bound to the new value */
331 SCIP_NODE* node, /**< node to update lower bound for */
332 SCIP_SET* set, /**< global SCIP settings */
333 SCIP_Real newestimate /**< new estimated bound for the node */
334 );
335
336/** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
338 SCIP_NODE* node, /**< node to propagate implications on */
339 BMS_BLKMEM* blkmem, /**< block memory */
340 SCIP_SET* set, /**< global SCIP settings */
341 SCIP_STAT* stat, /**< problem statistics */
342 SCIP_PROB* transprob, /**< transformed problem after presolve */
343 SCIP_PROB* origprob, /**< original problem */
344 SCIP_TREE* tree, /**< branch and bound tree */
345 SCIP_REOPT* reopt, /**< reoptimization data structure */
346 SCIP_LP* lp, /**< current LP data */
347 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
348 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
349 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
350 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
351 );
352
353/** returns all bound changes based on dual information.
354 *
355 * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
356 * method to ensure optimality within reoptimization.
357 *
358 * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
359 * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
360 *
361 * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
362 * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
363 * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
364 */
366 SCIP_NODE* node, /**< node data */
367 SCIP_VAR** vars, /**< array of variables on which the bound change is based on dual information */
368 SCIP_Real* bounds, /**< array of bounds which are based on dual information */
369 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which are based on dual information */
370 int* nvars, /**< number of variables on which the bound change is based on dual information
371 * if this is larger than the array size, arrays should be reallocated and method
372 * should be called again */
373 int varssize /**< available slots in arrays */
374 );
375
376/** returns the number of bound changes based on dual information.
377 *
378 * currently, this methods works only for bound changes made by strong branching on binary variables. we need this
379 * method to ensure optimality within reoptimization.
380 *
381 * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
382 * with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
383 *
384 * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
385 * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
386 * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
387 */
389 SCIP_NODE* node
390 );
391
392/*
393 * Tree methods
394 */
395
396/** creates an initialized tree data structure */
398 SCIP_TREE** tree, /**< pointer to tree data structure */
399 BMS_BLKMEM* blkmem, /**< block memory buffers */
400 SCIP_SET* set, /**< global SCIP settings */
401 SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */
402 );
403
404/** frees tree data structure */
406 SCIP_TREE** tree, /**< pointer to tree data structure */
407 BMS_BLKMEM* blkmem, /**< block memory buffers */
408 SCIP_SET* set, /**< global SCIP settings */
409 SCIP_STAT* stat, /**< problem statistics */
410 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
411 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
412 SCIP_LP* lp /**< current LP data */
413 );
414
415/** clears and resets tree data structure and deletes all nodes */
417 SCIP_TREE* tree, /**< tree data structure */
418 BMS_BLKMEM* blkmem, /**< block memory buffers */
419 SCIP_SET* set, /**< global SCIP settings */
420 SCIP_STAT* stat, /**< problem statistics */
421 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
422 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
423 SCIP_LP* lp /**< current LP data */
424 );
425
426/** creates the root node of the tree and puts it into the leaves queue */
428 SCIP_TREE* tree, /**< tree data structure */
429 SCIP_REOPT* reopt, /**< reoptimization data structure */
430 BMS_BLKMEM* blkmem, /**< block memory buffers */
431 SCIP_SET* set, /**< global SCIP settings */
432 SCIP_STAT* stat, /**< problem statistics */
433 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
434 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
435 SCIP_LP* lp /**< current LP data */
436 );
437
438/** creates a temporary presolving root node of the tree and installs it as focus node */
440 SCIP_TREE* tree, /**< tree data structure */
441 SCIP_REOPT* reopt, /**< reoptimization data structure */
442 BMS_BLKMEM* blkmem, /**< block memory buffers */
443 SCIP_SET* set, /**< global SCIP settings */
444 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
445 SCIP_STAT* stat, /**< problem statistics */
446 SCIP_PROB* transprob, /**< transformed problem */
447 SCIP_PROB* origprob, /**< original problem */
448 SCIP_PRIMAL* primal, /**< primal data */
449 SCIP_LP* lp, /**< current LP data */
450 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
451 SCIP_CONFLICT* conflict, /**< conflict analysis data */
452 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
453 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
454 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
455 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
456 );
457
458/** frees the temporary presolving root and resets tree data structure */
460 SCIP_TREE* tree, /**< tree data structure */
461 SCIP_REOPT* reopt, /**< reoptimization data structure */
462 BMS_BLKMEM* blkmem, /**< block memory buffers */
463 SCIP_SET* set, /**< global SCIP settings */
464 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
465 SCIP_STAT* stat, /**< problem statistics */
466 SCIP_PROB* transprob, /**< transformed problem */
467 SCIP_PROB* origprob, /**< original problem */
468 SCIP_PRIMAL* primal, /**< primal data */
469 SCIP_LP* lp, /**< current LP data */
470 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
471 SCIP_CONFLICT* conflict, /**< conflict analysis data */
472 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
473 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
474 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
475 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
476 );
477
478/** returns the node selector associated with the given node priority queue */
480 SCIP_TREE* tree /**< branch and bound tree */
481 );
482
483/** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
485 SCIP_TREE* tree, /**< branch and bound tree */
486 SCIP_SET* set, /**< global SCIP settings */
487 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
488 SCIP_STAT* stat, /**< problem statistics */
489 SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
490 );
491
492/** cuts off nodes with lower bound not better than given upper bound */
494 SCIP_TREE* tree, /**< branch and bound tree */
495 SCIP_REOPT* reopt, /**< reoptimization data structure */
496 BMS_BLKMEM* blkmem, /**< block memory */
497 SCIP_SET* set, /**< global SCIP settings */
498 SCIP_STAT* stat, /**< dynamic problem statistics */
499 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
500 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
501 SCIP_LP* lp, /**< current LP data */
502 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
503 );
504
505/** constructs the LP relaxation of the focus node */
507 SCIP_TREE* tree, /**< branch and bound tree */
508 BMS_BLKMEM* blkmem, /**< block memory */
509 SCIP_SET* set, /**< global SCIP settings */
510 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
511 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
512 SCIP_LP* lp, /**< current LP data */
513 SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
514 );
515
516/** loads LP state for fork/subroot of the focus node */
518 SCIP_TREE* tree, /**< branch and bound tree */
519 BMS_BLKMEM* blkmem, /**< block memory buffers */
520 SCIP_SET* set, /**< global SCIP settings */
521 SCIP_PROB* prob, /**< problem data */
522 SCIP_STAT* stat, /**< dynamic problem statistics */
523 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
524 SCIP_LP* lp /**< current LP data */
525 );
526
527/** calculates the node selection priority for moving the given variable's LP value to the given target value;
528 * this node selection priority can be given to the SCIPcreateChild() call
529 */
531 SCIP_TREE* tree, /**< branch and bound tree */
532 SCIP_SET* set, /**< global SCIP settings */
533 SCIP_STAT* stat, /**< dynamic problem statistics */
534 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
535 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed
536 * fixed should only be used, when both bounds changed
537 */
538 SCIP_Real targetvalue /**< new value of the variable in the child node */
539 );
540
541/** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
542 * branching; this estimate can be given to the SCIPcreateChild() call
543 */
545 SCIP_TREE* tree, /**< branch and bound tree */
546 SCIP_SET* set, /**< global SCIP settings */
547 SCIP_STAT* stat, /**< dynamic problem statistics */
548 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
549 SCIP_Real targetvalue /**< new value of the variable in the child node */
550 );
551
552/** branches on a variable x
553 * if x is a continuous variable, then two child nodes will be created
554 * (x <= x', x >= x')
555 * but if the bounds of x are such that their relative difference is smaller than epsilon,
556 * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
557 * i.e., no children are created
558 * if x is not a continuous variable, then:
559 * if solution value x' is fractional, two child nodes will be created
560 * (x <= floor(x'), x >= ceil(x')),
561 * if solution value is integral, the x' is equal to lower or upper bound of the branching
562 * variable and the bounds of x are finite, then two child nodes will be created
563 * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
564 * otherwise (up to) three child nodes will be created
565 * (x <= x'-1, x == x', x >= x'+1)
566 * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
567 * will be created (the third one would be infeasible anyway)
568 */
570 SCIP_TREE* tree, /**< branch and bound tree */
571 SCIP_REOPT* reopt, /**< reoptimization data structure */
572 BMS_BLKMEM* blkmem, /**< block memory */
573 SCIP_SET* set, /**< global SCIP settings */
574 SCIP_STAT* stat, /**< problem statistics data */
575 SCIP_PROB* transprob, /**< transformed problem after presolve */
576 SCIP_PROB* origprob, /**< original problem */
577 SCIP_LP* lp, /**< current LP data */
578 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
579 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
580 SCIP_VAR* var, /**< variable to branch on */
581 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 */
582 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
583 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
584 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
585 );
586
587/** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
589 SCIP_TREE* tree, /**< branch and bound tree */
590 SCIP_REOPT* reopt, /**< reoptimization data structure */
591 BMS_BLKMEM* blkmem, /**< block memory */
592 SCIP_SET* set, /**< global SCIP settings */
593 SCIP_STAT* stat, /**< problem statistics data */
594 SCIP_PROB* transprob, /**< transformed problem after presolve */
595 SCIP_PROB* origprob, /**< original problem */
596 SCIP_LP* lp, /**< current LP data */
597 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
598 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
599 SCIP_VAR* var, /**< variable to branch on */
600 SCIP_Real left, /**< left side of the domain hole */
601 SCIP_Real right, /**< right side of the domain hole */
602 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
603 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
604 );
605
606/** n-ary branching on a variable x
607 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
608 * The branching value is selected as in SCIPtreeBranchVar().
609 * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
610 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
611 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
612 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
613 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
614 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
615 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
616 *
617 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
618 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
619 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
620 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
621 * (except for one child if the branching value is not in the middle).
622 */
624 SCIP_TREE* tree, /**< branch and bound tree */
625 SCIP_REOPT* reopt, /**< reoptimization data structure */
626 BMS_BLKMEM* blkmem, /**< block memory */
627 SCIP_SET* set, /**< global SCIP settings */
628 SCIP_STAT* stat, /**< problem statistics data */
629 SCIP_PROB* transprob, /**< transformed problem after presolve */
630 SCIP_PROB* origprob, /**< original problem */
631 SCIP_LP* lp, /**< current LP data */
632 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
633 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
634 SCIP_VAR* var, /**< variable to branch on */
635 SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
636 * A branching value is required for branching on continuous variables */
637 int n, /**< attempted number of children to be created, must be >= 2 */
638 SCIP_Real minwidth, /**< minimal domain width in children */
639 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
640 int* nchildren /**< buffer to store number of created children, or NULL */
641 );
642
643/** adds a diving bound change to the tree together with the information if this is a bound change
644 * for the preferred direction or not
645 */
647 SCIP_TREE* tree, /**< branch and bound tree */
648 BMS_BLKMEM* blkmem, /**< block memory buffers */
649 SCIP_VAR* var, /**< variable to apply the bound change to */
650 SCIP_BRANCHDIR dir, /**< direction of the bound change */
651 SCIP_Real value, /**< value to adjust this variable bound to */
652 SCIP_Bool preferred /**< is this a bound change for the preferred child? */
653 );
654
655/** get the dive bound change data for the preferred or the alternative direction */
657 SCIP_TREE* tree, /**< branch and bound tree */
658 SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
659 SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
660 SCIP_Real** values, /**< pointer to store bound change values */
661 int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
662 SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
663 );
664
665/** clear the tree dive bound change data structure */
667 SCIP_TREE* tree /**< branch and bound tree */
668 );
669
670/** switches to probing mode and creates a probing root */
672 SCIP_TREE* tree, /**< branch and bound tree */
673 BMS_BLKMEM* blkmem, /**< block memory */
674 SCIP_SET* set, /**< global SCIP settings */
675 SCIP_LP* lp, /**< current LP data */
676 SCIP_RELAXATION* relaxation, /**< global relaxation data */
677 SCIP_PROB* transprob, /**< transformed problem after presolve */
678 SCIP_Bool strongbranching /**< is the probing mode used for strongbranching? */
679 );
680
681/** creates a new probing child node in the probing path */
683 SCIP_TREE* tree, /**< branch and bound tree */
684 BMS_BLKMEM* blkmem, /**< block memory */
685 SCIP_SET* set, /**< global SCIP settings */
686 SCIP_LP* lp /**< current LP data */
687 );
688
689/** sets the LP state for the current probing node
690 *
691 * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
692 * to NULL by the method
693 *
694 * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
695 * respective information should not be set
696 */
698 SCIP_TREE* tree, /**< branch and bound tree */
699 BMS_BLKMEM* blkmem, /**< block memory */
700 SCIP_LP* lp, /**< current LP data */
701 SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
702 SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
703 SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
704 SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
705 );
706
707/** loads the LP state for the current probing node */
709 SCIP_TREE* tree, /**< branch and bound tree */
710 BMS_BLKMEM* blkmem, /**< block memory buffers */
711 SCIP_SET* set, /**< global SCIP settings */
712 SCIP_PROB* prob, /**< problem data */
713 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
714 SCIP_LP* lp /**< current LP data */
715 );
716
717/** marks the probing node to have a solved LP relaxation */
719 SCIP_TREE* tree, /**< branch and bound tree */
720 BMS_BLKMEM* blkmem, /**< block memory */
721 SCIP_LP* lp /**< current LP data */
722 );
723
724/** undoes all changes to the problem applied in probing up to the given probing depth;
725 * the changes of the probing node of the given probing depth are the last ones that remain active;
726 * changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone
727 */
729 SCIP_TREE* tree, /**< branch and bound tree */
730 SCIP_REOPT* reopt, /**< reoptimization data structure */
731 BMS_BLKMEM* blkmem, /**< block memory buffers */
732 SCIP_SET* set, /**< global SCIP settings */
733 SCIP_STAT* stat, /**< problem statistics */
734 SCIP_PROB* transprob, /**< transformed problem */
735 SCIP_PROB* origprob, /**< original problem */
736 SCIP_LP* lp, /**< current LP data */
737 SCIP_PRIMAL* primal, /**< primal data structure */
738 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
739 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
740 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
741 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
742 int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
743 );
744
745/** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
746 * variables and restores active constraints arrays of focus node
747 */
749 SCIP_TREE* tree, /**< branch and bound tree */
750 SCIP_REOPT* reopt, /**< reoptimization data structure */
751 BMS_BLKMEM* blkmem, /**< block memory buffers */
752 SCIP_SET* set, /**< global SCIP settings */
753 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
754 SCIP_STAT* stat, /**< problem statistics */
755 SCIP_PROB* transprob, /**< transformed problem after presolve */
756 SCIP_PROB* origprob, /**< original problem */
757 SCIP_LP* lp, /**< current LP data */
758 SCIP_RELAXATION* relaxation, /**< global relaxation data */
759 SCIP_PRIMAL* primal, /**< primal LP data */
760 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
761 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
762 SCIP_EVENTFILTER* eventfilter, /**< global event filter */
763 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
764 );
765
766/** stores relaxation solution before diving or probing */
768 SCIP_TREE* tree, /**< branch and bound tree */
769 SCIP_SET* set, /**< global SCIP settings */
770 SCIP_RELAXATION* relaxation, /**< global relaxation data */
771 SCIP_PROB* transprob /**< transformed problem after presolve */
772 );
773
774/** restores relaxation solution after diving or probing */
776 SCIP_TREE* tree, /**< branch and bound tree */
777 SCIP_SET* set, /**< global SCIP settings */
778 SCIP_RELAXATION* relaxation, /**< global relaxation data */
779 SCIP_PROB* transprob /**< transformed problem after presolve */
780 );
781
782
783/** gets number of children of the focus node */
785 SCIP_TREE* tree /**< branch and bound tree */
786 );
787
788/** gets number of siblings of the focus node */
790 SCIP_TREE* tree /**< branch and bound tree */
791 );
792
793/** gets number of leaves in the tree (excluding children and siblings of focus nodes) */
795 SCIP_TREE* tree /**< branch and bound tree */
796 );
797
798/** gets number of open nodes in the tree (children + siblings + leaves) */
800 SCIP_TREE* tree /**< branch and bound tree */
801 );
802
803/** returns whether the active path goes completely down to the focus node */
805 SCIP_TREE* tree /**< branch and bound tree */
806 );
807
808/** returns whether the current node is a temporary probing node */
810 SCIP_TREE* tree /**< branch and bound tree */
811 );
812
813/** returns the temporary probing root node, or NULL if the we are not in probing mode */
815 SCIP_TREE* tree /**< branch and bound tree */
816 );
817
818/** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
820 SCIP_TREE* tree /**< branch and bound tree */
821 );
822
823/** gets focus node of the tree */
825 SCIP_TREE* tree /**< branch and bound tree */
826 );
827
828/** gets depth of focus node in the tree, or -1 if no focus node exists */
830 SCIP_TREE* tree /**< branch and bound tree */
831 );
832
833/** returns, whether the LP was or is to be solved in the focus node */
835 SCIP_TREE* tree /**< branch and bound tree */
836 );
837
838/** sets mark to solve or to ignore the LP while processing the focus node */
840 SCIP_TREE* tree, /**< branch and bound tree */
841 SCIP_Bool solvelp /**< should the LP be solved in focus node? */
842 );
843
844/** returns whether the LP of the focus node is already constructed */
846 SCIP_TREE* tree /**< branch and bound tree */
847 );
848
849/** returns whether the focus node is already solved and only propagated again */
851 SCIP_TREE* tree /**< branch and bound tree */
852 );
853
854/** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
856 SCIP_TREE* tree /**< branch and bound tree */
857 );
858
859/** 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 */
861 SCIP_TREE* tree /**< branch and bound tree */
862 );
863
864/** returns, whether the LP was or is to be solved in the current node */
866 SCIP_TREE* tree /**< branch and bound tree */
867 );
868
869/** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
871 SCIP_TREE* tree /**< branch and bound tree */
872 );
873
874/** gets the root node of the tree */
876 SCIP_TREE* tree /**< branch and bound tree */
877 );
878
879/** returns whether we are in probing and the objective value of at least one column was changed */
881 SCIP_TREE* tree /**< branch and bound tree */
882 );
883
884/** marks the current probing node to have a changed objective function */
886 SCIP_TREE* tree /**< branch and bound tree */
887 );
888
889#ifdef NDEBUG
890
891/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
892 * speed up the algorithms.
893 */
894
895#define SCIPtreeGetNLeaves(tree) SCIPnodepqLen((tree)->leaves)
896#define SCIPtreeGetNChildren(tree) ((tree)->nchildren)
897#define SCIPtreeGetNSiblings(tree) ((tree)->nsiblings)
898#define SCIPtreeGetNNodes(tree) \
899 (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree))
900#define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
901#define SCIPtreeProbing(tree) ((tree)->probingroot != NULL)
902#define SCIPtreeGetProbingRoot(tree) (tree)->probingroot
903#define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
904#define SCIPtreeGetFocusNode(tree) (tree)->focusnode
905#define SCIPtreeGetFocusDepth(tree) ((tree)->focusnode != NULL ? (int)(tree)->focusnode->depth : -1)
906#define SCIPtreeHasFocusNodeLP(tree) (tree)->focusnodehaslp
907#define SCIPtreeSetFocusNodeLP(tree,solvelp) ((tree)->focusnodehaslp = solvelp)
908#define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed
909#define SCIPtreeInRepropagation(tree) ((tree)->focusnode != NULL \
910 && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
911#define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
912#define SCIPtreeGetCurrentDepth(tree) ((tree)->pathlen-1)
913#define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
914#define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth)
915#define SCIPtreeGetRootNode(tree) ((tree)->root)
916#define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged)
917#define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE)
918
919#endif
920
921
922/** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
924 SCIP_TREE* tree /**< branch and bound tree */
925 );
926
927/** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
929 SCIP_TREE* tree /**< branch and bound tree */
930 );
931
932/** gets the best child of the focus node w.r.t. the node selection strategy */
934 SCIP_TREE* tree, /**< branch and bound tree */
935 SCIP_SET* set /**< global SCIP settings */
936 );
937
938/** gets the best sibling of the focus node w.r.t. the node selection strategy */
940 SCIP_TREE* tree, /**< branch and bound tree */
941 SCIP_SET* set /**< global SCIP settings */
942 );
943
944/** gets the best leaf from the node queue w.r.t. the node selection strategy */
946 SCIP_TREE* tree /**< branch and bound tree */
947 );
948
949/** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
951 SCIP_TREE* tree, /**< branch and bound tree */
952 SCIP_SET* set /**< global SCIP settings */
953 );
954
955/** gets the minimal lower bound of all nodes in the tree */
957 SCIP_TREE* tree, /**< branch and bound tree */
958 SCIP_SET* set /**< global SCIP settings */
959 );
960
961/** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */
963 SCIP_TREE* tree, /**< branch and bound tree */
964 SCIP_SET* set /**< global SCIP settings */
965 );
966
967/** gets the average lower bound of all nodes in the tree */
969 SCIP_TREE* tree, /**< branch and bound tree */
970 SCIP_Real cutoffbound /**< global cutoff bound */
971 );
972
973/** query if focus node was already branched on */
975 SCIP_TREE* tree, /**< branch and bound tree */
976 SCIP_NODE* node /**< tree node, or NULL to check focus node */
977 );
978
979#ifdef __cplusplus
980}
981#endif
982
983#endif
common defines and data types used in all packages of SCIP
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
SCIP_Bool cutoff
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:437
internal methods for node selectors and node priority queues
public methods for branch and bound tree
data structures for branch and bound tree
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:2380
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition tree.c:8466
SCIP_NODE * SCIPtreeGetProbingRoot(SCIP_TREE *tree)
Definition tree.c:8398
SCIP_RETCODE SCIPnodeReleaseLPIState(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition tree.c:276
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:2136
void SCIPnodeGetDualBoundchgs(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_BOUNDTYPE *boundtypes, int *nvars, int varssize)
Definition tree.c:7728
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7253
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:1238
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition tree.c:8411
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition tree.c:8385
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition tree.c:8428
SCIP_Real SCIPtreeGetAvgLowerbound(SCIP_TREE *tree, SCIP_Real cutoffbound)
Definition tree.c:7414
SCIP_Bool SCIPtreeIsPathComplete(SCIP_TREE *tree)
Definition tree.c:8368
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition tree.c:8564
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition tree.c:8531
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
Definition tree.c:5195
SCIP_RETCODE SCIPnodeDelCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition tree.c:1671
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
Definition tree.c:2486
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:5827
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:5969
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition tree.c:1302
SCIP_RETCODE SCIPnodeCaptureLPIState(SCIP_NODE *node, int nuses)
Definition tree.c:248
void SCIPnodeGetPropsAfterDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int *nvars, int varssize)
Definition tree.c:8041
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:6501
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:4945
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:5496
int SCIPtreeGetNChildren(SCIP_TREE *tree)
Definition tree.c:8328
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:6591
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:1102
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition tree.c:8486
void SCIPnodeMarkPropagated(SCIP_NODE *node, SCIP_TREE *tree)
Definition tree.c:1328
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
Definition tree.c:8348
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition tree.c:8553
SCIP_RETCODE SCIPtreeStoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition tree.c:7097
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:1040
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition tree.c:8575
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition tree.c:6340
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition tree.c:8520
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7324
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:1832
SCIP_RETCODE SCIPtreeRestoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
Definition tree.c:7141
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:2249
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:5101
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:2502
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7226
SCIP_RETCODE SCIPtreeLoadProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition tree.c:6645
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition tree.c:8542
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
Definition tree.c:7200
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:2107
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition tree.c:8455
int SCIPnodeGetNDualBndchgs(SCIP_NODE *node)
Definition tree.c:7683
SCIP_RETCODE SCIPnodeAddCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition tree.c:1628
int SCIPtreeGetNNodes(SCIP_TREE *tree)
Definition tree.c:8358
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition tree.c:5287
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:4994
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
Definition tree.c:8338
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7290
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
Definition tree.c:7280
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:6936
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
Definition tree.c:8445
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition tree.c:6372
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:4406
SCIP_RETCODE SCIPtreeCreate(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition tree.c:4864
void SCIPchildChgNodeselPrio(SCIP_TREE *tree, SCIP_NODE *child, SCIP_Real priority)
Definition tree.c:2468
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition tree.c:8503
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
Definition tree.c:7174
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:5055
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
Definition tree.c:1089
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition tree.c:6566
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition tree.c:6727
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:2426
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:5223
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:3644
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
Definition tree.c:8476
SCIP_NODESEL * SCIPtreeGetNodesel(SCIP_TREE *tree)
Definition tree.c:5185
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition tree.c:5437
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition tree.c:7362
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:6902
void SCIPnodeGetPropsBeforeDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int *npropvars, int propvarssize)
Definition tree.c:7959
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:3516
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition tree.c:6395
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:5142
type definitions for branching rules
struct SCIP_BranchCand SCIP_BRANCHCAND
Definition type_branch.h:55
struct SCIP_Conflict SCIP_CONFLICT
type definitions for conflict store
struct SCIP_ConflictStore SCIP_CONFLICTSTORE
type definitions for constraints and constraint handlers
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
type definitions for managing events
struct SCIP_EventFilter SCIP_EVENTFILTER
Definition type_event.h:174
struct SCIP_EventQueue SCIP_EVENTQUEUE
Definition type_event.h:175
type definitions for branching and inference history
enum SCIP_BranchDir SCIP_BRANCHDIR
type definitions for implications, variable bounds, and cliques
struct SCIP_CliqueTable SCIP_CLIQUETABLE
type definitions for LP management
struct SCIP_Lp SCIP_LP
Definition type_lp.h:110
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition type_lp.h:59
struct SCIP_LPiState SCIP_LPISTATE
Definition type_lpi.h:107
struct SCIP_LPiNorms SCIP_LPINORMS
Definition type_lpi.h:108
struct SCIP_Messagehdlr SCIP_MESSAGEHDLR
struct SCIP_Nodesel SCIP_NODESEL
type definitions for collecting primal CIP solutions and primal informations
struct SCIP_Primal SCIP_PRIMAL
Definition type_primal.h:39
type definitions for storing and manipulating the main problem
struct SCIP_Prob SCIP_PROB
Definition type_prob.h:52
type definitions for propagators
struct SCIP_Prop SCIP_PROP
Definition type_prop.h:51
struct SCIP_Relaxation SCIP_RELAXATION
Definition type_relax.h:46
type definitions for collecting reoptimization information
struct SCIP_Reopt SCIP_REOPT
Definition type_reopt.h:39
enum SCIP_Retcode SCIP_RETCODE
type definitions for global SCIP settings
struct SCIP_Set SCIP_SET
Definition type_set.h:71
type definitions for problem statistics
struct SCIP_Stat SCIP_STAT
Definition type_stat.h:69
type definitions for branch and bound tree
struct SCIP_Node SCIP_NODE
Definition type_tree.h:63
struct SCIP_Tree SCIP_TREE
Definition type_tree.h:65
type definitions for problem variables
struct SCIP_Var SCIP_VAR
Definition type_var.h:119