heur_adaptivediving.c File Reference

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	SCIP_DECL_HEURFREE (heurFreeAdaptivediving)
static SCIP_RETCODE	findAndStoreDivesets (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
static	SCIP_DECL_HEURINIT (heurInitAdaptivediving)
static	SCIP_DECL_HEUREXIT (heurExitAdaptivediving)
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)
static	SCIP_DECL_HEUREXEC (heurExecAdaptivediving)
SCIP_RETCODE	SCIPincludeHeurAdaptivediving (SCIP *scip)

Macro Definition Documentation

HEUR_NAME

#define HEUR_NAME   "adaptivediving"

Definition at line 31 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_DESC

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

Definition at line 32 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING

Definition at line 33 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_PRIORITY

#define HEUR_PRIORITY   -70000

Definition at line 34 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_FREQ

#define HEUR_FREQ   5

Definition at line 35 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_FREQOFS

#define HEUR_FREQOFS   3

Definition at line 36 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 37 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE

Definition at line 38 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 39 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

DIVESETS_INITIALSIZE

#define DIVESETS_INITIALSIZE   10

Definition at line 41 of file heur_adaptivediving.c.

Referenced by findAndStoreDivesets().

DEFAULT_INITIALSEED

#define DEFAULT_INITIALSEED   13

Definition at line 42 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

DEFAULT_SELTYPE

#define DEFAULT_SELTYPE   'w'

Definition at line 47 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 48 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

DEFAULT_USEADAPTIVECONTEXT

#define DEFAULT_USEADAPTIVECONTEXT   FALSE

Definition at line 53 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 54 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 55 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 56 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

DEFAULT_MAXLPITEROFS

#define DEFAULT_MAXLPITEROFS   1500L

additional number of allowed LP iterations

Definition at line 57 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

DEFAULT_BESTSOLWEIGHT

#define DEFAULT_BESTSOLWEIGHT   10.0

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

Definition at line 58 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

Function Documentation

divesetGetSelectionScore()

static 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

diveset	diving settings data structure
heurdata	heuristic data
divecontext	context for diving statistics
scoreptr	pointer to store the score

Definition at line 90 of file heur_adaptivediving.c.

References NULL, SCIP_DECL_HEURCOPY(), 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()

static SCIP_DECL_HEURCOPY ( heurCopyAdaptivediving  )

static

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

Definition at line 140 of file heur_adaptivediving.c.

Referenced by divesetGetSelectionScore().

SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeAdaptivediving  )

static

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

Definition at line 154 of file heur_adaptivediving.c.

findAndStoreDivesets()

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

static

find publicly available divesets and store them

Parameters

scip	SCIP data structure
heur	the heuristic
heurdata	heuristic data

Definition at line 181 of file heur_adaptivediving.c.

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

SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitAdaptivediving  )

static

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

Definition at line 233 of file heur_adaptivediving.c.

Referenced by findAndStoreDivesets().

SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitAdaptivediving  )

static

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

Definition at line 259 of file heur_adaptivediving.c.

getLPIterlimit()

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

static

get LP iteration limit for diving

Parameters

scip	SCIP data structure
heur	the heuristic
heurdata	heuristic data

Definition at line 282 of file heur_adaptivediving.c.

References NULL, sampleWeighted(), SCIP_DIVECONTEXT_ADAPTIVE, SCIP_Longint, SCIP_Real, SCIPdivesetGetNLPIterations(), SCIPgetNNodeLPIterations(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), and SCIPheurGetNSolsFound().

sampleWeighted()

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

static

sample from a distribution defined by weights

Parameters

scip	SCIP data structure
rng	random number generator
weights	weights of a ground set that define the sampling distribution
nweights	number of elements in the ground set

Definition at line 337 of file heur_adaptivediving.c.

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

Referenced by getLPIterlimit(), and selectDiving().

selectDiving()

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

static

select the diving method to apply

Parameters

scip	SCIP data structure
heur	the heuristic
heurdata	heuristic data
selection	selection made

Definition at line 379 of file heur_adaptivediving.c.

References divesetGetSelectionScore(), MAX, NULL, sampleWeighted(), SCIP_Bool, SCIP_CALL, SCIP_DECL_HEUREXEC(), SCIP_DIVECONTEXT_ADAPTIVE, SCIP_DIVECONTEXT_TOTAL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPheurGetNCalls(), SCIPisDivesetAvailable(), SCIPrandomGetInt(), SCIPrandomGetReal(), and sqrt().

Referenced by sampleWeighted().

SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecAdaptivediving  )

static

execution method of primal heuristic

Definition at line 493 of file heur_adaptivediving.c.

Referenced by selectDiving().

SCIPincludeHeurAdaptivediving()

SCIP_RETCODE SCIPincludeHeurAdaptivediving

(

SCIP *

scip

)

creates the adaptivediving heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 579 of file heur_adaptivediving.c.

References DEFAULT_BESTSOLWEIGHT, DEFAULT_EPSILON, DEFAULT_INITIALSEED, DEFAULT_MAXLPITEROFS, DEFAULT_MAXLPITERQUOT, DEFAULT_SCORETYPE, DEFAULT_SELCONFIDENCECOEFF, DEFAULT_SELTYPE, DEFAULT_USEADAPTIVECONTEXT, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_CALL_TERMINATE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPcreateRandom(), SCIPfreeMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurFree(), SCIPsetHeurInit(), and TRUE.

Referenced by SCIPincludeDefaultPlugins().