Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Adaptive large neighborhood search heuristic that orchestrates popular LNS heuristics.

Author
Gregor Hendel

Definition in file heur_alns.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heur_alns.h"
#include "scip/heuristics.h"
#include "scip/pub_bandit_epsgreedy.h"
#include "scip/pub_bandit_exp3.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  NH_Stats
 
struct  NH_FixingRate
 
struct  Nh
 
struct  data_mutation
 
struct  data_crossover
 
struct  data_dins
 
struct  data_trustregion
 
struct  SolveLimits
 
struct  VarPrio
 

Macros

#define HEUR_NAME   "alns"
 
#define HEUR_DESC   "Large neighborhood search heuristic that orchestrates the popular neighborhoods Local Branching, RINS, RENS, DINS etc."
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS
 
#define HEUR_PRIORITY   -1100500
 
#define HEUR_FREQ   20
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_DURINGLPLOOP
 
#define HEUR_USESSUBSCIP   TRUE
 
#define NNEIGHBORHOODS   9
 
#define DEFAULT_SHOWNBSTATS   FALSE
 
#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   5000LL
 
#define DEFAULT_WAITINGNODES   25LL
 
#define DEFAULT_TARGETNODEFACTOR   1.05
 
#define LRATEMIN   0.01
 
#define LPLIMFAC   4.0
 
#define DEFAULT_INITDURINGROOT   FALSE
 
#define DEFAULT_MAXCALLSSAMESOL   -1
 
#define DEFAULT_MINIMPROVELOW   0.01
 
#define DEFAULT_MINIMPROVEHIGH   0.01
 
#define MINIMPROVEFAC   1.5
 
#define DEFAULT_STARTMINIMPROVE   0.01
 
#define DEFAULT_ADJUSTMINIMPROVE   FALSE
 
#define DEFAULT_ADJUSTTARGETNODES   TRUE
 
#define DEFAULT_BESTSOLWEIGHT   1
 
#define DEFAULT_BANDITALGO   'u'
 
#define DEFAULT_REWARDCONTROL   0.8
 
#define DEFAULT_SCALEBYEFFORT   TRUE
 
#define DEFAULT_RESETWEIGHTS   TRUE
 
#define DEFAULT_SUBSCIPRANDSEEDS   FALSE
 
#define DEFAULT_REWARDBASELINE   0.5
 
#define DEFAULT_FIXTOL   0.1
 
#define DEFAULT_UNFIXTOL   0.1
 
#define DEFAULT_USELOCALREDCOST   FALSE
 
#define DEFAULT_BETA   0.0
 
#define DEFAULT_EPS   0.4685844
 
#define DEFAULT_ALPHA   0.0016
 
#define DEFAULT_GAMMA   0.07041455
 
#define DEFAULT_USEREDCOST   TRUE
 
#define DEFAULT_USEPSCOST   TRUE
 
#define DEFAULT_USEDISTANCES   TRUE
 
#define DEFAULT_DOMOREFIXINGS   TRUE
 
#define DEFAULT_ADJUSTFIXINGRATE   TRUE
 
#define FIXINGRATE_DECAY   0.75
 
#define FIXINGRATE_STARTINC   0.2
 
#define DEFAULT_USESUBSCIPHEURS   FALSE
 
#define DEFAULT_COPYCUTS   FALSE
 
#define DEFAULT_REWARDFILENAME   "-"
 
#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   1.0
 
#define DEFAULT_MINFIXINGRATE_RINS   0.3
 
#define DEFAULT_MAXFIXINGRATE_RINS   0.9
 
#define DEFAULT_ACTIVE_RINS   TRUE
 
#define DEFAULT_PRIORITY_RINS   1.0
 
#define DEFAULT_MINFIXINGRATE_MUTATION   0.3
 
#define DEFAULT_MAXFIXINGRATE_MUTATION   0.9
 
#define DEFAULT_ACTIVE_MUTATION   TRUE
 
#define DEFAULT_PRIORITY_MUTATION   1.0
 
#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING   0.3
 
#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING   0.9
 
#define DEFAULT_ACTIVE_LOCALBRANCHING   TRUE
 
#define DEFAULT_PRIORITY_LOCALBRANCHING   1.0
 
#define DEFAULT_MINFIXINGRATE_PROXIMITY   0.3
 
#define DEFAULT_MAXFIXINGRATE_PROXIMITY   0.9
 
#define DEFAULT_ACTIVE_PROXIMITY   TRUE
 
#define DEFAULT_PRIORITY_PROXIMITY   1.0
 
#define DEFAULT_MINFIXINGRATE_CROSSOVER   0.3
 
#define DEFAULT_MAXFIXINGRATE_CROSSOVER   0.9
 
#define DEFAULT_ACTIVE_CROSSOVER   TRUE
 
#define DEFAULT_PRIORITY_CROSSOVER   1.0
 
#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE   0.3
 
#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE   0.9
 
#define DEFAULT_ACTIVE_ZEROOBJECTIVE   TRUE
 
#define DEFAULT_PRIORITY_ZEROOBJECTIVE   1.0
 
#define DEFAULT_MINFIXINGRATE_DINS   0.3
 
#define DEFAULT_MAXFIXINGRATE_DINS   0.9
 
#define DEFAULT_ACTIVE_DINS   TRUE
 
#define DEFAULT_PRIORITY_DINS   1.0
 
#define DEFAULT_MINFIXINGRATE_TRUSTREGION   0.3
 
#define DEFAULT_MAXFIXINGRATE_TRUSTREGION   0.9
 
#define DEFAULT_ACTIVE_TRUSTREGION   FALSE
 
#define DEFAULT_PRIORITY_TRUSTREGION   1.0
 
#define DEFAULT_NSOLS_CROSSOVER   2
 
#define DEFAULT_NPOOLSOLS_DINS   5
 
#define DEFAULT_VIOLPENALTY_TRUSTREGION   100.0
 
#define EVENTHDLR_NAME   "Alns"
 
#define EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"
 
#define SCIP_EVENTTYPE_ALNS   (SCIP_EVENTTYPE_LPSOLVED | SCIP_EVENTTYPE_SOLFOUND | SCIP_EVENTTYPE_BESTSOLFOUND)
 
#define TABLE_NAME_NEIGHBORHOOD   "neighborhood"
 
#define TABLE_DESC_NEIGHBORHOOD   "ALNS neighborhood 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 NH_Stats NH_STATS
 
typedef struct Nh NH
 
typedef struct VarPrio VARPRIO
 
typedef enum HistIndex HISTINDEX
 
typedef struct SolveLimits SOLVELIMITS
 

Enumerations

enum  RewardType {
  REWARDTYPE_TOTAL,
  REWARDTYPE_BESTSOL,
  REWARDTYPE_CLOSEDGAP,
  REWARDTYPE_NOSOLPENALTY,
  NREWARDTYPES
}
 
enum  HistIndex {
  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 resetCurrentNeighborhood (SCIP_HEURDATA *heurdata)
 
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, NH_STATS *runstats)
 
static void increaseTargetNodeLimit (SCIP_HEURDATA *heurdata)
 
static void resetTargetNodeLimit (SCIP_HEURDATA *heurdata)
 
static void updateTargetNodeLimit (SCIP_HEURDATA *heurdata, NH_STATS *runstats, SCIP_STATUS subscipstatus)
 
static void resetMinimumImprovement (SCIP_HEURDATA *heurdata)
 
static void increaseMinimumImprovement (SCIP_HEURDATA *heurdata)
 
static void decreaseMinimumImprovement (SCIP_HEURDATA *heurdata)
 
static void updateMinimumImprovement (SCIP_HEURDATA *heurdata, SCIP_STATUS subscipstatus, NH_STATS *runstats)
 
static SCIP_RETCODE neighborhoodStatsReset (SCIP *scip, NH_STATS *stats)
 
static SCIP_RETCODE alnsIncludeNeighborhood (SCIP *scip, SCIP_HEURDATA *heurdata, NH **neighborhood, const char *name, SCIP_Real minfixingrate, SCIP_Real maxfixingrate, SCIP_Bool active, SCIP_Real 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 alnsFreeNeighborhood (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_DECL_EVENTEXEC (eventExecAlns)
 
static void initRunStats (SCIP *scip, NH_STATS *stats)
 
static void updateRunStats (NH_STATS *stats, SCIP *subscip)
 
static int getHistIndex (SCIP_STATUS subscipstatus)
 
static void printNeighborhoodStatistics (SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
 
static void updateNeighborhoodStats (NH_STATS *runstats, NH *neighborhood, SCIP_STATUS subscipstatus)
 
static SCIP_DECL_SORTINDCOMP (sortIndCompAlns)
 
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 neighborhoodGetRefsol (SCIP *scip, NH *neighborhood, SCIP_SOL **solptr)
 
static SCIP_RETCODE alnsFixMoreVariables (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 (heurCopyAlns)
 
static SCIP_RETCODE alnsUnfixVariables (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, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
 
static SCIP_BANDITgetBandit (SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE selectNeighborhood (SCIP *scip, SCIP_HEURDATA *heurdata, int *neighborhoodidx)
 
static SCIP_RETCODE getReward (SCIP *scip, SCIP_HEURDATA *heurdata, NH_STATS *runstats, SCIP_Real *rewardptr)
 
static SCIP_RETCODE updateBanditAlgorithm (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real reward, int neighborhoodidx)
 
static SCIP_RETCODE setupSubScip (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SOLVELIMITS *solvelimits, SCIP_HEUR *heur, SCIP_Bool objchgd)
 
static SCIP_DECL_HEUREXEC (heurExecAlns)
 
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 (heurInitAlns)
 
static SCIP_DECL_HEURINITSOL (heurInitsolAlns)
 
static SCIP_DECL_HEUREXIT (heurExitAlns)
 
static SCIP_DECL_HEURFREE (heurFreeAlns)
 
static SCIP_DECL_TABLEOUTPUT (tableOutputNeighborhood)
 
SCIP_RETCODE SCIPincludeHeurAlns (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "alns"

◆ HEUR_DESC

#define HEUR_DESC   "Large neighborhood search heuristic that orchestrates the popular neighborhoods Local Branching, RINS, RENS, DINS etc."

Definition at line 78 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS

Definition at line 79 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1100500

Definition at line 80 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_FREQ

#define HEUR_FREQ   20

Definition at line 81 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 82 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 83 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_TIMING

Definition at line 84 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 85 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ NNEIGHBORHOODS

#define NNEIGHBORHOODS   9

Definition at line 87 of file heur_alns.c.

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURFREE(), and SCIPincludeHeurAlns().

◆ DEFAULT_SHOWNBSTATS

#define DEFAULT_SHOWNBSTATS   FALSE

show statistics on neighborhoods?

Definition at line 89 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

Definition at line 94 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_NODESQUOTMIN

#define DEFAULT_NODESQUOTMIN   0.0

Definition at line 95 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_NODESOFFSET

#define DEFAULT_NODESOFFSET   500LL

Definition at line 96 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_NSOLSLIM

#define DEFAULT_NSOLSLIM   3

Definition at line 97 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   50LL

Definition at line 98 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000LL

Definition at line 99 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_WAITINGNODES

#define DEFAULT_WAITINGNODES   25LL

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

Definition at line 100 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_TARGETNODEFACTOR

#define DEFAULT_TARGETNODEFACTOR   1.05

Definition at line 101 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ LRATEMIN

#define LRATEMIN   0.01

lower bound for learning rate for target nodes and minimum improvement

Definition at line 102 of file heur_alns.c.

Referenced by updateFixingRateIncrement().

◆ LPLIMFAC

#define LPLIMFAC   4.0

Definition at line 103 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_INITDURINGROOT

#define DEFAULT_INITDURINGROOT   FALSE

Definition at line 104 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_MAXCALLSSAMESOL

#define DEFAULT_MAXCALLSSAMESOL   -1

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

Definition at line 105 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_MINIMPROVELOW

#define DEFAULT_MINIMPROVELOW   0.01

Definition at line 110 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_MINIMPROVEHIGH

#define DEFAULT_MINIMPROVEHIGH   0.01

Definition at line 111 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ MINIMPROVEFAC

#define MINIMPROVEFAC   1.5

Definition at line 112 of file heur_alns.c.

Referenced by decreaseMinimumImprovement(), and increaseMinimumImprovement().

◆ DEFAULT_STARTMINIMPROVE

#define DEFAULT_STARTMINIMPROVE   0.01

Definition at line 113 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_ADJUSTMINIMPROVE

#define DEFAULT_ADJUSTMINIMPROVE   FALSE

Definition at line 114 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_ADJUSTTARGETNODES

#define DEFAULT_ADJUSTTARGETNODES   TRUE

should the target nodes be dynamically adjusted?

Definition at line 115 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_BESTSOLWEIGHT

#define DEFAULT_BESTSOLWEIGHT   1

Definition at line 120 of file heur_alns.c.

Referenced by updateNeighborhoodStats().

◆ DEFAULT_BANDITALGO

#define DEFAULT_BANDITALGO   'u'

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

Definition at line 121 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_REWARDCONTROL

#define DEFAULT_REWARDCONTROL   0.8

reward control to increase the weight of the simple solution indicator and decrease the weight of the closed gap reward

Definition at line 122 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_SCALEBYEFFORT

#define DEFAULT_SCALEBYEFFORT   TRUE

should the reward be scaled by the effort?

Definition at line 123 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_RESETWEIGHTS

#define DEFAULT_RESETWEIGHTS   TRUE

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

Definition at line 124 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_SUBSCIPRANDSEEDS

#define DEFAULT_SUBSCIPRANDSEEDS   FALSE

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

Definition at line 125 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_REWARDBASELINE

#define DEFAULT_REWARDBASELINE   0.5

the reward baseline to separate successful and failed calls

Definition at line 126 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_FIXTOL

#define DEFAULT_FIXTOL   0.1

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

Definition at line 127 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_UNFIXTOL

#define DEFAULT_UNFIXTOL   0.1

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

Definition at line 128 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_USELOCALREDCOST

#define DEFAULT_USELOCALREDCOST   FALSE

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

Definition at line 129 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_BETA

#define DEFAULT_BETA   0.0

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

Definition at line 130 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_EPS

#define DEFAULT_EPS   0.4685844

increase exploration in epsilon-greedy bandit algorithm

Definition at line 136 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_ALPHA

#define DEFAULT_ALPHA   0.0016

parameter to increase the confidence width in UCB

Definition at line 137 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ 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 138 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_USEREDCOST

#define DEFAULT_USEREDCOST   TRUE

should reduced cost scores be used for variable priorization?

Definition at line 142 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_USEPSCOST

#define DEFAULT_USEPSCOST   TRUE

should pseudo cost scores be used for variable priorization?

Definition at line 143 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_USEDISTANCES

#define DEFAULT_USEDISTANCES   TRUE

should distances from fixed variables be used for variable priorization

Definition at line 144 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_DOMOREFIXINGS

#define DEFAULT_DOMOREFIXINGS   TRUE

should the ALNS heuristic do more fixings by itself based on variable prioritization until the target fixing rate is reached?

Definition at line 145 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_ADJUSTFIXINGRATE

#define DEFAULT_ADJUSTFIXINGRATE   TRUE

should the heuristic adjust the target fixing rate based on the success?

Definition at line 148 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ FIXINGRATE_DECAY

#define FIXINGRATE_DECAY   0.75

geometric decay for fixing rate adjustments

Definition at line 149 of file heur_alns.c.

Referenced by updateFixingRateIncrement().

◆ FIXINGRATE_STARTINC

#define FIXINGRATE_STARTINC   0.2

initial increment value for fixing rate

Definition at line 150 of file heur_alns.c.

Referenced by resetFixingRate().

◆ DEFAULT_USESUBSCIPHEURS

#define DEFAULT_USESUBSCIPHEURS   FALSE

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

Definition at line 151 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_COPYCUTS

#define DEFAULT_COPYCUTS   FALSE

should cutting planes be copied to the sub-SCIP?

Definition at line 152 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DEFAULT_REWARDFILENAME

#define DEFAULT_REWARDFILENAME   "-"

file name to store all rewards and the selection of the bandit

Definition at line 153 of file heur_alns.c.

Referenced by SCIP_DECL_HEURINIT(), and SCIPincludeHeurAlns().

◆ DEFAULT_SEED

#define DEFAULT_SEED   113

Definition at line 156 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ MUTATIONSEED

#define MUTATIONSEED   121

Definition at line 157 of file heur_alns.c.

Referenced by DECL_NHINIT().

◆ CROSSOVERSEED

#define CROSSOVERSEED   321

Definition at line 158 of file heur_alns.c.

Referenced by DECL_NHINIT().

◆ DEFAULT_MINFIXINGRATE_RENS

#define DEFAULT_MINFIXINGRATE_RENS   0.3

Definition at line 161 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_RENS

#define DEFAULT_MAXFIXINGRATE_RENS   0.9

Definition at line 162 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_RENS

#define DEFAULT_ACTIVE_RENS   TRUE

Definition at line 163 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_RENS

#define DEFAULT_PRIORITY_RENS   1.0

Definition at line 164 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_RINS

#define DEFAULT_MINFIXINGRATE_RINS   0.3

Definition at line 166 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_RINS

#define DEFAULT_MAXFIXINGRATE_RINS   0.9

Definition at line 167 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_RINS

#define DEFAULT_ACTIVE_RINS   TRUE

Definition at line 168 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_RINS

#define DEFAULT_PRIORITY_RINS   1.0

Definition at line 169 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_MUTATION

#define DEFAULT_MINFIXINGRATE_MUTATION   0.3

Definition at line 171 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_MUTATION

#define DEFAULT_MAXFIXINGRATE_MUTATION   0.9

Definition at line 172 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_MUTATION

#define DEFAULT_ACTIVE_MUTATION   TRUE

Definition at line 173 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_MUTATION

#define DEFAULT_PRIORITY_MUTATION   1.0

Definition at line 174 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_LOCALBRANCHING

#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING   0.3

Definition at line 176 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_LOCALBRANCHING

#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING   0.9

Definition at line 177 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_LOCALBRANCHING

#define DEFAULT_ACTIVE_LOCALBRANCHING   TRUE

Definition at line 178 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_LOCALBRANCHING

#define DEFAULT_PRIORITY_LOCALBRANCHING   1.0

Definition at line 179 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_PROXIMITY

#define DEFAULT_MINFIXINGRATE_PROXIMITY   0.3

Definition at line 181 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_PROXIMITY

#define DEFAULT_MAXFIXINGRATE_PROXIMITY   0.9

Definition at line 182 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_PROXIMITY

#define DEFAULT_ACTIVE_PROXIMITY   TRUE

Definition at line 183 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_PROXIMITY

#define DEFAULT_PRIORITY_PROXIMITY   1.0

Definition at line 184 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_CROSSOVER

#define DEFAULT_MINFIXINGRATE_CROSSOVER   0.3

Definition at line 186 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_CROSSOVER

#define DEFAULT_MAXFIXINGRATE_CROSSOVER   0.9

Definition at line 187 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_CROSSOVER

#define DEFAULT_ACTIVE_CROSSOVER   TRUE

Definition at line 188 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_CROSSOVER

#define DEFAULT_PRIORITY_CROSSOVER   1.0

Definition at line 189 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE

#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE   0.3

Definition at line 191 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE

#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE   0.9

Definition at line 192 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_ZEROOBJECTIVE

#define DEFAULT_ACTIVE_ZEROOBJECTIVE   TRUE

Definition at line 193 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_ZEROOBJECTIVE

#define DEFAULT_PRIORITY_ZEROOBJECTIVE   1.0

Definition at line 194 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_DINS

#define DEFAULT_MINFIXINGRATE_DINS   0.3

Definition at line 196 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_DINS

#define DEFAULT_MAXFIXINGRATE_DINS   0.9

Definition at line 197 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_DINS

#define DEFAULT_ACTIVE_DINS   TRUE

Definition at line 198 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_DINS

#define DEFAULT_PRIORITY_DINS   1.0

Definition at line 199 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MINFIXINGRATE_TRUSTREGION

#define DEFAULT_MINFIXINGRATE_TRUSTREGION   0.3

Definition at line 201 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_MAXFIXINGRATE_TRUSTREGION

#define DEFAULT_MAXFIXINGRATE_TRUSTREGION   0.9

Definition at line 202 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_ACTIVE_TRUSTREGION

#define DEFAULT_ACTIVE_TRUSTREGION   FALSE

Definition at line 203 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_PRIORITY_TRUSTREGION

#define DEFAULT_PRIORITY_TRUSTREGION   1.0

Definition at line 204 of file heur_alns.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 207 of file heur_alns.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 208 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ DEFAULT_VIOLPENALTY_TRUSTREGION

#define DEFAULT_VIOLPENALTY_TRUSTREGION   100.0

the penalty for violating the trust region

Definition at line 209 of file heur_alns.c.

Referenced by includeNeighborhoods().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "Alns"

Definition at line 212 of file heur_alns.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIP_DECL_HEUREXEC().

◆ EVENTHDLR_DESC

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

Definition at line 213 of file heur_alns.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_EVENTTYPE_ALNS

Definition at line 214 of file heur_alns.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIP_DECL_HEUREXEC().

◆ TABLE_NAME_NEIGHBORHOOD

#define TABLE_NAME_NEIGHBORHOOD   "neighborhood"

Definition at line 217 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ TABLE_DESC_NEIGHBORHOOD

#define TABLE_DESC_NEIGHBORHOOD   "ALNS neighborhood statistics"

Definition at line 218 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ TABLE_POSITION_NEIGHBORHOOD

#define TABLE_POSITION_NEIGHBORHOOD   12500

the position of the statistics table

Definition at line 219 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ 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 220 of file heur_alns.c.

Referenced by SCIPincludeHeurAlns().

◆ DECL_VARFIXINGS

#define DECL_VARFIXINGS (   x)
Value:
SCIP* scip, /**< SCIP data structure */ \
NH* neighborhood, /**< ALNS 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:186

callback to collect variable fixings of neighborhood

Definition at line 262 of file heur_alns.c.

Referenced by computeIntegerVariableBoundsDins(), DECL_NHEXIT(), DECL_NHFREE(), fixMatchingSolutionValues(), and SCIP_DECL_HEUREXEC().

◆ DECL_CHANGESUBSCIP

#define DECL_CHANGESUBSCIP (   x)
Value:
SCIP* sourcescip, /**< source SCIP data structure */\
SCIP* targetscip, /**< target SCIP data structure */\
NH* neighborhood, /**< ALNS 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:93

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 279 of file heur_alns.c.

Referenced by addLocalBranchingConstraint(), DECL_CHANGESUBSCIP(), DECL_NHFREE(), and DECL_VARFIXINGS().

◆ 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 291 of file heur_alns.c.

Referenced by DECL_NHREFSOL(), and DECL_VARFIXINGS().

◆ 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 297 of file heur_alns.c.

Referenced by DECL_NHINIT().

◆ 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 303 of file heur_alns.c.

Referenced by DECL_CHANGESUBSCIP(), DECL_NHEXIT(), and DECL_NHFREE().

◆ 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 316 of file heur_alns.c.

Referenced by DECL_CHANGESUBSCIP(), and DECL_VARFIXINGS().

◆ 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:93

callback function to deactivate neighborhoods on problems where they are irrelevant

Definition at line 324 of file heur_alns.c.

Referenced by DECL_NHDEACTIVATE(), and DECL_NHREFSOL().

◆ NHISTENTRIES

#define NHISTENTRIES   7

Definition at line 341 of file heur_alns.c.

Referenced by neighborhoodStatsReset(), and printNeighborhoodStatistics().

Typedef Documentation

◆ DATA_CROSSOVER

crossover neighborhood data structure

Definition at line 241 of file heur_alns.c.

◆ DATA_MUTATION

typedef struct data_mutation DATA_MUTATION

mutation neighborhood data structure

Definition at line 243 of file heur_alns.c.

◆ DATA_DINS

typedef struct data_dins DATA_DINS

dins neighborhood data structure

Definition at line 245 of file heur_alns.c.

◆ DATA_TRUSTREGION

trustregion neighborhood data structure

Definition at line 247 of file heur_alns.c.

◆ NH_FIXINGRATE

typedef struct NH_FixingRate NH_FIXINGRATE

Definition at line 249 of file heur_alns.c.

◆ NH_STATS

typedef struct NH_Stats NH_STATS

fixing rate data structure neighborhood statistics data structure

Definition at line 251 of file heur_alns.c.

◆ NH

typedef struct Nh NH

neighborhood data structure

Definition at line 253 of file heur_alns.c.

◆ VARPRIO

typedef struct VarPrio VARPRIO

Definition at line 259 of file heur_alns.c.

◆ HISTINDEX

typedef enum HistIndex HISTINDEX

Definition at line 340 of file heur_alns.c.

◆ SOLVELIMITS

typedef struct SolveLimits SOLVELIMITS

Definition at line 500 of file heur_alns.c.

Enumeration Type Documentation

◆ RewardType

enum RewardType

reward types of ALNS

Enumerator
REWARDTYPE_TOTAL 

combination of the other rewards

REWARDTYPE_BESTSOL 

1, if a new solution was found, 0 otherwise

REWARDTYPE_CLOSEDGAP 

0 if no solution was found, closed gap otherwise

REWARDTYPE_NOSOLPENALTY 

1 if a solution was found, otherwise between 0 and 1 depending on the effort spent

NREWARDTYPES 

Definition at line 224 of file heur_alns.c.

◆ 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

Definition at line 330 of file heur_alns.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 521 of file heur_alns.c.

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

Referenced by SCIP_DECL_HEURINIT().

◆ resetCurrentNeighborhood()

static void resetCurrentNeighborhood ( SCIP_HEURDATA heurdata)
static

reset the currently active neighborhood

Definition at line 538 of file heur_alns.c.

References NULL, and updateFixingRateIncrement().

Referenced by resetFixingRate(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEURINITSOL().

◆ updateFixingRateIncrement()

static void updateFixingRateIncrement ( NH_FIXINGRATE fx)
static

update increment for fixing rate

Parameters
fxfixing rate

Definition at line 549 of file heur_alns.c.

References FIXINGRATE_DECAY, increaseFixingRate(), NH_FixingRate::increment, LRATEMIN, and MAX.

Referenced by resetCurrentNeighborhood(), and 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 563 of file heur_alns.c.

References decreaseFixingRate(), NH_FixingRate::increment, NH_FixingRate::maxfixingrate, and NH_FixingRate::targetfixingrate.

Referenced by updateFixingRate(), and updateFixingRateIncrement().

◆ 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 576 of file heur_alns.c.

References NH_FixingRate::increment, MAX, NH_FixingRate::minfixingrate, NH_FixingRate::targetfixingrate, and updateFixingRate().

Referenced by increaseFixingRate(), and updateFixingRate().

◆ updateFixingRate()

static void updateFixingRate ( NH neighborhood,
SCIP_STATUS  subscipstatus,
NH_STATS runstats 
)
static

◆ increaseTargetNodeLimit()

static void increaseTargetNodeLimit ( SCIP_HEURDATA heurdata)
static

increase target node limit

Parameters
heurdataheuristic data

Definition at line 631 of file heur_alns.c.

References resetTargetNodeLimit(), and SCIP_Longint.

Referenced by updateFixingRate(), and updateTargetNodeLimit().

◆ resetTargetNodeLimit()

static void resetTargetNodeLimit ( SCIP_HEURDATA heurdata)
static

reset target node limit

Parameters
heurdataheuristic data

Definition at line 644 of file heur_alns.c.

References updateTargetNodeLimit().

Referenced by increaseTargetNodeLimit(), and SCIP_DECL_HEURINITSOL().

◆ updateTargetNodeLimit()

static void updateTargetNodeLimit ( SCIP_HEURDATA heurdata,
NH_STATS runstats,
SCIP_STATUS  subscipstatus 
)
static

◆ resetMinimumImprovement()

static void resetMinimumImprovement ( SCIP_HEURDATA heurdata)
static

reset the minimum improvement for the sub-SCIPs

Parameters
heurdataheuristic data

Definition at line 690 of file heur_alns.c.

References increaseMinimumImprovement(), and NULL.

Referenced by SCIP_DECL_HEURINITSOL(), and updateTargetNodeLimit().

◆ increaseMinimumImprovement()

static void increaseMinimumImprovement ( SCIP_HEURDATA heurdata)
static

increase minimum improvement for the sub-SCIPs

Parameters
heurdataheuristic data

Definition at line 700 of file heur_alns.c.

References decreaseMinimumImprovement(), MINIMPROVEFAC, and NULL.

Referenced by resetMinimumImprovement(), and updateMinimumImprovement().

◆ decreaseMinimumImprovement()

static void decreaseMinimumImprovement ( SCIP_HEURDATA heurdata)
static

decrease the minimum improvement for the sub-SCIPs

Parameters
heurdataheuristic data

Definition at line 712 of file heur_alns.c.

References MAX, MINIMPROVEFAC, NULL, SCIPdebugMessage, and updateMinimumImprovement().

Referenced by increaseMinimumImprovement(), and updateMinimumImprovement().

◆ updateMinimumImprovement()

static void updateMinimumImprovement ( SCIP_HEURDATA heurdata,
SCIP_STATUS  subscipstatus,
NH_STATS runstats 
)
static

◆ neighborhoodStatsReset()

static SCIP_RETCODE neighborhoodStatsReset ( SCIP scip,
NH_STATS stats 
)
static

◆ alnsIncludeNeighborhood()

static SCIP_RETCODE alnsIncludeNeighborhood ( SCIP scip,
SCIP_HEURDATA heurdata,
NH **  neighborhood,
const char *  name,
SCIP_Real  minfixingrate,
SCIP_Real  maxfixingrate,
SCIP_Bool  active,
SCIP_Real  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 ALNS heuristic

Parameters
scipSCIP data structure
heurdataheuristic data of the ALNS 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
prioritypositive call priority to initialize bandit algorithms

Definition at line 799 of file heur_alns.c.

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

Referenced by includeNeighborhoods(), and neighborhoodStatsReset().

◆ alnsFreeNeighborhood()

static SCIP_RETCODE alnsFreeNeighborhood ( 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 862 of file heur_alns.c.

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

Referenced by alnsIncludeNeighborhood(), and 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 893 of file heur_alns.c.

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

Referenced by alnsFreeNeighborhood(), and 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 912 of file heur_alns.c.

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

Referenced by neighborhoodInit(), and 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 930 of file heur_alns.c.

References FALSE, NH_Stats::nbestsolsfound, NH_Stats::newupperbound, NH_Stats::nsolsfound, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPcheckSol(), SCIPfreeSol(), SCIPgetBestSol(), SCIPgetCutoffbound(), SCIPgetSolTransObj(), SCIPgetUpperbound(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.

Referenced by neighborhoodExit(), and SCIP_DECL_EVENTEXEC().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecAlns  )
static

execution callback of the event handler

transfer new solutions or interrupt the solving process manually

Definition at line 1006 of file heur_alns.c.

References EVENTHDLR_NAME, initRunStats(), NULL, SCIP_CALL, SCIP_EVENTTYPE_ALNS, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_LPSOLVED, SCIP_EVENTTYPE_SOLFOUND, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), SCIPinterruptSolve(), and transferSolution().

Referenced by transferSolution().

◆ initRunStats()

static void initRunStats ( SCIP scip,
NH_STATS stats 
)
static

initialize neighborhood statistics before the next run

Parameters
scipSCIP data structure
statsrun statistics

Definition at line 1040 of file heur_alns.c.

References NH_Stats::nbestsolsfound, NH_Stats::newupperbound, NH_Stats::nfixings, NH_Stats::nsolsfound, NH_Stats::oldupperbound, SCIPgetUpperbound(), updateRunStats(), and NH_Stats::usednodes.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIP_DECL_HEUREXEC().

◆ updateRunStats()

static void updateRunStats ( NH_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 1055 of file heur_alns.c.

References getHistIndex(), NULL, SCIPgetNNodes(), SCIPisTransformed(), and NH_Stats::usednodes.

Referenced by initRunStats(), and SCIP_DECL_HEUREXEC().

◆ getHistIndex()

static int getHistIndex ( SCIP_STATUS  subscipstatus)
static

◆ printNeighborhoodStatistics()

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

◆ updateNeighborhoodStats()

static void updateNeighborhoodStats ( NH_STATS runstats,
NH neighborhood,
SCIP_STATUS  subscipstatus 
)
static

update the statistics of the neighborhood based on the sub-SCIP run

Parameters
runstatsrun statistics
neighborhoodthe selected neighborhood
subscipstatusstatus of the sub-SCIP solve

Definition at line 1167 of file heur_alns.c.

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

Referenced by printNeighborhoodStatistics(), and SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sortIndCompAlns  )
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 1207 of file heur_alns.c.

References VarPrio::distances, getVariableRedcostScore(), NULL, VarPrio::pscostscores, VarPrio::randscores, VarPrio::redcostscores, SCIP_Real, VarPrio::usedistances, VarPrio::usepscost, and VarPrio::useredcost.

Referenced by updateNeighborhoodStats().

◆ 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 1276 of file heur_alns.c.

References getVariablePscostScore(), 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 alnsFixMoreVariables(), alnsUnfixVariables(), and SCIP_DECL_SORTINDCOMP().

◆ 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 1329 of file heur_alns.c.

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

Referenced by alnsFixMoreVariables(), alnsUnfixVariables(), and getVariableRedcostScore().

◆ 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 1358 of file heur_alns.c.

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

Referenced by alnsFixMoreVariables(), DECL_VARFIXINGS(), fixMatchingSolutionValues(), and getVariablePscostScore().

◆ 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
neighborhoodALNS neighborhood data structure
solptrsolution pointer

Definition at line 1394 of file heur_alns.c.

References alnsFixMoreVariables(), NULL, SCIP_CALL, SCIP_DIDNOTFIND, and SCIP_OKAY.

Referenced by neighborhoodFixVariables(), and tryAdd2variableBuffer().

◆ alnsFixMoreVariables()

static SCIP_RETCODE alnsFixMoreVariables ( 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 ALNS 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 1428 of file heur_alns.c.

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

Referenced by neighborhoodFixVariables(), and neighborhoodGetRefsol().

◆ 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 1598 of file heur_alns.c.

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

Referenced by alnsFixMoreVariables(), and SCIP_DECL_HEURINITSOL().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyAlns  )
static

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

Definition at line 1636 of file heur_alns.c.

References alnsUnfixVariables(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurAlns().

Referenced by createBandit().

◆ alnsUnfixVariables()

static SCIP_RETCODE alnsUnfixVariables ( 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 the ALNS 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 1654 of file heur_alns.c.

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

Referenced by neighborhoodFixVariables(), and SCIP_DECL_HEURCOPY().

◆ 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 ALNS 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 1801 of file heur_alns.c.

References alnsFixMoreVariables(), alnsUnfixVariables(), FALSE, Nh::fixingrate, MAX, neighborhoodChangeSubscip(), neighborhoodGetRefsol(), NH_Stats::nfixings, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNIntVars(), and NH_FixingRate::targetfixingrate.

Referenced by alnsUnfixVariables(), and SCIP_DECL_HEUREXEC().

◆ 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 1899 of file heur_alns.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, setLimits(), and TRUE.

Referenced by neighborhoodFixVariables(), and SCIP_DECL_HEUREXEC().

◆ 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 1939 of file heur_alns.c.

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

Referenced by neighborhoodChangeSubscip(), and setupSubScip().

◆ determineLimits()

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

determine limits for a sub-SCIP

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

Definition at line 1959 of file heur_alns.c.

References FALSE, getBandit(), MAX, SolveLimits::memorylimit, SolveLimits::nodelimit, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPgetBoolParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNNodes(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisInfinity(), SolveLimits::stallnodes, and SolveLimits::timelimit.

Referenced by SCIP_DECL_HEUREXEC(), and setLimits().

◆ getBandit()

static SCIP_BANDIT* getBandit ( SCIP_HEURDATA heurdata)
static

return the bandit algorithm that should be used

Parameters
heurdataheuristic data of the ALNS neighborhood

Definition at line 2027 of file heur_alns.c.

References NULL, and selectNeighborhood().

Referenced by determineLimits(), selectNeighborhood(), and updateBanditAlgorithm().

◆ selectNeighborhood()

static SCIP_RETCODE selectNeighborhood ( SCIP scip,
SCIP_HEURDATA heurdata,
int *  neighborhoodidx 
)
static

select a neighborhood depending on the selected bandit algorithm

Parameters
scipSCIP data structure
heurdataheuristic data of the ALNS neighborhood
neighborhoodidxpointer to store the selected neighborhood index

Definition at line 2037 of file heur_alns.c.

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

Referenced by getBandit(), and SCIP_DECL_HEUREXEC().

◆ getReward()

static SCIP_RETCODE getReward ( SCIP scip,
SCIP_HEURDATA heurdata,
NH_STATS runstats,
SCIP_Real rewardptr 
)
static

Calculate reward based on the selected reward measure

Parameters
scipSCIP data structure
heurdataheuristic data of the ALNS neighborhood
runstatsrun statistics
rewardptrarray to store the computed rewards, total and individual

Definition at line 2060 of file heur_alns.c.

References MAX, NH_Stats::nbestsolsfound, NH_Stats::newupperbound, NH_Stats::nfixings, NREWARDTYPES, NULL, NH_Stats::oldupperbound, REWARDTYPE_BESTSOL, REWARDTYPE_CLOSEDGAP, REWARDTYPE_NOSOLPENALTY, REWARDTYPE_TOTAL, SCIP_OKAY, SCIP_Real, SCIPgetLowerbound(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPisEQ(), SCIPisInfinity(), updateBanditAlgorithm(), and NH_Stats::usednodes.

Referenced by SCIP_DECL_HEUREXEC(), and selectNeighborhood().

◆ updateBanditAlgorithm()

static SCIP_RETCODE updateBanditAlgorithm ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_Real  reward,
int  neighborhoodidx 
)
static

update internal bandit algorithm statistics for future draws

Parameters
scipSCIP data structure
heurdataheuristic data of the ALNS neighborhood
rewardmeasured reward
neighborhoodidxthe neighborhood that was chosen

Definition at line 2141 of file heur_alns.c.

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

Referenced by getReward(), and SCIP_DECL_HEUREXEC().

◆ setupSubScip()

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecAlns  )
static

execution method of primal heuristic

Definition at line 2315 of file heur_alns.c.

References DECL_VARFIXINGS, determineLimits(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, Nh::fixingrate, getReward(), initRunStats(), MAX, Nh::name, neighborhoodChangeSubscip(), neighborhoodFixVariables(), NH_Stats::nfixings, NNEIGHBORHOODS, SolveLimits::nodelimit, NREWARDTYPES, NH_Stats::nruns, NULL, resetCurrentNeighborhood(), REWARDTYPE_TOTAL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EVENTTYPE_ALNS, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STATUS_UNKNOWN, SCIP_SUCCESS, SCIPABORT, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetStatus(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetFreq(), SCIPheurGetNCalls(), SCIPincludeEventhdlrBasic(), SCIPisStopped(), SCIPpresolve(), SCIPprintStatistics(), SCIPsnprintf(), SCIPsolGetNodenum(), SCIPsolve(), SCIPstartClock(), SCIPstopClock(), SCIPtransformProb(), SCIPwarningMessage(), selectNeighborhood(), NH_Stats::setupclock, setupSubScip(), Nh::stats, NH_Stats::submipclock, NH_FixingRate::targetfixingrate, TRUE, updateBanditAlgorithm(), updateFixingRate(), updateMinimumImprovement(), updateNeighborhoodStats(), updateRunStats(), updateTargetNodeLimit(), and NH_Stats::usednodes.

Referenced by setupSubScip().

◆ 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 2852 of file heur_alns.c.

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

Referenced by DECL_CHANGESUBSCIP(), and 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 2966 of file heur_alns.c.

References Nh::crossover, CROSSOVERSEED, Nh::data, DECL_NHEXIT, 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 2985 of file heur_alns.c.

References Nh::crossover, Nh::data, DECL_NHFREE, 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 3000 of file heur_alns.c.

References Nh::crossover, Nh::data, DECL_VARFIXINGS, 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 3091 of file heur_alns.c.

References Nh::crossover, Nh::data, DECL_NHINIT, 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 3112 of file heur_alns.c.

References Nh::data, DECL_NHEXIT, 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 3130 of file heur_alns.c.

References Nh::data, DECL_VARFIXINGS, 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 3225 of file heur_alns.c.

References DECL_CHANGESUBSCIP, 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(), and DECL_VARFIXINGS().

◆ DECL_CHANGESUBSCIP() [2/6]

static DECL_CHANGESUBSCIP ( changeSubscipLocalbranching  )
static

callback for local branching subproblem changes

Definition at line 3291 of file heur_alns.c.

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

◆ DECL_CHANGESUBSCIP() [3/6]

static DECL_CHANGESUBSCIP ( changeSubscipProximity  )
static

callback for proximity subproblem changes

Definition at line 3301 of file heur_alns.c.

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

◆ DECL_CHANGESUBSCIP() [4/6]

static DECL_CHANGESUBSCIP ( changeSubscipZeroobjective  )
static

◆ 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 3393 of file heur_alns.c.

References DECL_VARFIXINGS, MAX, 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 3584 of file heur_alns.c.

References Nh::data, DECL_NHFREE, 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 3595 of file heur_alns.c.

References Nh::data, DECL_CHANGESUBSCIP, 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 3606 of file heur_alns.c.

References Nh::data, DECL_NHREFSOL, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddTrustregionNeighborhoodConstraint(), SCIPdebugMsg, SCIPgetBestSol(), 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 3635 of file heur_alns.c.

References DECL_NHDEACTIVATE, 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 3655 of file heur_alns.c.

References DECL_NHDEACTIVATE, 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 3668 of file heur_alns.c.

References DECL_NHDEACTIVATE, 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 3681 of file heur_alns.c.

References includeNeighborhoods(), 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 ALNS heuristic

Definition at line 3695 of file heur_alns.c.

References alnsIncludeNeighborhood(), 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, SCIP_CALL, SCIP_DECL_HEURINIT(), SCIP_OKAY, SCIP_REAL_MAX, SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, TRUE, Nh::trustregion, and data_trustregion::violpenalty.

Referenced by DECL_NHDEACTIVATE(), and SCIPincludeHeurAlns().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitAlns  )
static

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

Definition at line 3786 of file heur_alns.c.

References DEFAULT_REWARDFILENAME, Nh::fixingrate, neighborhoodInit(), neighborhoodStatsReset(), NULL, resetFixingRate(), SCIP_CALL, SCIP_DECL_HEURINITSOL(), SCIP_FILECREATEERROR, SCIP_OKAY, SCIPdebugMsg, SCIPerrorMessage, SCIPheurGetData(), and Nh::stats.

Referenced by includeNeighborhoods().

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolAlns  )
static

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitAlns  )
static

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

Definition at line 3918 of file heur_alns.c.

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

Referenced by SCIP_DECL_HEURINITSOL().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeAlns  )
static

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

Definition at line 3948 of file heur_alns.c.

References alnsFreeNeighborhood(), NNEIGHBORHOODS, NULL, SCIP_CALL, SCIP_DECL_TABLEOUTPUT(), SCIP_OKAY, SCIPfreeBandit(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPheurGetData().

Referenced by SCIP_DECL_HEUREXIT().

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputNeighborhood  )
static

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

Definition at line 3980 of file heur_alns.c.

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

Referenced by SCIP_DECL_HEURFREE().