Scippy

SCIP

Solving Constraint Integer Programs

Data Fields
SCIP_Tree Struct Reference

Detailed Description

branch and bound tree

Definition at line 160 of file struct_tree.h.

#include <struct_tree.h>

Data Fields

SCIP_NODE * root
 
SCIP_NODEPQ * leaves
 
SCIP_NODE ** path
 
SCIP_NODE * focusnode
 
SCIP_NODE * focuslpfork
 
SCIP_NODE * focuslpstatefork
 
SCIP_NODE * focussubroot
 
SCIP_NODE * probingroot
 
SCIP_NODE ** children
 
SCIP_NODE ** siblings
 
SCIP_Real * childrenprio
 
SCIP_Real * siblingsprio
 
int * pathnlpcols
 
int * pathnlprows
 
SCIP_LPISTATE * probinglpistate
 
SCIP_LPINORMS * probinglpinorms
 
SCIP_PENDINGBDCHG * pendingbdchgs
 
SCIP_Longint focuslpstateforklpcount
 
int pendingbdchgssize
 
int npendingbdchgs
 
int childrensize
 
int nchildren
 
int siblingssize
 
int nsiblings
 
int pathlen
 
int pathsize
 
int effectiverootdepth
 
int appliedeffectiverootdepth
 
int correctlpdepth
 
int cutoffdepth
 
int repropdepth
 
int repropsubtreecount
 
SCIP_Bool focusnodehaslp
 
SCIP_Bool probingnodehaslp
 
SCIP_Bool focuslpconstructed
 
SCIP_Bool cutoffdelayed
 
SCIP_Bool probinglpwasflushed
 
SCIP_Bool probinglpwassolved
 
SCIP_Bool probingloadlpistate
 
SCIP_Bool probinglpwasrelax
 
SCIP_Bool probingsolvedlp
 
SCIP_Bool forcinglpmessage
 
SCIP_Bool sbprobing
 
SCIP_Bool probinglpwasprimfeas
 
SCIP_Bool probinglpwasdualfeas
 

Field Documentation

SCIP_NODE* SCIP_Tree::root

root node of the tree

Definition at line 162 of file struct_tree.h.

Referenced by conflictAddConflictCons(), focusnodeCleanupVars(), focusnodeToFork(), SCIPchgVarLb(), SCIPchgVarLbGlobal(), SCIPchgVarUb(), SCIPchgVarUbGlobal(), SCIPinferVarLbCons(), SCIPinferVarLbProp(), SCIPinferVarUbCons(), SCIPinferVarUbProp(), SCIPnodeAddBoundinfer(), SCIPnodeAddCons(), SCIPnodeAddHoleinfer(), SCIPnodeFree(), SCIPshrinkDisjunctiveVarSet(), SCIPtightenVarLb(), SCIPtightenVarLbGlobal(), SCIPtightenVarUb(), SCIPtightenVarUbGlobal(), SCIPtreeClear(), SCIPtreeCreatePresolvingRoot(), SCIPtreeCreateRoot(), SCIPtreeFreePresolvingRoot(), SCIPtreeGetRootNode(), and treeFindSwitchForks().

SCIP_NODEPQ* SCIP_Tree::leaves

leaves of the tree

Definition at line 163 of file struct_tree.h.

Referenced by nodeToLeaf(), SCIPgetLeaves(), SCIPgetNLeaves(), SCIPgetOpenNodesData(), SCIPnodeFocus(), SCIPtreeClear(), SCIPtreeCutoff(), SCIPtreeGetAvgLowerbound(), SCIPtreeGetBestChild(), SCIPtreeGetBestLeaf(), SCIPtreeGetBestNode(), SCIPtreeGetBestSibling(), SCIPtreeGetLowerbound(), SCIPtreeGetLowerboundNode(), SCIPtreeGetNLeaves(), SCIPtreeGetNodesel(), and SCIPtreeSetNodesel().

SCIP_NODE** SCIP_Tree::path

array of nodes storing the active path from root to current node, which is usually the focus or a probing node; in case of a cut off, the path may already end earlier

Definition at line 164 of file struct_tree.h.

Referenced by conflictAddConflictCons(), conflictAddConflictset(), conflictAnalyze(), conflictCreateReconvergenceConss(), nodeAssignParent(), SCIPconflictFlushConss(), SCIPnodeAddBoundinfer(), SCIPnodeCreateChild(), SCIPnodeFocus(), SCIPnodeMarkPropagated(), SCIPtreeEndProbing(), SCIPtreeGetCurrentDepth(), SCIPtreeGetCurrentNode(), SCIPtreeGetFocusDepth(), SCIPtreeGetFocusNode(), SCIPtreeGetProbingRoot(), SCIPtreeIsPathComplete(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), SCIPtreeProbing(), treeBacktrackProbing(), treeCheckPath(), treeCreateProbingNode(), treeEnsurePathMem(), treeFindSwitchForks(), treeSwitchPath(), treeUpdatePathLPSize(), and updatePseudocost().

SCIP_NODE* SCIP_Tree::focusnode

focus node: the node that is stored together with its children and siblings in the tree data structure; the focus node is the currently processed node; it doesn't need to be active all the time, because it may be cut off and the active path stops at the cut off node

Definition at line 167 of file struct_tree.h.

Referenced by focusnodeCleanupVars(), focusnodeToDeadend(), focusnodeToFork(), focusnodeToJunction(), focusnodeToPseudofork(), forkCreate(), junctionInit(), nodeAssignParent(), nodeRepropagate(), pseudoforkCreate(), SCIPbranchruleExecExternSol(), SCIPbranchruleExecLPSol(), SCIPbranchruleExecPseudoSol(), SCIPendDive(), SCIPnodeAddBoundinfer(), SCIPnodeAddHoleinfer(), SCIPnodeCreateChild(), SCIPnodeFocus(), SCIPnodeFree(), SCIPsolveCIP(), SCIPtreeBranchVar(), SCIPtreeBranchVarHole(), SCIPtreeBranchVarNary(), SCIPtreeCalcChildEstimate(), SCIPtreeClear(), SCIPtreeCreatePresolvingRoot(), SCIPtreeCreateRoot(), SCIPtreeEndProbing(), SCIPtreeFreePresolvingRoot(), SCIPtreeGetAvgLowerbound(), SCIPtreeGetCurrentDepth(), SCIPtreeGetCurrentNode(), SCIPtreeGetFocusDepth(), SCIPtreeGetFocusNode(), SCIPtreeGetLowerbound(), SCIPtreeInRepropagation(), SCIPtreeIsPathComplete(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), solveNodeLP(), treeBacktrackProbing(), and treeFindSwitchForks().

SCIP_NODE* SCIP_Tree::focuslpfork

LP defining pseudofork/fork/subroot of the focus node

Definition at line 171 of file struct_tree.h.

Referenced by nodeRepropagate(), SCIPnodeFocus(), SCIPtreeLoadLP(), and treeFindSwitchForks().

SCIP_NODE* SCIP_Tree::focuslpstatefork

LP state defining fork/subroot of the focus node

Definition at line 172 of file struct_tree.h.

Referenced by focusnodeToDeadend(), focusnodeToFork(), focusnodeToJunction(), focusnodeToPseudofork(), junctionInit(), nodeRepropagate(), pseudoforkCreate(), SCIPnodeFocus(), SCIPnodeFree(), SCIPprimalHeuristics(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), treeFindSwitchForks(), and updatePseudocost().

SCIP_NODE* SCIP_Tree::focussubroot

subroot of the focus node's sub tree

Definition at line 173 of file struct_tree.h.

Referenced by nodeRepropagate(), SCIPnodeFocus(), SCIPtreeLoadLP(), and treeFindSwitchForks().

SCIP_NODE* SCIP_Tree::probingroot

root node of the current probing path, or NULL

Definition at line 174 of file struct_tree.h.

Referenced by SCIPnodeAddBoundinfer(), SCIPnodeAddHoleinfer(), SCIPnodeFree(), SCIPtreeCreateProbingNode(), SCIPtreeEndProbing(), SCIPtreeGetProbingDepth(), SCIPtreeGetProbingRoot(), SCIPtreeProbing(), treeBacktrackProbing(), and treeCreateProbingNode().

SCIP_NODE** SCIP_Tree::children

array with children of the focus node

Definition at line 175 of file struct_tree.h.

Referenced by SCIPgetChildren(), SCIPgetOpenNodesData(), SCIPnodeFocus(), SCIPnodeFree(), SCIPtreeCreateRoot(), SCIPtreeCutoff(), SCIPtreeGetAvgLowerbound(), SCIPtreeGetBestChild(), SCIPtreeGetLowerbound(), SCIPtreeGetLowerboundNode(), SCIPtreeGetPrioChild(), treeAddChild(), treeChildrenToSiblings(), treeEnsureChildrenMem(), and treeRemoveChild().

SCIP_NODE** SCIP_Tree::siblings

array with siblings of the focus node

Definition at line 176 of file struct_tree.h.

Referenced by SCIPgetOpenNodesData(), SCIPgetSiblings(), SCIPnodeFocus(), SCIPnodeFree(), SCIPtreeCutoff(), SCIPtreeGetAvgLowerbound(), SCIPtreeGetBestSibling(), SCIPtreeGetLowerbound(), SCIPtreeGetLowerboundNode(), SCIPtreeGetPrioSibling(), treeChildrenToSiblings(), and treeRemoveSibling().

SCIP_Real* SCIP_Tree::childrenprio

array with node selection priorities of children

Definition at line 177 of file struct_tree.h.

Referenced by SCIPchildChgNodeselPrio(), SCIPtreeGetLowerboundNode(), SCIPtreeGetPrioChild(), treeAddChild(), treeChildrenToSiblings(), treeEnsureChildrenMem(), and treeRemoveChild().

SCIP_Real* SCIP_Tree::siblingsprio

array with node selection priorities of siblings

Definition at line 178 of file struct_tree.h.

Referenced by SCIPtreeGetLowerboundNode(), SCIPtreeGetPrioSibling(), treeChildrenToSiblings(), and treeRemoveSibling().

int* SCIP_Tree::pathnlpcols

array with number of LP columns for each problem in active path (except newly added columns of the focus node and the current probing node)

Definition at line 179 of file struct_tree.h.

Referenced by SCIPnodeFocus(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), treeBacktrackProbing(), treeCheckPath(), treeCreateProbingNode(), treeEnsurePathMem(), and treeUpdatePathLPSize().

int* SCIP_Tree::pathnlprows

array with number of LP rows for each problem in active path (except newly added rows of the focus node and the current probing node)

Definition at line 181 of file struct_tree.h.

Referenced by SCIPnodeFocus(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), treeBacktrackProbing(), treeCheckPath(), treeCreateProbingNode(), treeEnsurePathMem(), and treeUpdatePathLPSize().

SCIP_LPISTATE* SCIP_Tree::probinglpistate

LP state information before probing started

Definition at line 183 of file struct_tree.h.

Referenced by SCIPtreeEndProbing(), SCIPtreeLoadProbingLPState(), and SCIPtreeStartProbing().

SCIP_LPINORMS* SCIP_Tree::probinglpinorms

LP pricing norms information before probing started

Definition at line 184 of file struct_tree.h.

Referenced by SCIPtreeEndProbing(), SCIPtreeLoadProbingLPState(), and SCIPtreeStartProbing().

SCIP_PENDINGBDCHG* SCIP_Tree::pendingbdchgs

array of pending bound changes, or NULL

Definition at line 185 of file struct_tree.h.

Referenced by SCIPtreeClear(), treeAddPendingBdchg(), treeApplyPendingBdchgs(), and treeEnsurePendingbdchgsMem().

SCIP_Longint SCIP_Tree::focuslpstateforklpcount

LP number of last solved LP in current LP state fork, or -1 if unknown

Definition at line 186 of file struct_tree.h.

Referenced by nodeRepropagate(), SCIPnodeAddBoundinfer(), SCIPnodeFocus(), SCIPtreeClear(), and SCIPtreeLoadLPState().

int SCIP_Tree::pendingbdchgssize

size of pendingbdchgs array

Definition at line 187 of file struct_tree.h.

Referenced by treeEnsurePendingbdchgsMem().

int SCIP_Tree::npendingbdchgs

number of pending bound changes

Definition at line 188 of file struct_tree.h.

Referenced by SCIPshrinkDisjunctiveVarSet(), SCIPtreeClear(), treeAddPendingBdchg(), and treeApplyPendingBdchgs().

int SCIP_Tree::childrensize

available slots in children vector

Definition at line 189 of file struct_tree.h.

Referenced by treeChildrenToSiblings(), and treeEnsureChildrenMem().

int SCIP_Tree::nchildren

number of children of focus node (number of used slots in children vector)

Definition at line 190 of file struct_tree.h.

Referenced by enforceConstraints(), focusnodeToDeadend(), focusnodeToFork(), focusnodeToPseudofork(), forkCreate(), junctionInit(), nodeRepropagate(), pseudoforkCreate(), SCIPbranchruleExecExternSol(), SCIPbranchruleExecLPSol(), SCIPbranchruleExecPseudoSol(), SCIPconshdlrEnforceLPSol(), SCIPconshdlrEnforcePseudoSol(), SCIPgetChildren(), SCIPgetNChildren(), SCIPnodeFocus(), SCIPnodeFree(), SCIPsolveCIP(), SCIPtreeClear(), SCIPtreeCreatePresolvingRoot(), SCIPtreeCreateRoot(), SCIPtreeCutoff(), SCIPtreeGetAvgLowerbound(), SCIPtreeGetBestChild(), SCIPtreeGetLowerbound(), SCIPtreeGetLowerboundNode(), SCIPtreeGetNChildren(), SCIPtreeGetNNodes(), SCIPtreeGetPrioChild(), solveNode(), treeAddChild(), treeChildrenToSiblings(), treeRemoveChild(), and updateLoopStatus().

int SCIP_Tree::siblingssize

available slots in siblings vector

Definition at line 191 of file struct_tree.h.

Referenced by treeChildrenToSiblings().

int SCIP_Tree::nsiblings

number of siblings of focus node (number of used slots in siblings vector)

Definition at line 192 of file struct_tree.h.

Referenced by nodeRepropagate(), SCIPgetNSiblings(), SCIPgetSiblings(), SCIPnodeFocus(), SCIPnodeFree(), SCIPsolveCIP(), SCIPtreeClear(), SCIPtreeCreatePresolvingRoot(), SCIPtreeCreateRoot(), SCIPtreeCutoff(), SCIPtreeGetAvgLowerbound(), SCIPtreeGetBestSibling(), SCIPtreeGetLowerbound(), SCIPtreeGetLowerboundNode(), SCIPtreeGetNNodes(), SCIPtreeGetNSiblings(), SCIPtreeGetPrioSibling(), solveNode(), treeChildrenToSiblings(), and treeRemoveSibling().

int SCIP_Tree::pathlen

length of the current path

Definition at line 193 of file struct_tree.h.

Referenced by conflictAddConflictset(), conflictAnalyze(), conflictCreateReconvergenceConss(), conflictsetCalcInsertDepth(), nodeAssignParent(), SCIPconflictFlushConss(), SCIPnodeCreateChild(), SCIPnodeFocus(), SCIPnodeMarkPropagated(), SCIPtreeClear(), SCIPtreeCreateProbingNode(), SCIPtreeEndProbing(), SCIPtreeFreePresolvingRoot(), SCIPtreeGetCurrentDepth(), SCIPtreeGetCurrentNode(), SCIPtreeGetFocusDepth(), SCIPtreeGetFocusNode(), SCIPtreeGetProbingRoot(), SCIPtreeIsPathComplete(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), SCIPtreeProbing(), SCIPtreeStartProbing(), treeBacktrackProbing(), treeCheckPath(), treeCreateProbingNode(), treeFindSwitchForks(), treeSwitchPath(), and treeUpdatePathLPSize().

int SCIP_Tree::pathsize

number of available slots in path arrays

Definition at line 194 of file struct_tree.h.

Referenced by treeEnsurePathMem().

int SCIP_Tree::effectiverootdepth

first depth with node with at least two children

Definition at line 195 of file struct_tree.h.

Referenced by nodeReleaseParent(), SCIPnodeAddBoundinfer(), SCIPnodeAddCons(), SCIPnodeAddHoleinfer(), SCIPnodeFocus(), SCIPtreeClear(), SCIPtreeGetEffectiveRootDepth(), and treeApplyPendingBdchgs().

int SCIP_Tree::appliedeffectiverootdepth

the effective root depth which was already enforced (that is constraint and bound changes were made global)

Definition at line 196 of file struct_tree.h.

Referenced by SCIPnodeFocus(), and SCIPtreeClear().

int SCIP_Tree::correctlpdepth

depth to which current LP data corresponds to LP data of active path

Definition at line 197 of file struct_tree.h.

Referenced by SCIPnodeFocus(), SCIPtreeClear(), SCIPtreeLoadLP(), and SCIPtreeLoadLPState().

int SCIP_Tree::cutoffdepth

depth of first node in active path that is marked being cutoff

Definition at line 198 of file struct_tree.h.

Referenced by propagationRound(), propAndSolve(), SCIPgetCutoffdepth(), SCIPnodeCutoff(), SCIPnodeFocus(), SCIPtreeClear(), treeApplyPendingBdchgs(), treeBacktrackProbing(), treeFindSwitchForks(), and updateLoopStatus().

int SCIP_Tree::repropdepth

depth of first node in active path that has to be propagated again

Definition at line 199 of file struct_tree.h.

Referenced by SCIPgetRepropdepth(), SCIPnodeMarkPropagated(), SCIPnodePropagateAgain(), SCIPtreeClear(), treeBacktrackProbing(), and treeFindSwitchForks().

int SCIP_Tree::repropsubtreecount

cyclicly increased counter to create markers for subtree repropagation

Definition at line 200 of file struct_tree.h.

Referenced by nodeRepropagate(), SCIPtreeClear(), and treeNextRepropsubtreecount().

SCIP_Bool SCIP_Tree::focusnodehaslp

is LP being processed in the focus node?

Definition at line 201 of file struct_tree.h.

Referenced by nodeRepropagate(), SCIPnodeFocus(), SCIPtreeBranchVar(), SCIPtreeBranchVarHole(), SCIPtreeBranchVarNary(), SCIPtreeClear(), SCIPtreeEndProbing(), SCIPtreeHasFocusNodeLP(), and SCIPtreeSetFocusNodeLP().

SCIP_Bool SCIP_Tree::probingnodehaslp

was the LP solved (at least once) in the current probing node?

Definition at line 202 of file struct_tree.h.

Referenced by SCIPtreeClear(), SCIPtreeHasCurrentNodeLP(), SCIPtreeMarkProbingNodeHasLP(), and treeCreateProbingNode().

SCIP_Bool SCIP_Tree::focuslpconstructed

was the LP of the focus node already constructed?

Definition at line 203 of file struct_tree.h.

Referenced by SCIPnodeFocus(), SCIPtreeEndProbing(), SCIPtreeIsFocusNodeLPConstructed(), SCIPtreeLoadLP(), SCIPtreeLoadLPState(), treeBacktrackProbing(), treeCheckPath(), and treeUpdatePathLPSize().

SCIP_Bool SCIP_Tree::cutoffdelayed

the treeCutoff() call was delayed because of diving and has to be executed

Definition at line 204 of file struct_tree.h.

Referenced by SCIPendDive(), SCIPsolveCIP(), SCIPtreeClear(), and SCIPtreeCutoff().

SCIP_Bool SCIP_Tree::probinglpwasflushed

was the LP flushed before we entered the probing mode?

Definition at line 205 of file struct_tree.h.

Referenced by SCIPtreeClear(), SCIPtreeEndProbing(), and SCIPtreeStartProbing().

SCIP_Bool SCIP_Tree::probinglpwassolved

was the LP solved before we entered the probing mode?

Definition at line 206 of file struct_tree.h.

Referenced by SCIPtreeClear(), SCIPtreeEndProbing(), and SCIPtreeStartProbing().

SCIP_Bool SCIP_Tree::probingloadlpistate

must the LP state be reloaded because of a backtrack in probing?

Definition at line 207 of file struct_tree.h.

Referenced by SCIPtreeClear(), SCIPtreeEndProbing(), SCIPtreeLoadProbingLPState(), SCIPtreeStartProbing(), and treeBacktrackProbing().

SCIP_Bool SCIP_Tree::probinglpwasrelax

was the LP a valid relaxation before we entered the probing mode?

Definition at line 208 of file struct_tree.h.

Referenced by SCIPtreeClear(), SCIPtreeEndProbing(), and SCIPtreeStartProbing().

SCIP_Bool SCIP_Tree::probingsolvedlp

was the LP solved during probing mode, i.e., was SCIPsolveProbingLP() called?

Definition at line 209 of file struct_tree.h.

Referenced by SCIPtreeClear(), SCIPtreeEndProbing(), SCIPtreeStartProbing(), and solveProbingLP().

SCIP_Bool SCIP_Tree::forcinglpmessage

was forcing LP solving message be posted

Definition at line 210 of file struct_tree.h.

Referenced by solveNode().

SCIP_Bool SCIP_Tree::sbprobing

is the probing mode used for strong branching?

Definition at line 211 of file struct_tree.h.

Referenced by propagationRound(), SCIPtreeEndProbing(), and SCIPtreeStartProbing().

SCIP_Bool SCIP_Tree::probinglpwasprimfeas

primal feasibility when probing started

Definition at line 212 of file struct_tree.h.

Referenced by SCIPtreeEndProbing(), SCIPtreeLoadProbingLPState(), and SCIPtreeStartProbing().

SCIP_Bool SCIP_Tree::probinglpwasdualfeas

dual feasibility when probing started

Definition at line 213 of file struct_tree.h.

Referenced by SCIPtreeEndProbing(), SCIPtreeLoadProbingLPState(), and SCIPtreeStartProbing().