58#define PQ_PARENT(q) (((q)+1)/2-1)
59#define PQ_LEFTCHILD(p) (2*(p)+1)
60#define PQ_RIGHTCHILD(p) (2*(p)+2)
115 (*nodepq)->nodesel = nodesel;
116 (*nodepq)->slots =
NULL;
117 (*nodepq)->bfsposs =
NULL;
118 (*nodepq)->bfsqueue =
NULL;
121 (*nodepq)->lowerboundsum = 0.0;
200 nodepq->lowerboundsum = 0.0;
228 assert((*nodepq)->len >= 0);
232 if( (*nodepq)->nodesel == nodesel )
242 for(
i = 0;
i < (*nodepq)->len && retcode ==
SCIP_OKAY; ++
i )
290 SCIP_Real lowerbound;
299 nodesel =
nodepq->nodesel;
305 bfsposs =
nodepq->bfsposs;
306 bfsqueue =
nodepq->bfsqueue;
312 while( pos > 0 && nodesel->nodeselcomp(
set->scip, nodesel, node, slots[
PQ_PARENT(pos)]) < 0 )
316 bfsqueue[bfsposs[pos]] = pos;
333 SCIPsetDebugMsg(
set,
"inserted node %p[%g] at pos %d and bfspos %d of node queue\n", (
void*)node, lowerbound, pos,
bfspos);
365 nodesel =
nodepq->nodesel;
370 bfsposs =
nodepq->bfsposs;
371 bfsqueue =
nodepq->bfsqueue;
392 lastnode = slots[
nodepq->len];
401 while(
freepos > 0 && nodesel->nodeselcomp(
set->scip, nodesel, lastnode, slots[
parentpos]) < 0 )
427 if( nodesel->nodeselcomp(
set->scip, nodesel, lastnode, slots[
childpos]) <= 0 )
449 SCIP_Real lastlowerbound;
514 for( pos = 0; pos <
nodepq->len && node !=
nodepq->slots[pos]; ++pos )
635 return nodepq->lowerboundsum;
649 SCIP_Real cutoffbound
663 node =
nodepq->slots[pos];
668 SCIPsetDebugMsg(
set,
"free node in slot %d (len=%d) at depth %d with lowerbound=%g\n",
692 if(
set->reopt_enable )
758 if( nodesel->nodeselcopy !=
NULL )
802 (*nodesel)->stdpriority = stdpriority;
803 (*nodesel)->memsavepriority = memsavepriority;
812 (*nodesel)->nodeseldata = nodeseldata;
813 (*nodesel)->initialized =
FALSE;
875 if( *nodesel ==
NULL )
877 assert(!(*nodesel)->initialized);
881 if( (*nodesel)->nodeselfree !=
NULL )
883 SCIP_CALL( (*nodesel)->nodeselfree(
set->scip, *nodesel) );
912 if(
set->misc_resetstat )
918 if( nodesel->nodeselinit !=
NULL )
948 if( nodesel->nodeselexit !=
NULL )
973 if( nodesel->nodeselinitsol !=
NULL )
978 SCIP_CALL( nodesel->nodeselinitsol(
set->scip, nodesel) );
997 if( nodesel->nodeselexitsol !=
NULL )
1002 SCIP_CALL( nodesel->nodeselexitsol(
set->scip, nodesel) );
1048 return nodesel->nodeselcomp(
set->scip, nodesel, node1, node2);
1058 return nodesel->
name;
1068 return nodesel->
desc;
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
void SCIPclockReset(SCIP_CLOCK *clck)
void SCIPclockFree(SCIP_CLOCK **clck)
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
internal methods for clocks and timing issues
common defines and data types used in all packages of SCIP
#define SCIP_CALL_FINALLY(x, y)
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
int SCIPnodeGetDepth(SCIP_NODE *node)
const char * SCIPnodeselGetDesc(SCIP_NODESEL *nodesel)
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
SCIP_Bool SCIPnodeselIsInitialized(SCIP_NODESEL *nodesel)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
int SCIPnodeselGetMemsavePriority(SCIP_NODESEL *nodesel)
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
SCIP_Real SCIPnodeselGetSetupTime(SCIP_NODESEL *nodesel)
SCIP_Real SCIPnodeselGetTime(SCIP_NODESEL *nodesel)
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
SCIP_RETCODE SCIPsetNodeselMemsavePriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
internal methods for LP management
static const char * paramname[]
#define BMSfreeMemory(ptr)
#define BMSreallocMemoryArray(ptr, num)
#define BMSduplicateMemoryArray(ptr, source, num)
#define BMSclearMemory(ptr)
struct BMS_BlkMem BMS_BLKMEM
#define BMSfreeMemoryArrayNull(ptr)
#define BMSallocMemory(ptr)
SCIP_Real SCIPnodepqGetLowerbound(SCIP_NODEPQ *nodepq, SCIP_SET *set)
void SCIPnodeselSetExit(SCIP_NODESEL *nodesel,)
void SCIPnodeselSetInit(SCIP_NODESEL *nodesel,)
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
void SCIPnodeselSetCopy(SCIP_NODESEL *nodesel,)
void SCIPnodeselSetFree(SCIP_NODESEL *nodesel,)
void SCIPnodeselSetInitsol(SCIP_NODESEL *nodesel,)
void SCIPnodepqDestroy(SCIP_NODEPQ **nodepq)
SCIP_RETCODE SCIPnodepqRemove(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
SCIP_RETCODE SCIPnodeselExit(SCIP_NODESEL *nodesel, SCIP_SET *set)
void SCIPnodeselEnableOrDisableClocks(SCIP_NODESEL *nodesel, SCIP_Bool enable)
int SCIPnodeselCompare(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
SCIP_RETCODE SCIPnodeselCreate(SCIP_NODESEL **nodesel, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELCOPY((*nodeselcopy)), SCIP_DECL_NODESELFREE((*nodeselfree)), SCIP_DECL_NODESELINIT((*nodeselinit)), SCIP_DECL_NODESELEXIT((*nodeselexit)), SCIP_DECL_NODESELINITSOL((*nodeselinitsol)), SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)), SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
SCIP_RETCODE SCIPnodepqFree(SCIP_NODEPQ **nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
SCIP_RETCODE SCIPnodepqBound(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_Real cutoffbound)
SCIP_RETCODE SCIPnodeselFree(SCIP_NODESEL **nodesel, SCIP_SET *set)
static int nodepqFindNode(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
SCIP_RETCODE SCIPnodeselCopyInclude(SCIP_NODESEL *nodesel, SCIP_SET *set)
SCIP_RETCODE SCIPnodepqSetNodesel(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
static SCIP_RETCODE nodepqResize(SCIP_NODEPQ *nodepq, SCIP_SET *set, int minsize)
SCIP_RETCODE SCIPnodeselExitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
void SCIPnodeselSetExitsol(SCIP_NODESEL *nodesel,)
static SCIP_Bool nodepqDelPos(SCIP_NODEPQ *nodepq, SCIP_SET *set, int rempos)
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
void SCIPnodeselSetStdPriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
SCIP_RETCODE SCIPnodepqClear(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
SCIP_NODESEL * SCIPnodepqGetNodesel(SCIP_NODEPQ *nodepq)
SCIP_RETCODE SCIPnodepqInsert(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
SCIP_NODE * SCIPnodepqFirst(const SCIP_NODEPQ *nodepq)
int SCIPnodepqCompare(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
SCIP_RETCODE SCIPnodepqCreate(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
static SCIP_RETCODE doNodeselCreate(SCIP_NODESEL **nodesel, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELCOPY((*nodeselcopy)), SCIP_DECL_NODESELFREE((*nodeselfree)), SCIP_DECL_NODESELINIT((*nodeselinit)), SCIP_DECL_NODESELEXIT((*nodeselexit)), SCIP_DECL_NODESELINITSOL((*nodeselinitsol)), SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)), SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
SCIP_Real SCIPnodepqGetLowerboundSum(SCIP_NODEPQ *nodepq)
SCIP_RETCODE SCIPnodeselInitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
SCIP_NODE * SCIPnodepqGetLowerboundNode(SCIP_NODEPQ *nodepq, SCIP_SET *set)
SCIP_RETCODE SCIPnodeselInit(SCIP_NODESEL *nodesel, SCIP_SET *set)
void SCIPnodeselSetMemsavePriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
internal methods for node selectors and node priority queues
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
int SCIPparamGetInt(SCIP_PARAM *param)
internal methods for handling parameter settings
public methods for message output
public data structures and miscellaneous methods
SCIP_RETCODE SCIPreoptCheckCutoff(SCIP_REOPT *reopt, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_NODE *node, SCIP_EVENTTYPE eventtype, SCIP_LP *lp, SCIP_LPSOLSTAT lpsolstat, SCIP_Bool isrootnode, SCIP_Bool isfocusnode, SCIP_Real lowerbound, int effectiverootdepth)
data structures and methods for collecting reoptimization information
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
int SCIPsetCalcTreeGrowSize(SCIP_SET *set, int num)
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
internal methods for global SCIP settings
internal methods for problem statistics
SCIP_NODESELDATA * nodeseldata
data structures for node selectors and node priority queues
SCIP main data structure.
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
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)
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
internal methods for branch and bound tree
#define SCIP_EVENTTYPE_NODEINFEASIBLE
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_NODESELEXIT(x)
#define SCIP_DECL_NODESELCOMP(x)
#define SCIP_DECL_NODESELINITSOL(x)
#define SCIP_DECL_NODESELCOPY(x)
#define SCIP_DECL_NODESELEXITSOL(x)
#define SCIP_DECL_NODESELINIT(x)
#define SCIP_DECL_NODESELSELECT(x)
#define SCIP_DECL_NODESELFREE(x)
struct SCIP_NodeselData SCIP_NODESELDATA
struct SCIP_ParamData SCIP_PARAMDATA
#define SCIP_DECL_PARAMCHGD(x)
enum SCIP_Retcode SCIP_RETCODE
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
methods for creating output for visualization tools (VBC, BAK)