Scippy

SCIP

Solving Constraint Integer Programs

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

Referenced by SCIPincludeHeurAdaptivediving().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING

Definition at line 42 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -70000

Definition at line 43 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ HEUR_FREQ

#define HEUR_FREQ   5

Definition at line 44 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   3

Definition at line 45 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 46 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE

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

Referenced by SCIPincludeHeurAdaptivediving().

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

◆ 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 62 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 63 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 64 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 65 of file heur_adaptivediving.c.

Referenced by SCIPincludeHeurAdaptivediving().

◆ DEFAULT_MAXLPITEROFS

#define DEFAULT_MAXLPITEROFS   1500L

additional number of allowed LP iterations

Definition at line 66 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 67 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
divesetdiving settings data structure
heurdataheuristic data
divecontextcontext for diving statistics
scoreptrpointer to store the score

Definition at line 99 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 149 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 163 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
scipSCIP data structure
heurthe heuristic
heurdataheuristic data

Definition at line 190 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 241 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 274 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
scipSCIP data structure
heurthe heuristic
heurdataheuristic data

Definition at line 297 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
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 352 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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecAdaptivediving  )
static

execution method of primal heuristic

Definition at line 508 of file heur_adaptivediving.c.

Referenced by selectDiving().

◆ SCIPincludeHeurAdaptivediving()