48 #define PQ_PARENT(q) (((q)+1)/2-1) 49 #define PQ_LEFTCHILD(p) (2*(p)+1) 50 #define PQ_RIGHTCHILD(p) (2*(p)+2) 57 assert(elem1 != NULL);
58 assert(elem2 != NULL);
67 assert(elem1 == elem2);
81 assert(nodepq != NULL);
83 if( minsize <= nodepq->size )
101 assert(nodepq != NULL);
104 (*nodepq)->nodesel = nodesel;
105 (*nodepq)->slots = NULL;
106 (*nodepq)->bfsposs = NULL;
107 (*nodepq)->bfsqueue = NULL;
110 (*nodepq)->lowerboundsum = 0.0;
120 assert(nodepq != NULL);
121 assert(*nodepq != NULL);
140 assert(nodepq != NULL);
141 assert(*nodepq != NULL);
165 assert(nodepq != NULL);
167 if( nodepq->
len > 0 )
176 for( i = 0; i < nodepq->
len; ++i )
178 assert(nodepq->
slots[i] != NULL);
197 assert(nodepq != NULL);
213 assert(nodepq != NULL);
214 assert(*nodepq != NULL);
215 assert((*nodepq)->len >= 0);
216 assert(nodesel != NULL);
217 assert(nodesel->nodeselcomp != NULL);
219 if( (*nodepq)->nodesel == nodesel )
229 for( i = 0; i < (*nodepq)->len && retcode ==
SCIP_OKAY; ++i )
258 assert(nodepq != NULL);
259 assert(nodepq->
nodesel != NULL);
260 assert(nodepq->
nodesel->nodeselcomp != NULL);
281 assert(nodepq != NULL);
282 assert(nodepq->
len >= 0);
284 assert(node != NULL);
287 assert(nodesel != NULL);
288 assert(nodesel->nodeselcomp != NULL);
291 slots = nodepq->
slots;
299 while( pos > 0 && nodesel->nodeselcomp(set->scip, nodesel, node, slots[
PQ_PARENT(pos)]) < 0 )
303 bfsqueue[bfsposs[pos]] = pos;
310 bfspos = nodepq->
len-1;
313 bfsqueue[bfspos] = bfsqueue[
PQ_PARENT(bfspos)];
314 bfsposs[bfsqueue[bfspos]] = bfspos;
317 bfsqueue[bfspos] = pos;
318 bfsposs[pos] = bfspos;
320 SCIPsetDebugMsg(
set,
"inserted node %p[%g] at pos %d and bfspos %d of node queue\n", (
void*)node, lowerbound, pos, bfspos);
347 assert(nodepq != NULL);
348 assert(nodepq->
len > 0);
350 assert(0 <= rempos && rempos < nodepq->len);
353 assert(nodesel != NULL);
354 assert(nodesel->nodeselcomp != NULL);
356 slots = nodepq->
slots;
362 freebfspos = bfsposs[rempos];
363 assert(0 <= freebfspos && freebfspos < nodepq->len);
365 SCIPsetDebugMsg(
set,
"delete node %p[%g] at pos %d and bfspos %d of node queue\n",
379 lastnode = slots[nodepq->
len];
380 lastbfspos = bfsposs[nodepq->
len];
381 parentfelldown =
FALSE;
382 if( freepos < nodepq->len )
388 while( freepos > 0 && nodesel->nodeselcomp(set->scip, nodesel, lastnode, slots[parentpos]) < 0 )
390 slots[freepos] = slots[parentpos];
391 bfsposs[freepos] = bfsposs[parentpos];
392 bfsqueue[bfsposs[freepos]] = freepos;
395 parentfelldown =
TRUE;
397 if( !parentfelldown )
407 assert(childpos < nodepq->len);
409 if( brotherpos < nodepq->len
410 && nodesel->nodeselcomp(set->scip, nodesel, slots[brotherpos], slots[childpos]) < 0 )
411 childpos = brotherpos;
414 if( nodesel->nodeselcomp(set->scip, nodesel, lastnode, slots[childpos]) <= 0 )
418 slots[freepos] = slots[childpos];
419 bfsposs[freepos] = bfsposs[childpos];
420 bfsqueue[bfsposs[freepos]] = freepos;
424 assert(0 <= freepos && freepos < nodepq->len);
426 slots[freepos] = lastnode;
427 bfsposs[freepos] = lastbfspos;
428 bfsqueue[lastbfspos] = freepos;
432 lastbfsqueueidx = bfsqueue[nodepq->
len];
433 bfsparentfelldown =
FALSE;
434 if( freebfspos < nodepq->len )
444 bfsqueue[freebfspos] = bfsqueue[parentpos];
445 bfsposs[bfsqueue[freebfspos]] = freebfspos;
446 freebfspos = parentpos;
448 bfsparentfelldown =
TRUE;
450 if( !bfsparentfelldown )
460 assert(childpos < nodepq->len);
462 if( brotherpos < nodepq->len
464 childpos = brotherpos;
471 bfsqueue[freebfspos] = bfsqueue[childpos];
472 bfsposs[bfsqueue[freebfspos]] = freebfspos;
473 freebfspos = childpos;
476 assert(0 <= freebfspos && freebfspos < nodepq->len);
478 bfsqueue[freebfspos] = lastbfsqueueidx;
479 bfsposs[lastbfsqueueidx] = freebfspos;
482 return parentfelldown;
495 assert(nodepq != NULL);
496 assert(nodepq->
len >= 0);
498 assert(node != NULL);
501 for( pos = 0; pos < nodepq->
len && node != nodepq->
slots[pos]; ++pos )
504 if( pos == nodepq->
len )
536 assert(nodepq != NULL);
537 assert(nodepq->
len >= 0);
539 if( nodepq->
len == 0 )
542 assert(nodepq->
slots[0] != NULL);
544 return nodepq->
slots[0];
552 assert(nodepq != NULL);
554 return nodepq->
slots;
562 assert(nodepq != NULL);
563 assert(nodepq->
len >= 0);
574 assert(nodepq != NULL);
575 assert(nodepq->
nodesel != NULL);
578 if( nodepq->
len > 0 )
583 assert(0 <= bfspos && bfspos < nodepq->len);
584 assert(nodepq->
slots[bfspos] != NULL);
597 assert(nodepq != NULL);
598 assert(nodepq->
nodesel != NULL);
602 if( nodepq->
len > 0 )
607 assert(0 <= bfspos && bfspos < nodepq->len);
608 assert(nodepq->
slots[bfspos] != NULL);
609 return nodepq->
slots[bfspos];
620 assert(nodepq != NULL);
642 assert(nodepq != NULL);
644 SCIPsetDebugMsg(
set,
"bounding node queue of length %d with cutoffbound=%g\n", nodepq->
len, cutoffbound);
648 assert(pos < nodepq->len);
649 node = nodepq->
slots[pos];
650 assert(node != NULL);
654 SCIPsetDebugMsg(
set,
"free node in slot %d (len=%d) at depth %d with lowerbound=%g\n",
673 if( !parentfelldown )
678 if( set->reopt_enable )
680 assert(reopt != NULL);
711 assert(paramdata != NULL);
726 assert(paramdata != NULL);
740 assert(nodesel != NULL);
742 assert(set->scip != NULL);
744 if( nodesel->nodeselcopy != NULL )
747 SCIP_CALL( nodesel->nodeselcopy(set->scip, nodesel) );
776 assert(nodesel != NULL);
777 assert(name != NULL);
778 assert(desc != NULL);
779 assert(nodeselselect != NULL);
780 assert(nodeselcomp != NULL);
785 (*nodesel)->stdpriority = stdpriority;
786 (*nodesel)->memsavepriority = memsavepriority;
787 (*nodesel)->nodeselcopy = nodeselcopy;
788 (*nodesel)->nodeselfree = nodeselfree;
789 (*nodesel)->nodeselinit = nodeselinit;
790 (*nodesel)->nodeselexit = nodeselexit;
791 (*nodesel)->nodeselinitsol = nodeselinitsol;
792 (*nodesel)->nodeselexitsol = nodeselexitsol;
793 (*nodesel)->nodeselselect = nodeselselect;
794 (*nodesel)->nodeselcomp = nodeselcomp;
795 (*nodesel)->nodeseldata = nodeseldata;
796 (*nodesel)->initialized =
FALSE;
805 &(*nodesel)->stdpriority,
FALSE, stdpriority, INT_MIN/4, INT_MAX/2,
811 &(*nodesel)->memsavepriority,
TRUE, memsavepriority, INT_MIN/4, INT_MAX/4,
823 assert(nodesel != NULL);
824 assert(*nodesel != NULL);
825 assert(!(*nodesel)->initialized);
829 if( (*nodesel)->nodeselfree != NULL )
831 SCIP_CALL( (*nodesel)->nodeselfree(set->scip, *nodesel) );
851 assert(nodesel != NULL);
860 if( set->misc_resetstat )
866 if( nodesel->nodeselinit != NULL )
871 SCIP_CALL( nodesel->nodeselinit(set->scip, nodesel) );
887 assert(nodesel != NULL);
896 if( nodesel->nodeselexit != NULL )
901 SCIP_CALL( nodesel->nodeselexit(set->scip, nodesel) );
917 assert(nodesel != NULL);
921 if( nodesel->nodeselinitsol != NULL )
926 SCIP_CALL( nodesel->nodeselinitsol(set->scip, nodesel) );
941 assert(nodesel != NULL);
945 if( nodesel->nodeselexitsol != NULL )
950 SCIP_CALL( nodesel->nodeselexitsol(set->scip, nodesel) );
967 assert(nodesel != NULL);
968 assert(nodesel->nodeselselect != NULL);
970 assert(selnode != NULL);
975 SCIP_CALL( nodesel->nodeselselect(set->scip, nodesel, selnode) );
991 assert(nodesel != NULL);
992 assert(nodesel->nodeselcomp != NULL);
994 assert(node1 != NULL);
995 assert(node2 != NULL);
997 return nodesel->nodeselcomp(set->scip, nodesel, node1, node2);
1005 assert(nodesel != NULL);
1007 return nodesel->
name;
1015 assert(nodesel != NULL);
1017 return nodesel->
desc;
1025 assert(nodesel != NULL);
1037 assert(nodesel != NULL);
1038 assert(
set != NULL);
1041 set->nodesel = NULL;
1049 assert(nodesel != NULL);
1061 assert(nodesel != NULL);
1062 assert(
set != NULL);
1065 set->nodesel = NULL;
1073 assert(nodesel != NULL);
1084 assert(nodesel != NULL);
1097 assert(nodesel != NULL);
1099 nodesel->nodeselcopy = nodeselcopy;
1108 assert(nodesel != NULL);
1110 nodesel->nodeselfree = nodeselfree;
1119 assert(nodesel != NULL);
1121 nodesel->nodeselinit = nodeselinit;
1130 assert(nodesel != NULL);
1132 nodesel->nodeselexit = nodeselexit;
1141 assert(nodesel != NULL);
1143 nodesel->nodeselinitsol = nodeselinitsol;
1152 assert(nodesel != NULL);
1154 nodesel->nodeselexitsol = nodeselexitsol;
1162 assert(nodesel != NULL);
1173 assert(nodesel != NULL);
1184 assert(nodesel != NULL);
1194 assert(nodesel != NULL);
void SCIPnodeselSetFree(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
void SCIPnodepqDestroy(SCIP_NODEPQ **nodepq)
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
#define SCIP_DECL_NODESELCOMP(x)
SCIP_RETCODE SCIPnodepqBound(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_Real cutoffbound)
int SCIPnodeselGetMemsavePriority(SCIP_NODESEL *nodesel)
void SCIPnodeselEnableOrDisableClocks(SCIP_NODESEL *nodesel, SCIP_Bool enable)
#define BMSfreeMemoryArrayNull(ptr)
internal methods for branch and bound tree
void SCIPnodeselSetInit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINIT((*nodeselinit)))
SCIP_RETCODE SCIPnodeselExitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
int SCIPnodepqCompare(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
internal methods for clocks and timing issues
struct SCIP_ParamData SCIP_PARAMDATA
#define SCIP_DECL_NODESELINITSOL(x)
static SCIP_DECL_PARAMCHGD(paramChgdNodeselStdPriority)
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
static SCIP_DECL_SORTPTRCOMP(nodeCompNumber)
const char * SCIPnodeselGetDesc(SCIP_NODESEL *nodesel)
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
SCIP_RETCODE SCIPsetNodeselMemsavePriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_NODE * SCIPnodepqGetLowerboundNode(SCIP_NODEPQ *nodepq, SCIP_SET *set)
enum SCIP_Retcode SCIP_RETCODE
SCIP_Real SCIPnodepqGetLowerboundSum(SCIP_NODEPQ *nodepq)
SCIP_RETCODE SCIPnodeselInitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
internal methods for handling parameter settings
int SCIPnodeGetDepth(SCIP_NODE *node)
methods for creating output for visualization tools (VBC, BAK)
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
#define BMSfreeMemory(ptr)
SCIP_NODESEL * SCIPnodepqGetNodesel(SCIP_NODEPQ *nodepq)
static int nodepqFindNode(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
static SCIP_RETCODE nodepqResize(SCIP_NODEPQ *nodepq, SCIP_SET *set, int minsize)
#define SCIP_DECL_NODESELEXITSOL(x)
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
internal methods for LP management
SCIP_RETCODE SCIPnodeselExit(SCIP_NODESEL *nodesel, SCIP_SET *set)
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
#define SCIP_DECL_NODESELINIT(x)
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPnodeselCopyInclude(SCIP_NODESEL *nodesel, SCIP_SET *set)
SCIP_RETCODE SCIPnodepqInsert(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
struct SCIP_NodeselData SCIP_NODESELDATA
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
#define BMSfreeMemoryArray(ptr)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPclockReset(SCIP_CLOCK *clck)
SCIP_RETCODE SCIPnodepqSetNodesel(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
#define SCIP_DECL_NODESELFREE(x)
SCIP_RETCODE SCIPnodeselFree(SCIP_NODESEL **nodesel, SCIP_SET *set)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
internal methods for node selectors and node priority queues
internal methods for global SCIP settings
SCIP main data structure.
SCIP_Real SCIPnodeselGetTime(SCIP_NODESEL *nodesel)
int SCIPnodeselCompare(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
int SCIPsetCalcTreeGrowSize(SCIP_SET *set, int num)
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)
SCIP_RETCODE SCIPnodeselInit(SCIP_NODESEL *nodesel, SCIP_SET *set)
void SCIPnodeselSetInitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
#define BMSduplicateMemoryArray(ptr, source, num)
SCIP_RETCODE SCIPnodepqFree(SCIP_NODEPQ **nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
data structures and methods for collecting reoptimization information
public data structures and miscellaneous methods
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
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)
#define SCIP_DECL_NODESELEXIT(x)
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)
SCIP_RETCODE SCIPnodepqRemove(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
void SCIPnodeselSetMemsavePriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
void SCIPclockFree(SCIP_CLOCK **clck)
SCIP_RETCODE SCIPnodepqCreate(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
void SCIPnodeselSetExit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXIT((*nodeselexit)))
#define SCIP_EVENTTYPE_NODEINFEASIBLE
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
SCIP_NODE * SCIPnodepqFirst(const SCIP_NODEPQ *nodepq)
SCIP_NODESELDATA * nodeseldata
int SCIPparamGetInt(SCIP_PARAM *param)
SCIP_Real SCIPnodeselGetSetupTime(SCIP_NODESEL *nodesel)
void SCIPnodeselSetStdPriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
SCIP_Real SCIPnodepqGetLowerbound(SCIP_NODEPQ *nodepq, SCIP_SET *set)
static SCIP_Bool nodepqDelPos(SCIP_NODEPQ *nodepq, SCIP_SET *set, int rempos)
public methods for message output
data structures for node selectors and node priority queues
SCIP_RETCODE SCIPnodepqClear(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
internal methods for problem statistics
#define SCIP_DECL_NODESELCOPY(x)
#define BMSallocMemory(ptr)
#define BMSreallocMemoryArray(ptr, num)
void SCIPnodeselSetCopy(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
int SCIPnodeselGetStdPriority(SCIP_NODESEL *nodesel)
#define SCIP_DECL_NODESELSELECT(x)
void SCIPnodeselSetExitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
SCIP_RETCODE SCIPnodeFree(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
SCIP_Bool SCIPnodeselIsInitialized(SCIP_NODESEL *nodesel)
SCIP_RETCODE SCIPsetNodeselStdPriority(SCIP *scip, SCIP_NODESEL *nodesel, int priority)