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	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_DIVESET *	diveset
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.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.

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

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

SCIPfreeRandom	(	scip	,
		&heurdata->	randnumgen )

References heurdata.

Referenced by conshdlrdataFree(), DECL_NHEXIT(), DECL_NHEXIT(), DECL_NHEXIT(), DECL_NHEXIT(), DECL_NHINIT(), DECL_NHINIT(), probdataFree(), runCyckerlin(), SCIP_DECL_BRANCHEXIT(), SCIP_DECL_BRANCHEXITSOL(), SCIP_DECL_BRANCHFREE(), SCIP_DECL_CONSEXIT(), SCIP_DECL_CONSFREE(), SCIP_DECL_CUTSELEXIT(), SCIP_DECL_CUTSELEXIT(), SCIP_DECL_CUTSELEXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXIT(), SCIP_DECL_NLHDLREXIT(), SCIP_DECL_NLPIFREE(), SCIP_DECL_NLPIFREEPROBLEM(), SCIP_DECL_NLPIFREEPROBLEM(), SCIP_DECL_NLPIFREEPROBLEM(), SCIP_DECL_PRICEREXIT(), SCIP_DECL_PROPEXIT(), SCIP_DECL_PROPEXITSOL(), SCIP_DECL_PROPEXITSOL(), SCIP_DECL_READERREAD(), SCIP_DECL_SEPAEXIT(), SCIP_DECL_SEPAEXIT(), SCIP_DECL_SEPAEXIT(), SCIP_DECL_SEPAEXIT(), SCIP_DECL_SEPAEXIT(), SCIP_DECL_SEPAEXITSOL(), SCIPpermuteProb(), and SCIPsolveConcurrent().

◆ 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

scip	SCIP data structure
heur	the heuristic
heurdata	heuristic 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))	)

References DEFAULT_INITIALSEED, heurdata, SCIP_OKAY, and SCIPgetNOrigVars().

Referenced by SCIP_DECL_BRANCHINIT().

◆ 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

scip	SCIP data structure
heur	the heuristic
heurdata	heuristic 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

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

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 assert(), divesetGetSelectionScore(), divesets, heurdata, 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(), SCIPrandomGetReal(), and selection.

◆ 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 517 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 537 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	)

References diveset, heurdata, lpiterlimit, result, SCIP_DIVECONTEXT_ADAPTIVE, and SCIP_FOUNDSOL.

Referenced by executeDivingHeuristic(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEUREXEC().

◆ 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 assert(), 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, heurdata, 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().

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:

{

SCIP_HEURDATA* heurdata

heurdata

Definition heur_actconsdiving.c:229

SCIP_HEURDATA

struct SCIP_HeurData SCIP_HEURDATA

Definition type_heur.h:77

execution method of primal heuristic

Definition at line 505 of file heur_adaptivediving.c.

◆ divesets

divesets = heurdata->divesets

Definition at line 506 of file heur_adaptivediving.c.

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

◆ lpiterlimit

lpiterlimit = getLPIterlimit(scip, heur, heurdata)

Definition at line 507 of file heur_adaptivediving.c.

Referenced by getLPIterlimit(), if(), SCIPlpiIsIterlimExc(), SCIPlpiIsTimelimExc(), and SCIPperformGenericDivingAlgorithm().

◆ selection

◆ result

if result = SCIP_DELAYED

Definition at line 534 of file heur_adaptivediving.c.

Detailed Description

Macros

Functions

Variables

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

◆ assert() [1/10]

◆ assert() [2/10]

◆ assert() [3/10]

◆ assert() [4/10]

◆ if() [1/4]

◆ SCIPfreeRandom()

◆ SCIPfreeMemory()

◆ SCIPheurSetData()

◆ findAndStoreDivesets()

◆ SCIPcreateSol()

◆ SCIPsetRandomSeed()

◆ SCIPfreeSol()

◆ getLPIterlimit()

◆ sampleWeighted()

◆ selectDiving() [1/2]

◆ assert() [5/10]

◆ assert() [6/10]

◆ if() [2/4]

◆ assert() [7/10]

◆ assert() [8/10]

◆ SCIPdebugMsg() [1/2]

◆ if() [3/4]

◆ if() [4/4]

◆ selectDiving() [2/2]

◆ assert() [9/10]

◆ assert() [10/10]

◆ SCIPdebugMsg() [2/2]

◆ SCIPperformGenericDivingAlgorithm()

◆ SCIPincludeHeurAdaptivediving()

Variable Documentation

◆ heurdata

◆ SCIP_OKAY

◆ lastselection

◆ diveset

◆ divesets

◆ lpiterlimit

◆ selection

◆ result