34#ifndef __SCIP_TREE_H__
35#define __SCIP_TREE_H__
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)
common defines and data types used in all packages of SCIP
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
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)
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
SCIP_NODE * SCIPtreeGetProbingRoot(SCIP_TREE *tree)
SCIP_RETCODE SCIPnodeReleaseLPIState(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_LP *lp)
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)
void SCIPnodeGetDualBoundchgs(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_BOUNDTYPE *boundtypes, int *nvars, int varssize)
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
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)
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
SCIP_Real SCIPtreeGetAvgLowerbound(SCIP_TREE *tree, SCIP_Real cutoffbound)
SCIP_Bool SCIPtreeIsPathComplete(SCIP_TREE *tree)
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
SCIP_RETCODE SCIPtreeSetNodesel(SCIP_TREE *tree, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_NODESEL *nodesel)
SCIP_RETCODE SCIPnodeDelCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
void SCIPnodeSetEstimate(SCIP_NODE *node, SCIP_SET *set, SCIP_Real newestimate)
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)
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)
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
SCIP_RETCODE SCIPnodeCaptureLPIState(SCIP_NODE *node, int nuses)
void SCIPnodeGetPropsAfterDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int *nvars, int varssize)
SCIP_RETCODE SCIPtreeStartProbing(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob, SCIP_Bool strongbranching)
SCIP_RETCODE SCIPtreeFree(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
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)
int SCIPtreeGetNChildren(SCIP_TREE *tree)
SCIP_RETCODE SCIPtreeSetProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp, SCIP_LPISTATE **lpistate, SCIP_LPINORMS **lpinorms, SCIP_Bool primalfeas, SCIP_Bool dualfeas)
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)
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
void SCIPnodeMarkPropagated(SCIP_NODE *node, SCIP_TREE *tree)
int SCIPtreeGetNLeaves(SCIP_TREE *tree)
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
SCIP_RETCODE SCIPtreeStoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
SCIP_RETCODE SCIPnodeCreateChild(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real nodeselprio, SCIP_Real estimate)
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
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)
SCIP_RETCODE SCIPtreeRestoreRelaxSol(SCIP_TREE *tree, SCIP_SET *set, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob)
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)
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)
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)
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
SCIP_RETCODE SCIPtreeLoadProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
SCIP_NODE * SCIPtreeGetPrioSibling(SCIP_TREE *tree)
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)
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
int SCIPnodeGetNDualBndchgs(SCIP_NODE *node)
SCIP_RETCODE SCIPnodeAddCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
int SCIPtreeGetNNodes(SCIP_TREE *tree)
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
SCIP_RETCODE SCIPtreeClear(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
int SCIPtreeGetNSiblings(SCIP_TREE *tree)
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
SCIP_NODE * SCIPtreeGetBestLeaf(SCIP_TREE *tree)
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)
SCIP_Bool SCIPtreeHasFocusNodeLP(SCIP_TREE *tree)
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
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)
SCIP_RETCODE SCIPtreeCreate(SCIP_TREE **tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_NODESEL *nodesel)
void SCIPchildChgNodeselPrio(SCIP_TREE *tree, SCIP_NODE *child, SCIP_Real priority)
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
SCIP_NODE * SCIPtreeGetPrioChild(SCIP_TREE *tree)
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)
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
SCIP_RETCODE SCIPnodeUpdateLowerboundLP(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp)
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)
SCIP_RETCODE SCIPtreeLoadLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
SCIP_Bool SCIPtreeInRepropagation(SCIP_TREE *tree)
SCIP_NODESEL * SCIPtreeGetNodesel(SCIP_TREE *tree)
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
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)
void SCIPnodeGetPropsBeforeDual(SCIP_NODE *node, SCIP_VAR **vars, SCIP_Real *varbounds, SCIP_BOUNDTYPE *varboundtypes, int *npropvars, int propvarssize)
SCIP_RETCODE SCIPtreeLoadLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool *initroot)
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
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)
type definitions for branching rules
struct SCIP_BranchCand SCIP_BRANCHCAND
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
type definitions for managing events
struct SCIP_EventFilter SCIP_EVENTFILTER
struct SCIP_EventQueue SCIP_EVENTQUEUE
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
enum SCIP_BoundType SCIP_BOUNDTYPE
struct SCIP_LPiState SCIP_LPISTATE
struct SCIP_LPiNorms SCIP_LPINORMS
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
type definitions for storing and manipulating the main problem
struct SCIP_Prob SCIP_PROB
type definitions for propagators
struct SCIP_Prop SCIP_PROP
struct SCIP_Relaxation SCIP_RELAXATION
type definitions for collecting reoptimization information
struct SCIP_Reopt SCIP_REOPT
enum SCIP_Retcode SCIP_RETCODE
type definitions for global SCIP settings
type definitions for problem statistics
struct SCIP_Stat SCIP_STAT
type definitions for branch and bound tree
struct SCIP_Node SCIP_NODE
struct SCIP_Tree SCIP_TREE
type definitions for problem variables