Scippy

SCIP

Solving Constraint Integer Programs

heur.h File Reference

Detailed Description

internal methods for primal heuristics

Author
Tobias Achterberg

Definition in file heur.h.

#include "scip/def.h"
#include "blockmemshell/memory.h"
#include "scip/type_retcode.h"
#include "scip/type_result.h"
#include "scip/type_set.h"
#include "scip/type_primal.h"
#include "scip/type_heur.h"
#include "scip/pub_heur.h"
#include "scip/stat.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPdivesetCreate (SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_DIVETYPE divetypemask, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)))
 
void SCIPdivesetReset (SCIP_DIVESET *diveset)
 
void SCIPdivesetUpdateStats (SCIP_DIVESET *diveset, SCIP_STAT *stat, int depth, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Bool leavesol)
 
SCIP_RETCODE SCIPdivesetGetScore (SCIP_DIVESET *diveset, SCIP_SET *set, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
 
void SCIPdivesetUpdateLPStats (SCIP_DIVESET *diveset, SCIP_STAT *stat, SCIP_Longint niterstoadd)
 
SCIP_RETCODE SCIPheurCopyInclude (SCIP_HEUR *heur, SCIP_SET *set)
 
SCIP_RETCODE SCIPheurCreate (SCIP_HEUR **heur, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, unsigned int timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
 
SCIP_RETCODE SCIPheurFree (SCIP_HEUR **heur, SCIP_SET *set)
 
SCIP_RETCODE SCIPheurInit (SCIP_HEUR *heur, SCIP_SET *set)
 
SCIP_RETCODE SCIPheurExit (SCIP_HEUR *heur, SCIP_SET *set)
 
SCIP_RETCODE SCIPheurInitsol (SCIP_HEUR *heur, SCIP_SET *set)
 
SCIP_RETCODE SCIPheurExitsol (SCIP_HEUR *heur, SCIP_SET *set)
 
SCIP_Bool SCIPheurShouldBeExecuted (SCIP_HEUR *heur, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool *delayed)
 
SCIP_RETCODE SCIPheurExec (SCIP_HEUR *heur, SCIP_SET *set, SCIP_PRIMAL *primal, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool nodeinfeasible, int *ndelayedheurs, SCIP_RESULT *result)
 
void SCIPheurSetPriority (SCIP_HEUR *heur, SCIP_SET *set, int priority)
 
void SCIPheurSetCopy (SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
 
void SCIPheurSetFree (SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
 
void SCIPheurSetInit (SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
 
void SCIPheurSetExit (SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
 
void SCIPheurSetInitsol (SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
 
void SCIPheurSetExitsol (SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
 
void SCIPheurEnableOrDisableClocks (SCIP_HEUR *heur, SCIP_Bool enable)
 

Function Documentation

SCIP_RETCODE SCIPdivesetCreate ( SCIP_DIVESET **  diveset,
SCIP_HEUR heur,
const char *  name,
SCIP_SET set,
SCIP_MESSAGEHDLR messagehdlr,
BMS_BLKMEM blkmem,
SCIP_Real  minreldepth,
SCIP_Real  maxreldepth,
SCIP_Real  maxlpiterquot,
SCIP_Real  maxdiveubquot,
SCIP_Real  maxdiveavgquot,
SCIP_Real  maxdiveubquotnosol,
SCIP_Real  maxdiveavgquotnosol,
SCIP_Real  lpresolvedomchgquot,
int  lpsolvefreq,
int  maxlpiterofs,
SCIP_Bool  backtrack,
SCIP_Bool  onlylpbranchcands,
SCIP_DIVETYPE  divetypemask,
SCIP_DECL_DIVESETGETSCORE((*divesetgetscore))   
)

create a set of diving heuristic settings

Parameters
divesetpointer to the freshly created diveset
heurthe heuristic to which this dive setting belongs
namename for the diveset, or NULL if the name of the heuristic should be used
setglobal SCIP settings
messagehdlrmessage handler
blkmemblock memory for parameter settings
minreldepthminimal relative depth to start diving
maxreldepthmaximal relative depth to start diving
maxlpiterquotmaximal fraction of diving LP iterations compared to node LP iterations
maxdiveubquotmaximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
maxdiveavgquotmaximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
maxdiveubquotnosolmaximal UBQUOT when no solution was found yet (0.0: no limit)
maxdiveavgquotnosolmaximal AVGQUOT when no solution was found yet (0.0: no limit)
lpresolvedomchgquotpercentage of immediate domain changes during probing to trigger LP resolve
lpsolvefreqLP solve frequency for (0: only if enough domain reductions are found by propagation)
maxlpiterofsadditional number of allowed LP iterations
backtrackuse one level of backtracking if infeasibility is encountered?
onlylpbranchcandsshould only LP branching candidates be considered instead of the slower but more general constraint handler diving variable selection?
divetypemaskbit mask that represents the supported dive types by this dive set

Definition at line 176 of file heur.c.

References BMSallocMemory, BMSduplicateMemoryArray, FALSE, heurAddDiveset(), NULL, paramname, SCIP_ALLOC, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_REAL_MAX, SCIPdivesetReset(), SCIPheurGetName(), SCIPsetAddBoolParam(), SCIPsetAddIntParam(), SCIPsetAddRealParam(), SCIPsnprintf(), and TRUE.

Referenced by SCIPcreateDiveset().

void SCIPdivesetUpdateStats ( SCIP_DIVESET diveset,
SCIP_STAT stat,
int  depth,
int  nprobingnodes,
int  nbacktracks,
SCIP_Longint  nsolsfound,
SCIP_Longint  nbestsolsfound,
SCIP_Bool  leavesol 
)

update diveset statistics and global diveset statistics

Parameters
divesetdiveset to be reset
statglobal SCIP statistics
depththe depth reached this time
nprobingnodesthe number of probing nodes explored this time
nbacktracksthe number of backtracks during probing this time
nsolsfoundnumber of new solutions found this time
nbestsolsfoundnumber of new best solutions found this time
leavesolhas the diving heuristic reached a feasible leaf

Definition at line 108 of file heur.c.

References MAX, SCIP_Diveset::maxdepth, SCIP_Diveset::maxsoldepth, MIN, SCIP_Diveset::mindepth, SCIP_Diveset::minsoldepth, SCIP_Diveset::nbestsolsfound, SCIP_Diveset::ncalls, SCIP_Stat::ndivesetcalls, SCIP_Diveset::nsolcalls, SCIP_Diveset::nsolsfound, NULL, SCIP_Diveset::totaldepth, SCIP_Stat::totaldivesetdepth, SCIP_Diveset::totalnbacktracks, SCIP_Diveset::totalnnodes, and SCIP_Diveset::totalsoldepth.

Referenced by SCIPupdateDivesetStats().

SCIP_RETCODE SCIPdivesetGetScore ( SCIP_DIVESET diveset,
SCIP_SET set,
SCIP_DIVETYPE  divetype,
SCIP_VAR divecand,
SCIP_Real  divecandsol,
SCIP_Real  divecandfrac,
SCIP_Real candscore,
SCIP_Bool roundup 
)

get the candidate score and preferred rounding direction for a candidate variable

Parameters
divesetgeneral diving settings
setSCIP settings
divetypethe type of diving that should be applied
divecandthe candidate for which the branching direction is requested
divecandsolLP solution value of the candidate
divecandfracfractionality of the candidate
candscorepointer to store the candidate score
rounduppointer to store whether preferred direction for diving is upwards

Definition at line 599 of file heur.c.

References SCIP_Diveset::divetypemask, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by SCIPgetDivesetScore().

void SCIPdivesetUpdateLPStats ( SCIP_DIVESET diveset,
SCIP_STAT stat,
SCIP_Longint  niterstoadd 
)

update diveset LP statistics, should be called after every LP solved by this diving heuristic

Parameters
divesetdiving settings
statglobal SCIP statistics
niterstoaddadditional number of LP iterations to be added

Definition at line 573 of file heur.c.

References SCIP_Stat::ndivesetlpiterations, SCIP_Stat::ndivesetlps, SCIP_Diveset::nlpiterations, and SCIP_Diveset::nlps.

Referenced by SCIPupdateDivesetLPStats().

SCIP_RETCODE SCIPheurCopyInclude ( SCIP_HEUR heur,
SCIP_SET set 
)

copies the given primal heuristic to a new scip

Parameters
heurprimal heuristic
setSCIP_SET of SCIP to copy to

Definition at line 624 of file heur.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and SCIPheurGetName().

Referenced by SCIPsetCopyPlugins().

SCIP_RETCODE SCIPheurCreate ( SCIP_HEUR **  heur,
SCIP_SET set,
SCIP_MESSAGEHDLR messagehdlr,
BMS_BLKMEM blkmem,
const char *  name,
const char *  desc,
char  dispchar,
int  priority,
int  freq,
int  freqofs,
int  maxdepth,
unsigned int  timingmask,
SCIP_Bool  usessubscip,
SCIP_DECL_HEURCOPY((*heurcopy))  ,
SCIP_DECL_HEURFREE((*heurfree))  ,
SCIP_DECL_HEURINIT((*heurinit))  ,
SCIP_DECL_HEUREXIT((*heurexit))  ,
SCIP_DECL_HEURINITSOL((*heurinitsol))  ,
SCIP_DECL_HEUREXITSOL((*heurexitsol))  ,
SCIP_DECL_HEUREXEC((*heurexec))  ,
SCIP_HEURDATA heurdata 
)

creates a primal heuristic

Parameters
heurpointer to primal heuristic data structure
setglobal SCIP settings
messagehdlrmessage handler
blkmemblock memory for parameter settings
namename of primal heuristic
descdescription of primal heuristic
dispchardisplay character of primal heuristic
prioritypriority of the primal heuristic
freqfrequency for calling primal heuristic
freqofsfrequency offset for calling primal heuristic
maxdepthmaximal depth level to call heuristic at (-1: no limit)
timingmaskpositions in the node solving loop where heuristic should be executed
usessubscipdoes the heuristic use a secondary SCIP instance?
heurdataprimal heuristic data

Definition at line 643 of file heur.c.

References BMSallocMemory, BMSduplicateMemoryArray, FALSE, NULL, paramname, SCIP_ALLOC, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPclockCreate(), SCIPsetAddIntParam(), SCIPsnprintf(), and TRUE.

Referenced by SCIPincludeHeur(), and SCIPincludeHeurBasic().

SCIP_RETCODE SCIPheurFree ( SCIP_HEUR **  heur,
SCIP_SET set 
)

calls destructor and frees memory of primal heuristic

Parameters
heurpointer to primal heuristic data structure
setglobal SCIP settings

Definition at line 728 of file heur.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, divesetFree(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPclockFree().

SCIP_RETCODE SCIPheurExit ( SCIP_HEUR heur,
SCIP_SET set 
)

calls exit method of primal heuristic

Parameters
heurprimal heuristic
setglobal SCIP settings

Definition at line 812 of file heur.c.

References FALSE, SCIP_Heur::initialized, SCIP_Heur::name, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIP_Heur::setuptime.

Referenced by SCIPsetExitPlugins().

SCIP_RETCODE SCIPheurInitsol ( SCIP_HEUR heur,
SCIP_SET set 
)

informs primal heuristic that the branch and bound process is being started

Parameters
heurprimal heuristic
setglobal SCIP settings

Definition at line 842 of file heur.c.

References SCIP_Heur::delaypos, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Heur::setuptime.

Referenced by SCIPsetExitprePlugins().

SCIP_RETCODE SCIPheurExitsol ( SCIP_HEUR heur,
SCIP_SET set 
)

informs primal heuristic that the branch and bound process data is being freed

Parameters
heurprimal heuristic
setglobal SCIP settings

Definition at line 872 of file heur.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Heur::setuptime.

Referenced by SCIPsetInitsolPlugins().

SCIP_Bool SCIPheurShouldBeExecuted ( SCIP_HEUR heur,
int  depth,
int  lpstateforkdepth,
SCIP_HEURTIMING  heurtiming,
SCIP_Bool delayed 
)

should the heuristic be executed at the given depth, frequency, timing, ...

Parameters
heurprimal heuristic
depthdepth of current node
lpstateforkdepthdepth of the last node with solved LP
heurtimingcurrent point in the node solving process
delayedpointer to store whether the heuristic should be delayed

Definition at line 896 of file heur.c.

References SCIP_Heur::delaypos, FALSE, SCIP_Heur::freq, SCIP_Heur::freqofs, SCIP_Heur::maxdepth, SCIP_Bool, SCIP_HEURTIMING_AFTERLPNODE, SCIP_HEURTIMING_AFTERLPPLUNGE, SCIP_HEURTIMING_AFTERPSEUDONODE, SCIP_HEURTIMING_AFTERPSEUDOPLUNGE, SCIP_HEURTIMING_BEFOREPRESOL, SCIP_HEURTIMING_DURINGPRESOLLOOP, SCIP_Heur::timingmask, and TRUE.

Referenced by SCIPheurExec(), and SCIPprimalHeuristics().

SCIP_RETCODE SCIPheurExec ( SCIP_HEUR heur,
SCIP_SET set,
SCIP_PRIMAL primal,
int  depth,
int  lpstateforkdepth,
SCIP_HEURTIMING  heurtiming,
SCIP_Bool  nodeinfeasible,
int *  ndelayedheurs,
SCIP_RESULT result 
)

calls execution method of primal heuristic

Parameters
heurprimal heuristic
setglobal SCIP settings
primalprimal data
depthdepth of current node
lpstateforkdepthdepth of the last node with solved LP
heurtimingcurrent point in the node solving process
nodeinfeasiblewas the current node already detected to be infeasible?
ndelayedheurspointer to count the number of delayed heuristics
resultpointer to store the result of the callback method

Definition at line 958 of file heur.c.

References SCIP_Heur::delaypos, FALSE, SCIP_Heur::freq, SCIP_Heur::freqofs, SCIP_Heur::heurclock, SCIP_Heur::maxdepth, SCIP_Heur::name, SCIP_Primal::nbestsolsfound, SCIP_Heur::nbestsolsfound, SCIP_Heur::ncalls, SCIP_Primal::nsolsfound, SCIP_Heur::nsolsfound, NULL, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_HEURTIMING_BEFOREPRESOL, SCIP_HEURTIMING_DURINGPRESOLLOOP, SCIP_INVALIDRESULT, SCIP_Longint, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPdebugMessage, SCIPerrorMessage, and SCIPheurShouldBeExecuted().

Referenced by SCIPprimalHeuristics().

void SCIPheurSetPriority ( SCIP_HEUR heur,
SCIP_SET set,
int  priority 
)

sets priority of primal heuristic

Parameters
heurprimal heuristic
setglobal SCIP settings
prioritynew priority of the primal heuristic

Definition at line 1218 of file heur.c.

References FALSE, NULL, and SCIP_Heur::priority.

Referenced by SCIPsetHeurPriority().

void SCIPheurSetCopy ( SCIP_HEUR heur,
SCIP_DECL_HEURCOPY((*heurcopy))   
)

sets copy callback of primal heuristic

Parameters
heurprimal heuristic

Definition at line 1081 of file heur.c.

References NULL.

Referenced by SCIPsetHeurCopy().

void SCIPheurSetFree ( SCIP_HEUR heur,
SCIP_DECL_HEURFREE((*heurfree))   
)

sets destructor callback of primal heuristic

Parameters
heurprimal heuristic

Definition at line 1092 of file heur.c.

References NULL.

Referenced by SCIPsetHeurFree().

void SCIPheurSetInit ( SCIP_HEUR heur,
SCIP_DECL_HEURINIT((*heurinit))   
)

sets initialization callback of primal heuristic

Parameters
heurprimal heuristic

Definition at line 1103 of file heur.c.

References NULL.

Referenced by SCIPsetHeurInit().

void SCIPheurSetExit ( SCIP_HEUR heur,
SCIP_DECL_HEUREXIT((*heurexit))   
)

sets deinitialization callback of primal heuristic

Parameters
heurprimal heuristic

Definition at line 1114 of file heur.c.

References NULL.

Referenced by SCIPsetHeurExit().

void SCIPheurSetInitsol ( SCIP_HEUR heur,
SCIP_DECL_HEURINITSOL((*heurinitsol))   
)

sets solving process initialization callback of primal heuristic

Parameters
heurprimal heuristic

Definition at line 1125 of file heur.c.

References NULL.

Referenced by SCIPsetHeurInitsol().

void SCIPheurSetExitsol ( SCIP_HEUR heur,
SCIP_DECL_HEUREXITSOL((*heurexitsol))   
)

sets solving process deinitialization callback of primal heuristic

Parameters
heurprimal heuristic

Definition at line 1136 of file heur.c.

References NULL.

Referenced by SCIPsetHeurExitsol().

void SCIPheurEnableOrDisableClocks ( SCIP_HEUR heur,
SCIP_Bool  enable 
)

enables or disables all clocks of heur, depending on the value of the flag

Parameters
heurthe heuristic for which all clocks should be enabled or disabled
enableshould the clocks of the heuristic be enabled?

Definition at line 1313 of file heur.c.

References SCIP_Heur::heurclock, NULL, SCIPclockEnableOrDisable(), and SCIP_Heur::setuptime.

Referenced by SCIPsetSetReoptimizationParams().