SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
methods for node selectors
Definition in file nodesel.c.
#include <assert.h>#include <string.h>#include "scip/def.h"#include "scip/set.h"#include "scip/clock.h"#include "scip/stat.h"#include "scip/visual.h"#include "scip/paramset.h"#include "scip/tree.h"#include "scip/reopt.h"#include "scip/lp.h"#include "scip/scip.h"#include "scip/nodesel.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/struct_nodesel.h"#include "scip/struct_scip.h"Go to the source code of this file.
Macros | |
| #define | PQ_PARENT(q) (((q)+1)/2-1) |
| #define | PQ_LEFTCHILD(p) (2*(p)+1) |
| #define | PQ_RIGHTCHILD(p) (2*(p)+2) |
| #define PQ_PARENT | ( | q | ) | (((q)+1)/2-1) |
Definition at line 48 of file nodesel.c.
Referenced by nodepqDelPos(), and SCIPnodepqInsert().
| #define PQ_LEFTCHILD | ( | p | ) | (2*(p)+1) |
Definition at line 49 of file nodesel.c.
Referenced by nodepqDelPos(), and SCIPnodepqBound().
| #define PQ_RIGHTCHILD | ( | p | ) | (2*(p)+2) |
Definition at line 50 of file nodesel.c.
Referenced by nodepqDelPos(), and SCIPnodepqBound().
|
static |
|
static |
resizes node memory to hold at least the given number of nodes
| nodepq | node priority queue |
| set | global SCIP settings |
| minsize | minimal number of storable nodes |
Definition at line 75 of file nodesel.c.
References SCIP_NodePQ::bfsposs, SCIP_NodePQ::bfsqueue, BMSreallocMemoryArray, SCIP_ALLOC, SCIP_OKAY, SCIPsetCalcTreeGrowSize(), SCIP_NodePQ::size, and SCIP_NodePQ::slots.
Referenced by SCIPnodepqInsert(), and SCIPnodepqSetNodesel().
| SCIP_RETCODE SCIPnodepqCreate | ( | SCIP_NODEPQ ** | nodepq, |
| SCIP_SET * | set, | ||
| SCIP_NODESEL * | nodesel | ||
| ) |
creates node priority queue
| nodepq | pointer to a node priority queue |
| set | global SCIP settings |
| nodesel | node selector to use for sorting the nodes in the queue |
Definition at line 95 of file nodesel.c.
References BMSallocMemory, SCIP_ALLOC, and SCIP_OKAY.
Referenced by SCIPnodepqSetNodesel(), and SCIPtreeCreate().
| void SCIPnodepqDestroy | ( | SCIP_NODEPQ ** | nodepq | ) |
frees node priority queue, but not the data nodes themselves
| nodepq | pointer to a node priority queue |
Definition at line 116 of file nodesel.c.
References BMSfreeMemory, and BMSfreeMemoryArrayNull.
Referenced by SCIPnodepqFree(), and SCIPnodepqSetNodesel().
| SCIP_RETCODE SCIPnodepqFree | ( | SCIP_NODEPQ ** | nodepq, |
| BMS_BLKMEM * | blkmem, | ||
| SCIP_SET * | set, | ||
| SCIP_STAT * | stat, | ||
| SCIP_EVENTQUEUE * | eventqueue, | ||
| SCIP_TREE * | tree, | ||
| SCIP_LP * | lp | ||
| ) |
frees node priority queue and all nodes in the queue
| nodepq | pointer to a node priority queue |
| blkmem | block memory buffers |
| set | global SCIP settings |
| stat | problem statistics |
| eventqueue | event queue |
| tree | branch and bound tree |
| lp | current LP data |
Definition at line 130 of file nodesel.c.
References SCIP_CALL, SCIP_OKAY, SCIPnodepqClear(), and SCIPnodepqDestroy().
Referenced by SCIPtreeFree().
| SCIP_RETCODE SCIPnodepqClear | ( | SCIP_NODEPQ * | nodepq, |
| BMS_BLKMEM * | blkmem, | ||
| SCIP_SET * | set, | ||
| SCIP_STAT * | stat, | ||
| SCIP_EVENTQUEUE * | eventqueue, | ||
| SCIP_TREE * | tree, | ||
| SCIP_LP * | lp | ||
| ) |
deletes all nodes in the node priority queue
| nodepq | node priority queue |
| blkmem | block memory buffers |
| set | global SCIP settings |
| stat | problem statistics |
| eventqueue | event queue |
| tree | branch and bound tree |
| lp | current LP data |
Definition at line 153 of file nodesel.c.
References SCIP_NodePQ::len, SCIP_NodePQ::lowerboundsum, SCIP_CALL, SCIP_NODETYPE_LEAF, SCIP_OKAY, SCIPnodeFree(), SCIPnodeGetType(), SCIPsortDownPtr(), and SCIP_NodePQ::slots.
Referenced by SCIPnodepqFree(), and SCIPtreeClear().
| SCIP_NODESEL* SCIPnodepqGetNodesel | ( | SCIP_NODEPQ * | nodepq | ) |
returns the node selector associated with the given node priority queue
| nodepq | node priority queue |
Definition at line 193 of file nodesel.c.
References SCIP_NodePQ::nodesel.
Referenced by SCIPtreeGetBestChild(), SCIPtreeGetBestNode(), SCIPtreeGetBestSibling(), SCIPtreeGetNodesel(), and SCIPtreeSetNodesel().
| SCIP_RETCODE SCIPnodepqSetNodesel | ( | SCIP_NODEPQ ** | nodepq, |
| SCIP_SET * | set, | ||
| SCIP_NODESEL * | nodesel | ||
| ) |
sets the node selector used for sorting the nodes in the queue, and resorts the queue if necessary
| nodepq | pointer to a node priority queue |
| set | global SCIP settings |
| nodesel | node selector to use for sorting the nodes in the queue |
Definition at line 203 of file nodesel.c.
References SCIP_NodePQ::len, nodepqResize(), SCIP_CALL, SCIP_OKAY, SCIPnodepqCreate(), SCIPnodepqDestroy(), SCIPnodepqInsert(), and SCIP_NodePQ::slots.
Referenced by SCIPtreeSetNodesel().
| int SCIPnodepqCompare | ( | SCIP_NODEPQ * | nodepq, |
| SCIP_SET * | set, | ||
| SCIP_NODE * | node1, | ||
| SCIP_NODE * | node2 | ||
| ) |
compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2
| nodepq | node priority queue |
| set | global SCIP settings |
| node1 | first node to compare |
| node2 | second node to compare |
Definition at line 251 of file nodesel.c.
References SCIP_NodePQ::nodesel, and SCIPnodeselCompare().
Referenced by SCIPnodeFocus().
| SCIP_RETCODE SCIPnodepqInsert | ( | SCIP_NODEPQ * | nodepq, |
| SCIP_SET * | set, | ||
| SCIP_NODE * | node | ||
| ) |
inserts node into node priority queue
| nodepq | node priority queue |
| set | global SCIP settings |
| node | node to be inserted |
Definition at line 267 of file nodesel.c.
References SCIP_NodePQ::bfsposs, SCIP_NodePQ::bfsqueue, SCIP_NodePQ::len, SCIP_NodePQ::lowerboundsum, nodepqResize(), SCIP_NodePQ::nodesel, PQ_PARENT, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPnodeGetLowerbound(), SCIPsetDebugMsg, and SCIP_NodePQ::slots.
Referenced by nodeToLeaf(), and SCIPnodepqSetNodesel().
|
static |
deletes node at given position from the node priority queue; returns TRUE, if the parent fell down to the free position
| nodepq | node priority queue |
| set | global SCIP settings |
| rempos | queue position of node to remove |
Definition at line 329 of file nodesel.c.
References SCIP_NodePQ::bfsposs, SCIP_NodePQ::bfsqueue, FALSE, SCIP_NodePQ::len, SCIP_NodePQ::lowerboundsum, SCIP_NodePQ::nodesel, PQ_LEFTCHILD, PQ_PARENT, PQ_RIGHTCHILD, SCIP_Bool, SCIP_Real, SCIPnodeGetLowerbound(), SCIPsetDebugMsg, SCIP_NodePQ::slots, and TRUE.
Referenced by SCIPnodepqBound(), and SCIPnodepqRemove().
|
static |
returns the position of given node in the priority queue, or -1 if not existing
| nodepq | node priority queue |
| set | global SCIP settings |
| node | node to find |
Definition at line 487 of file nodesel.c.
References SCIP_NodePQ::len, and SCIP_NodePQ::slots.
Referenced by SCIPnodepqRemove().
| SCIP_RETCODE SCIPnodepqRemove | ( | SCIP_NODEPQ * | nodepq, |
| SCIP_SET * | set, | ||
| SCIP_NODE * | node | ||
| ) |
removes node from the node priority queue
| nodepq | node priority queue |
| set | global SCIP settings |
| node | node to remove |
Definition at line 511 of file nodesel.c.
References nodepqDelPos(), nodepqFindNode(), SCIP_INVALIDDATA, SCIP_OKAY, and SCIPerrorMessage.
Referenced by SCIPnodeFocus().
| SCIP_NODE* SCIPnodepqFirst | ( | const SCIP_NODEPQ * | nodepq | ) |
returns the best node of the queue without removing it
| nodepq | node priority queue |
Definition at line 532 of file nodesel.c.
References SCIP_NodePQ::len, and SCIP_NodePQ::slots.
Referenced by SCIPtreeGetBestLeaf().
| SCIP_NODE** SCIPnodepqNodes | ( | const SCIP_NODEPQ * | nodepq | ) |
returns the nodes array of the queue
| nodepq | node priority queue |
Definition at line 548 of file nodesel.c.
References SCIP_NodePQ::slots.
Referenced by SCIPgetLeaves(), and SCIPgetOpenNodesData().
| int SCIPnodepqLen | ( | const SCIP_NODEPQ * | nodepq | ) |
returns the number of nodes stored in the node priority queue
| nodepq | node priority queue |
Definition at line 558 of file nodesel.c.
References SCIP_NodePQ::len.
Referenced by SCIPgetLeaves(), SCIPgetNLeaves(), SCIPgetOpenNodesData(), and SCIPtreeGetNLeaves().
| SCIP_Real SCIPnodepqGetLowerbound | ( | SCIP_NODEPQ * | nodepq, |
| SCIP_SET * | set | ||
| ) |
gets the minimal lower bound of all nodes in the queue
| nodepq | node priority queue |
| set | global SCIP settings |
Definition at line 569 of file nodesel.c.
References SCIP_NodePQ::bfsqueue, SCIP_NodePQ::len, SCIP_NodePQ::nodesel, SCIPnodeGetLowerbound(), SCIPsetInfinity(), and SCIP_NodePQ::slots.
Referenced by SCIPtreeGetLowerbound().
| SCIP_NODE* SCIPnodepqGetLowerboundNode | ( | SCIP_NODEPQ * | nodepq, |
| SCIP_SET * | set | ||
| ) |
gets the node with minimal lower bound of all nodes in the queue
| nodepq | node priority queue |
| set | global SCIP settings |
Definition at line 592 of file nodesel.c.
References SCIP_NodePQ::bfsqueue, SCIP_NodePQ::len, SCIP_NodePQ::nodesel, and SCIP_NodePQ::slots.
Referenced by SCIPtreeGetLowerboundNode().
| SCIP_Real SCIPnodepqGetLowerboundSum | ( | SCIP_NODEPQ * | nodepq | ) |
gets the sum of lower bounds of all nodes in the queue
| nodepq | node priority queue |
Definition at line 616 of file nodesel.c.
References SCIP_NodePQ::lowerboundsum.
Referenced by SCIPtreeGetAvgLowerbound().
| 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 | ||
| ) |
free all nodes from the queue that are cut off by the given upper bound
| nodepq | node priority queue |
| blkmem | block memory buffer |
| set | global SCIP settings |
| stat | dynamic problem statistics |
| eventqueue | event queue |
| tree | branch and bound tree |
| reopt | reoptimization data structure |
| lp | current LP data |
| cutoffbound | cutoff bound: all nodes with lowerbound >= cutoffbound are cut off |
Definition at line 626 of file nodesel.c.
References FALSE, SCIP_NodePQ::len, nodepqDelPos(), PQ_LEFTCHILD, PQ_RIGHTCHILD, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_NODEINFEASIBLE, SCIP_NODETYPE_LEAF, SCIP_OKAY, SCIPlpGetSolstat(), SCIPnodeFree(), SCIPnodeGetDepth(), SCIPnodeGetLowerbound(), SCIPnodeGetType(), SCIPreoptCheckCutoff(), SCIPsetDebugMsg, SCIPsetIsGE(), SCIPsetIsLT(), SCIPtreeGetEffectiveRootDepth(), SCIPtreeGetFocusNode(), SCIPvisualCutoffNode(), SCIP_NodePQ::slots, and SCIP_Stat::visual.
Referenced by SCIPtreeCutoff().
|
static |
method to call, when the standard mode priority of a node selector was changed
Definition at line 706 of file nodesel.c.
References SCIP_CALL, SCIP_OKAY, SCIPparamGetData(), SCIPparamGetInt(), and SCIPsetNodeselStdPriority().
|
static |
method to call, when the memory saving mode priority of a node selector was changed
Definition at line 721 of file nodesel.c.
References SCIP_CALL, SCIP_OKAY, SCIPparamGetData(), SCIPparamGetInt(), and SCIPsetNodeselMemsavePriority().
| SCIP_RETCODE SCIPnodeselCopyInclude | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set | ||
| ) |
copies the given node selector to a new scip
| nodesel | node selector |
| set | SCIP_SET of SCIP to copy to |
Definition at line 735 of file nodesel.c.
References SCIP_CALL, SCIP_OKAY, SCIPnodeselGetName(), and SCIPsetDebugMsg.
| 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 | ||
| ) |
creates a node selector
| nodesel | pointer to store node selector |
| set | global SCIP settings |
| messagehdlr | message handler |
| blkmem | block memory for parameter settings |
| name | name of node selector |
| desc | description of node selector |
| stdpriority | priority of the node selector in standard mode |
| memsavepriority | priority of the node selector in memory saving mode |
| nodeseldata | node selector data |
Definition at line 753 of file nodesel.c.
References BMSallocMemory, BMSduplicateMemoryArray, FALSE, SCIP_ALLOC, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPclockCreate(), SCIPsetAddIntParam(), SCIPsnprintf(), and TRUE.
Referenced by SCIPincludeNodesel(), and SCIPincludeNodeselBasic().
| SCIP_RETCODE SCIPnodeselFree | ( | SCIP_NODESEL ** | nodesel, |
| SCIP_SET * | set | ||
| ) |
frees memory of node selector
| nodesel | pointer to node selector data structure |
| set | global SCIP settings |
Definition at line 818 of file nodesel.c.
References BMSfreeMemory, BMSfreeMemoryArray, SCIP_CALL, SCIP_OKAY, and SCIPclockFree().
Referenced by SCIPsetFree().
| SCIP_RETCODE SCIPnodeselInit | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set | ||
| ) |
initializes node selector
| nodesel | node selector |
| set | global SCIP settings |
Definition at line 846 of file nodesel.c.
References SCIP_Nodesel::initialized, SCIP_Nodesel::name, SCIP_Nodesel::nodeseltime, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockReset(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIP_Nodesel::setuptime, and TRUE.
| SCIP_RETCODE SCIPnodeselExit | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set | ||
| ) |
deinitializes node selector
| nodesel | node selector |
| set | global SCIP settings |
Definition at line 882 of file nodesel.c.
References FALSE, SCIP_Nodesel::initialized, SCIP_Nodesel::name, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIP_Nodesel::setuptime.
Referenced by SCIPsetInitPlugins().
| SCIP_RETCODE SCIPnodeselInitsol | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set | ||
| ) |
informs node selector that the branch and bound process is being started
| nodesel | node selector |
| set | global SCIP settings |
Definition at line 912 of file nodesel.c.
References SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Nodesel::setuptime.
Referenced by SCIPsetExitprePlugins().
| SCIP_RETCODE SCIPnodeselExitsol | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set | ||
| ) |
informs node selector that the branch and bound process data is being freed
| nodesel | node selector |
| set | global SCIP settings |
Definition at line 936 of file nodesel.c.
References SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Nodesel::setuptime.
Referenced by SCIPsetInitsolPlugins().
| SCIP_RETCODE SCIPnodeselSelect | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set, | ||
| SCIP_NODE ** | selnode | ||
| ) |
select next node to be processed
| nodesel | node selector |
| set | global SCIP settings |
| selnode | pointer to store node to be processed next |
Definition at line 960 of file nodesel.c.
References SCIP_Nodesel::nodeseltime, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), and SCIPclockStop().
Referenced by SCIPsolveCIP().
| int SCIPnodeselCompare | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set, | ||
| SCIP_NODE * | node1, | ||
| SCIP_NODE * | node2 | ||
| ) |
compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2
| nodesel | node selector |
| set | global SCIP settings |
| node1 | first node to compare |
| node2 | second node to compare |
Definition at line 984 of file nodesel.c.
Referenced by SCIPnodepqCompare(), SCIPtreeGetBestChild(), SCIPtreeGetBestNode(), and SCIPtreeGetBestSibling().
| void SCIPnodeselSetStdPriority | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set, | ||
| int | priority | ||
| ) |
gets priority of node selector in standard mode
| nodesel | node selector |
| set | global SCIP settings |
| priority | new priority of the node selector |
Definition at line 1031 of file nodesel.c.
References SCIP_Nodesel::stdpriority.
Referenced by SCIPsetNodeselStdPriority().
| void SCIPnodeselSetMemsavePriority | ( | SCIP_NODESEL * | nodesel, |
| SCIP_SET * | set, | ||
| int | priority | ||
| ) |
sets priority of node selector in memory saving mode
| nodesel | node selector |
| set | global SCIP settings |
| priority | new priority of the node selector |
Definition at line 1055 of file nodesel.c.
References SCIP_Nodesel::memsavepriority.
Referenced by SCIPsetNodeselMemsavePriority().
| void SCIPnodeselSetCopy | ( | SCIP_NODESEL * | nodesel, |
| SCIP_DECL_NODESELCOPY((*nodeselcopy)) | |||
| ) |
sets copy method of node selector
| nodesel | node selector |
Definition at line 1092 of file nodesel.c.
Referenced by SCIPsetNodeselCopy().
| void SCIPnodeselSetFree | ( | SCIP_NODESEL * | nodesel, |
| SCIP_DECL_NODESELFREE((*nodeselfree)) | |||
| ) |
sets destructor method of node selector
| nodesel | node selector |
Definition at line 1103 of file nodesel.c.
Referenced by SCIPsetNodeselFree().
| void SCIPnodeselSetInit | ( | SCIP_NODESEL * | nodesel, |
| SCIP_DECL_NODESELINIT((*nodeselinit)) | |||
| ) |
sets initialization method of node selector
| nodesel | node selector |
Definition at line 1114 of file nodesel.c.
Referenced by SCIPsetNodeselInit().
| void SCIPnodeselSetExit | ( | SCIP_NODESEL * | nodesel, |
| SCIP_DECL_NODESELEXIT((*nodeselexit)) | |||
| ) |
sets deinitialization method of node selector
| nodesel | node selector |
Definition at line 1125 of file nodesel.c.
Referenced by SCIPsetNodeselExit().
| void SCIPnodeselSetInitsol | ( | SCIP_NODESEL * | nodesel, |
| SCIP_DECL_NODESELINITSOL((*nodeselinitsol)) | |||
| ) |
sets solving process initialization method of node selector
| nodesel | node selector |
Definition at line 1136 of file nodesel.c.
Referenced by SCIPsetNodeselInitsol().
| void SCIPnodeselSetExitsol | ( | SCIP_NODESEL * | nodesel, |
| SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)) | |||
| ) |
sets solving process deinitialization method of node selector
| nodesel | node selector |
Definition at line 1147 of file nodesel.c.
Referenced by SCIPsetNodeselExitsol().
| void SCIPnodeselEnableOrDisableClocks | ( | SCIP_NODESEL * | nodesel, |
| SCIP_Bool | enable | ||
| ) |
enables or disables all clocks of nodesel, depending on the value of the flag
| nodesel | the node selector for which all clocks should be enabled or disabled |
| enable | should the clocks of the node selector be enabled? |
Definition at line 1168 of file nodesel.c.
References SCIP_Nodesel::nodeseltime, SCIPclockEnableOrDisable(), and SCIP_Nodesel::setuptime.