SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

diving heuristic that selects adaptively between the existing, public dive sets

Author
Gregor Hendel

Definition in file heur_adaptivediving.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_adaptivediving.h"
#include "scip/heuristics.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Macros

#define HEUR_NAME   "adaptivediving"
#define HEUR_DESC   "diving heuristic that selects adaptively between the existing, public divesets"
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING
#define HEUR_PRIORITY   -70000
#define HEUR_FREQ   5
#define HEUR_FREQOFS   3
#define HEUR_MAXDEPTH   -1
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE
#define HEUR_USESSUBSCIP   FALSE
#define DIVESETS_INITIALSIZE   10
#define DEFAULT_INITIALSEED   13
#define DEFAULT_SELTYPE   'w'
#define DEFAULT_SCORETYPE   'c'
#define DEFAULT_USEADAPTIVECONTEXT   FALSE
#define DEFAULT_SELCONFIDENCECOEFF   10.0
#define DEFAULT_EPSILON   1.0
#define DEFAULT_MAXLPITERQUOT   0.1
#define DEFAULT_MAXLPITEROFS   1500L
#define DEFAULT_BESTSOLWEIGHT   10.0

Functions

static SCIP_RETCODE divesetGetSelectionScore (SCIP_DIVESET *diveset, SCIP_HEURDATA *heurdata, SCIP_DIVECONTEXT divecontext, SCIP_Real *scoreptr)
static SCIP_DECL_HEURCOPY (heurCopyAdaptivediving)
static assert (heur !=NULL)
 assert (strcmp(SCIPheurGetName(heur), HEUR_NAME)==0)
 assert (scip !=NULL)
 assert (heurdata !=NULL)
 if (heurdata->divesets !=NULL)
 SCIPfreeRandom (scip, &heurdata->randnumgen)
 SCIPfreeMemory (scip, &heurdata)
 SCIPheurSetData (heur, NULL)
static SCIP_RETCODE findAndStoreDivesets (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
 SCIPcreateSol (scip, &heurdata->sol, heur))
 SCIPsetRandomSeed (scip, heurdata->randnumgen,(unsigned int)(DEFAULT_INITIALSEED+SCIPgetNOrigVars(scip)+SCIPgetNOrigConss(scip)))
 SCIPfreeSol (scip, &heurdata->sol))
static SCIP_Longint getLPIterlimit (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
static int sampleWeighted (SCIP *scip, SCIP_RANDNUMGEN *rng, SCIP_Real *weights, int nweights)
static SCIP_RETCODE selectDiving (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, int *selection)
 assert (result !=NULL)
 assert (SCIPhasCurrentNodeLP(scip))
 if (heurdata->divesets==NULL)
 assert (divesets !=NULL)
 assert (heurdata->ndivesets > 0)
 SCIPdebugMsg (scip, "heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n", SCIPgetDepth(scip), SCIPgetNSols(scip), nodeinfeasible, SCIPgetNNodes(scip), SCIPgetLastDivenode(scip))
 if (nodeinfeasible)
 if (lpiterlimit<=0) return SCIP_OKAY
 selectDiving (scip, heur, heurdata, &selection))
 assert (selection >=0 &&selection< heurdata->ndivesets)
 assert (diveset !=NULL)
 SCIPdebugMsg (scip, "Selected diveset %s\n", SCIPdivesetGetName(diveset))
 SCIPperformGenericDivingAlgorithm (scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
SCIP_RETCODE SCIPincludeHeurAdaptivediving (SCIP *scip)

Variables

 heurdata = SCIPheurGetData(heur)
return SCIP_OKAY
heurdata lastselection = -1
static SCIP_DIVESETdiveset
SCIP_DIVESET ** divesets = heurdata->divesets
SCIP_Longint lpiterlimit = getLPIterlimit(scip, heur, heurdata)
int selection
result = SCIP_DELAYED

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "adaptivediving"

Definition at line 40 of file heur_adaptivediving.c.

◆ HEUR_DESC

#define HEUR_DESC   "diving heuristic that selects adaptively between the existing, public divesets"

Definition at line 41 of file heur_adaptivediving.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING

Definition at line 42 of file heur_adaptivediving.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -70000

Definition at line 43 of file heur_adaptivediving.c.

◆ HEUR_FREQ

#define HEUR_FREQ   5

Definition at line 44 of file heur_adaptivediving.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   3

Definition at line 45 of file heur_adaptivediving.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 46 of file heur_adaptivediving.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE

Definition at line 47 of file heur_adaptivediving.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 48 of file heur_adaptivediving.c.

◆ DIVESETS_INITIALSIZE

#define DIVESETS_INITIALSIZE   10

Definition at line 50 of file heur_adaptivediving.c.

Referenced by findAndStoreDivesets().

◆ DEFAULT_INITIALSEED

#define DEFAULT_INITIALSEED   13

Definition at line 51 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving(), and SCIPsetRandomSeed().

◆ DEFAULT_SELTYPE

#define DEFAULT_SELTYPE   'w'

Definition at line 56 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ DEFAULT_SCORETYPE

#define DEFAULT_SCORETYPE   'c'

score parameter for selection: minimize either average 'n'odes, LP 'i'terations, backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 1 / solutions'u'ccess

Definition at line 57 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ DEFAULT_USEADAPTIVECONTEXT

#define DEFAULT_USEADAPTIVECONTEXT   FALSE

Definition at line 60 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ DEFAULT_SELCONFIDENCECOEFF

#define DEFAULT_SELCONFIDENCECOEFF   10.0

coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores

Definition at line 61 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ DEFAULT_EPSILON

#define DEFAULT_EPSILON   1.0

parameter that increases probability of exploration among divesets (only active if seltype is 'e')

Definition at line 62 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ DEFAULT_MAXLPITERQUOT

#define DEFAULT_MAXLPITERQUOT   0.1

maximal fraction of diving LP iterations compared to node LP iterations

Definition at line 63 of file heur_adaptivediving.c.

◆ DEFAULT_MAXLPITEROFS

#define DEFAULT_MAXLPITEROFS   1500L

additional number of allowed LP iterations

Definition at line 64 of file heur_adaptivediving.c.

◆ DEFAULT_BESTSOLWEIGHT

#define DEFAULT_BESTSOLWEIGHT   10.0

weight of incumbent solutions compared to other solutions in computation of LP iteration limit

Definition at line 65 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving(), updateHeurStatsDiving(), updateHeurStatsLNS(), and updateNeighborhoodStats().

Function Documentation

◆ divesetGetSelectionScore()

SCIP_RETCODE divesetGetSelectionScore ( SCIP_DIVESET * diveset,
SCIP_HEURDATA * heurdata,
SCIP_DIVECONTEXT divecontext,
SCIP_Real * scoreptr )
static

get the selection score for this dive set

Parameters
divesetdiving settings data structure
heurdataheuristic data
divecontextcontext for diving statistics
scoreptrpointer to store the score

Definition at line 97 of file heur_adaptivediving.c.

References assert(), diveset, heurdata, NULL, SCIP_INVALID, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPABORT, SCIPdivesetGetAvgDepth(), SCIPdivesetGetNBacktracks(), SCIPdivesetGetNCalls(), SCIPdivesetGetNConflicts(), SCIPdivesetGetNLPIterations(), SCIPdivesetGetNProbingNodes(), SCIPdivesetGetNSols(), SCIPdivesetGetSolSuccess(), and SCIPerrorMessage.

Referenced by selectDiving().

◆ SCIP_DECL_HEURCOPY()

SCIP_DECL_HEURCOPY ( heurCopyAdaptivediving )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 147 of file heur_adaptivediving.c.

References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurAdaptivediving().

◆ assert() [1/10]

assert ( heur ! = NULL)

destructor of primal heuristic to free user data (called when SCIP is exiting)

initialization method of primal heuristic (called after problem was transformed)

deinitialization method of primal heuristic (called before transformed problem is freed)

References NULL.

◆ assert() [2/10]

assert ( strcmp(SCIPheurGetName(heur), HEUR_NAME) = =0)

References HEUR_NAME.

◆ assert() [3/10]

assert ( scip ! = NULL)

References NULL.

◆ assert() [4/10]

assert ( heurdata ! = NULL)

References heurdata, and NULL.

◆ if() [1/4]

if ( heurdata->divesets ! = NULL)

Definition at line 173 of file heur_adaptivediving.c.

References heurdata, NULL, and SCIPfreeBlockMemoryArray.

◆ SCIPfreeRandom()

◆ SCIPfreeMemory()

SCIPfreeMemory ( scip ,
& heurdata )

References heurdata.

◆ SCIPheurSetData()

SCIPheurSetData ( heur ,
NULL  )

References NULL.

◆ findAndStoreDivesets()

SCIP_RETCODE findAndStoreDivesets ( SCIP * scip,
SCIP_HEUR * heur,
SCIP_HEURDATA * heurdata )
static

find publicly available divesets and store them

Parameters
scipSCIP data structure
heurthe heuristic
heurdataheuristic data

Definition at line 188 of file heur_adaptivediving.c.

References assert(), diveset, DIVESETS_INITIALSIZE, h, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPdivesetGetName(), SCIPdivesetIsPublic(), SCIPgetHeurs(), SCIPgetNHeurs(), SCIPheurGetDivesets(), SCIPheurGetNDivesets(), and SCIPreallocBlockMemoryArray.

Referenced by if().

◆ SCIPcreateSol()

SCIPcreateSol ( scip ,
&heurdata-> sol,
heur  )

References heurdata.

◆ SCIPsetRandomSeed()

SCIPsetRandomSeed ( scip ,
heurdata-> randnumgen,
(unsigned int)(DEFAULT_INITIALSEED+SCIPgetNOrigVars(scip)+SCIPgetNOrigConss(scip))  )

◆ SCIPfreeSol()

SCIPfreeSol ( scip ,
&heurdata-> sol )

References heurdata, and SCIP_OKAY.

◆ getLPIterlimit()

SCIP_Longint getLPIterlimit ( SCIP * scip,
SCIP_HEUR * heur,
SCIP_HEURDATA * heurdata )
static

get LP iteration limit for diving

Parameters
scipSCIP data structure
heurthe heuristic
heurdataheuristic data

Definition at line 295 of file heur_adaptivediving.c.

References assert(), heurdata, i, lpiterlimit, ncalls, nlpiterations, nsolsfound, NULL, SCIP_DIVECONTEXT_ADAPTIVE, SCIP_Longint, SCIP_Real, SCIPdivesetGetNLPIterations(), SCIPgetNNodeLPIterations(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), and SCIPheurGetNSolsFound().

◆ sampleWeighted()

int sampleWeighted ( SCIP * scip,
SCIP_RANDNUMGEN * rng,
SCIP_Real * weights,
int nweights )
static

sample from a distribution defined by weights

Parameters
scipSCIP data structure
rngrandom number generator
weightsweights of a ground set that define the sampling distribution
nweightsnumber of elements in the ground set

Definition at line 350 of file heur_adaptivediving.c.

References assert(), SCIP_MAXSTRLEN, SCIP_Real, SCIPdebugMsg, SCIPrandomGetReal(), and w.

Referenced by selectDiving().

◆ selectDiving() [1/2]

SCIP_RETCODE selectDiving ( SCIP * scip,
SCIP_HEUR * heur,
SCIP_HEURDATA * heurdata,
int * selection )
static

◆ assert() [5/10]

assert ( result ! = NULL)

References NULL, and result.

◆ assert() [6/10]

assert ( SCIPhasCurrentNodeLP(scip) )

References heurdata.

◆ if() [2/4]

if ( heurdata-> divesets = NULL)

Definition at line 521 of file heur_adaptivediving.c.

References findAndStoreDivesets(), heurdata, NULL, and SCIP_CALL.

◆ assert() [7/10]

assert ( divesets ! = NULL)

References divesets, and NULL.

◆ assert() [8/10]

assert ( heurdata-> ndivesets,
0  )

References heurdata.

◆ SCIPdebugMsg() [1/2]

SCIPdebugMsg ( scip ,
"heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n" ,
SCIPgetDepth(scip) ,
SCIPgetNSols(scip) ,
nodeinfeasible ,
SCIPgetNNodes(scip) ,
SCIPgetLastDivenode(scip)  )

◆ if() [3/4]

if ( nodeinfeasible )

Definition at line 541 of file heur_adaptivediving.c.

References SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, and SCIPdebugMsg.

◆ if() [4/4]

if ( lpiterlimit<= 0)

References lpiterlimit, and SCIP_OKAY.

◆ selectDiving() [2/2]

selectDiving ( scip ,
heur ,
heurdata ,
& selection )

References heurdata, and selection.

◆ assert() [9/10]

assert ( selection >=0 &&selection< heurdata-> ndivesets)

References diveset, divesets, and selection.

◆ assert() [10/10]

assert ( diveset ! = NULL)

References diveset, and NULL.

◆ SCIPdebugMsg() [2/2]

SCIPdebugMsg ( scip ,
"Selected diveset %s\n" ,
SCIPdivesetGetName(diveset)  )

References diveset.

◆ SCIPperformGenericDivingAlgorithm()

SCIPperformGenericDivingAlgorithm ( scip ,
diveset ,
heurdata-> sol,
heur ,
result ,
nodeinfeasible ,
lpiterlimit ,
- 1,
-1. 0,
SCIP_DIVECONTEXT_ADAPTIVE  )

◆ SCIPincludeHeurAdaptivediving()

Variable Documentation

◆ heurdata

heurdata = SCIPheurGetData(heur)

Definition at line 170 of file heur_adaptivediving.c.

◆ SCIP_OKAY

return SCIP_OKAY

Definition at line 183 of file heur_adaptivediving.c.

◆ lastselection

heurdata lastselection = -1

Definition at line 248 of file heur_adaptivediving.c.

◆ diveset

diveset
Initial value:
{
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77

execution method of primal heuristic

Definition at line 509 of file heur_adaptivediving.c.

◆ divesets

divesets = heurdata->divesets

Definition at line 510 of file heur_adaptivediving.c.

Referenced by assert(), assert(), and selectDiving().

◆ lpiterlimit

◆ selection

◆ result

if result = SCIP_DELAYED

Definition at line 538 of file heur_adaptivediving.c.