SCIP

Solving Constraint Integer Programs

SCIP_Tree Struct Reference

Detailed Description

branch and bound tree

Definition at line 175 of file struct_tree.h.

#include <struct_tree.h>

Data Fields

SCIP_NODEroot

SCIP_NODEPQleaves

SCIP_NODE ** path

SCIP_NODEfocusnode

SCIP_NODEfocuslpfork

SCIP_NODEfocuslpstatefork

SCIP_NODEfocussubroot

SCIP_NODEprobingroot

SCIP_NODE ** children

SCIP_NODE ** siblings

SCIP_Realchildrenprio

SCIP_Realsiblingsprio

SCIP_VAR ** divebdchgvars [2]

SCIP_BRANCHDIRdivebdchgdirs [2]

SCIP_Realdivebdchgvals [2]

int * pathnlpcols

int * pathnlprows

SCIP_LPISTATEprobinglpistate

SCIP_LPISTATEfocuslpistate

SCIP_LPINORMSprobinglpinorms

SCIP_PENDINGBDCHGpendingbdchgs

SCIP_Realprobdiverelaxsol

SCIP_Longint focuslpstateforklpcount

int divebdchgsize [2]

int ndivebdchanges [2]

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

int probingsumchgdobjs

SCIP_Bool focusnodehaslp

SCIP_Bool probingnodehaslp

SCIP_Bool focuslpconstructed

SCIP_Bool cutoffdelayed

SCIP_Bool probinglpwasflushed

SCIP_Bool probinglpwassolved

SCIP_Bool probinglpwasrelax

SCIP_Bool probingsolvedlp

SCIP_Bool forcinglpmessage

SCIP_Bool probingobjchanged

SCIP_Bool sbprobing

SCIP_Bool probinglpwasprimfeas

SCIP_Bool probinglpwasprimchecked

SCIP_Bool probinglpwasdualfeas

SCIP_Bool probinglpwasdualchecked

SCIP_Bool probdiverelaxstored

SCIP_Bool probdiverelaxincludeslp

◆ leaves

 SCIP_NODEPQ* SCIP_Tree::leaves

leaves of the tree

Definition at line 178 of file struct_tree.h.

◆ path

 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 179 of file struct_tree.h.

◆ focusnode

 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 182 of file struct_tree.h.

◆ focuslpfork

 SCIP_NODE* SCIP_Tree::focuslpfork

LP defining pseudofork/fork/subroot of the focus node

Definition at line 186 of file struct_tree.h.

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

◆ focuslpstatefork

 SCIP_NODE* SCIP_Tree::focuslpstatefork

LP state defining fork/subroot of the focus node

Definition at line 187 of file struct_tree.h.

◆ focussubroot

 SCIP_NODE* SCIP_Tree::focussubroot

subroot of the focus node's sub tree

Definition at line 188 of file struct_tree.h.

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

◆ probingroot

 SCIP_NODE* SCIP_Tree::probingroot

root node of the current probing path, or NULL

Definition at line 189 of file struct_tree.h.

◆ children

 SCIP_NODE** SCIP_Tree::children

array with children of the focus node

Definition at line 190 of file struct_tree.h.

◆ siblings

 SCIP_NODE** SCIP_Tree::siblings

array with siblings of the focus node

Definition at line 191 of file struct_tree.h.

◆ childrenprio

 SCIP_Real* SCIP_Tree::childrenprio

array with node selection priorities of children

Definition at line 192 of file struct_tree.h.

◆ siblingsprio

 SCIP_Real* SCIP_Tree::siblingsprio

array with node selection priorities of siblings

Definition at line 193 of file struct_tree.h.

◆ divebdchgvars

 SCIP_VAR** SCIP_Tree::divebdchgvars[2]

two arrays to store variables for branching

Definition at line 194 of file struct_tree.h.

Referenced by SCIPtreeAddDiveBoundChange(), and SCIPtreeGetDiveBoundChangeData().

◆ divebdchgdirs

 SCIP_BRANCHDIR* SCIP_Tree::divebdchgdirs[2]

arrays to hold the directions for diving

Definition at line 195 of file struct_tree.h.

Referenced by SCIPtreeAddDiveBoundChange(), and SCIPtreeGetDiveBoundChangeData().

◆ divebdchgvals

 SCIP_Real* SCIP_Tree::divebdchgvals[2]

arrays to store bound change values for diving

Definition at line 196 of file struct_tree.h.

Referenced by SCIPtreeAddDiveBoundChange(), and SCIPtreeGetDiveBoundChangeData().

◆ pathnlpcols

 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 197 of file struct_tree.h.

◆ pathnlprows

 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 199 of file struct_tree.h.

◆ probinglpistate

 SCIP_LPISTATE* SCIP_Tree::probinglpistate

LP state information before probing started

Definition at line 201 of file struct_tree.h.

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

◆ focuslpistate

 SCIP_LPISTATE* SCIP_Tree::focuslpistate

LP state information of focus node

Definition at line 202 of file struct_tree.h.

◆ probinglpinorms

 SCIP_LPINORMS* SCIP_Tree::probinglpinorms

LP pricing norms information before probing started

Definition at line 203 of file struct_tree.h.

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

◆ pendingbdchgs

 SCIP_PENDINGBDCHG* SCIP_Tree::pendingbdchgs

array of pending bound changes, or NULL

Definition at line 204 of file struct_tree.h.

◆ probdiverelaxsol

 SCIP_Real* SCIP_Tree::probdiverelaxsol

array with stored original relaxation solution during diving or probing

Definition at line 205 of file struct_tree.h.

Referenced by SCIPtreeRestoreRelaxSol(), and SCIPtreeStoreRelaxSol().

◆ focuslpstateforklpcount

 SCIP_Longint SCIP_Tree::focuslpstateforklpcount

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

Definition at line 206 of file struct_tree.h.

◆ divebdchgsize

 int SCIP_Tree::divebdchgsize[2]

holds the two sizes of the dive bound change information

Definition at line 207 of file struct_tree.h.

◆ ndivebdchanges

 int SCIP_Tree::ndivebdchanges[2]

current number of stored dive bound changes for the next depth

Definition at line 208 of file struct_tree.h.

◆ pendingbdchgssize

 int SCIP_Tree::pendingbdchgssize

size of pendingbdchgs array

Definition at line 209 of file struct_tree.h.

Referenced by treeEnsurePendingbdchgsMem().

◆ npendingbdchgs

 int SCIP_Tree::npendingbdchgs

number of pending bound changes

Definition at line 210 of file struct_tree.h.

◆ childrensize

 int SCIP_Tree::childrensize

available slots in children vector

Definition at line 211 of file struct_tree.h.

Referenced by treeChildrenToSiblings(), and treeEnsureChildrenMem().

◆ nchildren

 int SCIP_Tree::nchildren

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

Definition at line 212 of file struct_tree.h.

◆ siblingssize

 int SCIP_Tree::siblingssize

available slots in siblings vector

Definition at line 213 of file struct_tree.h.

Referenced by treeChildrenToSiblings().

◆ nsiblings

 int SCIP_Tree::nsiblings

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

Definition at line 214 of file struct_tree.h.

◆ pathsize

 int SCIP_Tree::pathsize

number of available slots in path arrays

Definition at line 216 of file struct_tree.h.

Referenced by treeEnsurePathMem().

◆ effectiverootdepth

 int SCIP_Tree::effectiverootdepth

first depth with node with at least two children

Definition at line 217 of file struct_tree.h.

◆ appliedeffectiverootdepth

 int SCIP_Tree::appliedeffectiverootdepth

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

Definition at line 218 of file struct_tree.h.

Referenced by SCIPnodeFocus(), and SCIPtreeClear().

◆ correctlpdepth

 int SCIP_Tree::correctlpdepth

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

Definition at line 219 of file struct_tree.h.

◆ cutoffdepth

 int SCIP_Tree::cutoffdepth

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

Definition at line 220 of file struct_tree.h.

◆ repropdepth

 int SCIP_Tree::repropdepth

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

Definition at line 221 of file struct_tree.h.

◆ repropsubtreecount

 int SCIP_Tree::repropsubtreecount

cyclicly increased counter to create markers for subtree repropagation

Definition at line 222 of file struct_tree.h.

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

◆ probingsumchgdobjs

 int SCIP_Tree::probingsumchgdobjs

number of changed objective coefficients in all probing nodes

Definition at line 223 of file struct_tree.h.

◆ focusnodehaslp

 SCIP_Bool SCIP_Tree::focusnodehaslp

is LP being processed in the focus node?

Definition at line 224 of file struct_tree.h.

◆ probingnodehaslp

 SCIP_Bool SCIP_Tree::probingnodehaslp

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

Definition at line 225 of file struct_tree.h.

◆ focuslpconstructed

 SCIP_Bool SCIP_Tree::focuslpconstructed

was the LP of the focus node already constructed?

Definition at line 226 of file struct_tree.h.

◆ cutoffdelayed

 SCIP_Bool SCIP_Tree::cutoffdelayed

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

Definition at line 227 of file struct_tree.h.

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

◆ probinglpwasflushed

 SCIP_Bool SCIP_Tree::probinglpwasflushed

was the LP flushed before we entered the probing mode?

Definition at line 228 of file struct_tree.h.

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

◆ probinglpwassolved

 SCIP_Bool SCIP_Tree::probinglpwassolved

was the LP solved before we entered the probing mode?

Definition at line 229 of file struct_tree.h.

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

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

Definition at line 230 of file struct_tree.h.

◆ probinglpwasrelax

 SCIP_Bool SCIP_Tree::probinglpwasrelax

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

Definition at line 231 of file struct_tree.h.

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

◆ probingsolvedlp

 SCIP_Bool SCIP_Tree::probingsolvedlp

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

Definition at line 232 of file struct_tree.h.

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

◆ forcinglpmessage

 SCIP_Bool SCIP_Tree::forcinglpmessage

was forcing LP solving message be posted

Definition at line 233 of file struct_tree.h.

Referenced by solveNode().

◆ probingobjchanged

 SCIP_Bool SCIP_Tree::probingobjchanged

was the objective function changed during probing?

Definition at line 234 of file struct_tree.h.

◆ sbprobing

 SCIP_Bool SCIP_Tree::sbprobing

is the probing mode used for strong branching?

Definition at line 235 of file struct_tree.h.

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

◆ probinglpwasprimfeas

 SCIP_Bool SCIP_Tree::probinglpwasprimfeas

primal feasibility when probing started

Definition at line 236 of file struct_tree.h.

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

◆ probinglpwasprimchecked

 SCIP_Bool SCIP_Tree::probinglpwasprimchecked

primal feasibility has been checked when probing started

Definition at line 237 of file struct_tree.h.

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

◆ probinglpwasdualfeas

 SCIP_Bool SCIP_Tree::probinglpwasdualfeas

dual feasibility when probing started

Definition at line 238 of file struct_tree.h.

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

◆ probinglpwasdualchecked

 SCIP_Bool SCIP_Tree::probinglpwasdualchecked

dual feasibility has been check when probing started

Definition at line 239 of file struct_tree.h.

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

◆ probdiverelaxstored

 SCIP_Bool SCIP_Tree::probdiverelaxstored

was a relax solution stored before diving or probing ?

Definition at line 240 of file struct_tree.h.

Referenced by SCIPendDive(), SCIPtreeEndProbing(), SCIPtreeRestoreRelaxSol(), and SCIPtreeStoreRelaxSol().

◆ probdiverelaxincludeslp

 SCIP_Bool SCIP_Tree::probdiverelaxincludeslp

did the stored relaxation solution include all lp cuts ?

Definition at line 241 of file struct_tree.h.

Referenced by SCIPtreeRestoreRelaxSol(), and SCIPtreeStoreRelaxSol().