Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Adaptive heuristic to schedule LNS and diving heuristics.

Author
Gregor Hendel
Antonia Chmiela

Definition in file heur_scheduler.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heur_scheduler.h"
#include "scip/heuristics.h"
#include "scip/pub_bandit_epsgreedy.h"
#include "scip/pub_bandit_exp3.h"
#include "scip/pub_bandit_exp3ix.h"
#include "scip/pub_bandit.h"
#include "scip/pub_bandit_ucb.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_select.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_bandit.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_table.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>
#include <strings.h>

Go to the source code of this file.

Data Structures

struct  Heur_Stats
 
struct  NH_FixingRate
 
struct  SolveFreq
 
struct  Nh
 
struct  Diving_Heur
 
struct  data_mutation
 
struct  data_crossover
 
struct  data_dins
 
struct  data_trustregion
 
struct  SolveLimits
 
struct  VarPrio
 

Macros

#define HEUR_NAME   "scheduler"
 
#define HEUR_DESC   "Adaptive heuristic to schedule LNS and diving heuristics"
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS
 
#define HEUR_PRIORITY   -30000
 
#define HEUR_FREQ   -1
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#define NNEIGHBORHOODS   9
 
#define DIVINGHEURS_INITIALSIZE   10
 
#define DEFAULT_NODESQUOT   0.1
 
#define DEFAULT_NODESQUOTMIN   0.0
 
#define DEFAULT_NODESOFFSET   500LL
 
#define DEFAULT_NSOLSLIM   3
 
#define DEFAULT_MINNODES   50LL
 
#define DEFAULT_MAXNODES   500LL
 
#define DEFAULT_WAITINGNODES   0LL
 
#define DEFAULT_INITLNSNODELIMIT   50
 
#define DEFAULT_INITDIVINGNODELIMIT   500LL
 
#define DEFAULT_TARGETNODEFACTOR   1.05
 
#define LRATEMIN   0.01
 
#define LPLIMFAC   4.0
 
#define DEFAULT_INITDURINGROOT   FALSE
 
#define DEFAULT_MAXCALLSSAMESOL   -1
 
#define DEFAULT_HEURTIMELIMIT   60.0
 
#define DEFAULT_BESTSOLWEIGHT   1
 
#define DEFAULT_BANDITALGO   'i'
 
#define DEFAULT_RESETWEIGHTS   FALSE
 
#define DEFAULT_SUBSCIPRANDSEEDS   FALSE
 
#define DEFAULT_FIXTOL   0.1
 
#define DEFAULT_UNFIXTOL   0.1
 
#define DEFAULT_BETA   0.0
 
#define DEFAULT_NSELECTIONS   5
 
#define DEFAULT_USEREDCOST   TRUE
 
#define DEFAULT_USEPSCOST   TRUE
 
#define DEFAULT_USEDISTANCES   TRUE
 
#define DEFAULT_USELOCALREDCOST   FALSE
 
#define DEFAULT_EFFORTREWARDWEIGHT   0.2
 
#define DEFAULT_SOLREWARDWEIGHT   0.3
 
#define DEFAULT_QUALREWARDWEIGHT   0.3
 
#define DEFAULT_CONFLICTREWARDWEIGHT   0.2
 
#define DEFAULT_EPS   0.4685844
 
#define DEFAULT_ALPHA   0.0016
 
#define DEFAULT_GAMMA   0.07041455
 
#define SOLVEFREQ_DECAY   0.75
 
#define SOLVEFREQ_STARTINC   0.2
 
#define MAXSOLVEFREQ   0.3
 
#define MINSOLVEFREQ   0.05
 
#define FIXINGRATE_DECAY   0.75
 
#define FIXINGRATE_STARTINC   0.2
 
#define DEFAULT_USESUBSCIPHEURS   FALSE
 
#define DEFAULT_COPYCUTS   FALSE
 
#define DEFAULT_SEED   113
 
#define MUTATIONSEED   121
 
#define CROSSOVERSEED   321
 
#define DEFAULT_MINFIXINGRATE_RENS   0.3
 
#define DEFAULT_MAXFIXINGRATE_RENS   0.9
 
#define DEFAULT_ACTIVE_RENS   TRUE
 
#define DEFAULT_PRIORITY_RENS   -1100000
 
#define DEFAULT_MINFIXINGRATE_RINS   0.3
 
#define DEFAULT_MAXFIXINGRATE_RINS   0.9
 
#define DEFAULT_ACTIVE_RINS   TRUE
 
#define DEFAULT_PRIORITY_RINS   -1101000
 
#define DEFAULT_MINFIXINGRATE_MUTATION   0.3
 
#define DEFAULT_MAXFIXINGRATE_MUTATION   0.9
 
#define DEFAULT_ACTIVE_MUTATION   TRUE
 
#define DEFAULT_PRIORITY_MUTATION   -1103010
 
#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING   0.3
 
#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING   0.9
 
#define DEFAULT_ACTIVE_LOCALBRANCHING   TRUE
 
#define DEFAULT_PRIORITY_LOCALBRANCHING   -1102000
 
#define DEFAULT_MINFIXINGRATE_PROXIMITY   0.3
 
#define DEFAULT_MAXFIXINGRATE_PROXIMITY   0.9
 
#define DEFAULT_ACTIVE_PROXIMITY   TRUE
 
#define DEFAULT_PRIORITY_PROXIMITY   -2000000
 
#define DEFAULT_MINFIXINGRATE_CROSSOVER   0.3
 
#define DEFAULT_MAXFIXINGRATE_CROSSOVER   0.9
 
#define DEFAULT_ACTIVE_CROSSOVER   TRUE
 
#define DEFAULT_PRIORITY_CROSSOVER   -1104000
 
#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE   0.3
 
#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE   0.9
 
#define DEFAULT_ACTIVE_ZEROOBJECTIVE   TRUE
 
#define DEFAULT_PRIORITY_ZEROOBJECTIVE   100
 
#define DEFAULT_MINFIXINGRATE_DINS   0.3
 
#define DEFAULT_MAXFIXINGRATE_DINS   0.9
 
#define DEFAULT_ACTIVE_DINS   TRUE
 
#define DEFAULT_PRIORITY_DINS   -1105000
 
#define DEFAULT_MINFIXINGRATE_TRUSTREGION   0.3
 
#define DEFAULT_MAXFIXINGRATE_TRUSTREGION   0.9
 
#define DEFAULT_ACTIVE_TRUSTREGION   FALSE
 
#define DEFAULT_PRIORITY_TRUSTREGION   -1102010
 
#define DEFAULT_NSOLS_CROSSOVER   2
 
#define DEFAULT_NPOOLSOLS_DINS   5
 
#define DEFAULT_VIOLPENALTY_TRUSTREGION   100.0
 
#define EVENTHDLR_NAME   "Scheduler"
 
#define EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"
 
#define SCIP_EVENTTYPE_SCHEDULER   (SCIP_EVENTTYPE_LPSOLVED | SCIP_EVENTTYPE_SOLFOUND | SCIP_EVENTTYPE_BESTSOLFOUND)
 
#define TABLE_NAME_NEIGHBORHOOD   "scheduler"
 
#define TABLE_DESC_NEIGHBORHOOD   "scheduler heuristics statistics"
 
#define TABLE_POSITION_NEIGHBORHOOD   12500
 
#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD   SCIP_STAGE_TRANSFORMED
 
#define DECL_VARFIXINGS(x)
 
#define DECL_CHANGESUBSCIP(x)
 
#define DECL_NHINIT(x)
 
#define DECL_NHEXIT(x)
 
#define DECL_NHFREE(x)
 
#define DECL_NHREFSOL(x)
 
#define DECL_NHDEACTIVATE(x)
 
#define NHISTENTRIES   7
 

Typedefs

typedef struct data_crossover DATA_CROSSOVER
 
typedef struct data_mutation DATA_MUTATION
 
typedef struct data_dins DATA_DINS
 
typedef struct data_trustregion DATA_TRUSTREGION
 
typedef struct NH_FixingRate NH_FIXINGRATE
 
typedef struct SolveFreq SOLVEFREQ
 
typedef struct Heur_Stats HEUR_STATS
 
typedef struct Nh NH
 
typedef struct Diving_Heur DIVING_HEUR
 
typedef struct VarPrio VARPRIO
 
typedef enum HistIndex HISTINDEX
 
typedef struct SolveLimits SOLVELIMITS
 

Enumerations

enum  HistIndex {
  HIDX_OPT = 0,
  HIDX_USR = 1,
  HIDX_NODELIM = 2,
  HIDX_STALLNODE = 3,
  HIDX_INFEAS = 4,
  HIDX_SOLLIM = 5,
  HIDX_OTHER = 6,
  HIDX_OPT = 0,
  HIDX_USR = 1,
  HIDX_NODELIM = 2,
  HIDX_STALLNODE = 3,
  HIDX_INFEAS = 4,
  HIDX_SOLLIM = 5,
  HIDX_OTHER = 6
}
 

Functions

static SCIP_RETCODE resetFixingRate (SCIP *scip, NH_FIXINGRATE *fixingrate)
 
static void updateFixingRateIncrement (NH_FIXINGRATE *fx)
 
static void increaseFixingRate (NH_FIXINGRATE *fx)
 
static void decreaseFixingRate (NH_FIXINGRATE *fx)
 
static void updateFixingRate (NH *neighborhood, SCIP_STATUS subscipstatus, HEUR_STATS *runstats)
 
static void resetCurrentNeighborhood (SCIP_HEURDATA *heurdata)
 
static void resetTargetNodeLimit (SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE heurStatsReset (SCIP *scip, HEUR_STATS *stats, SCIP_Bool usediving)
 
static SCIP_RETCODE schedulerIncludeNeighborhood (SCIP *scip, SCIP_HEURDATA *heurdata, NH **neighborhood, const char *name, SCIP_Real minfixingrate, SCIP_Real maxfixingrate, SCIP_Bool active, int priority, DECL_VARFIXINGS((*varfixings)), DECL_CHANGESUBSCIP((*changesubscip)), DECL_NHINIT((*nhinit)), DECL_NHEXIT((*nhexit)), DECL_NHFREE((*nhfree)), DECL_NHREFSOL((*nhrefsol)), DECL_NHDEACTIVATE((*nhdeactivate)))
 
static SCIP_RETCODE schedulerFreeNeighborhood (SCIP *scip, NH **neighborhood)
 
static SCIP_RETCODE neighborhoodInit (SCIP *scip, NH *neighborhood)
 
static SCIP_RETCODE neighborhoodExit (SCIP *scip, NH *neighborhood)
 
static SCIP_RETCODE transferSolution (SCIP *subscip, SCIP_EVENTDATA *eventdata)
 
static SCIP_RETCODE schedulerFreeDivingHeur (SCIP *scip, DIVING_HEUR **divingheur)
 
static SCIP_DECL_EVENTEXEC (eventExecScheduler)
 
static void initRunStats (SCIP *scip, HEUR_STATS *stats)
 
static void updateRunStats (HEUR_STATS *stats, SCIP *subscip)
 
static int getHistIndex (SCIP_STATUS subscipstatus)
 
static void printNeighborhoodStatistics (SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
 
static void printDivingHeurStatistics (SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
 
static void updateHeurStatsDiving (HEUR_STATS *runstats, DIVING_HEUR *divingheur)
 
static void updateHeurStatsLNS (HEUR_STATS *runstats, NH *neighborhood, SCIP_STATUS *subscipstatus)
 
static SCIP_DECL_SORTINDCOMP (sortIndCompScheduler)
 
static SCIP_Real getVariableRedcostScore (SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval, SCIP_Bool uselocalredcost)
 
static SCIP_Real getVariablePscostScore (SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval, SCIP_Bool uselocallpsol)
 
static void tryAdd2variableBuffer (SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_Bool integer)
 
static SCIP_RETCODE LNSFixMoreVariables (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *refsol, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, int ntargetfixings, SCIP_Bool *success)
 
static SCIP_RETCODE createBandit (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *priorities, unsigned int initseed)
 
static SCIP_DECL_HEURCOPY (heurCopyScheduler)
 
static SCIP_RETCODE neighborhoodGetRefsol (SCIP *scip, NH *neighborhood, SCIP_SOL **solptr)
 
static SCIP_RETCODE LNSUnfixVariables (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, int ntargetfixings, SCIP_Bool *success)
 
static SCIP_RETCODE neighborhoodFixVariables (SCIP *scip, SCIP_HEURDATA *heurdata, NH *neighborhood, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_RESULT *result)
 
static SCIP_RETCODE neighborhoodChangeSubscip (SCIP *sourcescip, SCIP *targetscip, NH *neighborhood, SCIP_VAR **targetvars, int *ndomchgs, int *nchgobjs, int *naddedconss, SCIP_Bool *success)
 
static SCIP_RETCODE setLimits (SCIP *subscip, SOLVELIMITS *solvelimits)
 
static SCIP_RETCODE determineLimits (SCIP *scip, SCIP_HEUR *heur, int selection, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
 
static SCIP_Real getReward (SCIP *scip, SCIP_HEURDATA *heurdata, int selection, HEUR_STATS *runstats, SCIP_STATUS subscipstatus)
 
static SCIP_RETCODE setupSubScip (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SOLVELIMITS *solvelimits, SCIP_HEUR *heur, SCIP_Bool objchgd)
 
static void initSolveFreq (SOLVEFREQ *solvefreqdata)
 
static void updateSolveFreqIncrement (SOLVEFREQ *solvefreqdata)
 
static void increaseSolveFreq (SOLVEFREQ *solvefreqdata)
 
static void decreaseSolveFreq (SOLVEFREQ *solvefreqdata)
 
static void updateSolveFreq (DIVING_HEUR *divingheur, HEUR_STATS *stats)
 
static SCIP_RETCODE includeDivingHeurs (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE selectHeuristic (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection)
 
static SCIP_RETCODE updateSelectionStrategy (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real reward, int selection)
 
static SCIP_RETCODE executeDivingHeuristic (SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_RESULT *result)
 
static SCIP_RETCODE executeLNSHeuristic (SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_STATUS *subscipstatus, SCIP_RESULT *result)
 
static SCIP_RETCODE executeHeuristic (SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_STATUS *subscipstatus, SCIP_RESULT *result)
 
static SCIP_RETCODE reinitBandit (SCIP *scip, SCIP_HEURDATA *heurdata, int nactions)
 
static SCIP_RETCODE initRest (SCIP *scip, SCIP_HEUR *heur)
 
static SCIP_DECL_HEUREXEC (heurExecScheduler)
 
static DECL_VARFIXINGS (varFixingsRens)
 
static DECL_CHANGESUBSCIP (changeSubscipRens)
 
static SCIP_RETCODE fixMatchingSolutionValues (SCIP *scip, SCIP_SOL **sols, int nsols, SCIP_VAR **vars, int nvars, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings)
 
static DECL_VARFIXINGS (varFixingsRins)
 
static DECL_NHINIT (nhInitCrossover)
 
static DECL_NHEXIT (nhExitCrossover)
 
static DECL_NHFREE (nhFreeCrossover)
 
static DECL_VARFIXINGS (varFixingsCrossover)
 
static DECL_NHREFSOL (nhRefsolCrossover)
 
static DECL_NHINIT (nhInitMutation)
 
static DECL_NHEXIT (nhExitMutation)
 
static DECL_VARFIXINGS (varFixingsMutation)
 
static SCIP_RETCODE addLocalBranchingConstraint (SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, int distance, SCIP_Bool *success, int *naddedconss)
 
static DECL_CHANGESUBSCIP (changeSubscipLocalbranching)
 
static DECL_CHANGESUBSCIP (changeSubscipProximity)
 
static DECL_CHANGESUBSCIP (changeSubscipZeroobjective)
 
static void computeIntegerVariableBoundsDins (SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
 
static DECL_VARFIXINGS (varFixingsDins)
 
static DECL_CHANGESUBSCIP (changeSubscipDins)
 
static DECL_NHFREE (nhFreeDins)
 
static DECL_NHFREE (nhFreeTrustregion)
 
static DECL_CHANGESUBSCIP (changeSubscipTrustregion)
 
static DECL_NHREFSOL (nhRefsolIncumbent)
 
static DECL_NHDEACTIVATE (nhDeactivateDiscreteVars)
 
static DECL_NHDEACTIVATE (nhDeactivateBinVars)
 
static DECL_NHDEACTIVATE (nhDeactivateObjVars)
 
static SCIP_RETCODE includeNeighborhoods (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_DECL_HEURINIT (heurInitScheduler)
 
static SCIP_DECL_HEURINITSOL (heurInitsolScheduler)
 
static SCIP_DECL_HEUREXIT (heurExitScheduler)
 
static SCIP_DECL_HEURFREE (heurFreeScheduler)
 
static SCIP_DECL_TABLEOUTPUT (tableOutputNeighborhood)
 
SCIP_RETCODE SCIPincludeHeurScheduler (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "scheduler"

◆ HEUR_DESC

#define HEUR_DESC   "Adaptive heuristic to schedule LNS and diving heuristics"

Definition at line 80 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS

Definition at line 81 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -30000

Definition at line 82 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 83 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 84 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 85 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 86 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 87 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ NNEIGHBORHOODS

#define NNEIGHBORHOODS   9

Definition at line 89 of file heur_scheduler.c.

Referenced by SCIP_DECL_HEURFREE(), and SCIPincludeHeurScheduler().

◆ DIVINGHEURS_INITIALSIZE

#define DIVINGHEURS_INITIALSIZE   10

Definition at line 90 of file heur_scheduler.c.

Referenced by includeDivingHeurs().

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

Definition at line 95 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_NODESQUOTMIN

#define DEFAULT_NODESQUOTMIN   0.0

Definition at line 96 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_NODESOFFSET

#define DEFAULT_NODESOFFSET   500LL

Definition at line 97 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_NSOLSLIM

#define DEFAULT_NSOLSLIM   3

Definition at line 98 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   50LL

Definition at line 99 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   500LL

Definition at line 100 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_WAITINGNODES

#define DEFAULT_WAITINGNODES   0LL

number of nodes since last incumbent solution that the heuristic should wait

Definition at line 101 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_INITLNSNODELIMIT

#define DEFAULT_INITLNSNODELIMIT   50

Definition at line 102 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_INITDIVINGNODELIMIT

#define DEFAULT_INITDIVINGNODELIMIT   500LL

Definition at line 103 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_TARGETNODEFACTOR

#define DEFAULT_TARGETNODEFACTOR   1.05

Definition at line 104 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ LRATEMIN

#define LRATEMIN   0.01

lower bound for learning rate for target nodes and minimum improvement

Definition at line 105 of file heur_scheduler.c.

Referenced by updateFixingRateIncrement(), and updateSolveFreqIncrement().

◆ LPLIMFAC

#define LPLIMFAC   4.0

Definition at line 106 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_INITDURINGROOT

#define DEFAULT_INITDURINGROOT   FALSE

Definition at line 107 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_MAXCALLSSAMESOL

#define DEFAULT_MAXCALLSSAMESOL   -1

number of allowed executions of the heuristic on the same incumbent solution

Definition at line 108 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_HEURTIMELIMIT

#define DEFAULT_HEURTIMELIMIT   60.0

time limit for a single heuristic run

Definition at line 109 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_BESTSOLWEIGHT

#define DEFAULT_BESTSOLWEIGHT   1

Definition at line 114 of file heur_scheduler.c.

Referenced by updateHeurStatsDiving(), and updateHeurStatsLNS().

◆ DEFAULT_BANDITALGO

#define DEFAULT_BANDITALGO   'i'

the default bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy, exp.3-(i)x

Definition at line 115 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_RESETWEIGHTS

#define DEFAULT_RESETWEIGHTS   FALSE

should the bandit algorithms be reset when a new problem is read?

Definition at line 116 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_SUBSCIPRANDSEEDS

#define DEFAULT_SUBSCIPRANDSEEDS   FALSE

should random seeds of sub-SCIPs be altered to increase diversification?

Definition at line 117 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_FIXTOL

#define DEFAULT_FIXTOL   0.1

tolerance by which the fixing rate may be missed without generic fixing

Definition at line 118 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_UNFIXTOL

#define DEFAULT_UNFIXTOL   0.1

tolerance by which the fixing rate may be exceeded without generic unfixing

Definition at line 119 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_BETA

#define DEFAULT_BETA   0.0

default reward offset between 0 and 1 at every observation for exp3

Definition at line 120 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_NSELECTIONS

#define DEFAULT_NSELECTIONS   5

number of heuristics picked by the scheduler in one call (-1: number of controlled heuristics, 0: until new incumbent is found)

Definition at line 121 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_USEREDCOST

#define DEFAULT_USEREDCOST   TRUE

should reduced cost scores be used for variable priorization?

Definition at line 126 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_USEPSCOST

#define DEFAULT_USEPSCOST   TRUE

should pseudo cost scores be used for variable priorization?

Definition at line 127 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_USEDISTANCES

#define DEFAULT_USEDISTANCES   TRUE

should distances from fixed variables be used for variable priorization

Definition at line 128 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_USELOCALREDCOST

#define DEFAULT_USELOCALREDCOST   FALSE

should local reduced costs be used for generic (un)fixing?

Definition at line 129 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_EFFORTREWARDWEIGHT

#define DEFAULT_EFFORTREWARDWEIGHT   0.2

Definition at line 134 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_SOLREWARDWEIGHT

#define DEFAULT_SOLREWARDWEIGHT   0.3

Definition at line 135 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_QUALREWARDWEIGHT

#define DEFAULT_QUALREWARDWEIGHT   0.3

Definition at line 136 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_CONFLICTREWARDWEIGHT

#define DEFAULT_CONFLICTREWARDWEIGHT   0.2

Definition at line 137 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_EPS

#define DEFAULT_EPS   0.4685844

increase exploration in epsilon-greedy bandit algorithm

Definition at line 143 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_ALPHA

#define DEFAULT_ALPHA   0.0016

parameter to increase the confidence width in UCB

Definition at line 144 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_GAMMA

#define DEFAULT_GAMMA   0.07041455

default weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3

Definition at line 145 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ SOLVEFREQ_DECAY

#define SOLVEFREQ_DECAY   0.75

geometric decay for solving freq adjustments

Definition at line 150 of file heur_scheduler.c.

Referenced by updateSolveFreqIncrement().

◆ SOLVEFREQ_STARTINC

#define SOLVEFREQ_STARTINC   0.2

initial increment value for solving frequency

Definition at line 151 of file heur_scheduler.c.

Referenced by initSolveFreq().

◆ MAXSOLVEFREQ

#define MAXSOLVEFREQ   0.3

maximal solving frequency

Definition at line 152 of file heur_scheduler.c.

Referenced by initSolveFreq().

◆ MINSOLVEFREQ

#define MINSOLVEFREQ   0.05

minimal solving frequency

Definition at line 153 of file heur_scheduler.c.

Referenced by initSolveFreq().

◆ FIXINGRATE_DECAY

#define FIXINGRATE_DECAY   0.75

geometric decay for fixing rate adjustments

Definition at line 158 of file heur_scheduler.c.

Referenced by updateFixingRateIncrement().

◆ FIXINGRATE_STARTINC

#define FIXINGRATE_STARTINC   0.2

initial increment value for fixing rate

Definition at line 159 of file heur_scheduler.c.

Referenced by resetFixingRate().

◆ DEFAULT_USESUBSCIPHEURS

#define DEFAULT_USESUBSCIPHEURS   FALSE

should the heuristic activate other sub-SCIP heuristics during its search?

Definition at line 160 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_COPYCUTS

#define DEFAULT_COPYCUTS   FALSE

should cutting planes be copied to the sub-SCIP?

Definition at line 161 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DEFAULT_SEED

#define DEFAULT_SEED   113

Definition at line 164 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ MUTATIONSEED

#define MUTATIONSEED   121

Definition at line 165 of file heur_scheduler.c.

Referenced by DECL_NHINIT().

◆ CROSSOVERSEED

#define CROSSOVERSEED   321

Definition at line 166 of file heur_scheduler.c.

Referenced by DECL_NHINIT().

◆ DEFAULT_MINFIXINGRATE_RENS

#define DEFAULT_MINFIXINGRATE_RENS   0.3

Definition at line 169 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_RENS

#define DEFAULT_MAXFIXINGRATE_RENS   0.9

Definition at line 170 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_RENS

#define DEFAULT_ACTIVE_RENS   TRUE

Definition at line 171 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_RENS

#define DEFAULT_PRIORITY_RENS   -1100000

Definition at line 173 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_RINS

#define DEFAULT_MINFIXINGRATE_RINS   0.3

Definition at line 175 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_RINS

#define DEFAULT_MAXFIXINGRATE_RINS   0.9

Definition at line 176 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_RINS

#define DEFAULT_ACTIVE_RINS   TRUE

Definition at line 177 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_RINS

#define DEFAULT_PRIORITY_RINS   -1101000

Definition at line 179 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_MUTATION

#define DEFAULT_MINFIXINGRATE_MUTATION   0.3

Definition at line 181 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_MUTATION

#define DEFAULT_MAXFIXINGRATE_MUTATION   0.9

Definition at line 182 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_MUTATION

#define DEFAULT_ACTIVE_MUTATION   TRUE

Definition at line 183 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_MUTATION

#define DEFAULT_PRIORITY_MUTATION   -1103010

Definition at line 185 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_LOCALBRANCHING

#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING   0.3

Definition at line 187 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_LOCALBRANCHING

#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING   0.9

Definition at line 188 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_LOCALBRANCHING

#define DEFAULT_ACTIVE_LOCALBRANCHING   TRUE

Definition at line 189 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_LOCALBRANCHING

#define DEFAULT_PRIORITY_LOCALBRANCHING   -1102000

Definition at line 191 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_PROXIMITY

#define DEFAULT_MINFIXINGRATE_PROXIMITY   0.3

Definition at line 193 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_PROXIMITY

#define DEFAULT_MAXFIXINGRATE_PROXIMITY   0.9

Definition at line 194 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_PROXIMITY

#define DEFAULT_ACTIVE_PROXIMITY   TRUE

Definition at line 195 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_PROXIMITY

#define DEFAULT_PRIORITY_PROXIMITY   -2000000

Definition at line 197 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_CROSSOVER

#define DEFAULT_MINFIXINGRATE_CROSSOVER   0.3

Definition at line 199 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_CROSSOVER

#define DEFAULT_MAXFIXINGRATE_CROSSOVER   0.9

Definition at line 200 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_CROSSOVER

#define DEFAULT_ACTIVE_CROSSOVER   TRUE

Definition at line 201 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_CROSSOVER

#define DEFAULT_PRIORITY_CROSSOVER   -1104000

Definition at line 203 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE

#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE   0.3

Definition at line 205 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE

#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE   0.9

Definition at line 206 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_ZEROOBJECTIVE

#define DEFAULT_ACTIVE_ZEROOBJECTIVE   TRUE

Definition at line 207 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_ZEROOBJECTIVE

#define DEFAULT_PRIORITY_ZEROOBJECTIVE   100

Definition at line 209 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_DINS

#define DEFAULT_MINFIXINGRATE_DINS   0.3

Definition at line 211 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_DINS

#define DEFAULT_MAXFIXINGRATE_DINS   0.9

Definition at line 212 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_DINS

#define DEFAULT_ACTIVE_DINS   TRUE

Definition at line 213 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_DINS

#define DEFAULT_PRIORITY_DINS   -1105000

Definition at line 215 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_TRUSTREGION

#define DEFAULT_MINFIXINGRATE_TRUSTREGION   0.3

Definition at line 217 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_TRUSTREGION

#define DEFAULT_MAXFIXINGRATE_TRUSTREGION   0.9

Definition at line 218 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_TRUSTREGION

#define DEFAULT_ACTIVE_TRUSTREGION   FALSE

Definition at line 219 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_TRUSTREGION

#define DEFAULT_PRIORITY_TRUSTREGION   -1102010

Definition at line 221 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_NSOLS_CROSSOVER

#define DEFAULT_NSOLS_CROSSOVER   2

parameter for the number of solutions that crossover should combine

Definition at line 224 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_NPOOLSOLS_DINS

#define DEFAULT_NPOOLSOLS_DINS   5

number of pool solutions where binary solution values must agree

Definition at line 225 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_VIOLPENALTY_TRUSTREGION

#define DEFAULT_VIOLPENALTY_TRUSTREGION   100.0

the penalty for violating the trust region

Definition at line 226 of file heur_scheduler.c.

Referenced by includeNeighborhoods().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "Scheduler"

Definition at line 229 of file heur_scheduler.c.

Referenced by executeLNSHeuristic(), and SCIP_DECL_EVENTEXEC().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"

Definition at line 230 of file heur_scheduler.c.

Referenced by executeLNSHeuristic().

◆ SCIP_EVENTTYPE_SCHEDULER

Definition at line 231 of file heur_scheduler.c.

Referenced by executeLNSHeuristic(), and SCIP_DECL_EVENTEXEC().

◆ TABLE_NAME_NEIGHBORHOOD

#define TABLE_NAME_NEIGHBORHOOD   "scheduler"

Definition at line 234 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ TABLE_DESC_NEIGHBORHOOD

#define TABLE_DESC_NEIGHBORHOOD   "scheduler heuristics statistics"

Definition at line 235 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ TABLE_POSITION_NEIGHBORHOOD

#define TABLE_POSITION_NEIGHBORHOOD   12500

the position of the statistics table

Definition at line 236 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ TABLE_EARLIEST_STAGE_NEIGHBORHOOD

#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD   SCIP_STAGE_TRANSFORMED

output of the statistics table is only printed from this stage onwards

Definition at line 237 of file heur_scheduler.c.

Referenced by SCIPincludeHeurScheduler().

◆ DECL_VARFIXINGS

#define DECL_VARFIXINGS (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
NH* neighborhood, /**< neighborhood data structure */ \
SCIP_VAR** varbuf, /**< buffer array to collect variables to fix */\
SCIP_Real* valbuf, /**< buffer array to collect fixing values */ \
int* nfixings, /**< pointer to store the number of fixings */ \
SCIP_RESULT* result /**< result pointer */ \
)
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Definition: heur_alns.c:371
SCIP_VAR ** x
Definition: circlepacking.c:63
#define SCIP_Real
Definition: def.h:173

callback to collect variable fixings of neighborhood

Definition at line 268 of file heur_scheduler.c.

◆ DECL_CHANGESUBSCIP

#define DECL_CHANGESUBSCIP (   x)
Value:
SCIP* sourcescip, /**< source SCIP data structure */\
SCIP* targetscip, /**< target SCIP data structure */\
NH* neighborhood, /**< neighborhood data structure */\
SCIP_VAR** subvars, /**< array of targetscip variables in the same order as the source SCIP variables */\
int* ndomchgs, /**< pointer to store the number of performed domain changes */\
int* nchgobjs, /**< pointer to store the number of changed objective coefficients */ \
int* naddedconss, /**< pointer to store the number of additional constraints */\
SCIP_Bool* success /**< pointer to store if the sub-MIP was successfully adjusted */\
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Definition: heur_alns.c:371
SCIP_VAR ** x
Definition: circlepacking.c:63
#define SCIP_Bool
Definition: def.h:91

callback for subproblem changes other than variable fixings

this callback can be used to further modify the subproblem by changes other than variable fixings. Typical modifications include restrictions of variable domains, the formulation of additional constraints, or changed objective coefficients.

The callback should set the success pointer to indicate whether it was successful with its modifications or not.

Definition at line 285 of file heur_scheduler.c.

◆ DECL_NHINIT

#define DECL_NHINIT (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
NH* neighborhood /**< neighborhood data structure */ \
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Definition: heur_alns.c:371
SCIP_VAR ** x
Definition: circlepacking.c:63

optional initialization callback for neighborhoods when a new problem is read

Definition at line 297 of file heur_scheduler.c.

◆ DECL_NHEXIT

#define DECL_NHEXIT (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
NH* neighborhood /**< neighborhood data structure */ \
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Definition: heur_alns.c:371
SCIP_VAR ** x
Definition: circlepacking.c:63

deinitialization callback for neighborhoods when exiting a problem

Definition at line 303 of file heur_scheduler.c.

◆ DECL_NHFREE

#define DECL_NHFREE (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
NH* neighborhood /**< neighborhood data structure */ \
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Definition: heur_alns.c:371
SCIP_VAR ** x
Definition: circlepacking.c:63

deinitialization callback for neighborhoods before SCIP is freed

Definition at line 309 of file heur_scheduler.c.

◆ DECL_NHREFSOL

#define DECL_NHREFSOL (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
NH* neighborhood, /**< neighborhood data structure */ \
SCIP_SOL** solptr, /**< pointer to store the reference solution */ \
SCIP_RESULT* result /**< pointer to indicate the callback success whether a reference solution is available */ \
)
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Definition: heur_alns.c:371
SCIP_VAR ** x
Definition: circlepacking.c:63

callback function to return a feasible reference solution for further fixings

The reference solution should be stored in the solptr. The result pointer can be used to indicate either

  • SCIP_SUCCESS or
  • SCIP_DIDNOTFIND

Definition at line 322 of file heur_scheduler.c.

◆ DECL_NHDEACTIVATE

#define DECL_NHDEACTIVATE (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
SCIP_Bool* deactivate /**< pointer to store whether the neighborhood should be deactivated (TRUE) for an instance */ \
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_VAR ** x
Definition: circlepacking.c:63
#define SCIP_Bool
Definition: def.h:91

callback function to deactivate neighborhoods on problems where they are irrelevant

Definition at line 330 of file heur_scheduler.c.

◆ NHISTENTRIES

#define NHISTENTRIES   7

Definition at line 347 of file heur_scheduler.c.

Referenced by heurStatsReset(), and printNeighborhoodStatistics().

Typedef Documentation

◆ DATA_CROSSOVER

crossover neighborhood data structure

Definition at line 244 of file heur_scheduler.c.

◆ DATA_MUTATION

typedef struct data_mutation DATA_MUTATION

mutation neighborhood data structure

Definition at line 246 of file heur_scheduler.c.

◆ DATA_DINS

typedef struct data_dins DATA_DINS

dins neighborhood data structure

Definition at line 248 of file heur_scheduler.c.

◆ DATA_TRUSTREGION

trustregion neighborhood data structure

Definition at line 250 of file heur_scheduler.c.

◆ NH_FIXINGRATE

typedef struct NH_FixingRate NH_FIXINGRATE

Definition at line 252 of file heur_scheduler.c.

◆ SOLVEFREQ

typedef struct SolveFreq SOLVEFREQ

fixing rate data structure

Definition at line 254 of file heur_scheduler.c.

◆ HEUR_STATS

typedef struct Heur_Stats HEUR_STATS

diving heuristic solving frequency data structure heuristic statistics data structure

Definition at line 256 of file heur_scheduler.c.

◆ NH

typedef struct Nh NH

neighborhood data structure

Definition at line 258 of file heur_scheduler.c.

◆ DIVING_HEUR

typedef struct Diving_Heur DIVING_HEUR

diving heuristic data structure

Definition at line 260 of file heur_scheduler.c.

◆ VARPRIO

typedef struct VarPrio VARPRIO

Definition at line 265 of file heur_scheduler.c.

◆ HISTINDEX

typedef enum HistIndex HISTINDEX

Definition at line 346 of file heur_scheduler.c.

◆ SOLVELIMITS

typedef struct SolveLimits SOLVELIMITS

Definition at line 544 of file heur_scheduler.c.

Enumeration Type Documentation

◆ HistIndex

enum HistIndex

sub-SCIP status code enumerator

Enumerator
HIDX_OPT 

sub-SCIP was solved to optimality

HIDX_USR 

sub-SCIP was user interrupted

HIDX_NODELIM 

sub-SCIP reached the node limit

HIDX_STALLNODE 

sub-SCIP reached the stall node limit

HIDX_INFEAS 

sub-SCIP was infeasible

HIDX_SOLLIM 

sub-SCIP reached the solution limit

HIDX_OTHER 

sub-SCIP reached none of the above codes

HIDX_OPT 

sub-SCIP was solved to optimality

HIDX_USR 

sub-SCIP was user interrupted

HIDX_NODELIM 

sub-SCIP reached the node limit

HIDX_STALLNODE 

sub-SCIP reached the stall node limit

HIDX_INFEAS 

sub-SCIP was infeasible

HIDX_SOLLIM 

sub-SCIP reached the solution limit

HIDX_OTHER 

sub-SCIP reached none of the above codes

Definition at line 336 of file heur_scheduler.c.

Function Documentation

◆ resetFixingRate()

static SCIP_RETCODE resetFixingRate ( SCIP scip,
NH_FIXINGRATE fixingrate 
)
static

Reset target fixing rate

Parameters
scipSCIP data structure
fixingrateheuristic fixing rate

Definition at line 565 of file heur_scheduler.c.

References FIXINGRATE_STARTINC, NH_FixingRate::increment, NH_FixingRate::maxfixingrate, NULL, SCIP_OKAY, and NH_FixingRate::targetfixingrate.

Referenced by SCIP_DECL_HEURINIT().

◆ updateFixingRateIncrement()

static void updateFixingRateIncrement ( NH_FIXINGRATE fx)
static

update increment for fixing rate

Parameters
fxfixing rate

Definition at line 582 of file heur_scheduler.c.

References FIXINGRATE_DECAY, NH_FixingRate::increment, LRATEMIN, and MAX.

Referenced by updateFixingRate().

◆ increaseFixingRate()

static void increaseFixingRate ( NH_FIXINGRATE fx)
static

increase fixing rate

decrease also the rate by which the target fixing rate is adjusted

Parameters
fxfixing rate

Definition at line 595 of file heur_scheduler.c.

References NH_FixingRate::increment, NH_FixingRate::maxfixingrate, MIN, and NH_FixingRate::targetfixingrate.

Referenced by updateFixingRate().

◆ decreaseFixingRate()

static void decreaseFixingRate ( NH_FIXINGRATE fx)
static

decrease fixing rate

decrease also the rate by which the target fixing rate is adjusted

Parameters
fxfixing rate

Definition at line 608 of file heur_scheduler.c.

References NH_FixingRate::increment, MAX, NH_FixingRate::minfixingrate, and NH_FixingRate::targetfixingrate.

Referenced by updateFixingRate().

◆ updateFixingRate()

◆ resetCurrentNeighborhood()

static void resetCurrentNeighborhood ( SCIP_HEURDATA heurdata)
static

reset the currently active neighborhood

Definition at line 665 of file heur_scheduler.c.

References NULL.

Referenced by executeLNSHeuristic(), and SCIP_DECL_HEURINITSOL().

◆ resetTargetNodeLimit()

static void resetTargetNodeLimit ( SCIP_HEURDATA heurdata)
static

reset target node limit

Parameters
heurdataheuristic data

Definition at line 676 of file heur_scheduler.c.

Referenced by reinitBandit(), and SCIP_DECL_HEURINITSOL().

◆ heurStatsReset()

static SCIP_RETCODE heurStatsReset ( SCIP scip,
HEUR_STATS stats,
SCIP_Bool  usediving 
)
static

◆ schedulerIncludeNeighborhood()

static SCIP_RETCODE schedulerIncludeNeighborhood ( SCIP scip,
SCIP_HEURDATA heurdata,
NH **  neighborhood,
const char *  name,
SCIP_Real  minfixingrate,
SCIP_Real  maxfixingrate,
SCIP_Bool  active,
int  priority,
DECL_VARFIXINGS((*varfixings))  ,
DECL_CHANGESUBSCIP((*changesubscip))  ,
DECL_NHINIT((*nhinit))  ,
DECL_NHEXIT((*nhexit))  ,
DECL_NHFREE((*nhfree))  ,
DECL_NHREFSOL((*nhrefsol))  ,
DECL_NHDEACTIVATE((*nhdeactivate))   
)
static

create a neighborhood of the specified name and include it into the scheduler heuristic

Parameters
scipSCIP data structure
heurdataheuristic data of the scheduler heuristic
neighborhoodpointer to store the neighborhood
namename for this neighborhood
minfixingratedefault value for minfixingrate parameter of this neighborhood
maxfixingratedefault value for maxfixingrate parameter of this neighborhood
activedefault value for active parameter of this neighborhood
prioritypriority for heuristic in rootnode

Definition at line 719 of file heur_scheduler.c.

References BMSduplicateMemoryArray, NULL, paramname, SCIP_ALLOC, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPcreateClock(), SCIPsnprintf(), and TRUE.

Referenced by includeNeighborhoods().

◆ schedulerFreeNeighborhood()

static SCIP_RETCODE schedulerFreeNeighborhood ( SCIP scip,
NH **  neighborhood 
)
static

release all data and free neighborhood

Parameters
scipSCIP data structure
neighborhoodpointer to neighborhood that should be freed

Definition at line 784 of file heur_scheduler.c.

References BMSfreeMemoryArray, Nh::name, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeClock(), NH_Stats::setupclock, and Nh::stats.

Referenced by SCIP_DECL_HEURFREE().

◆ neighborhoodInit()

static SCIP_RETCODE neighborhoodInit ( SCIP scip,
NH neighborhood 
)
static

initialize neighborhood specific data

Parameters
scipSCIP data structure
neighborhoodneighborhood to initialize

Definition at line 815 of file heur_scheduler.c.

References NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by SCIP_DECL_HEURINIT().

◆ neighborhoodExit()

static SCIP_RETCODE neighborhoodExit ( SCIP scip,
NH neighborhood 
)
static

deinitialize neighborhood specific data

Parameters
scipSCIP data structure
neighborhoodneighborhood to initialize

Definition at line 834 of file heur_scheduler.c.

References NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by SCIP_DECL_HEUREXIT().

◆ transferSolution()

static SCIP_RETCODE transferSolution ( SCIP subscip,
SCIP_EVENTDATA eventdata 
)
static

creates a new solution for the original problem by copying the solution of the subproblem

Parameters
subscipSCIP data structure of the subproblem
eventdataevent handler data

Definition at line 852 of file heur_scheduler.c.

References FALSE, Heur_Stats::nbestsolsfound, Heur_Stats::newupperbound, Heur_Stats::nsolsfound, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetBestSol(), SCIPgetUpperbound(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.

Referenced by SCIP_DECL_EVENTEXEC().

◆ schedulerFreeDivingHeur()

static SCIP_RETCODE schedulerFreeDivingHeur ( SCIP scip,
DIVING_HEUR **  divingheur 
)
static

release all data and free diving heuristic

Parameters
scipSCIP data structure
divingheurpointer to diving heuristic that should be freed

Definition at line 903 of file heur_scheduler.c.

References Heur_Stats::execclock, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeClock(), Heur_Stats::setupclock, Diving_Heur::solvefreqdata, and Diving_Heur::stats.

Referenced by SCIP_DECL_HEURFREE().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecScheduler  )
static

◆ initRunStats()

static void initRunStats ( SCIP scip,
HEUR_STATS stats 
)
static

◆ updateRunStats()

static void updateRunStats ( HEUR_STATS stats,
SCIP subscip 
)
static

update run stats after the sub SCIP was solved

Parameters
statsrun statistics
subscipsub-SCIP instance, or NULL

Definition at line 985 of file heur_scheduler.c.

References NULL, SCIPgetNNodes(), SCIPisTransformed(), and Heur_Stats::usednodes.

Referenced by executeLNSHeuristic().

◆ getHistIndex()

static int getHistIndex ( SCIP_STATUS  subscipstatus)
static

◆ printNeighborhoodStatistics()

static void printNeighborhoodStatistics ( SCIP scip,
SCIP_HEURDATA heurdata,
FILE *  file 
)
static

◆ printDivingHeurStatistics()

static void printDivingHeurStatistics ( SCIP scip,
SCIP_HEURDATA heurdata,
FILE *  file 
)
static

◆ updateHeurStatsDiving()

static void updateHeurStatsDiving ( HEUR_STATS runstats,
DIVING_HEUR divingheur 
)
static

update the statistics of the diving heuristic based on the heuristic run

Parameters
runstatsrun statistics
divingheurthe selected diving heuristic or NULL if LNS was used

Definition at line 1168 of file heur_scheduler.c.

References DEFAULT_BESTSOLWEIGHT, Heur_Stats::nbacktracks, Heur_Stats::nbestsolsfound, Heur_Stats::nconflicts, Heur_Stats::nprobnodes, Heur_Stats::nruns, Heur_Stats::nrunsbestsol, Heur_Stats::nsolsfound, NULL, and Diving_Heur::stats.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateHeurStatsLNS()

static void updateHeurStatsLNS ( HEUR_STATS runstats,
NH neighborhood,
SCIP_STATUS subscipstatus 
)
static

update the statistics of LNS heuristic based on the heuristic run

Parameters
runstatsrun statistics
neighborhoodthe selected neighborhood or NULL if diving was used
subscipstatusstatus of the sub-SCIP solve or NULL if diving was used

Definition at line 1197 of file heur_scheduler.c.

References DEFAULT_BESTSOLWEIGHT, getHistIndex(), Heur_Stats::nbestsolsfound, Heur_Stats::nruns, Heur_Stats::nrunsbestsol, Heur_Stats::nsolsfound, NULL, Nh::stats, Heur_Stats::statushist, and Heur_Stats::usednodes.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sortIndCompScheduler  )
static

sort callback for variable pointers using the ALNS variable prioritization

the variable prioritization works hierarchically as follows. A variable a has the higher priority over b iff

  • variable distances should be used and a has a smaller distance than b
  • variable reduced costs should be used and a has a smaller score than b
  • variable pseudo costs should be used and a has a smaller score than b
  • based on previously assigned random scores
Note
: distances are context-based. For fixing more variables, distances are initialized from the already fixed variables. For unfixing variables, distances are initialized starting from the unfixed variables

Definition at line 1240 of file heur_scheduler.c.

References VarPrio::distances, NULL, VarPrio::pscostscores, VarPrio::randscores, VarPrio::redcostscores, VarPrio::usedistances, VarPrio::usepscost, and VarPrio::useredcost.

◆ getVariableRedcostScore()

static SCIP_Real getVariableRedcostScore ( SCIP scip,
SCIP_VAR var,
SCIP_Real  refsolval,
SCIP_Bool  uselocalredcost 
)
static

Compute the reduced cost score for this variable in the reference solution

Parameters
scipSCIP data structure
varthe variable for which the score should be computed
refsolvalsolution value in reference solution
uselocalredcostshould local reduced costs be used for generic (un)fixing?

Definition at line 1309 of file heur_scheduler.c.

References MAX, NULL, REALABS, SCIP_LPSOLSTAT_OPTIMAL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPgetLPSolstat(), SCIPgetVarRedcost(), SCIPhasCurrentNodeLP(), SCIPinfinity(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasIntegral(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootSol(), SCIPvarGetLPSol(), and SCIPvarGetStatus().

Referenced by LNSFixMoreVariables(), and LNSUnfixVariables().

◆ getVariablePscostScore()

static SCIP_Real getVariablePscostScore ( SCIP scip,
SCIP_VAR var,
SCIP_Real  refsolval,
SCIP_Bool  uselocallpsol 
)
static

get the pseudo cost score of this variable with respect to the reference solution

Parameters
scipSCIP data structure
varthe variable for which the score should be computed
refsolvalsolution value in reference solution
uselocallpsolshould local LP solution be used?

Definition at line 1362 of file heur_scheduler.c.

References NULL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPgetVarPseudocostVal(), SCIPisEQ(), SCIPvarGetLPSol(), SCIPvarGetRootSol(), and SCIPvarGetStatus().

Referenced by LNSFixMoreVariables(), and LNSUnfixVariables().

◆ tryAdd2variableBuffer()

static void tryAdd2variableBuffer ( SCIP scip,
SCIP_VAR var,
SCIP_Real  val,
SCIP_VAR **  varbuf,
SCIP_Real valbuf,
int *  nfixings,
SCIP_Bool  integer 
)
static

add variable and solution value to buffer data structure for variable fixings. The method checks if the value still lies within the variable bounds. The value stays unfixed otherwise.

Parameters
scipSCIP data structure
var(source) SCIP variable that should be added to the buffer
valfixing value for this variable
varbufvariable buffer to store variables that should be fixed
valbufvalue buffer to store fixing values
nfixingspointer to number of fixed buffer variables, will be increased by 1
integeris this an integer variable?

Definition at line 1391 of file heur_scheduler.c.

References Heur_Stats::nfixings, SCIPfloor(), SCIPgetNVars(), SCIPisFeasIntegral(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and SCIPvarIsIntegral().

Referenced by DECL_VARFIXINGS(), fixMatchingSolutionValues(), and LNSFixMoreVariables().

◆ LNSFixMoreVariables()

static SCIP_RETCODE LNSFixMoreVariables ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_SOL refsol,
SCIP_VAR **  varbuf,
SCIP_Real valbuf,
int *  nfixings,
int  ntargetfixings,
SCIP_Bool success 
)
static

fix additional variables found in feasible reference solution if the ones that the neighborhood found were not enough

use not always the best solution for the values, but a reference solution provided by the neighborhood itself

Note
it may happen that the target fixing rate is not completely reached. This is the case if intermediate, dual reductions render the solution values of the reference solution infeasible for the current, global variable bounds.
Parameters
scipSCIP data structure
heurdataheuristic data of the Scheduler neighborhood
refsolfeasible reference solution for more variable fixings
varbufbuffer array to store variables to fix
valbufbuffer array to store fixing values
nfixingspointer to store the number of fixings
ntargetfixingsnumber of required target fixings
successpointer to store whether the target fixings have been successfully reached

Definition at line 1429 of file heur_scheduler.c.

References b, BMSclearMemoryArray, VarPrio::distances, FALSE, getVariablePscostScore(), getVariableRedcostScore(), MIN, Heur_Stats::nfixings, NULL, VarPrio::pscostscores, VarPrio::randscores, VarPrio::redcostscores, VarPrio::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbanditGetRandnumgen(), SCIPfreeBufferArray, SCIPgetSolVals(), SCIPgetVarsData(), SCIPrandomGetReal(), SCIPselectInd(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvariablegraphBreadthFirst(), TRUE, tryAdd2variableBuffer(), VarPrio::usedistances, VarPrio::usepscost, and VarPrio::useredcost.

Referenced by neighborhoodFixVariables().

◆ createBandit()

static SCIP_RETCODE createBandit ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_Real priorities,
unsigned int  initseed 
)
static

create the bandit algorithm for the heuristic depending on the user parameter

Parameters
scipSCIP data structure
heurdataheuristic data structure
prioritiescall priorities for active neighborhoods
initseedinitial random seed

Definition at line 1595 of file heur_scheduler.c.

References FALSE, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPcreateBanditEpsgreedy(), SCIPcreateBanditExp3(), SCIPcreateBanditExp3IX(), SCIPcreateBanditUcb(), and SCIPerrorMessage.

Referenced by reinitBandit(), and SCIP_DECL_HEURINITSOL().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyScheduler  )
static

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

Definition at line 1641 of file heur_scheduler.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurScheduler().

◆ neighborhoodGetRefsol()

static SCIP_RETCODE neighborhoodGetRefsol ( SCIP scip,
NH neighborhood,
SCIP_SOL **  solptr 
)
static

query neighborhood for a reference solution for further fixings

Parameters
scipSCIP data structure
neighborhoodneighborhood data structure
solptrsolution pointer

Definition at line 1655 of file heur_scheduler.c.

References NULL, SCIP_CALL, SCIP_DIDNOTFIND, and SCIP_OKAY.

Referenced by neighborhoodFixVariables().

◆ LNSUnfixVariables()

static SCIP_RETCODE LNSUnfixVariables ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR **  varbuf,
SCIP_Real valbuf,
int *  nfixings,
int  ntargetfixings,
SCIP_Bool success 
)
static

unfix some of the variables because there are too many fixed

a variable is ideally unfixed if it is close to other unfixed variables and fixing it has a high reduced cost impact

Parameters
scipSCIP data structure
heurdataheuristic data of neighborhood
varbufbuffer array to store variables to fix
valbufbuffer array to store fixing values
nfixingspointer to store the number of fixings
ntargetfixingsnumber of required target fixings
successpointer to store whether the target fixings have been successfully reached

Definition at line 1686 of file heur_scheduler.c.

References BMSclearMemoryArray, VarPrio::distances, FALSE, getVariablePscostScore(), getVariableRedcostScore(), Heur_Stats::nfixings, NULL, VarPrio::pscostscores, VarPrio::randscores, VarPrio::redcostscores, VarPrio::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbanditGetRandnumgen(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetVars(), SCIPrandomGetReal(), SCIPselectDownInd(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), TRUE, VarPrio::usedistances, VarPrio::usepscost, and VarPrio::useredcost.

Referenced by neighborhoodFixVariables().

◆ neighborhoodFixVariables()

static SCIP_RETCODE neighborhoodFixVariables ( SCIP scip,
SCIP_HEURDATA heurdata,
NH neighborhood,
SCIP_VAR **  varbuf,
SCIP_Real valbuf,
int *  nfixings,
SCIP_RESULT result 
)
static

call variable fixing callback for this neighborhood and orchestrate additional variable fixings, if necessary

Parameters
scipSCIP data structure
heurdataheuristic data of the scheduler neighborhood
neighborhoodneighborhood data structure
varbufbuffer array to keep variables that should be fixed
valbufbuffer array to keep fixing values
nfixingspointer to store the number of variable fixings
resultpointer to store the result of the fixing operation

Definition at line 1833 of file heur_scheduler.c.

References FALSE, Nh::fixingrate, LNSFixMoreVariables(), LNSUnfixVariables(), MAX, MIN, neighborhoodGetRefsol(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNIntVars(), and NH_FixingRate::targetfixingrate.

Referenced by executeLNSHeuristic().

◆ neighborhoodChangeSubscip()

static SCIP_RETCODE neighborhoodChangeSubscip ( SCIP sourcescip,
SCIP targetscip,
NH neighborhood,
SCIP_VAR **  targetvars,
int *  ndomchgs,
int *  nchgobjs,
int *  naddedconss,
SCIP_Bool success 
)
static

change the sub-SCIP by restricting variable domains, changing objective coefficients, or adding constraints

Parameters
sourcescipsource SCIP data structure
targetsciptarget SCIP data structure
neighborhoodneighborhood
targetvarsarray of target SCIP variables aligned with source SCIP variables
ndomchgspointer to store the number of variable domain changes
nchgobjspointer to store the number of changed objective coefficients
naddedconsspointer to store the number of added constraints
successpointer to store whether the sub-SCIP has been successfully modified

Definition at line 1930 of file heur_scheduler.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by executeLNSHeuristic().

◆ setLimits()

static SCIP_RETCODE setLimits ( SCIP subscip,
SOLVELIMITS solvelimits 
)
static

set sub-SCIP solving limits

Parameters
subscipSCIP data structure
solvelimitspointer to solving limits data structure

Definition at line 1970 of file heur_scheduler.c.

References SolveLimits::memorylimit, SolveLimits::nodelimit, NULL, SCIP_CALL, SCIP_OKAY, SCIPsetLongintParam(), SCIPsetRealParam(), SolveLimits::stallnodes, and SolveLimits::timelimit.

Referenced by setupSubScip().

◆ determineLimits()

static SCIP_RETCODE determineLimits ( SCIP scip,
SCIP_HEUR heur,
int  selection,
SOLVELIMITS solvelimits,
SCIP_Bool runagain 
)
static

determine limits for a sub-SCIP

Parameters
scipSCIP data structure
heurthis heuristic
selectionindex of selected neighborhood
solvelimitspointer to solving limits data structure
runagaincan we solve another sub-SCIP with these limits

Definition at line 1990 of file heur_scheduler.c.

References FALSE, SolveLimits::memorylimit, SolveLimits::nodelimit, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPdebugMsg, SCIPgetBoolParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPheurGetData(), SCIPisInfinity(), SolveLimits::stallnodes, and SolveLimits::timelimit.

Referenced by executeLNSHeuristic().

◆ getReward()

static SCIP_Real getReward ( SCIP scip,
SCIP_HEURDATA heurdata,
int  selection,
HEUR_STATS runstats,
SCIP_STATUS  subscipstatus 
)
static

Calculate reward based on the selected reward measure

Parameters
scipSCIP data structure
heurdataheuristic data of the scheduler neighborhood
selectionindex of selected heuristic
runstatsrun statistics
subscipstatusstatus of the sub-SCIP if LNS was used

Definition at line 2037 of file heur_scheduler.c.

References Heur_Stats::divingdepth, MIN, Heur_Stats::nbestsolsfound, Heur_Stats::nconflicts, Heur_Stats::newupperbound, Heur_Stats::oldupperbound, SCIP_Real, SCIP_STATUS_TIMELIMIT, SCIPgetLowerbound(), SCIPisEQ(), SCIPisInfinity(), and Heur_Stats::usednodes.

Referenced by SCIP_DECL_HEUREXEC().

◆ setupSubScip()

static SCIP_RETCODE setupSubScip ( SCIP scip,
SCIP subscip,
SCIP_VAR **  subvars,
SOLVELIMITS solvelimits,
SCIP_HEUR heur,
SCIP_Bool  objchgd 
)
static

set up the sub-SCIP parameters, objective cutoff, and solution limits

Parameters
scipSCIP data structure
subscipsub-SCIP data structure
subvarsarray of sub-SCIP variables in the order of the main SCIP
solvelimitspointer to solving limits data structure
heurthis heuristic
objchgddid the objective change between the source and the target SCIP?

Definition at line 2115 of file heur_scheduler.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPcreateConsLinear(), SCIPfindBranchrule(), SCIPfindNodesel(), SCIPgetNVars(), SCIPgetUpperbound(), SCIPgetVars(), SCIPheurGetData(), SCIPheurGetNCalls(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisParamFixed(), SCIPreleaseCons(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsumepsilon(), SCIPvarGetObj(), setLimits(), and TRUE.

Referenced by executeLNSHeuristic().

◆ initSolveFreq()

static void initSolveFreq ( SOLVEFREQ solvefreqdata)
static

initialize solving frequency

Parameters
solvefreqdatadiving heuristic solving freq data

Definition at line 2239 of file heur_scheduler.c.

References SolveFreq::currentsolvefreq, SolveFreq::increment, MAXSOLVEFREQ, SolveFreq::maxsolvefreq, MINSOLVEFREQ, SolveFreq::minsolvefreq, NULL, and SOLVEFREQ_STARTINC.

Referenced by includeDivingHeurs().

◆ updateSolveFreqIncrement()

static void updateSolveFreqIncrement ( SOLVEFREQ solvefreqdata)
static

update increment for solving frequency

Parameters
solvefreqdatadiving heuristic solving freq data

Definition at line 2256 of file heur_scheduler.c.

References SolveFreq::increment, LRATEMIN, MAX, and SOLVEFREQ_DECAY.

Referenced by updateSolveFreq().

◆ increaseSolveFreq()

static void increaseSolveFreq ( SOLVEFREQ solvefreqdata)
static

increase solving frequency

decrease also the rate by which the solving frequency is adjusted

Parameters
solvefreqdatadiving heuristic solving freq data

Definition at line 2269 of file heur_scheduler.c.

References SolveFreq::currentsolvefreq, SolveFreq::increment, SolveFreq::maxsolvefreq, and MIN.

Referenced by updateSolveFreq().

◆ decreaseSolveFreq()

static void decreaseSolveFreq ( SOLVEFREQ solvefreqdata)
static

decrease solving frequency

decrease also the rate by which the solving frequency is adjusted

Parameters
solvefreqdatadiving heuristic solving freq data

Definition at line 2282 of file heur_scheduler.c.

References SolveFreq::currentsolvefreq, SolveFreq::increment, MAX, and SolveFreq::minsolvefreq.

Referenced by updateSolveFreq().

◆ updateSolveFreq()

static void updateSolveFreq ( DIVING_HEUR divingheur,
HEUR_STATS stats 
)
static

update solve frequency for diving heuristics

Parameters
divingheurdiving heuristic
statsrun statistics for this run

Definition at line 2292 of file heur_scheduler.c.

References decreaseSolveFreq(), increaseSolveFreq(), Diving_Heur::nodelimit, Heur_Stats::nprobnodes, Heur_Stats::nsolsfound, Diving_Heur::solvefreqdata, and updateSolveFreqIncrement().

Referenced by SCIP_DECL_HEUREXEC().

◆ includeDivingHeurs()

◆ selectHeuristic()

static SCIP_RETCODE selectHeuristic ( SCIP scip,
SCIP_HEURDATA heurdata,
int *  selection 
)
static

select a heuristic depending on the selected bandit algorithm

Parameters
scipSCIP data structure
heurdataheuristic data of the scheduler heuristic
selectionpointer to store the selected heuristic index

Definition at line 2381 of file heur_scheduler.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPbanditSelect().

Referenced by SCIP_DECL_HEUREXEC().

◆ updateSelectionStrategy()

static SCIP_RETCODE updateSelectionStrategy ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_Real  reward,
int  selection 
)
static

update selection strategy with observed reward for future draws

Parameters
scipSCIP data structure
heurdataheuristic data of the scheduler heuristic
rewardmeasured reward
selectionthe heuristic index that was chosen

Definition at line 2417 of file heur_scheduler.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbanditUpdate(), and SCIPdebugMsg.

Referenced by SCIP_DECL_HEUREXEC().

◆ executeDivingHeuristic()

◆ executeLNSHeuristic()

static SCIP_RETCODE executeLNSHeuristic ( SCIP scip,
SCIP_HEUR heur,
int  selection,
HEUR_STATS runstats,
SCIP_STATUS subscipstatus,
SCIP_RESULT result 
)
static

◆ executeHeuristic()

static SCIP_RETCODE executeHeuristic ( SCIP scip,
SCIP_HEUR heur,
int  selection,
HEUR_STATS runstats,
SCIP_STATUS subscipstatus,
SCIP_RESULT result 
)
static

execute selected heuristic

Parameters
scipSCIP data structure
heurscheduler heuristic
selectionthe heuristic index that was chosen
runstatsstatistics of call to selection
subscipstatuspointer to store status of the sub-SCIP solve or NULL if diving was used
resultpointer to store the result of the heuristic call

Definition at line 2704 of file heur_scheduler.c.

References executeDivingHeuristic(), executeLNSHeuristic(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPheurGetData().

Referenced by SCIP_DECL_HEUREXEC().

◆ reinitBandit()

static SCIP_RETCODE reinitBandit ( SCIP scip,
SCIP_HEURDATA heurdata,
int  nactions 
)
static

reinitialize bandit algorithm since the number of actions has changed

Parameters
scipSCIP data structure
heurdataheuristic data
nactionsnew number of actions

Definition at line 2736 of file heur_scheduler.c.

References createBandit(), NULL, resetTargetNodeLimit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBandit(), SCIPfreeBufferArray, and SCIPgetNVars().

Referenced by initRest().

◆ initRest()

static SCIP_RETCODE initRest ( SCIP scip,
SCIP_HEUR heur 
)
static

initializes everything that was missing because diving heuristics were not proccessed by SCIP yet. In particular, the function adds diving heuristics to heurdata, heurdata->maxdivingnodelimit, heurdata->maxlnsnodelimit and heurdata->sortedindices if heurdata->defaultroot is set to TRUE

Parameters
scipSCIP data structure
heurscheduler heuristic

Definition at line 2778 of file heur_scheduler.c.

References includeDivingHeurs(), reinitBandit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPheurGetData(), and SCIPsortRealInt().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEUREXEC()

◆ DECL_VARFIXINGS() [1/5]

◆ DECL_CHANGESUBSCIP() [1/6]

◆ fixMatchingSolutionValues()

static SCIP_RETCODE fixMatchingSolutionValues ( SCIP scip,
SCIP_SOL **  sols,
int  nsols,
SCIP_VAR **  vars,
int  nvars,
SCIP_VAR **  varbuf,
SCIP_Real valbuf,
int *  nfixings 
)
static

collect fixings by matching solution values in a collection of solutions for all binary and integer variables, or for a custom set of variables

Parameters
scipSCIP data structure
solsarray of 2 or more solutions. It is okay for the array to contain one element equal to NULL to represent the current LP solution
nsolsnumber of solutions in the array
varsvariable array for which solution values must agree
nvarsnumber of variables, or -1 for all binary and integer variables
varbufbuffer storage for variable fixings
valbufbuffer storage for fixing values
nfixingspointer to store the number of fixings

Definition at line 3110 of file heur_scheduler.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNBinVars(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisEQ(), SCIPvarIsBinary(), SCIPvarIsIntegral(), TRUE, and tryAdd2variableBuffer().

Referenced by DECL_VARFIXINGS().

◆ DECL_VARFIXINGS() [2/5]

◆ DECL_NHINIT() [1/2]

static DECL_NHINIT ( nhInitCrossover  )
static

initialization callback for crossover when a new problem is read

Definition at line 3224 of file heur_scheduler.c.

References Nh::crossover, CROSSOVERSEED, Nh::data, NULL, data_crossover::rng, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfreeRandom(), SCIPgetNVars(), data_crossover::selsol, and TRUE.

◆ DECL_NHEXIT() [1/2]

static DECL_NHEXIT ( nhExitCrossover  )
static

deinitialization callback for crossover when exiting a problem

Definition at line 3243 of file heur_scheduler.c.

References Nh::crossover, Nh::data, NULL, data_crossover::rng, SCIP_OKAY, and SCIPfreeRandom().

◆ DECL_NHFREE() [1/3]

static DECL_NHFREE ( nhFreeCrossover  )
static

deinitialization callback for crossover before SCIP is freed

Definition at line 3258 of file heur_scheduler.c.

References Nh::crossover, Nh::data, NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ DECL_VARFIXINGS() [3/5]

◆ DECL_NHREFSOL() [1/2]

static DECL_NHREFSOL ( nhRefsolCrossover  )
static

callback for crossover reference solution

Definition at line 3349 of file heur_scheduler.c.

References Nh::crossover, Nh::data, NULL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, and data_crossover::selsol.

◆ DECL_NHINIT() [2/2]

static DECL_NHINIT ( nhInitMutation  )
static

initialization callback for mutation when a new problem is read

Definition at line 3370 of file heur_scheduler.c.

References Nh::data, Nh::mutation, MUTATIONSEED, NULL, data_mutation::rng, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcreateRandom(), SCIPgetNVars(), and TRUE.

◆ DECL_NHEXIT() [2/2]

static DECL_NHEXIT ( nhExitMutation  )
static

deinitialization callback for mutation when exiting a problem

Definition at line 3388 of file heur_scheduler.c.

References Nh::data, Nh::mutation, NULL, data_mutation::rng, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeRandom().

◆ DECL_VARFIXINGS() [4/5]

◆ addLocalBranchingConstraint()

static SCIP_RETCODE addLocalBranchingConstraint ( SCIP sourcescip,
SCIP targetscip,
SCIP_VAR **  subvars,
int  distance,
SCIP_Bool success,
int *  naddedconss 
)
static

add local branching constraint

Parameters
sourcescipsource SCIP data structure
targetsciptarget SCIP data structure
subvarsarray of sub SCIP variables in same order as source SCIP variables
distanceright hand side of the local branching constraint
successpointer to store of a local branching constraint has been successfully added
naddedconsspointer to increase the number of added constraints

Definition at line 3483 of file heur_scheduler.c.

References FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsBasicLinear(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPinfinity(), SCIPisEQ(), SCIPreleaseCons(), and TRUE.

Referenced by DECL_CHANGESUBSCIP().

◆ DECL_CHANGESUBSCIP() [2/6]

static DECL_CHANGESUBSCIP ( changeSubscipLocalbranching  )
static

callback for local branching subproblem changes

Definition at line 3549 of file heur_scheduler.c.

References addLocalBranchingConstraint(), SCIP_CALL, SCIP_OKAY, and SCIPgetNBinVars().

◆ DECL_CHANGESUBSCIP() [3/6]

static DECL_CHANGESUBSCIP ( changeSubscipProximity  )
static

callback for proximity subproblem changes

Definition at line 3559 of file heur_scheduler.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObj(), SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetVarsData(), and TRUE.

◆ DECL_CHANGESUBSCIP() [4/6]

static DECL_CHANGESUBSCIP ( changeSubscipZeroobjective  )
static

callback for zeroobjective subproblem changes

Definition at line 3611 of file heur_scheduler.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPchgVarObj(), SCIPconshdlrGetNActiveConss(), SCIPfindConshdlr(), SCIPgetNObjVars(), SCIPgetVarsData(), and TRUE.

◆ computeIntegerVariableBoundsDins()

static void computeIntegerVariableBoundsDins ( SCIP scip,
SCIP_VAR var,
SCIP_Real lbptr,
SCIP_Real ubptr 
)
static

compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ

Parameters
scipSCIP data structure of the original problem
varthe variable for which bounds should be computed
lbptrpointer to store the lower bound in the DINS sub-SCIP
ubptrpointer to store the upper bound in the DINS sub-SCIP

Definition at line 3651 of file heur_scheduler.c.

References MAX, MIN, REALABS, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetBestSol(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetLPSol(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by DECL_CHANGESUBSCIP(), and DECL_VARFIXINGS().

◆ DECL_VARFIXINGS() [5/5]

◆ DECL_CHANGESUBSCIP() [5/6]

static DECL_CHANGESUBSCIP ( changeSubscipDins  )
static

◆ DECL_NHFREE() [2/3]

static DECL_NHFREE ( nhFreeDins  )
static

deinitialization callback for DINS before SCIP is freed

Definition at line 3842 of file heur_scheduler.c.

References Nh::data, Nh::dins, NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ DECL_NHFREE() [3/3]

static DECL_NHFREE ( nhFreeTrustregion  )
static

deinitialization callback for trustregion before SCIP is freed

Definition at line 3853 of file heur_scheduler.c.

References Nh::data, NULL, SCIP_OKAY, SCIPfreeBlockMemory, and Nh::trustregion.

◆ DECL_CHANGESUBSCIP() [6/6]

static DECL_CHANGESUBSCIP ( changeSubscipTrustregion  )
static

add trust region neighborhood constraint and auxiliary objective variable

Definition at line 3864 of file heur_scheduler.c.

References Nh::data, SCIP_CALL, SCIP_OKAY, SCIPaddTrustregionNeighborhoodConstraint(), Nh::trustregion, and data_trustregion::violpenalty.

◆ DECL_NHREFSOL() [2/2]

static DECL_NHREFSOL ( nhRefsolIncumbent  )
static

callback that returns the incumbent solution as a reference point

Definition at line 3883 of file heur_scheduler.c.

References NULL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, and SCIPgetBestSol().

◆ DECL_NHDEACTIVATE() [1/3]

static DECL_NHDEACTIVATE ( nhDeactivateDiscreteVars  )
static

callback function that deactivates a neighborhood on problems with no discrete variables

Definition at line 3903 of file heur_scheduler.c.

References NULL, SCIP_OKAY, SCIPgetNBinVars(), and SCIPgetNIntVars().

◆ DECL_NHDEACTIVATE() [2/3]

static DECL_NHDEACTIVATE ( nhDeactivateBinVars  )
static

callback function that deactivates a neighborhood on problems with no binary variables

Definition at line 3916 of file heur_scheduler.c.

References NULL, SCIP_OKAY, and SCIPgetNBinVars().

◆ DECL_NHDEACTIVATE() [3/3]

static DECL_NHDEACTIVATE ( nhDeactivateObjVars  )
static

callback function that deactivates a neighborhood on problems with no objective variables

Definition at line 3929 of file heur_scheduler.c.

References NULL, SCIP_OKAY, and SCIPgetNObjVars().

◆ includeNeighborhoods()

static SCIP_RETCODE includeNeighborhoods ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

include all neighborhoods

Parameters
scipSCIP data structure
heurdataheuristic data of the scheduler heuristic

Definition at line 3943 of file heur_scheduler.c.

References Nh::crossover, Nh::data, DEFAULT_ACTIVE_CROSSOVER, DEFAULT_ACTIVE_DINS, DEFAULT_ACTIVE_LOCALBRANCHING, DEFAULT_ACTIVE_MUTATION, DEFAULT_ACTIVE_PROXIMITY, DEFAULT_ACTIVE_RENS, DEFAULT_ACTIVE_RINS, DEFAULT_ACTIVE_TRUSTREGION, DEFAULT_ACTIVE_ZEROOBJECTIVE, DEFAULT_MAXFIXINGRATE_CROSSOVER, DEFAULT_MAXFIXINGRATE_DINS, DEFAULT_MAXFIXINGRATE_LOCALBRANCHING, DEFAULT_MAXFIXINGRATE_MUTATION, DEFAULT_MAXFIXINGRATE_PROXIMITY, DEFAULT_MAXFIXINGRATE_RENS, DEFAULT_MAXFIXINGRATE_RINS, DEFAULT_MAXFIXINGRATE_TRUSTREGION, DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE, DEFAULT_MINFIXINGRATE_CROSSOVER, DEFAULT_MINFIXINGRATE_DINS, DEFAULT_MINFIXINGRATE_LOCALBRANCHING, DEFAULT_MINFIXINGRATE_MUTATION, DEFAULT_MINFIXINGRATE_PROXIMITY, DEFAULT_MINFIXINGRATE_RENS, DEFAULT_MINFIXINGRATE_RINS, DEFAULT_MINFIXINGRATE_TRUSTREGION, DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE, DEFAULT_NPOOLSOLS_DINS, DEFAULT_NSOLS_CROSSOVER, DEFAULT_PRIORITY_CROSSOVER, DEFAULT_PRIORITY_DINS, DEFAULT_PRIORITY_LOCALBRANCHING, DEFAULT_PRIORITY_MUTATION, DEFAULT_PRIORITY_PROXIMITY, DEFAULT_PRIORITY_RENS, DEFAULT_PRIORITY_RINS, DEFAULT_PRIORITY_TRUSTREGION, DEFAULT_PRIORITY_ZEROOBJECTIVE, DEFAULT_VIOLPENALTY_TRUSTREGION, Nh::dins, FALSE, HEUR_NAME, data_dins::npoolsols, data_crossover::nsols, NULL, data_crossover::rng, schedulerIncludeNeighborhood(), SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, TRUE, Nh::trustregion, and data_trustregion::violpenalty.

Referenced by SCIPincludeHeurScheduler().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitScheduler  )
static

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

Definition at line 4034 of file heur_scheduler.c.

References FALSE, Nh::fixingrate, heurStatsReset(), neighborhoodInit(), NULL, resetFixingRate(), SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPfreeBlockMemoryArray, SCIPheurGetData(), and Nh::stats.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolScheduler  )
static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 4078 of file heur_scheduler.c.

References Nh::active, createBandit(), NULL, resetCurrentNeighborhood(), resetTargetNodeLimit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbanditGetNActions(), SCIPfreeBandit(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPheurGetData(), SCIPresetBandit(), SCIPsortRealInt(), and SCIPswapPointers().

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitScheduler  )
static

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

Definition at line 4198 of file heur_scheduler.c.

References neighborhoodExit(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), and SCIPheurGetData().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeScheduler  )
static

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

Definition at line 4225 of file heur_scheduler.c.

References NNEIGHBORHOODS, NULL, schedulerFreeDivingHeur(), schedulerFreeNeighborhood(), SCIP_CALL, SCIP_OKAY, SCIPfreeBandit(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPheurGetData().

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputNeighborhood  )
static

output method of statistics table to output file stream 'file'

Definition at line 4273 of file heur_scheduler.c.

References HEUR_NAME, NULL, printDivingHeurStatistics(), printNeighborhoodStatistics(), SCIP_OKAY, SCIPfindHeur(), and SCIPheurGetData().