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.15

#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 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.

◆ DEFAULT_INITIALSEED

#define DEFAULT_INITIALSEED 13

Definition at line 51 of file heur_adaptivediving.c.

◆ DEFAULT_SELTYPE

#define DEFAULT_SELTYPE 'w'

Definition at line 56 of file heur_adaptivediving.c.

◆ 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 59 of file heur_adaptivediving.c.

◆ DEFAULT_USEADAPTIVECONTEXT

#define DEFAULT_USEADAPTIVECONTEXT FALSE

Definition at line 60 of file heur_adaptivediving.c.

◆ 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.

◆ 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.

◆ DEFAULT_MAXLPITERQUOT

#define DEFAULT_MAXLPITERQUOT 0.15

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.

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 97 of file heur_adaptivediving.c.

References 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()

static 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 HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurAdaptivediving().

◆ 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 161 of file heur_adaptivediving.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeMemory, SCIPfreeRandom(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

◆ 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 188 of file heur_adaptivediving.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitAdaptivediving )

static

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

Definition at line 239 of file heur_adaptivediving.c.

References DEFAULT_INITIALSEED, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPfreeBlockMemoryArray, SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPheurGetData(), SCIPheurGetName(), and SCIPsetRandomSeed().

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitAdaptivediving )

static

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

Definition at line 272 of file heur_adaptivediving.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().

◆ 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 295 of file heur_adaptivediving.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ 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 345 of file heur_adaptivediving.c.

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

Referenced by 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 388 of file heur_adaptivediving.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecAdaptivediving )

static

execution method of primal heuristic

Definition at line 502 of file heur_adaptivediving.c.

References findAndStoreDivesets(), getLPIterlimit(), HEUR_NAME, NULL, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTRUN, SCIP_DIVECONTEXT_ADAPTIVE, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPdebugMsg, SCIPdivesetGetName(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLastDivenode(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNSols(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPisGE(), SCIPisLPSolBasic(), SCIPperformGenericDivingAlgorithm(), selectDiving(), and SCIP_Diveset::sol.

◆ SCIPincludeHeurAdaptivediving()

SCIP_RETCODE SCIPincludeHeurAdaptivediving ( SCIP * scip )

creates the adaptivediving heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 588 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, SCIPheurMarkExact(), SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurFree(), SCIPsetHeurInit(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DIVESETS_INITIALSIZE

◆ DEFAULT_INITIALSEED

◆ DEFAULT_SELTYPE

◆ DEFAULT_SCORETYPE

◆ DEFAULT_USEADAPTIVECONTEXT

◆ DEFAULT_SELCONFIDENCECOEFF

◆ DEFAULT_EPSILON

◆ DEFAULT_MAXLPITERQUOT

◆ DEFAULT_MAXLPITEROFS

◆ DEFAULT_BESTSOLWEIGHT

Function Documentation

◆ divesetGetSelectionScore()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ findAndStoreDivesets()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ getLPIterlimit()

◆ sampleWeighted()

◆ selectDiving()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurAdaptivediving()