40#define HEUR_NAME "adaptivediving"
41#define HEUR_DESC "diving heuristic that selects adaptively between the existing, public divesets"
42#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
43#define HEUR_PRIORITY -70000
46#define HEUR_MAXDEPTH -1
47#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
48#define HEUR_USESSUBSCIP FALSE
50#define DIVESETS_INITIALSIZE 10
51#define DEFAULT_INITIALSEED 13
56#define DEFAULT_SELTYPE 'w'
57#define DEFAULT_SCORETYPE 'c'
60#define DEFAULT_USEADAPTIVECONTEXT FALSE
61#define DEFAULT_SELCONFIDENCECOEFF 10.0
62#define DEFAULT_EPSILON 1.0
63#define DEFAULT_MAXLPITERQUOT 0.1
64#define DEFAULT_MAXLPITEROFS 1500L
65#define DEFAULT_BESTSOLWEIGHT 10.0
222 int newsize = 2 *
heurdata->divesetssize;
339 for(
c = 0;
c < nelems; ++
c )
341 pos += sprintf(pos,
"%.4f ", elems[
c]);
362 SCIPdebugMsg(
scip,
"Weights: %s\n", printRealArray(strbuf, weights, nweights));
367 for(
w = 0;
w < nweights; ++
w )
369 weightsum += weights[
w];
377 for(
w = 0;
w < nweights - 1; ++
w )
379 weightsum += weights[
w];
381 if( weightsum >= randomnr )
418 for( d = 0; d <
heurdata->ndivesets; ++d )
422 methodunavailable[d] = ! available;
433 epsilon_t =
MAX(epsilon_t, 0.05);
447 for( d = 0; d <
heurdata->ndivesets; ++d )
451 if( methodunavailable[d] )
456 if( score < bestscore )
468 for( d = 0; d < ndivesets; ++d )
474 weights[d] = methodunavailable[d] ? 0.0 : 1 / (score + 1e-4);
530 SCIPdebugMsg(
scip,
"heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n",
625 "parameter that increases probability of exploration among divesets (only active if seltype is 'e')",
629 "score parameter for selection: minimize either average 'n'odes, LP 'i'terations,"
630 "backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 1 / solutions'u'ccess",
634 "selection strategy: (e)psilon-greedy, (w)eighted distribution, (n)ext diving",
638 "should the heuristic use its own statistics, or shared statistics?", &
heurdata->useadaptivecontext,
TRUE,
642 "coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores",
646 "maximal fraction of diving LP iterations compared to node LP iterations",
650 "additional number of allowed LP iterations",
654 "weight of incumbent solutions compared to other solutions in computation of LP iteration limit",
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
int SCIPgetNOrigConss(SCIP *scip)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
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)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Bool SCIPdivesetIsPublic(SCIP_DIVESET *diveset)
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_Real SCIPdivesetGetAvgDepth(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
SCIP_RETCODE SCIPisDivesetAvailable(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Bool *available)
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_HEUR ** SCIPgetHeurs(SCIP *scip)
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
int SCIPgetNHeurs(SCIP *scip)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPallocMemory(scip, ptr)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemory(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
int SCIPgetNSols(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
#define DEFAULT_MAXLPITERQUOT
#define DEFAULT_MAXLPITEROFS
static SCIP_DIVESET * diveset
static SCIP_Longint getLPIterlimit(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE divesetGetSelectionScore(SCIP_DIVESET *diveset, SCIP_HEURDATA *heurdata, SCIP_DIVECONTEXT divecontext, SCIP_Real *scoreptr)
#define DEFAULT_INITIALSEED
SCIPheurSetData(heur, NULL)
static int sampleWeighted(SCIP *scip, SCIP_RANDNUMGEN *rng, SCIP_Real *weights, int nweights)
static SCIP_RETCODE findAndStoreDivesets(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define DEFAULT_USEADAPTIVECONTEXT
SCIP_RETCODE SCIPincludeHeurAdaptivediving(SCIP *scip)
#define DEFAULT_SCORETYPE
#define DEFAULT_SELCONFIDENCECOEFF
#define DIVESETS_INITIALSIZE
SCIPfreeSol(scip, &heurdata->sol))
SCIPfreeRandom(scip, &heurdata->randnumgen)
static SCIP_RETCODE selectDiving(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, int *selection)
SCIPsetRandomSeed(scip, heurdata->randnumgen,(unsigned int)(DEFAULT_INITIALSEED+SCIPgetNOrigVars(scip)+SCIPgetNOrigConss(scip)))
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
#define DEFAULT_BESTSOLWEIGHT
SCIPcreateSol(scip, &heurdata->sol, heur))
diving heuristic that selects adaptively between the existing, public dive sets
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
#define SCIP_DECL_HEURCOPY(x)
enum SCIP_DiveContext SCIP_DIVECONTEXT
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURINIT(x)
struct SCIP_Diveset SCIP_DIVESET
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
@ SCIP_DIVECONTEXT_ADAPTIVE
struct SCIP_RandNumGen SCIP_RANDNUMGEN
enum SCIP_Retcode SCIP_RETCODE