29 #define NODESEL_NAME "bfs" 30 #define NODESEL_DESC "best first search" 31 #define NODESEL_STDPRIORITY 100000 32 #define NODESEL_MEMSAVEPRIORITY 0 39 #define MINPLUNGEDEPTH -1 40 #define MAXPLUNGEDEPTH -1 41 #define MAXPLUNGEQUOT 0.25 46 struct SCIP_NodeselData
66 assert(nodesel != NULL);
82 assert(nodesel != NULL);
88 assert(nodeseldata != NULL);
107 assert(nodesel != NULL);
109 assert(
scip != NULL);
110 assert(selnode != NULL);
116 assert(nodeseldata != NULL);
119 minplungedepth = nodeseldata->minplungedepth;
120 maxplungedepth = nodeseldata->maxplungedepth;
121 maxplungequot = nodeseldata->maxplungequot;
122 if( minplungedepth == -1 )
126 minplungedepth += 10;
127 if( maxplungedepth >= 0 )
128 minplungedepth = MIN(minplungedepth, maxplungedepth);
130 if( maxplungedepth == -1 )
132 maxplungedepth =
MAX(maxplungedepth, minplungedepth);
136 if( plungedepth >= maxplungedepth )
139 SCIPdebugMsg(
scip,
"plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
150 if( plungedepth < minplungedepth )
154 minplungedepth, maxplungedepth, plungedepth);
168 cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
170 maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
172 SCIPdebugMsg(
scip,
"plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
173 minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
232 assert(nodesel != NULL);
234 assert(
scip != NULL);
273 if( depth1 < depth2 )
275 else if( depth1 > depth2 )
308 nodeselSelectBfs, nodeselCompBfs, nodeseldata) );
310 assert(nodesel != NULL);
317 "nodeselection/bfs/minplungedepth",
318 "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
321 "nodeselection/bfs/maxplungedepth",
322 "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
325 "nodeselection/bfs/maxplungequot",
326 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
int SCIPgetPlungeDepth(SCIP *scip)
#define NODESEL_STDPRIORITY
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_RETCODE SCIPincludeNodeselBasic(SCIP *scip, SCIP_NODESEL **nodesel, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, 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 SCIPincludeNodeselBfs(SCIP *scip)
struct SCIP_NodeselData SCIP_NODESELDATA
static SCIP_DECL_NODESELFREE(nodeselFreeBfs)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
static SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
enum SCIP_NodeType SCIP_NODETYPE
#define NODESEL_MEMSAVEPRIORITY
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
node selector for best first search
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
static SCIP_DECL_NODESELCOMP(nodeselCompBfs)
static SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)