SCIP
Solving Constraint Integer Programs
heur_alns.c File Reference
Detailed Description
Adaptive large neighborhood search heuristic that orchestrates popular LNS heuristics.
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_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 | NH_Stats |
| struct | NH_FixingRate |
| struct | Nh |
| struct | data_mutation |
| struct | data_crossover |
| struct | data_dins |
| struct | data_trustregion |
| struct | SolveLimits |
| struct | VarPrio |
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 , 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_BANDIT * | getBandit (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" |
Definition at line 78 of file heur_alns.c.
◆ HEUR_DESC
| #define HEUR_DESC "Large neighborhood search heuristic that orchestrates the popular neighborhoods Local Branching, RINS, RENS, DINS etc." |
Definition at line 79 of file heur_alns.c.
◆ HEUR_DISPCHAR
| #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 80 of file heur_alns.c.
◆ HEUR_PRIORITY
| #define HEUR_PRIORITY -1100500 |
Definition at line 81 of file heur_alns.c.
◆ HEUR_FREQ
| #define HEUR_FREQ 20 |
Definition at line 82 of file heur_alns.c.
◆ HEUR_FREQOFS
| #define HEUR_FREQOFS 0 |
Definition at line 83 of file heur_alns.c.
◆ HEUR_MAXDEPTH
| #define HEUR_MAXDEPTH -1 |
Definition at line 84 of file heur_alns.c.
◆ HEUR_TIMING
| #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_DURINGLPLOOP |
Definition at line 85 of file heur_alns.c.
◆ HEUR_USESSUBSCIP
| #define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 86 of file heur_alns.c.
◆ NNEIGHBORHOODS
| #define NNEIGHBORHOODS 9 |
Definition at line 88 of file heur_alns.c.
◆ DEFAULT_SHOWNBSTATS
| #define DEFAULT_SHOWNBSTATS FALSE |
show statistics on neighborhoods?
Definition at line 90 of file heur_alns.c.
◆ DEFAULT_NODESQUOT
| #define DEFAULT_NODESQUOT 0.1 |
Definition at line 95 of file heur_alns.c.
◆ DEFAULT_NODESQUOTMIN
| #define DEFAULT_NODESQUOTMIN 0.0 |
Definition at line 96 of file heur_alns.c.
◆ DEFAULT_NODESOFFSET
| #define DEFAULT_NODESOFFSET 500LL |
Definition at line 97 of file heur_alns.c.
◆ DEFAULT_NSOLSLIM
| #define DEFAULT_NSOLSLIM 3 |
Definition at line 98 of file heur_alns.c.
◆ DEFAULT_MINNODES
| #define DEFAULT_MINNODES 50LL |
Definition at line 99 of file heur_alns.c.
◆ DEFAULT_MAXNODES
| #define DEFAULT_MAXNODES 5000LL |
Definition at line 100 of file heur_alns.c.
◆ DEFAULT_WAITINGNODES
| #define DEFAULT_WAITINGNODES 25LL |
number of nodes since last incumbent solution that the heuristic should wait
Definition at line 101 of file heur_alns.c.
◆ DEFAULT_TARGETNODEFACTOR
| #define DEFAULT_TARGETNODEFACTOR 1.05 |
Definition at line 102 of file heur_alns.c.
◆ LRATEMIN
| #define LRATEMIN 0.01 |
lower bound for learning rate for target nodes and minimum improvement
Definition at line 103 of file heur_alns.c.
◆ LPLIMFAC
| #define LPLIMFAC 4.0 |
Definition at line 104 of file heur_alns.c.
◆ DEFAULT_INITDURINGROOT
| #define DEFAULT_INITDURINGROOT FALSE |
Definition at line 105 of file heur_alns.c.
◆ DEFAULT_MAXCALLSSAMESOL
| #define DEFAULT_MAXCALLSSAMESOL -1 |
number of allowed executions of the heuristic on the same incumbent solution
Definition at line 106 of file heur_alns.c.
◆ DEFAULT_MINIMPROVELOW
| #define DEFAULT_MINIMPROVELOW 0.01 |
Definition at line 111 of file heur_alns.c.
◆ DEFAULT_MINIMPROVEHIGH
| #define DEFAULT_MINIMPROVEHIGH 0.01 |
Definition at line 112 of file heur_alns.c.
◆ MINIMPROVEFAC
| #define MINIMPROVEFAC 1.5 |
Definition at line 113 of file heur_alns.c.
◆ DEFAULT_STARTMINIMPROVE
| #define DEFAULT_STARTMINIMPROVE 0.01 |
Definition at line 114 of file heur_alns.c.
◆ DEFAULT_ADJUSTMINIMPROVE
| #define DEFAULT_ADJUSTMINIMPROVE FALSE |
Definition at line 115 of file heur_alns.c.
◆ DEFAULT_ADJUSTTARGETNODES
| #define DEFAULT_ADJUSTTARGETNODES TRUE |
should the target nodes be dynamically adjusted?
Definition at line 116 of file heur_alns.c.
◆ DEFAULT_BESTSOLWEIGHT
| #define DEFAULT_BESTSOLWEIGHT 1 |
Definition at line 121 of file heur_alns.c.
◆ 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 122 of file heur_alns.c.
◆ 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 123 of file heur_alns.c.
◆ DEFAULT_SCALEBYEFFORT
| #define DEFAULT_SCALEBYEFFORT TRUE |
should the reward be scaled by the effort?
Definition at line 124 of file heur_alns.c.
◆ DEFAULT_RESETWEIGHTS
| #define DEFAULT_RESETWEIGHTS TRUE |
should the bandit algorithms be reset when a new problem is read?
Definition at line 125 of file heur_alns.c.
◆ DEFAULT_SUBSCIPRANDSEEDS
| #define DEFAULT_SUBSCIPRANDSEEDS FALSE |
should random seeds of sub-SCIPs be altered to increase diversification?
Definition at line 126 of file heur_alns.c.
◆ DEFAULT_REWARDBASELINE
| #define DEFAULT_REWARDBASELINE 0.5 |
the reward baseline to separate successful and failed calls
Definition at line 127 of file heur_alns.c.
◆ DEFAULT_FIXTOL
| #define DEFAULT_FIXTOL 0.1 |
tolerance by which the fixing rate may be missed without generic fixing
Definition at line 128 of file heur_alns.c.
◆ DEFAULT_UNFIXTOL
| #define DEFAULT_UNFIXTOL 0.1 |
tolerance by which the fixing rate may be exceeded without generic unfixing
Definition at line 129 of file heur_alns.c.
◆ DEFAULT_USELOCALREDCOST
| #define DEFAULT_USELOCALREDCOST FALSE |
should local reduced costs be used for generic (un)fixing?
Definition at line 130 of file heur_alns.c.
◆ DEFAULT_BETA
| #define DEFAULT_BETA 0.0 |
default reward offset between 0 and 1 at every observation for exp3
Definition at line 131 of file heur_alns.c.
◆ DEFAULT_EPS
| #define DEFAULT_EPS 0.4685844 |
increase exploration in epsilon-greedy bandit algorithm
Definition at line 137 of file heur_alns.c.
◆ DEFAULT_ALPHA
| #define DEFAULT_ALPHA 0.0016 |
parameter to increase the confidence width in UCB
Definition at line 138 of file heur_alns.c.
◆ 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 139 of file heur_alns.c.
◆ DEFAULT_USEREDCOST
| #define DEFAULT_USEREDCOST TRUE |
should reduced cost scores be used for variable priorization?
Definition at line 143 of file heur_alns.c.
◆ DEFAULT_USEPSCOST
| #define DEFAULT_USEPSCOST TRUE |
should pseudo cost scores be used for variable priorization?
Definition at line 144 of file heur_alns.c.
◆ DEFAULT_USEDISTANCES
| #define DEFAULT_USEDISTANCES TRUE |
should distances from fixed variables be used for variable priorization
Definition at line 145 of file heur_alns.c.
◆ 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 147 of file heur_alns.c.
◆ 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.
◆ FIXINGRATE_DECAY
| #define FIXINGRATE_DECAY 0.75 |
geometric decay for fixing rate adjustments
Definition at line 149 of file heur_alns.c.
◆ FIXINGRATE_STARTINC
| #define FIXINGRATE_STARTINC 0.2 |
initial increment value for fixing rate
Definition at line 150 of file heur_alns.c.
◆ 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.
◆ DEFAULT_COPYCUTS
| #define DEFAULT_COPYCUTS FALSE |
should cutting planes be copied to the sub-SCIP?
Definition at line 152 of file heur_alns.c.
◆ 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.
◆ DEFAULT_SEED
| #define DEFAULT_SEED 113 |
Definition at line 156 of file heur_alns.c.
◆ MUTATIONSEED
| #define MUTATIONSEED 121 |
Definition at line 157 of file heur_alns.c.
◆ CROSSOVERSEED
| #define CROSSOVERSEED 321 |
Definition at line 158 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_RENS
| #define DEFAULT_MINFIXINGRATE_RENS 0.3 |
Definition at line 161 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_RENS
| #define DEFAULT_MAXFIXINGRATE_RENS 0.9 |
Definition at line 162 of file heur_alns.c.
◆ DEFAULT_ACTIVE_RENS
| #define DEFAULT_ACTIVE_RENS TRUE |
Definition at line 163 of file heur_alns.c.
◆ DEFAULT_PRIORITY_RENS
| #define DEFAULT_PRIORITY_RENS 1.0 |
Definition at line 164 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_RINS
| #define DEFAULT_MINFIXINGRATE_RINS 0.3 |
Definition at line 166 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_RINS
| #define DEFAULT_MAXFIXINGRATE_RINS 0.9 |
Definition at line 167 of file heur_alns.c.
◆ DEFAULT_ACTIVE_RINS
| #define DEFAULT_ACTIVE_RINS TRUE |
Definition at line 168 of file heur_alns.c.
◆ DEFAULT_PRIORITY_RINS
| #define DEFAULT_PRIORITY_RINS 1.0 |
Definition at line 169 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_MUTATION
| #define DEFAULT_MINFIXINGRATE_MUTATION 0.3 |
Definition at line 171 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_MUTATION
| #define DEFAULT_MAXFIXINGRATE_MUTATION 0.9 |
Definition at line 172 of file heur_alns.c.
◆ DEFAULT_ACTIVE_MUTATION
| #define DEFAULT_ACTIVE_MUTATION TRUE |
Definition at line 173 of file heur_alns.c.
◆ DEFAULT_PRIORITY_MUTATION
| #define DEFAULT_PRIORITY_MUTATION 1.0 |
Definition at line 174 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_LOCALBRANCHING
| #define DEFAULT_MINFIXINGRATE_LOCALBRANCHING 0.3 |
Definition at line 176 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_LOCALBRANCHING
| #define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING 0.9 |
Definition at line 177 of file heur_alns.c.
◆ DEFAULT_ACTIVE_LOCALBRANCHING
| #define DEFAULT_ACTIVE_LOCALBRANCHING TRUE |
Definition at line 178 of file heur_alns.c.
◆ DEFAULT_PRIORITY_LOCALBRANCHING
| #define DEFAULT_PRIORITY_LOCALBRANCHING 1.0 |
Definition at line 179 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_PROXIMITY
| #define DEFAULT_MINFIXINGRATE_PROXIMITY 0.3 |
Definition at line 181 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_PROXIMITY
| #define DEFAULT_MAXFIXINGRATE_PROXIMITY 0.9 |
Definition at line 182 of file heur_alns.c.
◆ DEFAULT_ACTIVE_PROXIMITY
| #define DEFAULT_ACTIVE_PROXIMITY TRUE |
Definition at line 183 of file heur_alns.c.
◆ DEFAULT_PRIORITY_PROXIMITY
| #define DEFAULT_PRIORITY_PROXIMITY 1.0 |
Definition at line 184 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_CROSSOVER
| #define DEFAULT_MINFIXINGRATE_CROSSOVER 0.3 |
Definition at line 186 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_CROSSOVER
| #define DEFAULT_MAXFIXINGRATE_CROSSOVER 0.9 |
Definition at line 187 of file heur_alns.c.
◆ DEFAULT_ACTIVE_CROSSOVER
| #define DEFAULT_ACTIVE_CROSSOVER TRUE |
Definition at line 188 of file heur_alns.c.
◆ DEFAULT_PRIORITY_CROSSOVER
| #define DEFAULT_PRIORITY_CROSSOVER 1.0 |
Definition at line 189 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE
| #define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE 0.3 |
Definition at line 191 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE
| #define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE 0.9 |
Definition at line 192 of file heur_alns.c.
◆ DEFAULT_ACTIVE_ZEROOBJECTIVE
| #define DEFAULT_ACTIVE_ZEROOBJECTIVE TRUE |
Definition at line 193 of file heur_alns.c.
◆ DEFAULT_PRIORITY_ZEROOBJECTIVE
| #define DEFAULT_PRIORITY_ZEROOBJECTIVE 1.0 |
Definition at line 194 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_DINS
| #define DEFAULT_MINFIXINGRATE_DINS 0.3 |
Definition at line 196 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_DINS
| #define DEFAULT_MAXFIXINGRATE_DINS 0.9 |
Definition at line 197 of file heur_alns.c.
◆ DEFAULT_ACTIVE_DINS
| #define DEFAULT_ACTIVE_DINS TRUE |
Definition at line 198 of file heur_alns.c.
◆ DEFAULT_PRIORITY_DINS
| #define DEFAULT_PRIORITY_DINS 1.0 |
Definition at line 199 of file heur_alns.c.
◆ DEFAULT_MINFIXINGRATE_TRUSTREGION
| #define DEFAULT_MINFIXINGRATE_TRUSTREGION 0.3 |
Definition at line 201 of file heur_alns.c.
◆ DEFAULT_MAXFIXINGRATE_TRUSTREGION
| #define DEFAULT_MAXFIXINGRATE_TRUSTREGION 0.9 |
Definition at line 202 of file heur_alns.c.
◆ DEFAULT_ACTIVE_TRUSTREGION
| #define DEFAULT_ACTIVE_TRUSTREGION FALSE |
Definition at line 203 of file heur_alns.c.
◆ DEFAULT_PRIORITY_TRUSTREGION
| #define DEFAULT_PRIORITY_TRUSTREGION 1.0 |
Definition at line 204 of file heur_alns.c.
◆ 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.
◆ 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.
◆ 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.
◆ EVENTHDLR_NAME
| #define EVENTHDLR_NAME "Alns" |
Definition at line 212 of file heur_alns.c.
◆ EVENTHDLR_DESC
| #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 213 of file heur_alns.c.
◆ SCIP_EVENTTYPE_ALNS
| #define SCIP_EVENTTYPE_ALNS (SCIP_EVENTTYPE_LPSOLVED | SCIP_EVENTTYPE_SOLFOUND | SCIP_EVENTTYPE_BESTSOLFOUND) |
Definition at line 214 of file heur_alns.c.
◆ TABLE_NAME_NEIGHBORHOOD
| #define TABLE_NAME_NEIGHBORHOOD "neighborhood" |
Definition at line 217 of file heur_alns.c.
◆ TABLE_DESC_NEIGHBORHOOD
| #define TABLE_DESC_NEIGHBORHOOD "ALNS neighborhood statistics" |
Definition at line 218 of file heur_alns.c.
◆ TABLE_POSITION_NEIGHBORHOOD
| #define TABLE_POSITION_NEIGHBORHOOD 12500 |
the position of the statistics table
Definition at line 219 of file heur_alns.c.
◆ 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.
◆ DECL_VARFIXINGS
| #define DECL_VARFIXINGS | ( | x | ) |
Value:
SCIP_RETCODE x ( \
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 */ \
)
Definition: objbenders.h:44
Definition: heur_alns.c:371
Definition: struct_var.h:208
Definition: struct_scip.h:70
callback to collect variable fixings of neighborhood
Definition at line 261 of file heur_alns.c.
◆ DECL_CHANGESUBSCIP
| #define DECL_CHANGESUBSCIP | ( | x | ) |
Value:
SCIP_RETCODE x ( \
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 */\
)
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 278 of file heur_alns.c.
◆ DECL_NHINIT
| #define DECL_NHINIT | ( | x | ) |
Value:
optional initialization callback for neighborhoods when a new problem is read
Definition at line 290 of file heur_alns.c.
◆ DECL_NHEXIT
| #define DECL_NHEXIT | ( | x | ) |
Value:
deinitialization callback for neighborhoods when exiting a problem
Definition at line 296 of file heur_alns.c.
◆ DECL_NHFREE
| #define DECL_NHFREE | ( | x | ) |
Value:
deinitialization callback for neighborhoods before SCIP is freed
Definition at line 302 of file heur_alns.c.
◆ DECL_NHREFSOL
| #define DECL_NHREFSOL | ( | x | ) |
Value:
SCIP_RETCODE x ( \
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 */ \
)
Definition: struct_sol.h:74
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 315 of file heur_alns.c.
◆ DECL_NHDEACTIVATE
| #define DECL_NHDEACTIVATE | ( | x | ) |
Value:
SCIP_RETCODE x (\
SCIP_Bool* deactivate /**< pointer to store whether the neighborhood should be deactivated (TRUE) for an instance */ \
)
callback function to deactivate neighborhoods on problems where they are irrelevant
Definition at line 323 of file heur_alns.c.
◆ NHISTENTRIES
| #define NHISTENTRIES 7 |
Definition at line 340 of file heur_alns.c.
Typedef Documentation
◆ DATA_CROSSOVER
| typedef struct data_crossover DATA_CROSSOVER |
crossover neighborhood data structure
Definition at line 240 of file heur_alns.c.
◆ DATA_MUTATION
| typedef struct data_mutation DATA_MUTATION |
mutation neighborhood data structure
Definition at line 242 of file heur_alns.c.
◆ DATA_DINS
dins neighborhood data structure
Definition at line 244 of file heur_alns.c.
◆ DATA_TRUSTREGION
| typedef struct data_trustregion DATA_TRUSTREGION |
trustregion neighborhood data structure
Definition at line 246 of file heur_alns.c.
◆ NH_FIXINGRATE
| typedef struct NH_FixingRate NH_FIXINGRATE |
Definition at line 248 of file heur_alns.c.
◆ NH_STATS
fixing rate data structure neighborhood statistics data structure
Definition at line 250 of file heur_alns.c.
◆ NH
neighborhood data structure
Definition at line 252 of file heur_alns.c.
◆ VARPRIO
Definition at line 258 of file heur_alns.c.
◆ HISTINDEX
Definition at line 339 of file heur_alns.c.
◆ SOLVELIMITS
| typedef struct SolveLimits SOLVELIMITS |
Definition at line 499 of file heur_alns.c.
Enumeration Type Documentation
◆ RewardType
| enum RewardType |
reward types of ALNS
Definition at line 223 of file heur_alns.c.
◆ HistIndex
| enum HistIndex |
sub-SCIP status code enumerator
Definition at line 329 of file heur_alns.c.
Function Documentation
◆ resetFixingRate()
|
static |
Reset target fixing rate
- Parameters
-
scip SCIP data structure fixingrate heuristic fixing rate
Definition at line 520 of file heur_alns.c.
References FIXINGRATE_STARTINC, NH_FixingRate::increment, NH_FixingRate::maxfixingrate, NULL, SCIP_OKAY, and NH_FixingRate::targetfixingrate.
Referenced by SCIP_DECL_HEURINIT().
◆ resetCurrentNeighborhood()
|
static |
reset the currently active neighborhood
Definition at line 537 of file heur_alns.c.
References NULL.
Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEURINITSOL().
◆ updateFixingRateIncrement()
|
static |
update increment for fixing rate
- Parameters
-
fx fixing rate
Definition at line 548 of file heur_alns.c.
References FIXINGRATE_DECAY, NH_FixingRate::increment, LRATEMIN, and MAX.
Referenced by updateFixingRate().
◆ increaseFixingRate()
|
static |
increase fixing rate
decrease also the rate by which the target fixing rate is adjusted
- Parameters
-
fx fixing rate
Definition at line 562 of file heur_alns.c.
References NH_FixingRate::increment, NH_FixingRate::maxfixingrate, MIN, and NH_FixingRate::targetfixingrate.
Referenced by updateFixingRate().
◆ decreaseFixingRate()
|
static |
decrease fixing rate
decrease also the rate by which the target fixing rate is adjusted
- Parameters
-
fx fixing rate
Definition at line 575 of file heur_alns.c.
References NH_FixingRate::increment, MAX, NH_FixingRate::minfixingrate, and NH_FixingRate::targetfixingrate.
Referenced by updateFixingRate().
◆ updateFixingRate()
|
static |
update fixing rate based on the results of the current run
- Parameters
-
neighborhood neighborhood subscipstatus status of the sub-SCIP run runstats run statistics for this run
Definition at line 585 of file heur_alns.c.
References decreaseFixingRate(), Nh::fixingrate, increaseFixingRate(), NH_Stats::nbestsolsfound, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, and updateFixingRateIncrement().
Referenced by SCIP_DECL_HEUREXEC().
◆ increaseTargetNodeLimit()
|
static |
increase target node limit
- Parameters
-
heurdata heuristic data
Definition at line 632 of file heur_alns.c.
References SCIP_Longint.
Referenced by updateTargetNodeLimit().
◆ resetTargetNodeLimit()
|
static |
reset target node limit
- Parameters
-
heurdata heuristic data
Definition at line 645 of file heur_alns.c.
Referenced by SCIP_DECL_HEURINITSOL().
◆ updateTargetNodeLimit()
|
static |
update target node limit based on the current run results
- Parameters
-
heurdata heuristic data runstats statistics of the run subscipstatus status of the sub-SCIP run
Definition at line 654 of file heur_alns.c.
References increaseTargetNodeLimit(), NH_Stats::nbestsolsfound, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, and SCIP_STATUS_USERINTERRUPT.
Referenced by SCIP_DECL_HEUREXEC().
◆ resetMinimumImprovement()
|
static |
reset the minimum improvement for the sub-SCIPs
- Parameters
-
heurdata heuristic data
Definition at line 691 of file heur_alns.c.
References NULL.
Referenced by SCIP_DECL_HEURINITSOL().
◆ increaseMinimumImprovement()
|
static |
increase minimum improvement for the sub-SCIPs
- Parameters
-
heurdata heuristic data
Definition at line 701 of file heur_alns.c.
References MIN, MINIMPROVEFAC, and NULL.
Referenced by updateMinimumImprovement().
◆ decreaseMinimumImprovement()
|
static |
decrease the minimum improvement for the sub-SCIPs
- Parameters
-
heurdata heuristic data
Definition at line 713 of file heur_alns.c.
References MAX, MINIMPROVEFAC, NULL, and SCIPdebugMessage.
Referenced by updateMinimumImprovement().
◆ updateMinimumImprovement()
|
static |
update the minimum improvement based on the status of the sub-SCIP
- Parameters
-
heurdata heuristic data subscipstatus status of the sub-SCIP run runstats run statistics for this run
Definition at line 726 of file heur_alns.c.
References decreaseMinimumImprovement(), increaseMinimumImprovement(), NH_Stats::nbestsolsfound, NULL, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, and SCIP_STATUS_USERINTERRUPT.
Referenced by SCIP_DECL_HEUREXEC().
◆ neighborhoodStatsReset()
|
static |
Reset neighborhood statistics
- Parameters
-
scip SCIP data structure stats neighborhood statistics
Definition at line 777 of file heur_alns.c.
References BMSclearMemoryArray, NH_Stats::nbestsolsfound, NH_Stats::nfixings, NHISTENTRIES, NH_Stats::nruns, NH_Stats::nrunsbestsol, NH_Stats::nsolsfound, NULL, SCIP_CALL, SCIP_OKAY, SCIPresetClock(), NH_Stats::setupclock, NH_Stats::statushist, NH_Stats::submipclock, and NH_Stats::usednodes.
Referenced by SCIP_DECL_HEURINIT().
◆ alnsIncludeNeighborhood()
|
static |
create a neighborhood of the specified name and include it into the ALNS heuristic
- Parameters
-
scip SCIP data structure heurdata heuristic data of the ALNS heuristic neighborhood pointer to store the neighborhood name name for this neighborhood minfixingrate default value for minfixingrate parameter of this neighborhood maxfixingrate default value for maxfixingrate parameter of this neighborhood active default value for active parameter of this neighborhood priority positive call priority to initialize bandit algorithms
Definition at line 802 of file heur_alns.c.
References active, BMSduplicateMemoryArray, NULL, paramname, SCIP_ALLOC, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPcreateClock(), SCIPsnprintf(), and TRUE.
Referenced by includeNeighborhoods().
◆ alnsFreeNeighborhood()
|
static |
release all data and free neighborhood
- Parameters
-
scip SCIP data structure neighborhood pointer to neighborhood that should be freed
Definition at line 865 of file heur_alns.c.
References BMSfreeMemoryArray, Nh::name, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeClock(), NH_Stats::setupclock, Nh::stats, and NH_Stats::submipclock.
Referenced by SCIP_DECL_HEURFREE().
◆ neighborhoodInit()
|
static |
initialize neighborhood specific data
- Parameters
-
scip SCIP data structure neighborhood neighborhood to initialize
Definition at line 896 of file heur_alns.c.
References NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by SCIP_DECL_HEURINIT().
◆ neighborhoodExit()
|
static |
deinitialize neighborhood specific data
- Parameters
-
scip SCIP data structure neighborhood neighborhood to initialize
Definition at line 915 of file heur_alns.c.
References NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by SCIP_DECL_HEUREXIT().
◆ transferSolution()
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
- Parameters
-
subscip SCIP data structure of the subproblem eventdata event handler data
Definition at line 933 of file heur_alns.c.
References FALSE, NH_Stats::nbestsolsfound, NH_Stats::newupperbound, NH_Stats::nsolsfound, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcheckSol(), SCIPfreeSol(), SCIPgetBestSol(), SCIPgetCutoffbound(), SCIPgetSolTransObj(), SCIPgetUpperbound(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.
Referenced by SCIP_DECL_EVENTEXEC().
◆ SCIP_DECL_EVENTEXEC()
|
static |
execution callback of the event handler
transfer new solutions or interrupt the solving process manually
Definition at line 1009 of file heur_alns.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_ALNS, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_LPSOLVED, SCIP_EVENTTYPE_SOLFOUND, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), SCIPinterruptSolve(), and transferSolution().
◆ initRunStats()
initialize neighborhood statistics before the next run
- Parameters
-
scip SCIP data structure stats run statistics
Definition at line 1043 of file heur_alns.c.
References NH_Stats::nbestsolsfound, NH_Stats::newupperbound, NH_Stats::nfixings, NH_Stats::nsolsfound, NH_Stats::oldupperbound, SCIPgetUpperbound(), and NH_Stats::usednodes.
Referenced by SCIP_DECL_HEUREXEC().
◆ updateRunStats()
update run stats after the sub SCIP was solved
- Parameters
-
stats run statistics subscip sub-SCIP instance, or NULL
Definition at line 1058 of file heur_alns.c.
References NULL, SCIPgetNNodes(), SCIPisTransformed(), and NH_Stats::usednodes.
Referenced by SCIP_DECL_HEUREXEC().
◆ getHistIndex()
|
static |
get the histogram index for this status
- Parameters
-
subscipstatus sub-SCIP status
Definition at line 1072 of file heur_alns.c.
References HIDX_INFEAS, HIDX_NODELIM, HIDX_OPT, HIDX_OTHER, HIDX_SOLLIM, HIDX_STALLNODE, HIDX_USR, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, and SCIP_STATUS_USERINTERRUPT.
Referenced by updateNeighborhoodStats().
◆ printNeighborhoodStatistics()
|
static |
print neighborhood statistics
- Parameters
-
scip SCIP data structure heurdata heuristic data file file handle, or NULL for standard out
Definition at line 1098 of file heur_alns.c.
References Nh::fixingrate, HIDX_INFEAS, HIDX_NODELIM, HIDX_OPT, HIDX_OTHER, HIDX_SOLLIM, HIDX_STALLNODE, HIDX_USR, Nh::name, NH_Stats::nbestsolsfound, NHISTENTRIES, NH_Stats::nruns, NH_Stats::nsolsfound, NULL, SCIP_LONGINT_FORMAT, SCIP_Real, SCIPgetClockTime(), SCIPgetConfidenceBoundUcb(), SCIPgetProbabilityExp3(), SCIPgetProbabilityExp3IX(), SCIPgetWeightsEpsgreedy(), SCIPinfoMessage(), NH_Stats::setupclock, Nh::stats, NH_Stats::statushist, NH_Stats::submipclock, NH_FixingRate::targetfixingrate, and NH_Stats::usednodes.
Referenced by SCIP_DECL_TABLEOUTPUT().
◆ updateNeighborhoodStats()
|
static |
update the statistics of the neighborhood based on the sub-SCIP run
- Parameters
-
runstats run statistics neighborhood the selected neighborhood subscipstatus status of the sub-SCIP solve
Definition at line 1176 of file heur_alns.c.
References DEFAULT_BESTSOLWEIGHT, getHistIndex(), NH_Stats::nbestsolsfound, NH_Stats::nruns, NH_Stats::nrunsbestsol, NH_Stats::nsolsfound, Nh::stats, NH_Stats::statushist, and NH_Stats::usednodes.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_SORTINDCOMP()
|
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 1216 of file heur_alns.c.
References VarPrio::distances, NULL, VarPrio::pscostscores, VarPrio::randscores, VarPrio::redcostscores, VarPrio::usedistances, VarPrio::usepscost, and VarPrio::useredcost.
◆ getVariableRedcostScore()
|
static |
Compute the reduced cost score for this variable in the reference solution
- Parameters
-
scip SCIP data structure var the variable for which the score should be computed refsolval solution value in reference solution uselocalredcost should local reduced costs be used for generic (un)fixing?
Definition at line 1285 of file heur_alns.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 alnsFixMoreVariables(), and alnsUnfixVariables().
◆ getVariablePscostScore()
|
static |
get the pseudo cost score of this variable with respect to the reference solution
- Parameters
-
scip SCIP data structure var the variable for which the score should be computed refsolval solution value in reference solution uselocallpsol should local LP solution be used?
Definition at line 1338 of file heur_alns.c.
References NULL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPgetVarPseudocostVal(), SCIPisEQ(), SCIPvarGetLPSol(), SCIPvarGetRootSol(), and SCIPvarGetStatus().
Referenced by alnsFixMoreVariables(), and alnsUnfixVariables().
◆ tryAdd2variableBuffer()
|
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
-
scip SCIP data structure var (source) SCIP variable that should be added to the buffer val fixing value for this variable varbuf variable buffer to store variables that should be fixed valbuf value buffer to store fixing values nfixings pointer to number of fixed buffer variables, will be increased by 1 integer is this an integer variable?
Definition at line 1367 of file heur_alns.c.
References SCIPfloor(), SCIPgetNVars(), SCIPisFeasIntegral(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and SCIPvarIsIntegral().
Referenced by alnsFixMoreVariables(), DECL_VARFIXINGS(), and fixMatchingSolutionValues().
◆ neighborhoodGetRefsol()
|
static |
query neighborhood for a reference solution for further fixings
- Parameters
-
scip SCIP data structure neighborhood ALNS neighborhood data structure solptr solution pointer
Definition at line 1403 of file heur_alns.c.
References NULL, SCIP_CALL, SCIP_DIDNOTFIND, and SCIP_OKAY.
Referenced by neighborhoodFixVariables().
◆ alnsFixMoreVariables()
|
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
-
scip SCIP data structure heurdata heuristic data of the ALNS neighborhood refsol feasible reference solution for more variable fixings varbuf buffer array to store variables to fix valbuf buffer array to store fixing values nfixings pointer to store the number of fixings ntargetfixings number of required target fixings success pointer to store whether the target fixings have been successfully reached
Definition at line 1437 of file heur_alns.c.
References b, BMSclearMemoryArray, VarPrio::distances, FALSE, getVariablePscostScore(), getVariableRedcostScore(), MIN, 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().
◆ createBandit()
|
static |
create the bandit algorithm for the heuristic depending on the user parameter
- Parameters
-
scip SCIP data structure heurdata heuristic data structure priorities call priorities for active neighborhoods initseed initial random seed
Definition at line 1607 of file heur_alns.c.
References FALSE, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPcreateBanditEpsgreedy(), SCIPcreateBanditExp3(), SCIPcreateBanditExp3IX(), SCIPcreateBanditUcb(), and SCIPerrorMessage.
Referenced by SCIP_DECL_HEURINITSOL().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1650 of file heur_alns.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurAlns().
◆ alnsUnfixVariables()
|
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
-
scip SCIP data structure heurdata heuristic data of the ALNS neighborhood varbuf buffer array to store variables to fix valbuf buffer array to store fixing values nfixings pointer to store the number of fixings ntargetfixings number of required target fixings success pointer to store whether the target fixings have been successfully reached
Definition at line 1668 of file heur_alns.c.
References BMSclearMemoryArray, VarPrio::distances, FALSE, getVariablePscostScore(), getVariableRedcostScore(), 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().
◆ neighborhoodFixVariables()
|
static |
call variable fixing callback for this neighborhood and orchestrate additional variable fixings, if necessary
- Parameters
-
scip SCIP data structure heurdata heuristic data of the ALNS neighborhood neighborhood neighborhood data structure varbuf buffer array to keep variables that should be fixed valbuf buffer array to keep fixing values nfixings pointer to store the number of variable fixings result pointer to store the result of the fixing operation
Definition at line 1815 of file heur_alns.c.
References alnsFixMoreVariables(), alnsUnfixVariables(), FALSE, Nh::fixingrate, 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 SCIP_DECL_HEUREXEC().
◆ neighborhoodChangeSubscip()
|
static |
change the sub-SCIP by restricting variable domains, changing objective coefficients, or adding constraints
- Parameters
-
sourcescip source SCIP data structure targetscip target SCIP data structure neighborhood neighborhood targetvars array of target SCIP variables aligned with source SCIP variables ndomchgs pointer to store the number of variable domain changes nchgobjs pointer to store the number of changed objective coefficients naddedconss pointer to store the number of added constraints success pointer to store whether the sub-SCIP has been successfully modified
Definition at line 1913 of file heur_alns.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ setLimits()
|
static |
set sub-SCIP solving limits
- Parameters
-
subscip SCIP data structure solvelimits pointer to solving limits data structure
Definition at line 1953 of file heur_alns.c.
References SolveLimits::memorylimit, SolveLimits::nodelimit, NULL, SCIP_CALL, SCIP_OKAY, SCIPsetLongintParam(), SCIPsetRealParam(), SolveLimits::stallnodes, and SolveLimits::timelimit.
Referenced by setupSubScip().
◆ determineLimits()
|
static |
determine limits for a sub-SCIP
- Parameters
-
scip SCIP data structure heur this heuristic solvelimits pointer to solving limits data structure runagain can we solve another sub-SCIP with these limits
Definition at line 1973 of file heur_alns.c.
References FALSE, MAX, SolveLimits::memorylimit, MIN, 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().
◆ getBandit()
|
static |
return the bandit algorithm that should be used
- Parameters
-
heurdata heuristic data of the ALNS neighborhood
Definition at line 2041 of file heur_alns.c.
References NULL.
Referenced by selectNeighborhood(), and updateBanditAlgorithm().
◆ selectNeighborhood()
|
static |
select a neighborhood depending on the selected bandit algorithm
- Parameters
-
scip SCIP data structure heurdata heuristic data of the ALNS neighborhood neighborhoodidx pointer to store the selected neighborhood index
Definition at line 2051 of file heur_alns.c.
References getBandit(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPbanditSelect().
Referenced by SCIP_DECL_HEUREXEC().
◆ getReward()
|
static |
Calculate reward based on the selected reward measure
- Parameters
-
scip SCIP data structure heurdata heuristic data of the ALNS neighborhood runstats run statistics rewardptr array to store the computed rewards, total and individual
Definition at line 2074 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(), and NH_Stats::usednodes.
Referenced by SCIP_DECL_HEUREXEC().
◆ updateBanditAlgorithm()
|
static |
update internal bandit algorithm statistics for future draws
- Parameters
-
scip SCIP data structure heurdata heuristic data of the ALNS neighborhood reward measured reward neighborhoodidx the neighborhood that was chosen
Definition at line 2155 of file heur_alns.c.
References getBandit(), NULL, SCIP_CALL, SCIP_OKAY, SCIPbanditUpdate(), and SCIPdebugMsg.
Referenced by SCIP_DECL_HEUREXEC().
◆ setupSubScip()
|
static |
set up the sub-SCIP parameters, objective cutoff, and solution limits
- Parameters
-
scip SCIP data structure subscip sub-SCIP data structure subvars array of sub-SCIP variables in the order of the main SCIP solvelimits pointer to solving limits data structure heur this heuristic objchgd did the objective change between the source and the target SCIP?
Definition at line 2178 of file heur_alns.c.
References FALSE, MIN, SolveLimits::nodelimit, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIP_REAL_FORMAT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPfloor(), SCIPgetLowerbound(), SCIPgetNVars(), SCIPgetUpperbound(), SCIPgetVars(), SCIPheurGetData(), SCIPheurGetNCalls(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisObjIntegral(), SCIPisParamFixed(), SCIPreleaseCons(), SCIPretransformObj(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsumepsilon(), SCIPvarGetObj(), setLimits(), SolveLimits::stallnodes, SolveLimits::timelimit, and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 2329 of file heur_alns.c.
References 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_LONGINT_FORMAT, 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.
◆ DECL_VARFIXINGS() [1/5]
|
static |
callback to collect variable fixings of RENS
Definition at line 2744 of file heur_alns.c.
References Nh::fixingrate, MIN, NULL, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPfrac(), SCIPfreeBufferArray, SCIPgetLPSolstat(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPisFeasIntegral(), SCIPround(), SCIPsortDownRealInt(), SCIPvarGetLPSol(), SCIPvarIsBinary(), SCIPvarIsIntegral(), NH_FixingRate::targetfixingrate, TRUE, and tryAdd2variableBuffer().
◆ DECL_CHANGESUBSCIP() [1/6]
|
static |
callback for RENS subproblem changes
Definition at line 2820 of file heur_alns.c.
References NULL, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPfloor(), SCIPgetLPSolstat(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPisFeasIntegral(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
◆ fixMatchingSolutionValues()
|
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
-
scip SCIP data structure sols array of 2 or more solutions. It is okay for the array to contain one element equal to NULL to represent the current LP solution nsols number of solutions in the array vars variable array for which solution values must agree nvars number of variables, or -1 for all binary and integer variables varbuf buffer storage for variable fixings valbuf buffer storage for fixing values nfixings pointer to store the number of fixings
Definition at line 2866 of file heur_alns.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]
|
static |
callback to collect variable fixings of RINS
Definition at line 2932 of file heur_alns.c.
References fixMatchingSolutionValues(), NULL, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_SOLORIGIN_ORIGINAL, SCIP_SUCCESS, SCIPgetBestSol(), SCIPgetLPSolstat(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), and SCIPsolGetOrigin().
◆ DECL_NHINIT() [1/2]
|
static |
initialization callback for crossover when a new problem is read
Definition at line 2980 of file heur_alns.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 |
deinitialization callback for crossover when exiting a problem
Definition at line 2999 of file heur_alns.c.
References Nh::crossover, Nh::data, NULL, data_crossover::rng, SCIP_OKAY, and SCIPfreeRandom().
◆ DECL_NHFREE() [1/3]
|
static |
deinitialization callback for crossover before SCIP is freed
Definition at line 3014 of file heur_alns.c.
References Nh::crossover, Nh::data, NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
◆ DECL_VARFIXINGS() [3/5]
|
static |
callback to collect variable fixings of crossover
Definition at line 3024 of file heur_alns.c.
References Nh::crossover, Nh::data, fixMatchingSolutionValues(), data_crossover::nsols, NULL, data_crossover::rng, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNSols(), SCIPgetSols(), SCIPrandomGetInt(), and data_crossover::selsol.
◆ DECL_NHREFSOL() [1/2]
|
static |
callback for crossover reference solution
Definition at line 3105 of file heur_alns.c.
References Nh::crossover, Nh::data, NULL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, and data_crossover::selsol.
◆ DECL_NHINIT() [2/2]
|
static |
initialization callback for mutation when a new problem is read
Definition at line 3126 of file heur_alns.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 |
deinitialization callback for mutation when exiting a problem
Definition at line 3144 of file heur_alns.c.
References Nh::data, Nh::mutation, NULL, data_mutation::rng, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeRandom().
◆ DECL_VARFIXINGS() [4/5]
|
static |
callback to collect variable fixings of mutation
Definition at line 3161 of file heur_alns.c.
References Nh::data, Nh::fixingrate, Nh::mutation, NULL, data_mutation::rng, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPrandomGetInt(), SCIPswapPointers(), NH_FixingRate::targetfixingrate, TRUE, and tryAdd2variableBuffer().
◆ addLocalBranchingConstraint()
|
static |
add local branching constraint
- Parameters
-
sourcescip source SCIP data structure targetscip target SCIP data structure subvars array of sub SCIP variables in same order as source SCIP variables distance right hand side of the local branching constraint success pointer to store of a local branching constraint has been successfully added naddedconss pointer to increase the number of added constraints
Definition at line 3239 of file heur_alns.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 |
callback for local branching subproblem changes
Definition at line 3305 of file heur_alns.c.
References addLocalBranchingConstraint(), SCIP_CALL, SCIP_OKAY, and SCIPgetNBinVars().
◆ DECL_CHANGESUBSCIP() [3/6]
|
static |
callback for proximity subproblem changes
Definition at line 3315 of file heur_alns.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObj(), SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetVarsData(), and TRUE.
◆ DECL_CHANGESUBSCIP() [4/6]
|
static |
callback for zeroobjective subproblem changes
Definition at line 3367 of file heur_alns.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPchgVarObj(), SCIPconshdlrGetNActiveConss(), SCIPfindConshdlr(), SCIPgetNObjVars(), SCIPgetVarsData(), and TRUE.
◆ computeIntegerVariableBoundsDins()
|
static |
compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ
- Parameters
-
scip SCIP data structure of the original problem var the variable for which bounds should be computed lbptr pointer to store the lower bound in the DINS sub-SCIP ubptr pointer to store the upper bound in the DINS sub-SCIP
Definition at line 3407 of file heur_alns.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]
|
static |
callback to collect variable fixings of DINS
Definition at line 3481 of file heur_alns.c.
References BMScopyMemoryArray, computeIntegerVariableBoundsDins(), Nh::data, Nh::dins, fixMatchingSolutionValues(), MIN, data_dins::npoolsols, NULL, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetLPSolstat(), SCIPgetNSols(), SCIPgetSols(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPsetSolVal(), SCIPvarGetRootSol(), TRUE, and tryAdd2variableBuffer().
◆ DECL_CHANGESUBSCIP() [5/6]
|
static |
callback for DINS subproblem changes
Definition at line 3562 of file heur_alns.c.
References addLocalBranchingConstraint(), computeIntegerVariableBoundsDins(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPgetNBinVars(), SCIPgetVarsData(), and TRUE.
◆ DECL_NHFREE() [2/3]
|
static |
deinitialization callback for DINS before SCIP is freed
Definition at line 3598 of file heur_alns.c.
References Nh::data, Nh::dins, NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
◆ DECL_NHFREE() [3/3]
|
static |
deinitialization callback for trustregion before SCIP is freed
Definition at line 3609 of file heur_alns.c.
References Nh::data, NULL, SCIP_OKAY, SCIPfreeBlockMemory, and Nh::trustregion.
◆ DECL_CHANGESUBSCIP() [6/6]
|
static |
add trust region neighborhood constraint and auxiliary objective variable
Definition at line 3620 of file heur_alns.c.
References Nh::data, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddTrustregionNeighborhoodConstraint(), SCIPdebugMsg, SCIPgetBestSol(), Nh::trustregion, and data_trustregion::violpenalty.
◆ DECL_NHREFSOL() [2/2]
|
static |
callback that returns the incumbent solution as a reference point
Definition at line 3649 of file heur_alns.c.
References NULL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, and SCIPgetBestSol().
◆ DECL_NHDEACTIVATE() [1/3]
|
static |
callback function that deactivates a neighborhood on problems with no discrete variables
Definition at line 3669 of file heur_alns.c.
References NULL, SCIP_OKAY, SCIPgetNBinVars(), and SCIPgetNIntVars().
◆ DECL_NHDEACTIVATE() [2/3]
|
static |
callback function that deactivates a neighborhood on problems with no binary variables
Definition at line 3682 of file heur_alns.c.
References NULL, SCIP_OKAY, and SCIPgetNBinVars().
◆ DECL_NHDEACTIVATE() [3/3]
|
static |
callback function that deactivates a neighborhood on problems with no objective variables
Definition at line 3695 of file heur_alns.c.
References NULL, SCIP_OKAY, and SCIPgetNObjVars().
◆ includeNeighborhoods()
|
static |
include all neighborhoods
- Parameters
-
scip SCIP data structure heurdata heuristic data of the ALNS heuristic
Definition at line 3709 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_OKAY, SCIP_REAL_MAX, SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, TRUE, Nh::trustregion, and data_trustregion::violpenalty.
Referenced by SCIPincludeHeurAlns().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 3800 of file heur_alns.c.
References DEFAULT_REWARDFILENAME, Nh::fixingrate, neighborhoodInit(), neighborhoodStatsReset(), NULL, resetFixingRate(), SCIP_CALL, SCIP_FILECREATEERROR, SCIP_OKAY, SCIPdebugMsg, SCIPerrorMessage, SCIPheurGetData(), and Nh::stats.
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 3848 of file heur_alns.c.
References Nh::active, createBandit(), NULL, resetCurrentNeighborhood(), resetMinimumImprovement(), resetTargetNodeLimit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbanditGetNActions(), SCIPfreeBandit(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPheurGetData(), SCIPresetBandit(), and SCIPswapPointers().
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 3932 of file heur_alns.c.
References neighborhoodExit(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 3962 of file heur_alns.c.
References alnsFreeNeighborhood(), NNEIGHBORHOODS, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBandit(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPheurGetData().
◆ SCIP_DECL_TABLEOUTPUT()
|
static |
output method of statistics table to output file stream 'file'
Definition at line 3994 of file heur_alns.c.
References HEUR_NAME, NULL, printNeighborhoodStatistics(), SCIP_OKAY, SCIPfindHeur(), and SCIPheurGetData().