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)
93 if( minsize <= nodepq->size )
115 (*nodepq)->nodesel = nodesel;
116 (*nodepq)->slots =
NULL;
117 (*nodepq)->bfsposs =
NULL;
118 (*nodepq)->bfsqueue =
NULL;
121 (*nodepq)->lowerboundsum = 0.0;
180 if( nodepq->
len > 0 )
189 for(
i = 0;
i < nodepq->
len; ++
i )
228 assert((*nodepq)->len >= 0);
232 if( (*nodepq)->nodesel == nodesel )
242 for(
i = 0;
i < (*nodepq)->len && retcode ==
SCIP_OKAY; ++
i )
304 slots = nodepq->
slots;
312 while( pos > 0 && nodesel->nodeselcomp(
set->scip, nodesel, node, slots[
PQ_PARENT(pos)]) < 0 )
316 bfsqueue[bfsposs[pos]] = pos;
323 bfspos = nodepq->
len-1;
326 bfsqueue[bfspos] = bfsqueue[
PQ_PARENT(bfspos)];
327 bfsposs[bfsqueue[bfspos]] = bfspos;
330 bfsqueue[bfspos] = pos;
331 bfsposs[pos] = bfspos;
333 SCIPsetDebugMsg(
set,
"inserted node %p[%g] at pos %d and bfspos %d of node queue\n", (
void*)node, lowerbound, pos, bfspos);
363 assert(0 <= rempos && rempos < nodepq->len);
369 slots = nodepq->
slots;
375 freebfspos = bfsposs[rempos];
376 assert(0 <= freebfspos && freebfspos < nodepq->len);
392 lastnode = slots[nodepq->
len];
393 lastbfspos = bfsposs[nodepq->
len];
394 parentfelldown =
FALSE;
395 if( freepos < nodepq->len )
401 while( freepos > 0 && nodesel->nodeselcomp(
set->scip, nodesel, lastnode, slots[parentpos]) < 0 )
403 slots[freepos] = slots[parentpos];
404 bfsposs[freepos] = bfsposs[parentpos];
405 bfsqueue[bfsposs[freepos]] = freepos;
408 parentfelldown =
TRUE;
410 if( !parentfelldown )
420 assert(childpos < nodepq->len);
422 if( brotherpos < nodepq->len
423 && nodesel->nodeselcomp(
set->scip, nodesel, slots[brotherpos], slots[childpos]) < 0 )
424 childpos = brotherpos;
427 if( nodesel->nodeselcomp(
set->scip, nodesel, lastnode, slots[childpos]) <= 0 )
431 slots[freepos] = slots[childpos];
432 bfsposs[freepos] = bfsposs[childpos];
433 bfsqueue[bfsposs[freepos]] = freepos;
437 assert(0 <= freepos && freepos < nodepq->len);
439 slots[freepos] = lastnode;
440 bfsposs[freepos] = lastbfspos;
441 bfsqueue[lastbfspos] = freepos;
445 lastbfsqueueidx = bfsqueue[nodepq->
len];
446 bfsparentfelldown =
FALSE;
447 if( freebfspos < nodepq->len )
457 bfsqueue[freebfspos] = bfsqueue[parentpos];
458 bfsposs[bfsqueue[freebfspos]] = freebfspos;
459 freebfspos = parentpos;
461 bfsparentfelldown =
TRUE;
463 if( !bfsparentfelldown )
473 assert(childpos < nodepq->len);
475 if( brotherpos < nodepq->len
477 childpos = brotherpos;
484 bfsqueue[freebfspos] = bfsqueue[childpos];
485 bfsposs[bfsqueue[freebfspos]] = freebfspos;
486 freebfspos = childpos;
489 assert(0 <= freebfspos && freebfspos < nodepq->len);
491 bfsqueue[freebfspos] = lastbfsqueueidx;
492 bfsposs[lastbfsqueueidx] = freebfspos;
495 return parentfelldown;
514 for( pos = 0; pos < nodepq->
len && node != nodepq->
slots[pos]; ++pos )
517 if( pos == nodepq->
len )
552 if( nodepq->
len == 0 )
557 return nodepq->
slots[0];
567 return nodepq->
slots;
591 if( nodepq->
len > 0 )
596 assert(0 <= bfspos && bfspos < nodepq->len);
615 if( nodepq->
len > 0 )
620 assert(0 <= bfspos && bfspos < nodepq->len);
622 return nodepq->
slots[bfspos];
657 SCIPsetDebugMsg(
set,
"bounding node queue of length %d with cutoffbound=%g\n", nodepq->
len, cutoffbound);
659 pos = nodepq->
len - 1;
663 assert(pos < nodepq->len);
664 node = nodepq->
slots[pos];
681 SCIPsetDebugMsg(
set,
"cutting off leaf node in slot %d (queuelen=%d) at depth %d with lowerbound=%g\n",
685 if(
set->reopt_enable )
704 if( node->
depth == 0 )
708 if(
set->misc_calcintegral )
778 if( nodesel->nodeselcopy !=
NULL )
822 (*nodesel)->stdpriority = stdpriority;
823 (*nodesel)->memsavepriority = memsavepriority;
824 (*nodesel)->nodeselcopy = nodeselcopy;
825 (*nodesel)->nodeselfree = nodeselfree;
826 (*nodesel)->nodeselinit = nodeselinit;
827 (*nodesel)->nodeselexit = nodeselexit;
828 (*nodesel)->nodeselinitsol = nodeselinitsol;
829 (*nodesel)->nodeselexitsol = nodeselexitsol;
830 (*nodesel)->nodeselselect = nodeselselect;
831 (*nodesel)->nodeselcomp = nodeselcomp;
832 (*nodesel)->nodeseldata = nodeseldata;
833 (*nodesel)->initialized =
FALSE;
842 &(*nodesel)->stdpriority,
FALSE, stdpriority, INT_MIN/4, INT_MAX/2,
848 &(*nodesel)->memsavepriority,
TRUE, memsavepriority, INT_MIN/4, INT_MAX/4,
882 nodeselcopy, nodeselfree, nodeselinit, nodeselexit, nodeselinitsol, nodeselexitsol, nodeselselect, nodeselcomp,
895 if( *nodesel ==
NULL )
897 assert(!(*nodesel)->initialized);
901 if( (*nodesel)->nodeselfree !=
NULL )
903 SCIP_CALL( (*nodesel)->nodeselfree(
set->scip, *nodesel) );
932 if(
set->misc_resetstat )
938 if( nodesel->nodeselinit !=
NULL )
968 if( nodesel->nodeselexit !=
NULL )
993 if( nodesel->nodeselinitsol !=
NULL )
998 SCIP_CALL( nodesel->nodeselinitsol(
set->scip, nodesel) );
1017 if( nodesel->nodeselexitsol !=
NULL )
1022 SCIP_CALL( nodesel->nodeselexitsol(
set->scip, nodesel) );
1046 SCIP_CALL( nodesel->nodeselselect(
set->scip, nodesel, selnode) );
1068 return nodesel->nodeselcomp(
set->scip, nodesel, node1, node2);
1078 return nodesel->
name;
1088 return nodesel->
desc;
1170 nodesel->nodeselcopy = nodeselcopy;
1181 nodesel->nodeselfree = nodeselfree;
1192 nodesel->nodeselinit = nodeselinit;
1203 nodesel->nodeselexit = nodeselexit;
1214 nodesel->nodeselinitsol = nodeselinitsol;
1225 nodesel->nodeselexitsol = nodeselexitsol;
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
void SCIPstatUpdatePrimalDualIntegrals(SCIP_STAT *stat, SCIP_SET *set, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_Real upperbound, SCIP_Real lowerbound)
internal methods for problem statistics
SCIP_NODESELDATA * nodeseldata
data structures for node selectors and node priority queues
SCIP main data structure.
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_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
internal methods for branch and bound tree
struct SCIP_EventFilter SCIP_EVENTFILTER
#define SCIP_EVENTTYPE_NODEINFEASIBLE
struct SCIP_EventQueue SCIP_EVENTQUEUE
struct SCIP_Messagehdlr SCIP_MESSAGEHDLR
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_NODESELEXIT(x)
#define SCIP_DECL_NODESELCOMP(x)
#define SCIP_DECL_NODESELINITSOL(x)
struct SCIP_Nodesel SCIP_NODESEL
#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_NodePQ SCIP_NODEPQ
struct SCIP_ParamData SCIP_PARAMDATA
#define SCIP_DECL_PARAMCHGD(x)
struct SCIP_Reopt SCIP_REOPT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_Stat SCIP_STAT
struct SCIP_Node SCIP_NODE
struct SCIP_Tree SCIP_TREE
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)