heur_alns.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*    Copyright (C) 2002-2021 Konrad-Zuse-Zentrum                            */
/*                            fuer Informationstechnik Berlin                */
/*                                                                           */
/*  SCIP is distributed under the terms of the ZIB Academic License.         */
/*                                                                           */
/*  You should have received a copy of the ZIB Academic License              */
/*  along with SCIP; see the file COPYING. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**@file   heur_alns.c
 * @ingroup DEFPLUGINS_HEUR
 * @brief  Adaptive large neighborhood search heuristic that orchestrates popular LNS heuristics
 * @author Gregor Hendel
 */

/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/

#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_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>

#if !defined(_WIN32) && !defined(_WIN64)
#include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */
#endif

#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
#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */

#define NNEIGHBORHOODS 9

/*
 * limit parameters for sub-SCIPs
 */
#define DEFAULT_NODESQUOT        0.1
#define DEFAULT_NODESOFFSET      500LL
#define DEFAULT_NSOLSLIM         3
#define DEFAULT_MINNODES         50LL
#define DEFAULT_MAXNODES         5000LL
#define DEFAULT_WAITINGNODES     25LL  /**< number of nodes since last incumbent solution that the heuristic should wait */
#define DEFAULT_TARGETNODEFACTOR 1.05
#define LRATEMIN                 0.01 /**<  lower bound for learning rate for target nodes and minimum improvement */
#define LPLIMFAC                 4.0

/*
 * parameters for the minimum improvement
 */
#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 /**< should the target nodes be dynamically adjusted? */

/*
 * bandit algorithm parameters
 */
#define DEFAULT_BESTSOLWEIGHT  1
#define DEFAULT_BANDITALGO     'u'  /**< the default bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy */
#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 */
#define DEFAULT_SCALEBYEFFORT  TRUE /**< should the reward be scaled by the effort? */
#define DEFAULT_RESETWEIGHTS   TRUE /**< should the bandit algorithms be reset when a new problem is read? */
#define DEFAULT_SUBSCIPRANDSEEDS FALSE /**< should random seeds of sub-SCIPs be altered to increase diversification? */
#define DEFAULT_REWARDBASELINE 0.5  /**< the reward baseline to separate successful and failed calls */
#define DEFAULT_FIXTOL         0.1  /**< tolerance by which the fixing rate may be missed without generic fixing */
#define DEFAULT_UNFIXTOL       0.1  /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
#define DEFAULT_USELOCALREDCOST FALSE /**< should local reduced costs be used for generic (un)fixing? */
#define DEFAULT_BETA           0.0  /**< default reward offset between 0 and 1 at every observation for exp3 */

/*
 * the following 3 parameters have been tuned by a simulation experiment
 * as described in the paper.
 */
#define DEFAULT_EPS            0.4685844   /**< increase exploration in epsilon-greedy bandit algorithm */
#define DEFAULT_ALPHA          0.0016      /**< parameter to increase the confidence width in UCB */
#define DEFAULT_GAMMA          0.07041455  /**< default weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
/*
 * parameters to control variable fixing
 */
#define DEFAULT_USEREDCOST       TRUE  /**< should reduced cost scores be used for variable priorization? */
#define DEFAULT_USEPSCOST        TRUE  /**< should pseudo cost scores be used for variable priorization? */
#define DEFAULT_USEDISTANCES     TRUE  /**< should distances from fixed variables be used for variable priorization */
#define DEFAULT_DOMOREFIXINGS    TRUE  /**< should the ALNS heuristic do more fixings by itself based on variable prioritization
                                         *  until the target fixing rate is reached? */
#define DEFAULT_ADJUSTFIXINGRATE TRUE  /**< should the heuristic adjust the target fixing rate based on the success? */
#define FIXINGRATE_DECAY         0.75  /**< geometric decay for fixing rate adjustments */
#define FIXINGRATE_STARTINC      0.2   /**< initial increment value for fixing rate */
#define DEFAULT_USESUBSCIPHEURS  FALSE /**< should the heuristic activate other sub-SCIP heuristics during its search?  */
#define DEFAULT_COPYCUTS         FALSE /**< should cutting planes be copied to the sub-SCIP? */
#define DEFAULT_REWARDFILENAME   "-"   /**< file name to store all rewards and the selection of the bandit */

/* individual random seeds */
#define DEFAULT_SEED 113
#define MUTATIONSEED 121
#define CROSSOVERSEED 321

/* individual neighborhood parameters */
#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 /**< parameter for the number of solutions that crossover should combine */
#define DEFAULT_NPOOLSOLS_DINS  5 /**< number of pool solutions where binary solution values must agree */
#define DEFAULT_VIOLPENALTY_TRUSTREGION 100.0  /**< the penalty for violating the trust region */

/* event handler properties */
#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)

/* properties of the ALNS neighborhood statistics table */
#define TABLE_NAME_NEIGHBORHOOD                  "neighborhood"
#define TABLE_DESC_NEIGHBORHOOD                  "ALNS neighborhood statistics"
#define TABLE_POSITION_NEIGHBORHOOD              12500                  /**< the position of the statistics table */
#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD        SCIP_STAGE_TRANSFORMED /**< output of the statistics table is only printed from this stage onwards */

/*
 * Data structures
 */

/*
 * additional neighborhood data structures
 */


typedef struct data_crossover DATA_CROSSOVER; /**< crossover neighborhood data structure */

typedef struct data_mutation DATA_MUTATION; /**< mutation neighborhood data structure */

typedef struct data_dins DATA_DINS; /**< dins neighborhood data structure */

typedef struct data_trustregion DATA_TRUSTREGION; /**< trustregion neighborhood data structure */

typedef struct NH_FixingRate NH_FIXINGRATE; /** fixing rate data structure */

typedef struct NH_Stats NH_STATS; /**< neighborhood statistics data structure */

typedef struct Nh NH;             /**< neighborhood data structure */


/*
 * variable priorization data structure for sorting
 */
typedef struct VarPrio VARPRIO;

/** callback to collect variable fixings of neighborhood */
 #define DECL_VARFIXINGS(x) SCIP_RETCODE x ( \
   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 */                          \
   )

/** 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 \p success pointer to indicate whether it was successful with its modifications or not.
 */
#define DECL_CHANGESUBSCIP(x) 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 */\
   )

/** optional initialization callback for neighborhoods when a new problem is read */
#define DECL_NHINIT(x) SCIP_RETCODE x (                                          \
   SCIP*                 scip,               /**< SCIP data structure */         \
   NH*                   neighborhood        /**< neighborhood data structure */ \
   )

/** deinitialization callback for neighborhoods when exiting a problem */
#define DECL_NHEXIT(x) SCIP_RETCODE x ( \
   SCIP*                 scip,               /**< SCIP data structure */         \
   NH*                   neighborhood        /**< neighborhood data structure */ \
   )

/** deinitialization callback for neighborhoods before SCIP is freed */
#define DECL_NHFREE(x) SCIP_RETCODE x (      \
   SCIP*                 scip,               /**< SCIP data structure */         \
   NH*                   neighborhood        /**< neighborhood data structure */ \
   )

/** callback function to return a feasible reference solution for further fixings
 *
 *  The reference solution should be stored in the \p solptr.
 *  The \p result pointer can be used to indicate either
 *
 *  - SCIP_SUCCESS or
 *  - SCIP_DIDNOTFIND
 */
#define DECL_NHREFSOL(x) SCIP_RETCODE x (                                       \
   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 */ \
   )

/** callback function to deactivate neighborhoods on problems where they are irrelevant */
#define DECL_NHDEACTIVATE(x) SCIP_RETCODE x (\
   SCIP*                 scip,               /**< SCIP data structure */  \
   SCIP_Bool*            deactivate          /**< pointer to store whether the neighborhood should be deactivated (TRUE) for an instance */ \
   )

/** sub-SCIP status code enumerator */
enum HistIndex
{
   HIDX_OPT              = 0,                /**< sub-SCIP was solved to optimality  */
   HIDX_USR              = 1,                /**< sub-SCIP was user interrupted */
   HIDX_NODELIM          = 2,                /**< sub-SCIP reached the node limit */
   HIDX_STALLNODE        = 3,                /**< sub-SCIP reached the stall node limit */
   HIDX_INFEAS           = 4,                /**< sub-SCIP was infeasible */
   HIDX_SOLLIM           = 5,                /**< sub-SCIP reached the solution limit */
   HIDX_OTHER            = 6                 /**< sub-SCIP reached none of the above codes */
};
typedef enum HistIndex HISTINDEX;
#define NHISTENTRIES 7


/** statistics for a neighborhood */
struct NH_Stats
{
   SCIP_CLOCK*           setupclock;         /**< clock for sub-SCIP setup time */
   SCIP_CLOCK*           submipclock;        /**< clock for the sub-SCIP solve */
   SCIP_Longint          usednodes;          /**< total number of used nodes */
   SCIP_Real             oldupperbound;      /**< upper bound before the sub-SCIP started */
   SCIP_Real             newupperbound;      /**< new upper bound for allrewards mode to work correctly */
   int                   nruns;              /**< number of runs of a neighborhood */
   int                   nrunsbestsol;       /**< number of runs that produced a new incumbent */
   SCIP_Longint          nsolsfound;         /**< the total number of solutions found */
   SCIP_Longint          nbestsolsfound;     /**< the total number of improving solutions found */
   int                   nfixings;           /**< the number of fixings in one run */
   int                   statushist[NHISTENTRIES]; /**< array to count sub-SCIP statuses */
};


/** fixing rate data structure to control the amount of target fixings of a neighborhood */
struct NH_FixingRate
{
   SCIP_Real             minfixingrate;      /**< the minimum fixing rate */
   SCIP_Real             targetfixingrate;   /**< the current target fixing rate */
   SCIP_Real             increment;          /**< the current increment by which the target fixing rate is in-/decreased */
   SCIP_Real             maxfixingrate;      /**< the maximum fixing rate */
};

/** neighborhood data structure with callbacks, statistics, fixing rate */
struct Nh
{
   char*                 name;               /**< the name of this neighborhood */
   NH_FIXINGRATE         fixingrate;         /**< fixing rate for this neighborhood */
   NH_STATS              stats;              /**< statistics for this neighborhood */
   DECL_VARFIXINGS       ((*varfixings));    /**< variable fixings callback for this neighborhood */
   DECL_CHANGESUBSCIP    ((*changesubscip)); /**< callback for subproblem changes other than variable fixings */
   DECL_NHINIT           ((*nhinit));        /**< initialization callback when a new problem is read */
   DECL_NHEXIT           ((*nhexit));        /**< deinitialization callback when exiting a problem */
   DECL_NHFREE           ((*nhfree));        /**< deinitialization callback before SCIP is freed */
   DECL_NHREFSOL         ((*nhrefsol));      /**< callback function to return a reference solution for further fixings, or NULL */
   DECL_NHDEACTIVATE     ((*nhdeactivate));  /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if it is always active */
   SCIP_Bool             active;             /**< is this neighborhood active or not? */
   SCIP_Real             priority;           /**< positive call priority to initialize bandit algorithms */
   union
   {
      DATA_MUTATION*     mutation;           /**< mutation data */
      DATA_CROSSOVER*    crossover;          /**< crossover data */
      DATA_DINS*         dins;               /**< dins data */
      DATA_TRUSTREGION*  trustregion;        /**< trustregion data */
   }                     data;               /**< data object for neighborhood specific data */
};

/** mutation neighborhood data structure */
struct data_mutation
{
   SCIP_RANDNUMGEN*      rng;                /**< random number generator */
};

/** crossover neighborhood data structure */
struct data_crossover
{
   int                   nsols;              /**< the number of solutions that crossover should combine */
   SCIP_RANDNUMGEN*      rng;                /**< random number generator to draw from the solution pool */
   SCIP_SOL*             selsol;             /**< best selected solution by crossover as reference point */
};

/** dins neighborhood data structure */
struct data_dins
{
   int                   npoolsols;          /**< number of pool solutions where binary solution values must agree */
};

struct data_trustregion
{
   SCIP_Real             violpenalty;        /**< the penalty for violating the trust region */
};

/** primal heuristic data */
struct SCIP_HeurData
{
   NH**                  neighborhoods;      /**< array of neighborhoods */
   SCIP_BANDIT*          bandit;             /**< bandit algorithm */
   char*                 rewardfilename;     /**< file name to store all rewards and the selection of the bandit */
   FILE*                 rewardfile;         /**< reward file pointer, or NULL */
   SCIP_Longint          nodesoffset;        /**< offset added to the nodes budget */
   SCIP_Longint          maxnodes;           /**< maximum number of nodes in a single sub-SCIP */
   SCIP_Longint          targetnodes;        /**< targeted number of nodes to start a sub-SCIP */
   SCIP_Longint          minnodes;           /**< minimum number of nodes required to start a sub-SCIP */
   SCIP_Longint          usednodes;          /**< total number of nodes already spent in sub-SCIPs */
   SCIP_Longint          waitingnodes;       /**< number of nodes since last incumbent solution that the heuristic should wait */
   SCIP_Real             nodesquot;          /**< fraction of nodes compared to the main SCIP for budget computation */
   SCIP_Real             startminimprove;    /**< initial factor by which ALNS should at least improve the incumbent */
   SCIP_Real             minimprovelow;      /**< lower threshold for the minimal improvement over the incumbent */
   SCIP_Real             minimprovehigh;     /**< upper bound for the minimal improvement over the incumbent */
   SCIP_Real             minimprove;         /**< factor by which ALNS should at least improve the incumbent */
   SCIP_Real             lplimfac;           /**< limit fraction of LPs per node to interrupt sub-SCIP */
   SCIP_Real             exp3_gamma;         /**< weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
   SCIP_Real             exp3_beta;          /**< reward offset between 0 and 1 at every observation for exp3 */
   SCIP_Real             epsgreedy_eps;      /**< increase exploration in epsilon-greedy bandit algorithm */
   SCIP_Real             ucb_alpha;          /**< parameter to increase the confidence width in UCB */
   SCIP_Real             rewardcontrol;      /**< reward control to increase the weight of the simple solution indicator
                                               *  and decrease the weight of the closed gap reward */
   SCIP_Real             targetnodefactor;   /**< factor by which target node number is eventually increased */
   SCIP_Real             rewardbaseline;     /**< the reward baseline to separate successful and failed calls */
   SCIP_Real             fixtol;             /**< tolerance by which the fixing rate may be missed without generic fixing */
   SCIP_Real             unfixtol;           /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
   int                   nneighborhoods;     /**< number of neighborhoods */
   int                   nactiveneighborhoods;/**< number of active neighborhoods */
   int                   ninitneighborhoods; /**< neighborhoods that were used at least one time */
   int                   nsolslim;           /**< limit on the number of improving solutions in a sub-SCIP call */
   int                   seed;               /**< initial random seed for bandit algorithms and random decisions by neighborhoods */
   int                   currneighborhood;   /**< index of currently selected neighborhood */
   int                   ndelayedcalls;      /**< the number of delayed calls */
   char                  banditalgo;         /**< the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy */
   SCIP_Bool             useredcost;         /**< should reduced cost scores be used for variable prioritization? */
   SCIP_Bool             usedistances;       /**< should distances from fixed variables be used for variable prioritization */
   SCIP_Bool             usepscost;          /**< should pseudo cost scores be used for variable prioritization? */
   SCIP_Bool             domorefixings;      /**< should the ALNS heuristic do more fixings by itself based on variable prioritization
                                               *  until the target fixing rate is reached? */
   SCIP_Bool             adjustfixingrate;   /**< should the heuristic adjust the target fixing rate based on the success? */
   SCIP_Bool             usesubscipheurs;    /**< should the heuristic activate other sub-SCIP heuristics during its search?  */
   SCIP_Bool             adjustminimprove;   /**< should the factor by which the minimum improvement is bound be dynamically updated? */
   SCIP_Bool             adjusttargetnodes;  /**< should the target nodes be dynamically adjusted? */
   SCIP_Bool             resetweights;       /**< should the bandit algorithms be reset when a new problem is read? */
   SCIP_Bool             subsciprandseeds;   /**< should random seeds of sub-SCIPs be altered to increase diversification? */
   SCIP_Bool             scalebyeffort;      /**< should the reward be scaled by the effort? */
   SCIP_Bool             copycuts;           /**< should cutting planes be copied to the sub-SCIP? */
   SCIP_Bool             uselocalredcost;    /**< should local reduced costs be used for generic (un)fixing? */
};

/** event handler data */
struct SCIP_EventData
{
   SCIP_VAR**            subvars;            /**< the variables of the subproblem */
   SCIP*                 sourcescip;         /**< original SCIP data structure */
   SCIP_HEUR*            heur;               /**< alns heuristic structure */
   SCIP_Longint          nodelimit;          /**< node limit of the run */
   SCIP_Real             lplimfac;           /**< limit fraction of LPs per node to interrupt sub-SCIP */
   NH_STATS*             runstats;           /**< run statistics for the current neighborhood */
   SCIP_Bool             allrewardsmode;     /**< true if solutions should only be checked for reward comparisons */
};

/** represents limits for the sub-SCIP solving process */
struct SolveLimits
{
   SCIP_Longint          nodelimit;          /**< maximum number of solving nodes for the sub-SCIP */
   SCIP_Real             memorylimit;        /**< memory limit for the sub-SCIP */
   SCIP_Real             timelimit;          /**< time limit for the sub-SCIP */
   SCIP_Longint          stallnodes;         /**< maximum number of nodes without (primal) stalling */
};

typedef struct SolveLimits SOLVELIMITS;

/** data structure that can be used for variable prioritization for additional fixings */
struct VarPrio
{
   SCIP*                 scip;               /**< SCIP data structure */
   SCIP_Real*            randscores;         /**< random scores for prioritization */
   int*                  distances;          /**< breadth-first distances from already fixed variables */
   SCIP_Real*            redcostscores;      /**< reduced cost scores for fixing a variable to a reference value */
   SCIP_Real*            pscostscores;       /**< pseudocost scores for fixing a variable to a reference value */
   unsigned int          useredcost:1;       /**< should reduced cost scores be used for variable prioritization? */
   unsigned int          usedistances:1;     /**< should distances from fixed variables be used for variable prioritization */
   unsigned int          usepscost:1;        /**< should pseudo cost scores be used for variable prioritization? */
};

/*
 * Local methods
 */

/** Reset target fixing rate */
static
SCIP_RETCODE resetFixingRate(
   SCIP*                 scip,               /**< SCIP data structure */
   NH_FIXINGRATE*        fixingrate          /**< heuristic fixing rate */
   )
{
   assert(scip != NULL);
   assert(fixingrate != NULL);
   fixingrate->increment = FIXINGRATE_STARTINC;

   /* always start with the most conservative value */
   fixingrate->targetfixingrate = fixingrate->maxfixingrate;

   return SCIP_OKAY;
}

/** reset the currently active neighborhood */
static
void resetCurrentNeighborhood(
   SCIP_HEURDATA*        heurdata
   )
{
   assert(heurdata != NULL);
   heurdata->currneighborhood = -1;
   heurdata->ndelayedcalls = 0;
}

/** update increment for fixing rate */
static
void updateFixingRateIncrement(
   NH_FIXINGRATE*        fx                  /**< fixing rate */
   )
{
   fx->increment *= FIXINGRATE_DECAY;
   fx->increment = MAX(fx->increment, LRATEMIN);
}


/** increase fixing rate
 *
 *  decrease also the rate by which the target fixing rate is adjusted
 */
static
void increaseFixingRate(
   NH_FIXINGRATE*        fx                  /**< fixing rate */
   )
{
   fx->targetfixingrate += fx->increment;
   fx->targetfixingrate = MIN(fx->targetfixingrate, fx->maxfixingrate);
}

/** decrease fixing rate
 *
 *  decrease also the rate by which the target fixing rate is adjusted
 */
static
void decreaseFixingRate(
   NH_FIXINGRATE*        fx                  /**< fixing rate */
   )
{
   fx->targetfixingrate -= fx->increment;
   fx->targetfixingrate = MAX(fx->targetfixingrate, fx->minfixingrate);
}

/** update fixing rate based on the results of the current run */
static
void updateFixingRate(
   NH*                   neighborhood,       /**< neighborhood */
   SCIP_STATUS           subscipstatus,      /**< status of the sub-SCIP run */
   NH_STATS*             runstats            /**< run statistics for this run */
   )
{
   NH_FIXINGRATE* fx;

   fx = &neighborhood->fixingrate;

   switch (subscipstatus)
   {
   case SCIP_STATUS_OPTIMAL:
   case SCIP_STATUS_INFEASIBLE:
   case SCIP_STATUS_INFORUNBD:
   case SCIP_STATUS_SOLLIMIT:
   case SCIP_STATUS_BESTSOLLIMIT:
      /* decrease the fixing rate (make subproblem harder) */
      decreaseFixingRate(fx);
      break;
   case SCIP_STATUS_STALLNODELIMIT:
   case SCIP_STATUS_USERINTERRUPT:
   case SCIP_STATUS_TERMINATE:
   case SCIP_STATUS_NODELIMIT:
      /* increase the fixing rate (make the subproblem easier) only if no solution was found */
      if( runstats->nbestsolsfound <= 0 )
         increaseFixingRate(fx);
      break;
      /* fall through cases to please lint */
   case SCIP_STATUS_UNKNOWN:
   case SCIP_STATUS_TOTALNODELIMIT:
   case SCIP_STATUS_TIMELIMIT:
   case SCIP_STATUS_MEMLIMIT:
   case SCIP_STATUS_GAPLIMIT:
   case SCIP_STATUS_RESTARTLIMIT:
   case SCIP_STATUS_UNBOUNDED:
   default:
      break;
   }

   updateFixingRateIncrement(fx);
}

/** increase target node limit */
static
void increaseTargetNodeLimit(
   SCIP_HEURDATA*        heurdata            /**< heuristic data */
   )
{
   heurdata->targetnodes = (SCIP_Longint)(heurdata->targetnodes * heurdata->targetnodefactor) + 1;

   /* respect upper and lower parametrized bounds on targetnodes */
   if( heurdata->targetnodes > heurdata->maxnodes )
      heurdata->targetnodes = heurdata->maxnodes;
}

/** reset target node limit */
static
void resetTargetNodeLimit(
   SCIP_HEURDATA*        heurdata            /**< heuristic data */
   )
{
   heurdata->targetnodes = heurdata->minnodes;
}

/** update target node limit based on the current run results */
static
void updateTargetNodeLimit(
   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
   NH_STATS*             runstats,           /**< statistics of the run */
   SCIP_STATUS           subscipstatus       /**< status of the sub-SCIP run */
   )
{
   switch (subscipstatus)
   {
   case SCIP_STATUS_STALLNODELIMIT:
   case SCIP_STATUS_NODELIMIT:
      /* the subproblem could be explored more */
      if( runstats->nbestsolsfound == 0 )
         increaseTargetNodeLimit(heurdata);
      break;
   case SCIP_STATUS_OPTIMAL:
   case SCIP_STATUS_INFEASIBLE:
   case SCIP_STATUS_INFORUNBD:
   case SCIP_STATUS_SOLLIMIT:
   case SCIP_STATUS_BESTSOLLIMIT:
      break;
   case SCIP_STATUS_USERINTERRUPT:
   case SCIP_STATUS_TERMINATE:
   case SCIP_STATUS_UNKNOWN:
   case SCIP_STATUS_TOTALNODELIMIT:
   case SCIP_STATUS_TIMELIMIT:
   case SCIP_STATUS_MEMLIMIT:
   case SCIP_STATUS_GAPLIMIT:
   case SCIP_STATUS_RESTARTLIMIT:
   case SCIP_STATUS_UNBOUNDED:
      break;
   default:
      break;
   }
}

/** reset the minimum improvement for the sub-SCIPs */
static
void resetMinimumImprovement(
   SCIP_HEURDATA*        heurdata            /**< heuristic data */
   )
{
   assert(heurdata != NULL);
   heurdata->minimprove = heurdata->startminimprove;
}

/** increase minimum improvement for the sub-SCIPs */
static
void increaseMinimumImprovement(
   SCIP_HEURDATA*        heurdata            /**< heuristic data */
   )
{
   assert(heurdata != NULL);

   heurdata->minimprove *= MINIMPROVEFAC;
   heurdata->minimprove = MIN(heurdata->minimprove, heurdata->minimprovehigh);
}

/** decrease the minimum improvement for the sub-SCIPs */
static
void decreaseMinimumImprovement(
   SCIP_HEURDATA*        heurdata            /**< heuristic data */
   )
{
   assert(heurdata != NULL);

   heurdata->minimprove /= MINIMPROVEFAC;
   SCIPdebugMessage("%.4f", heurdata->minimprovelow);
   heurdata->minimprove = MAX(heurdata->minimprove, heurdata->minimprovelow);
}

/** update the minimum improvement based on the status of the sub-SCIP */
static
void updateMinimumImprovement(
   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
   SCIP_STATUS           subscipstatus,      /**< status of the sub-SCIP run */
   NH_STATS*             runstats            /**< run statistics for this run */
   )
{
   assert(heurdata != NULL);

   /* if the sub-SCIP status was infeasible, we rather want to make the sub-SCIP easier
    * with a smaller minimum improvement.
    *
    * If a solution limit was reached, we may, set it higher.
    */
   switch (subscipstatus)
   {
   case SCIP_STATUS_INFEASIBLE:
   case SCIP_STATUS_INFORUNBD:
      /* subproblem was infeasible, probably due to the minimum improvement -> decrease minimum improvement */
      decreaseMinimumImprovement(heurdata);

      break;
   case SCIP_STATUS_SOLLIMIT:
   case SCIP_STATUS_BESTSOLLIMIT:
   case SCIP_STATUS_OPTIMAL:
      /* subproblem could be optimally solved -> try higher minimum improvement */
      increaseMinimumImprovement(heurdata);
      break;
   case SCIP_STATUS_NODELIMIT:
   case SCIP_STATUS_STALLNODELIMIT:
   case SCIP_STATUS_USERINTERRUPT:
      /* subproblem was too hard, decrease minimum improvement */
      if( runstats->nbestsolsfound <= 0 )
         decreaseMinimumImprovement(heurdata);
      break;
   case SCIP_STATUS_UNKNOWN:
   case SCIP_STATUS_TOTALNODELIMIT:
   case SCIP_STATUS_TIMELIMIT:
   case SCIP_STATUS_MEMLIMIT:
   case SCIP_STATUS_GAPLIMIT:
   case SCIP_STATUS_RESTARTLIMIT:
   case SCIP_STATUS_UNBOUNDED:
   case SCIP_STATUS_TERMINATE:
   default:
      break;
   }
}

/** Reset neighborhood statistics */
static
SCIP_RETCODE neighborhoodStatsReset(
   SCIP*                 scip,               /**< SCIP data structure */
   NH_STATS*             stats               /**< neighborhood statistics */
   )
{
   assert(scip != NULL);
   assert(stats != NULL);

   stats->nbestsolsfound = 0;
   stats->nruns = 0;
   stats->nrunsbestsol = 0;
   stats->nsolsfound = 0;
   stats->usednodes = 0L;
   stats->nfixings = 0L;

   BMSclearMemoryArray(stats->statushist, NHISTENTRIES);

   SCIP_CALL( SCIPresetClock(scip, stats->setupclock) );
   SCIP_CALL( SCIPresetClock(scip, stats->submipclock) );

   return SCIP_OKAY;
}

/** create a neighborhood of the specified name and include it into the ALNS heuristic */
static
SCIP_RETCODE alnsIncludeNeighborhood(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS heuristic */
   NH**                  neighborhood,       /**< pointer to store the neighborhood */
   const char*           name,               /**< name for this neighborhood */
   SCIP_Real             minfixingrate,      /**< default value for minfixingrate parameter of this neighborhood */
   SCIP_Real             maxfixingrate,      /**< default value for maxfixingrate parameter of this neighborhood */
   SCIP_Bool             active,             /**< default value for active parameter of this neighborhood */
   SCIP_Real             priority,           /**< positive call priority to initialize bandit algorithms */
   DECL_VARFIXINGS       ((*varfixings)),    /**< variable fixing callback for this neighborhood, or NULL */
   DECL_CHANGESUBSCIP    ((*changesubscip)), /**< subscip changes callback for this neighborhood, or NULL */
   DECL_NHINIT           ((*nhinit)),        /**< initialization callback for neighborhood, or NULL */
   DECL_NHEXIT           ((*nhexit)),        /**< deinitialization callback for neighborhood, or NULL */
   DECL_NHFREE           ((*nhfree)),        /**< deinitialization callback before SCIP is freed, or NULL */
   DECL_NHREFSOL         ((*nhrefsol)),      /**< callback function to return a reference solution for further fixings, or NULL */
   DECL_NHDEACTIVATE     ((*nhdeactivate))   /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if neighborhood is always active */
   )
{
   char paramname[SCIP_MAXSTRLEN];

   assert(scip != NULL);
   assert(heurdata != NULL);
   assert(neighborhood != NULL);
   assert(name != NULL);

   SCIP_CALL( SCIPallocBlockMemory(scip, neighborhood) );
   assert(*neighborhood != NULL);

   SCIP_ALLOC( BMSduplicateMemoryArray(&(*neighborhood)->name, name, strlen(name)+1) );

   SCIP_CALL( SCIPcreateClock(scip, &(*neighborhood)->stats.setupclock) );
   SCIP_CALL( SCIPcreateClock(scip, &(*neighborhood)->stats.submipclock) );

   (*neighborhood)->changesubscip = changesubscip;
   (*neighborhood)->varfixings = varfixings;
   (*neighborhood)->nhinit = nhinit;
   (*neighborhood)->nhexit = nhexit;
   (*neighborhood)->nhfree = nhfree;
   (*neighborhood)->nhrefsol = nhrefsol;
   (*neighborhood)->nhdeactivate = nhdeactivate;

   /* add parameters for this neighborhood */
   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/minfixingrate", name);
   SCIP_CALL( SCIPaddRealParam(scip, paramname, "minimum fixing rate for this neighborhood",
         &(*neighborhood)->fixingrate.minfixingrate, TRUE, minfixingrate, 0.0, 1.0, NULL, NULL) );
   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/maxfixingrate", name);
   SCIP_CALL( SCIPaddRealParam(scip, paramname, "maximum fixing rate for this neighborhood",
         &(*neighborhood)->fixingrate.maxfixingrate, TRUE, maxfixingrate, 0.0, 1.0, NULL, NULL) );
   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/active", name);
   SCIP_CALL( SCIPaddBoolParam(scip, paramname, "is this neighborhood active?",
         &(*neighborhood)->active, TRUE, active, NULL, NULL) );
   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/priority", name);
   SCIP_CALL( SCIPaddRealParam(scip, paramname, "positive call priority to initialize bandit algorithms",
         &(*neighborhood)->priority, TRUE, priority, 1e-2, 1.0, NULL, NULL) );

   /* add the neighborhood to the ALNS heuristic */
   heurdata->neighborhoods[heurdata->nneighborhoods++] = (*neighborhood);

   return SCIP_OKAY;
}

/** release all data and free neighborhood */
static
SCIP_RETCODE alnsFreeNeighborhood(
   SCIP*                 scip,               /**< SCIP data structure */
   NH**                  neighborhood        /**< pointer to neighborhood that should be freed */
   )
{
   NH* nhptr;
   assert(scip != NULL);
   assert(neighborhood != NULL);

   nhptr = *neighborhood;
   assert(nhptr != NULL);

   BMSfreeMemoryArray(&nhptr->name);

   /* release further, neighborhood specific data structures */
   if( nhptr->nhfree != NULL )
   {
      SCIP_CALL( nhptr->nhfree(scip, nhptr) );
   }

   SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.setupclock) );
   SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.submipclock) );

   SCIPfreeBlockMemory(scip, neighborhood);
   *neighborhood = NULL;

   return SCIP_OKAY;
}

/** initialize neighborhood specific data */
static
SCIP_RETCODE neighborhoodInit(
   SCIP*                 scip,               /**< SCIP data structure */
   NH*                   neighborhood        /**< neighborhood to initialize */
   )
{
   assert(scip != NULL);
   assert(neighborhood != NULL);

   /* call the init callback of the neighborhood */
   if( neighborhood->nhinit != NULL )
   {
      SCIP_CALL( neighborhood->nhinit(scip, neighborhood) );
   }

   return SCIP_OKAY;
}

/** deinitialize neighborhood specific data */
static
SCIP_RETCODE neighborhoodExit(
   SCIP*                 scip,               /**< SCIP data structure */
   NH*                   neighborhood        /**< neighborhood to initialize */
   )
{
   assert(scip != NULL);
   assert(neighborhood != NULL);

   if( neighborhood->nhexit != NULL )
   {
      SCIP_CALL( neighborhood->nhexit(scip, neighborhood) );
   }

   return SCIP_OKAY;
}

/** creates a new solution for the original problem by copying the solution of the subproblem */
static
SCIP_RETCODE transferSolution(
   SCIP*                 subscip,            /**< SCIP data structure of the subproblem */
   SCIP_EVENTDATA*       eventdata           /**< event handler data */
   )
{
   SCIP*      sourcescip;         /* original SCIP data structure */
   SCIP_VAR** subvars;            /* the variables of the subproblem */
   SCIP_HEUR* heur;               /* alns heuristic structure */
   SCIP_SOL*  subsol;             /* solution of the subproblem */
   SCIP_SOL*  newsol;             /* solution to be created for the original problem */
   SCIP_Bool  success;
   NH_STATS*  runstats;
   SCIP_SOL*  oldbestsol;

   assert(subscip != NULL);

   subsol = SCIPgetBestSol(subscip);
   assert(subsol != NULL);

   sourcescip = eventdata->sourcescip;
   subvars = eventdata->subvars;
   heur = eventdata->heur;
   runstats = eventdata->runstats;
   assert(sourcescip != NULL);
   assert(sourcescip != subscip);
   assert(heur != NULL);
   assert(subvars != NULL);
   assert(runstats != NULL);

   SCIP_CALL( SCIPtranslateSubSol(sourcescip, subscip, subsol, heur, subvars, &newsol) );

   oldbestsol = SCIPgetBestSol(sourcescip);

   /* in the special, experimental all rewards mode, the solution is only checked for feasibility
    * but not stored
    */
   if( eventdata->allrewardsmode )
   {
      SCIP_CALL( SCIPcheckSol(sourcescip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );

      if( success )
      {
         runstats->nsolsfound++;
         if( SCIPgetSolTransObj(sourcescip, newsol) < SCIPgetCutoffbound(sourcescip) )
            runstats->nbestsolsfound++;
      }

      SCIP_CALL( SCIPfreeSol(sourcescip, &newsol) );
   }
   else
   {
      /* try to add new solution to scip and free it immediately */
      SCIP_CALL( SCIPtrySolFree(sourcescip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );

      if( success )
      {
         runstats->nsolsfound++;
         if( SCIPgetBestSol(sourcescip) != oldbestsol )
            runstats->nbestsolsfound++;
      }
   }

   /* update new upper bound for reward later */
   runstats->newupperbound = SCIPgetUpperbound(sourcescip);

   return SCIP_OKAY;
}


/* ---------------- Callback methods of event handler ---------------- */

/** execution callback of the event handler
 *
 * transfer new solutions or interrupt the solving process manually
 */
static
SCIP_DECL_EVENTEXEC(eventExecAlns)
{
   assert(eventhdlr != NULL);
   assert(eventdata != NULL);
   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
   assert(event != NULL);
   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_ALNS);
   assert(eventdata != NULL);

   /* treat the different atomic events */
   switch( SCIPeventGetType(event) )
   {
   case SCIP_EVENTTYPE_SOLFOUND:
   case SCIP_EVENTTYPE_BESTSOLFOUND:
      /* try to transfer the solution to the original SCIP */
      SCIP_CALL( transferSolution(scip, eventdata) );
      break;
   case SCIP_EVENTTYPE_LPSOLVED:
      /* interrupt solution process of sub-SCIP */
      if( SCIPgetNLPs(scip) > eventdata->lplimfac * eventdata->nodelimit )
      {
         SCIPdebugMsg(scip, "interrupt after  %" SCIP_LONGINT_FORMAT " LPs\n", SCIPgetNLPs(scip));
         SCIP_CALL( SCIPinterruptSolve(scip) );
      }
      break;
   default:
      break;
   }

   return SCIP_OKAY;
}

/** initialize neighborhood statistics before the next run */
static
void initRunStats(
   SCIP*                 scip,               /**< SCIP data structure */
   NH_STATS*             stats               /**< run statistics */
   )
{
   stats->nbestsolsfound = 0;
   stats->nsolsfound = 0;
   stats->usednodes = 0L;
   stats->nfixings = 0;
   stats->oldupperbound = SCIPgetUpperbound(scip);
   stats->newupperbound = SCIPgetUpperbound(scip);
}

/** update run stats after the sub SCIP was solved */
static
void updateRunStats(
   NH_STATS*             stats,              /**< run statistics */
   SCIP*                 subscip             /**< sub-SCIP instance, or NULL */
   )
{
   /* treat an untransformed subscip as if none was created */
   if( subscip != NULL && ! SCIPisTransformed(subscip) )
      subscip = NULL;

   stats->usednodes = subscip != NULL ? SCIPgetNNodes(subscip) : 0L;
}

/** get the histogram index for this status */
static
int getHistIndex(
   SCIP_STATUS           subscipstatus       /**< sub-SCIP status */
   )
{
   switch (subscipstatus)
   {
   case SCIP_STATUS_OPTIMAL:
      return (int)HIDX_OPT;
   case SCIP_STATUS_INFEASIBLE:
      return (int)HIDX_INFEAS;
   case SCIP_STATUS_NODELIMIT:
      return (int)HIDX_NODELIM;
   case SCIP_STATUS_STALLNODELIMIT:
      return (int)HIDX_STALLNODE;
   case SCIP_STATUS_SOLLIMIT:
   case SCIP_STATUS_BESTSOLLIMIT:
      return (int)HIDX_SOLLIM;
   case SCIP_STATUS_USERINTERRUPT:
      return (int)HIDX_USR;
   default:
      return (int)HIDX_OTHER;
   } /*lint !e788*/
}

/** print neighborhood statistics */
static
void printNeighborhoodStatistics(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
   FILE*                 file                /**< file handle, or NULL for standard out */
   )
{
   int i;
   int j;
   HISTINDEX statusses[] = {HIDX_OPT, HIDX_INFEAS, HIDX_NODELIM, HIDX_STALLNODE, HIDX_SOLLIM, HIDX_USR, HIDX_OTHER};

   SCIPinfoMessage(scip, file, "Neighborhoods      : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %4s %4s %4s %4s %4s %4s %4s %4s\n",
            "Calls", "SetupTime", "SolveTime", "SolveNodes", "Sols", "Best", "Exp3", "EpsGreedy", "UCB", "TgtFixRate",
            "Opt", "Inf", "Node", "Stal", "Sol", "Usr", "Othr", "Actv");

   /* loop over neighborhoods and fill in statistics */
   for( i = 0; i < heurdata->nneighborhoods; ++i )
   {
      NH* neighborhood;
      SCIP_Real proba;
      SCIP_Real ucb;
      SCIP_Real epsgreedyweight;

      neighborhood = heurdata->neighborhoods[i];
      SCIPinfoMessage(scip, file, "  %-17s:", neighborhood->name);
      SCIPinfoMessage(scip, file, " %10d", neighborhood->stats.nruns);
      SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, neighborhood->stats.setupclock) );
      SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, neighborhood->stats.submipclock) );
      SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.usednodes );
      SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.nsolsfound);
      SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.nbestsolsfound);

      proba = 0.0;
      ucb = 1.0;
      epsgreedyweight = -1.0;

      if( heurdata->bandit != NULL && i < heurdata->nactiveneighborhoods )
      {
         switch (heurdata->banditalgo)
         {
         case 'u':
            ucb = SCIPgetConfidenceBoundUcb(heurdata->bandit, i);
            break;
         case 'g':
            epsgreedyweight = SCIPgetWeightsEpsgreedy(heurdata->bandit)[i];
            break;
         case 'e':
            proba = SCIPgetProbabilityExp3(heurdata->bandit, i);
            break;
         default:
            break;
         }
      }

      SCIPinfoMessage(scip, file, " %10.5f", proba);
      SCIPinfoMessage(scip, file, " %10.5f", epsgreedyweight);
      SCIPinfoMessage(scip, file, " %10.5f", ucb);
      SCIPinfoMessage(scip, file, " %10.3f", neighborhood->fixingrate.targetfixingrate);

      /* loop over status histogram */
      for( j = 0; j < NHISTENTRIES; ++j )
         SCIPinfoMessage(scip, file, " %4d", neighborhood->stats.statushist[statusses[j]]);

      SCIPinfoMessage(scip, file, " %4d", i < heurdata->nactiveneighborhoods ? 1 : 0);
      SCIPinfoMessage(scip, file, "\n");
   }
}

/** update the statistics of the neighborhood based on the sub-SCIP run */
static
void updateNeighborhoodStats(
   NH_STATS*             runstats,           /**< run statistics */
   NH*                   neighborhood,       /**< the selected neighborhood */
   SCIP_STATUS           subscipstatus       /**< status of the sub-SCIP solve */
   )
{  /*lint --e{715}*/
   NH_STATS* stats;
   stats = &neighborhood->stats;

   /* copy run statistics into neighborhood statistics */
   stats->nbestsolsfound += runstats->nbestsolsfound;
   stats->nsolsfound += runstats->nsolsfound;
   stats->usednodes += runstats->usednodes;
   stats->nruns += 1;

   if( runstats->nbestsolsfound > 0 )
      stats->nrunsbestsol += DEFAULT_BESTSOLWEIGHT;
   else if( runstats->nsolsfound > 0 )
      stats->nrunsbestsol++;

   /* update the counter for the subscip status */
   ++stats->statushist[getHistIndex(subscipstatus)];
}

/** 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
 */
static
SCIP_DECL_SORTINDCOMP(sortIndCompAlns)
{  /*lint --e{715}*/
   VARPRIO* varprio;

   varprio = (VARPRIO*)dataptr;
   assert(varprio != NULL);
   assert(varprio->randscores != NULL);

   if( ind1 == ind2 )
      return 0;

   /* priority is on distances, if enabled. The variable which is closer in a breadth-first search sense to
    * the already fixed variables has precedence */
   if( varprio->usedistances )
   {
      int dist1;
      int dist2;

      dist1 = varprio->distances[ind1];
      dist2 = varprio->distances[ind2];

      if( dist1 < 0 )
         dist1 = INT_MAX;

      if( dist2 < 0 )
         dist2 = INT_MAX;

      assert(varprio->distances != NULL);
      if( dist1 < dist2 )
         return -1;
      else if( dist1 > dist2 )
         return 1;
   }

   assert(! varprio->usedistances || varprio->distances[ind1] == varprio->distances[ind2]);

   /* if the indices tie considering distances or distances are disabled -> use reduced cost information instead */
   if( varprio->useredcost )
   {
      assert(varprio->redcostscores != NULL);

      if( varprio->redcostscores[ind1] < varprio->redcostscores[ind2] )
         return -1;
      else if( varprio->redcostscores[ind1] > varprio->redcostscores[ind2] )
         return 1;
   }

   /* use pseudo cost scores if reduced costs are disabled or a tie was found */
   if( varprio->usepscost )
   {
      assert(varprio->pscostscores != NULL);

      /* prefer the variable with smaller pseudocost score */
      if( varprio->pscostscores[ind1] < varprio->pscostscores[ind2] )
         return -1;
      else if( varprio->pscostscores[ind1] > varprio->pscostscores[ind2] )
         return 1;
   }

   if( varprio->randscores[ind1] < varprio->randscores[ind2] )
      return -1;
   else if( varprio->randscores[ind1] > varprio->randscores[ind2] )
      return 1;

   return ind1 - ind2;
}

/** Compute the reduced cost score for this variable in the reference solution */
static
SCIP_Real getVariableRedcostScore(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR*             var,                /**< the variable for which the score should be computed */
   SCIP_Real             refsolval,          /**< solution value in reference solution */
   SCIP_Bool             uselocalredcost     /**< should local reduced costs be used for generic (un)fixing? */
   )
{
   SCIP_Real bestbound;
   SCIP_Real redcost;
   SCIP_Real score;
   assert(scip != NULL);
   assert(var != NULL);

   /* prefer column variables */
   if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
      return SCIPinfinity(scip);

   if( ! uselocalredcost )
   {
      redcost = SCIPvarGetBestRootRedcost(var);

      bestbound = SCIPvarGetBestRootSol(var);

      /* using global reduced costs, the two factors yield a nonnegative score within tolerances */
      assert(SCIPisDualfeasZero(scip, redcost)
         || (SCIPisDualfeasNegative(scip, redcost) && ! SCIPisFeasPositive(scip, refsolval - bestbound))
         || (SCIPisDualfeasPositive(scip, redcost) && ! SCIPisFeasNegative(scip, refsolval - bestbound)));
   }
   else
   {
      /* this can be safely asserted here, since the heuristic would not reach this point, otherwise */
      assert(SCIPhasCurrentNodeLP(scip));
      assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);

      redcost = SCIPgetVarRedcost(scip, var);

      bestbound = SCIPvarGetLPSol(var);
   }

   assert(! SCIPisInfinity(scip, REALABS(bestbound)));
   assert(SCIPisDualfeasZero(scip, redcost) || SCIPisFeasIntegral(scip, bestbound));

   score = redcost * (refsolval - bestbound);

   /* max out numerical inaccuracies from global scores */
   if( ! uselocalredcost )
      score = MAX(score, 0.0);

   return score;
}

/** get the pseudo cost score of this variable with respect to the reference solution */
static
SCIP_Real getVariablePscostScore(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR*             var,                /**< the variable for which the score should be computed */
   SCIP_Real             refsolval           /**< solution value in reference solution */
   )
{
   SCIP_Real rootsolval;

   assert(scip != NULL);
   assert(var != NULL);

   /* variables that aren't LP columns have no pseudocost score */
   if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
      return 0.0;

   rootsolval = SCIPvarGetRootSol(var);

   /* the score is 0.0 if the values are equal */
   if( SCIPisEQ(scip, rootsolval, refsolval) )
      return 0.0;
   else
      return SCIPgetVarPseudocostVal(scip, var, refsolval - rootsolval);
}

/** 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.
 */
static
void tryAdd2variableBuffer(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR*             var,                /**< (source) SCIP variable that should be added to the buffer */
   SCIP_Real             val,                /**< fixing value for this variable */
   SCIP_VAR**            varbuf,             /**< variable buffer to store variables that should be fixed */
   SCIP_Real*            valbuf,             /**< value buffer to store fixing values */
   int*                  nfixings,           /**< pointer to number of fixed buffer variables, will be increased by 1 */
   SCIP_Bool             integer             /**< is this an integer variable? */
   )
{
   assert(SCIPisFeasIntegral(scip, val) || ! SCIPvarIsIntegral(var));
   assert(*nfixings < SCIPgetNVars(scip));

   /* round the value to its nearest integer */
   if( integer )
      val = SCIPfloor(scip, val + 0.5);

   /* only add fixing if it is still valid within the global variable bounds. Invalidity
    * of this solution value may come from a dual reduction that was performed after the solution from which
    * this value originated was found
    */
   if( SCIPvarGetLbGlobal(var) <= val && val <= SCIPvarGetUbGlobal(var) )
   {
      varbuf[*nfixings] = var;
      valbuf[*nfixings] = val;
      ++(*nfixings);
   }
}

/** query neighborhood for a reference solution for further fixings */
static
SCIP_RETCODE neighborhoodGetRefsol(
   SCIP*                 scip,               /**< SCIP data structure */
   NH*                   neighborhood,       /**< ALNS neighborhood data structure */
   SCIP_SOL**            solptr              /**< solution pointer */
   )
{
   assert(solptr != NULL);
   assert(scip != NULL);
   assert(neighborhood != NULL);

   *solptr = NULL;
   if( neighborhood->nhrefsol != NULL )
   {
      SCIP_RESULT result;
      SCIP_CALL( neighborhood->nhrefsol(scip, neighborhood, solptr, &result) );

      if( result == SCIP_DIDNOTFIND )
         *solptr = NULL;
      else
         assert(*solptr != NULL);
   }

   return SCIP_OKAY;
}

/** 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.
 */
static
SCIP_RETCODE alnsFixMoreVariables(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
   SCIP_SOL*             refsol,             /**< feasible reference solution for more variable fixings */
   SCIP_VAR**            varbuf,             /**< buffer array to store variables to fix */
   SCIP_Real*            valbuf,             /**< buffer array to store fixing values */
   int*                  nfixings,           /**< pointer to store the number of fixings */
   int                   ntargetfixings,     /**< number of required target fixings */
   SCIP_Bool*            success             /**< pointer to store whether the target fixings have been successfully reached */
   )
{
   VARPRIO varprio;
   SCIP_VAR** vars;
   SCIP_Real* redcostscores;
   SCIP_Real* pscostscores;
   SCIP_Real* solvals;
   SCIP_RANDNUMGEN* rng;
   SCIP_VAR** unfixedvars;
   SCIP_Bool* isfixed;
   int* distances;
   int* perm;
   SCIP_Real* randscores;
   int nbinvars;
   int nintvars;
   int nbinintvars;
   int nvars;
   int b;
   int nvarstoadd;
   int nunfixedvars;

   assert(scip != NULL);
   assert(varbuf != NULL);
   assert(nfixings != NULL);
   assert(success != NULL);
   assert(heurdata != NULL);
   assert(refsol != NULL);

   *success = FALSE;

   /* if the user parameter forbids more fixings, return immediately */
   if( ! heurdata->domorefixings )
      return SCIP_OKAY;

   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );

   nbinintvars = nbinvars + nintvars;

   if( ntargetfixings >= nbinintvars )
      return SCIP_OKAY;

   /* determine the number of required additional fixings */
   nvarstoadd = ntargetfixings - *nfixings;
   if( nvarstoadd == 0 )
      return SCIP_OKAY;

   varprio.usedistances = heurdata->usedistances && (*nfixings >= 1);
   varprio.useredcost = heurdata->useredcost;
   varprio.usepscost = heurdata->usepscost;
   varprio.scip = scip;
   rng = SCIPbanditGetRandnumgen(heurdata->bandit);
   assert(rng != NULL);

   SCIP_CALL( SCIPallocBufferArray(scip, &randscores, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &perm, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &isfixed, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, nbinintvars) );

   /* initialize variable graph distances from already fixed variables */
   if( varprio.usedistances )
   {
      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, varbuf, *nfixings, distances, INT_MAX, INT_MAX, ntargetfixings) );
   }
   else
   {
      /* initialize all equal distances to make them irrelevant */
      BMSclearMemoryArray(distances, nbinintvars);
   }

   BMSclearMemoryArray(isfixed, nbinintvars);

   /* mark binary and integer variables if they are fixed */
   for( b = 0; b < *nfixings; ++b )
   {
      int probindex;

      assert(varbuf[b] != NULL);
      probindex = SCIPvarGetProbindex(varbuf[b]);
      assert(probindex >= 0);

      if( probindex < nbinintvars )
         isfixed[probindex] = TRUE;
   }

   SCIP_CALL( SCIPgetSolVals(scip, refsol, nbinintvars, vars, solvals) );

   /* assign scores to unfixed every discrete variable of the problem */
   nunfixedvars = 0;
   for( b = 0; b < nbinintvars; ++b )
   {
      SCIP_VAR* var = vars[b];

      /* filter fixed variables */
      if( isfixed[b] )
         continue;

      /* filter variables with a solution value outside its global bounds */
      if( solvals[b] < SCIPvarGetLbGlobal(var) - 0.5 || solvals[b] > SCIPvarGetUbGlobal(var) + 0.5 )
         continue;

      redcostscores[nunfixedvars] = getVariableRedcostScore(scip, var, solvals[b], heurdata->uselocalredcost);
      pscostscores[nunfixedvars] = getVariablePscostScore(scip, var, solvals[b]);

      unfixedvars[nunfixedvars] = var;
      perm[nunfixedvars] = nunfixedvars;
      randscores[nunfixedvars] = SCIPrandomGetReal(rng, 0.0, 1.0);

      /* these assignments are based on the fact that nunfixedvars <= b */
      solvals[nunfixedvars] = solvals[b];
      distances[nunfixedvars] = distances[b];

      SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
         SCIPvarGetName(var), distances[nunfixedvars], redcostscores[nunfixedvars],
         pscostscores[nunfixedvars], randscores[nunfixedvars]);

      nunfixedvars++;
   }

   /* use selection algorithm (order of the variables does not matter) for quickly completing the fixing */
   varprio.randscores = randscores;
   varprio.distances = distances;
   varprio.redcostscores = redcostscores;
   varprio.pscostscores = pscostscores;

   nvarstoadd = MIN(nunfixedvars, nvarstoadd);

   /* select the first nvarstoadd many variables according to the score */
   if( nvarstoadd < nunfixedvars )
      SCIPselectInd(perm, sortIndCompAlns, &varprio, nvarstoadd, nunfixedvars);

   /* loop over the first elements of the selection defined in permutation. They represent the best variables */
   for( b = 0; b < nvarstoadd; ++b )
   {
      int permindex = perm[b];
      assert(permindex >= 0);
      assert(permindex < nunfixedvars);

      tryAdd2variableBuffer(scip, unfixedvars[permindex], solvals[permindex], varbuf, valbuf, nfixings, TRUE);
   }

   *success = TRUE;

   /* free buffer arrays */
   SCIPfreeBufferArray(scip, &pscostscores);
   SCIPfreeBufferArray(scip, &unfixedvars);
   SCIPfreeBufferArray(scip, &isfixed);
   SCIPfreeBufferArray(scip, &solvals);
   SCIPfreeBufferArray(scip, &redcostscores);
   SCIPfreeBufferArray(scip, &distances);
   SCIPfreeBufferArray(scip, &perm);
   SCIPfreeBufferArray(scip, &randscores);

   return SCIP_OKAY;
}

/** create the bandit algorithm for the heuristic depending on the user parameter */
static
SCIP_RETCODE createBandit(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
   SCIP_Real*            priorities,         /**< call priorities for active neighborhoods */
   unsigned int          initseed            /**< initial random seed */
   )
{
   switch (heurdata->banditalgo)
   {
   case 'u':
      SCIP_CALL( SCIPcreateBanditUcb(scip, &heurdata->bandit, priorities,
            heurdata->ucb_alpha, heurdata->nactiveneighborhoods, initseed) );
      break;

   case 'e':
      SCIP_CALL( SCIPcreateBanditExp3(scip, &heurdata->bandit, priorities,
            heurdata->exp3_gamma, heurdata->exp3_beta, heurdata->nactiveneighborhoods, initseed) );
      break;

   case 'g':
      SCIP_CALL( SCIPcreateBanditEpsgreedy(scip, &heurdata->bandit, priorities,
            heurdata->epsgreedy_eps, FALSE, 0.9, 0, heurdata->nactiveneighborhoods, initseed) );
      break;

   default:
      SCIPerrorMessage("Unknown bandit parameter %c\n", heurdata->banditalgo);
      return SCIP_INVALIDDATA;
   }

   return SCIP_OKAY;
}

/*
 * Callback methods of primal heuristic
 */

/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
static
SCIP_DECL_HEURCOPY(heurCopyAlns)
{  /*lint --e{715}*/
   assert(scip != NULL);
   assert(heur != NULL);
   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);

   /* call inclusion method of primal heuristic */
   SCIP_CALL( SCIPincludeHeurAlns(scip) );

   return SCIP_OKAY;
}

/** 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
 */
static
SCIP_RETCODE alnsUnfixVariables(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
   SCIP_VAR**            varbuf,             /**< buffer array to store variables to fix */
   SCIP_Real*            valbuf,             /**< buffer array to store fixing values */
   int*                  nfixings,           /**< pointer to store the number of fixings */
   int                   ntargetfixings,     /**< number of required target fixings */
   SCIP_Bool*            success             /**< pointer to store whether the target fixings have been successfully reached */
   )
{
   VARPRIO varprio;
   SCIP_Real* redcostscores;
   SCIP_Real* pscostscores;
   SCIP_Real* randscores;
   SCIP_VAR** unfixedvars;
   SCIP_VAR** varbufcpy;
   SCIP_Real* valbufcpy;
   SCIP_Bool* isfixedvar;
   SCIP_VAR** vars;
   SCIP_RANDNUMGEN* rng;
   int* distances;
   int* fixeddistances;
   int* perm;
   int nvars;
   int i;
   int nbinintvars;
   int nunfixed;

   *success = FALSE;

   nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
   if( nbinintvars == 0 )
      return SCIP_OKAY;

   assert(*nfixings > 0);

   nvars = SCIPgetNVars(scip);
   SCIP_CALL( SCIPallocBufferArray(scip, &isfixedvar, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &fixeddistances, *nfixings) );
   SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, *nfixings) );
   SCIP_CALL( SCIPallocBufferArray(scip, &randscores, *nfixings) );
   SCIP_CALL( SCIPallocBufferArray(scip, &perm, *nfixings) );
   SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, *nfixings) );

   SCIP_CALL( SCIPduplicateBufferArray(scip, &varbufcpy, varbuf, *nfixings) );
   SCIP_CALL( SCIPduplicateBufferArray(scip, &valbufcpy, valbuf, *nfixings) );

   /*
    * collect the unfixed binary and integer variables
    */
   BMSclearMemoryArray(isfixedvar, nvars);
   /* loop over fixed variables and mark their respective positions as fixed */
   for( i = 0; i < *nfixings; ++i )
   {
      int probindex = SCIPvarGetProbindex(varbuf[i]);

      assert(probindex >= 0);

      isfixedvar[probindex] = TRUE;
   }

   nunfixed = 0;
   vars = SCIPgetVars(scip);
   /* collect unfixed binary and integer variables */
   for( i = 0; i < nbinintvars; ++i )
   {
      if( ! isfixedvar[i] )
         unfixedvars[nunfixed++] = vars[i];
   }

   varprio.usedistances = heurdata->usedistances && nunfixed > 0;

   /* collect distances of all fixed variables from those that are not fixed */
   if( varprio.usedistances )
   {
      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, unfixedvars, nunfixed, distances, INT_MAX, INT_MAX, INT_MAX) );

      for( i = 0; i < *nfixings; ++i )
      {
         int probindex = SCIPvarGetProbindex(varbuf[i]);
         if( probindex >= 0 )
            fixeddistances[i] = distances[probindex];
      }
   }
   else
   {
      BMSclearMemoryArray(fixeddistances, *nfixings);
   }

   /* collect reduced cost scores of the fixings and assign random scores */
   rng = SCIPbanditGetRandnumgen(heurdata->bandit);
   for( i = 0; i < *nfixings; ++i )
   {
      SCIP_VAR* fixedvar = varbuf[i];
      SCIP_Real fixval = valbuf[i];

      /* use negative reduced cost and pseudo cost scores to prefer variable fixings with small score */
      redcostscores[i] = - getVariableRedcostScore(scip, fixedvar, fixval, heurdata->uselocalredcost);
      pscostscores[i] = - getVariablePscostScore(scip, fixedvar, fixval);
      randscores[i] = SCIPrandomGetReal(rng, 0.0, 1.0);
      perm[i] = i;

      SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
            SCIPvarGetName(fixedvar), fixeddistances[i], redcostscores[i], pscostscores[i], randscores[i]);
   }

   varprio.distances = fixeddistances;
   varprio.randscores = randscores;
   varprio.redcostscores = redcostscores;
   varprio.pscostscores = pscostscores;
   varprio.useredcost = heurdata->useredcost;
   varprio.usepscost = heurdata->usepscost;
   varprio.scip = scip;

   /* scores are assigned in such a way that variables with a smaller score should be fixed last */
   SCIPselectDownInd(perm, sortIndCompAlns, &varprio, ntargetfixings, *nfixings);

   /* bring the desired variables to the front of the array */
   for( i = 0; i < ntargetfixings; ++i )
   {
      valbuf[i] = valbufcpy[perm[i]];
      varbuf[i] = varbufcpy[perm[i]];
   }

   *nfixings = ntargetfixings;

   /* free the buffer arrays in reverse order of allocation */
   SCIPfreeBufferArray(scip, &valbufcpy);
   SCIPfreeBufferArray(scip, &varbufcpy);
   SCIPfreeBufferArray(scip, &pscostscores);
   SCIPfreeBufferArray(scip, &perm);
   SCIPfreeBufferArray(scip, &randscores);
   SCIPfreeBufferArray(scip, &redcostscores);
   SCIPfreeBufferArray(scip, &fixeddistances);
   SCIPfreeBufferArray(scip, &distances);
   SCIPfreeBufferArray(scip, &unfixedvars);
   SCIPfreeBufferArray(scip, &isfixedvar);

   *success = TRUE;

   return SCIP_OKAY;
}

/** call variable fixing callback for this neighborhood and orchestrate additional variable fixings, if necessary */
static
SCIP_RETCODE neighborhoodFixVariables(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
   NH*                   neighborhood,       /**< neighborhood data structure */
   SCIP_VAR**            varbuf,             /**< buffer array to keep variables that should be fixed */
   SCIP_Real*            valbuf,             /**< buffer array to keep fixing values */
   int*                  nfixings,           /**< pointer to store the number of variable fixings */
   SCIP_RESULT*          result              /**< pointer to store the result of the fixing operation */
   )
{
   int ntargetfixings;
   int nmaxfixings;
   int nminfixings;
   int nbinintvars;

   assert(scip != NULL);
   assert(neighborhood != NULL);
   assert(varbuf != NULL);
   assert(valbuf != NULL);
   assert(nfixings != NULL);
   assert(result != NULL);

   *nfixings = 0;

   *result = SCIP_DIDNOTRUN;
   ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)));

   if( neighborhood->varfixings != NULL )
   {
      SCIP_CALL( neighborhood->varfixings(scip, neighborhood, varbuf, valbuf, nfixings, result) );

      if( *result != SCIP_SUCCESS )
         return SCIP_OKAY;
   }
   else if( ntargetfixings == 0 )
   {
      *result = SCIP_SUCCESS;

      return SCIP_OKAY;
   }

   /* compute upper and lower target fixing limits using tolerance parameters */
   assert(neighborhood->varfixings == NULL || *result != SCIP_DIDNOTRUN);
   nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
   ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * nbinintvars);
   nminfixings = (int)((neighborhood->fixingrate.targetfixingrate - heurdata->fixtol) * nbinintvars);
   nminfixings = MAX(nminfixings, 0);
   nmaxfixings = (int)((neighborhood->fixingrate.targetfixingrate + heurdata->unfixtol) * nbinintvars);
   nmaxfixings = MIN(nmaxfixings, nbinintvars);

   SCIPdebugMsg(scip, "Neighborhood Fixings/Target: %d / %d <= %d <= %d\n",*nfixings, nminfixings, ntargetfixings, nmaxfixings);

   /* if too few fixings, use a strategy to select more variable fixings: randomized, LP graph, ReducedCost based, mix */
   if( (*result == SCIP_SUCCESS || *result == SCIP_DIDNOTRUN) && (*nfixings < nminfixings) )
   {
      SCIP_Bool success;
      SCIP_SOL* refsol;

      /* get reference solution from neighborhood */
      SCIP_CALL( neighborhoodGetRefsol(scip, neighborhood, &refsol) );

      /* try to fix more variables based on the reference solution */
      if( refsol != NULL )
      {
         SCIP_CALL( alnsFixMoreVariables(scip, heurdata, refsol, varbuf, valbuf, nfixings, ntargetfixings, &success) );
      }
      else
         success = FALSE;

      if( success )
         *result = SCIP_SUCCESS;
      else if( *result == SCIP_SUCCESS )
         *result = SCIP_DIDNOTFIND;
      else
         *result = SCIP_DIDNOTRUN;

      SCIPdebugMsg(scip, "After additional fixings: %d / %d\n",*nfixings, ntargetfixings);
   }
   else if( (SCIP_Real)(*nfixings) > nmaxfixings )
   {
      SCIP_Bool success;

      SCIP_CALL( alnsUnfixVariables(scip, heurdata, varbuf, valbuf, nfixings, ntargetfixings, &success) );

      assert(success);
      *result = SCIP_SUCCESS;
      SCIPdebugMsg(scip, "Unfixed variables, fixed variables remaining: %d\n", ntargetfixings);
   }
   else
   {
      SCIPdebugMsg(scip, "No additional fixings performed\n");
   }

   return SCIP_OKAY;
}

/** change the sub-SCIP by restricting variable domains, changing objective coefficients, or adding constraints */
static
SCIP_RETCODE neighborhoodChangeSubscip(
   SCIP*                 sourcescip,         /**< source SCIP data structure */
   SCIP*                 targetscip,         /**< target SCIP data structure */
   NH*                   neighborhood,       /**< neighborhood */
   SCIP_VAR**            targetvars,         /**< array of target SCIP variables aligned with source SCIP variables */
   int*                  ndomchgs,           /**< pointer to store the number of variable domain changes */
   int*                  nchgobjs,           /**< pointer to store the number of changed objective coefficients */
   int*                  naddedconss,        /**< pointer to store the number of added constraints */
   SCIP_Bool*            success             /**< pointer to store whether the sub-SCIP has been successfully modified */
   )
{
   assert(sourcescip != NULL);
   assert(targetscip != NULL);
   assert(neighborhood != NULL);
   assert(targetvars != NULL);
   assert(ndomchgs != NULL);
   assert(nchgobjs != NULL);
   assert(naddedconss != NULL);
   assert(success != NULL);

   *success = FALSE;
   *ndomchgs = 0;
   *nchgobjs = 0;
   *naddedconss = 0;

   /* call the change sub-SCIP callback of the neighborhood */
   if( neighborhood->changesubscip != NULL )
   {
      SCIP_CALL( neighborhood->changesubscip(sourcescip, targetscip, neighborhood, targetvars, ndomchgs, nchgobjs, naddedconss, success) );
   }
   else
   {
      *success = TRUE;
   }

   return SCIP_OKAY;
}

/** set sub-SCIP solving limits */
static
SCIP_RETCODE setLimits(
   SCIP*                 subscip,            /**< SCIP data structure */
   SOLVELIMITS*          solvelimits         /**< pointer to solving limits data structure */
   )
{
   assert(subscip != NULL);
   assert(solvelimits != NULL);

   assert(solvelimits->nodelimit >= solvelimits->stallnodes);

   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodes));
   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", solvelimits->timelimit) );
   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", solvelimits->memorylimit) );

   return SCIP_OKAY;
}

/** determine limits for a sub-SCIP */
static
SCIP_RETCODE determineLimits(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEUR*            heur,               /**< this heuristic */
   SOLVELIMITS*          solvelimits,        /**< pointer to solving limits data structure */
   SCIP_Bool*            runagain            /**< can we solve another sub-SCIP with these limits */
   )
{
   SCIP_HEURDATA* heurdata;
   SCIP_Real initfactor;
   SCIP_Real nodesquot;

   assert(scip != NULL);
   assert(heur != NULL);
   assert(solvelimits != NULL);
   assert(runagain != NULL);

   heurdata = SCIPheurGetData(heur);

   /* check whether there is enough time and memory left */
   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &solvelimits->timelimit) );
   if( ! SCIPisInfinity(scip, solvelimits->timelimit) )
      solvelimits->timelimit -= SCIPgetSolvingTime(scip);
   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &solvelimits->memorylimit) );

   /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
   if( ! SCIPisInfinity(scip, solvelimits->memorylimit) )
   {
      solvelimits->memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
      solvelimits->memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
   }

   /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
   if( solvelimits->timelimit <= 0.0 || solvelimits->memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
      *runagain = FALSE;

   nodesquot = heurdata->nodesquot;

   /* if the heuristic is used to measure all rewards, it will always be penalized here */
   if( heurdata->rewardfile == NULL )
      nodesquot *= (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0);

   /* calculate the search node limit of the heuristic  */
   solvelimits->stallnodes = (SCIP_Longint)(nodesquot * SCIPgetNNodes(scip));
   solvelimits->stallnodes += heurdata->nodesoffset;
   solvelimits->stallnodes -= heurdata->usednodes;
   solvelimits->stallnodes -= 100 * SCIPheurGetNCalls(heur);
   solvelimits->stallnodes = MIN(heurdata->maxnodes, solvelimits->stallnodes);

   /* use a smaller budget if not all neighborhoods have been initialized yet */
   assert(heurdata->ninitneighborhoods >= 0);
   initfactor = (heurdata->nactiveneighborhoods - heurdata->ninitneighborhoods + 1.0) / (heurdata->nactiveneighborhoods + 1.0);
   solvelimits->stallnodes = (SCIP_Longint)(solvelimits->stallnodes * initfactor);
   solvelimits->nodelimit = (SCIP_Longint)(heurdata->maxnodes);

   /* check whether we have enough nodes left to call subproblem solving */
   if( solvelimits->stallnodes < heurdata->targetnodes )
      *runagain = FALSE;

   return SCIP_OKAY;
}

/** return the bandit algorithm that should be used */
static
SCIP_BANDIT* getBandit(
   SCIP_HEURDATA*        heurdata            /**< heuristic data of the ALNS neighborhood */
   )
{
   assert(heurdata != NULL);
   return heurdata->bandit;
}

/** select a neighborhood depending on the selected bandit algorithm */
static
SCIP_RETCODE selectNeighborhood(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
   int*                  neighborhoodidx     /**< pointer to store the selected neighborhood index */
   )
{
   SCIP_BANDIT* bandit;
   assert(scip != NULL);
   assert(heurdata != NULL);
   assert(neighborhoodidx != NULL);

   *neighborhoodidx = -1;

   bandit = getBandit(heurdata);

   SCIP_CALL( SCIPbanditSelect(bandit, neighborhoodidx) );
   assert(*neighborhoodidx >= 0);

   return SCIP_OKAY;
}

/** Calculate reward based on the selected reward measure */
static
SCIP_RETCODE getReward(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
   NH_STATS*             runstats,           /**< run statistics */
   SCIP_Real*            rewardptr           /**< pointer to store the computed reward */
   )
{
   SCIP_Real reward = 0.0;
   SCIP_Real effort;
   int ndiscretevars;

   assert(rewardptr != NULL);
   assert(runstats->usednodes >= 0);
   assert(runstats->nfixings >= 0);

   effort = runstats->usednodes / 100.0;

   ndiscretevars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
   /* assume that every fixed variable linearly reduces the subproblem complexity */
   if( ndiscretevars > 0 )
   {
      effort = (1.0 - (runstats->nfixings / (SCIP_Real)ndiscretevars)) * effort;
   }
   assert(rewardptr != NULL);

   /* a positive reward is only assigned if a new incumbent solution was found */
   if( runstats->nbestsolsfound > 0 )
   {
      SCIP_Real bestsolreward;
      SCIP_Real closedgapreward;
      SCIP_Real rewardcontrol = heurdata->rewardcontrol;

      SCIP_Real lb;
      SCIP_Real ub;

      /* the indicator function is simply 1.0 */
      bestsolreward = 1.0;

      ub = runstats->newupperbound;
      lb = SCIPgetLowerbound(scip);

      /* compute the closed gap reward */
      if( SCIPisEQ(scip, ub, lb) || SCIPisInfinity(scip, runstats->oldupperbound) )
         closedgapreward = 1.0;
      else
      {
         closedgapreward = (runstats->oldupperbound - ub) / (runstats->oldupperbound - lb);
      }

      /* the reward is a convex combination of the best solution reward and the reward for the closed gap */
      reward = rewardcontrol * bestsolreward + (1.0 - rewardcontrol) * closedgapreward;

      /* optionally, scale the reward by the involved effort */
      if( heurdata->scalebyeffort )
         reward /= (effort + 1.0);

      /* add the baseline and rescale the reward into the interval [baseline, 1.0] */
      reward = heurdata->rewardbaseline + (1.0 - heurdata->rewardbaseline) * reward;
   }
   else
   {
      /* linearly decrease the reward based on the number of nodes spent */
      SCIP_Real maxeffort = heurdata->targetnodes;
      SCIP_Real usednodes = runstats->usednodes;

      if( ndiscretevars > 0 )
         usednodes *= (1.0 - (runstats->nfixings / (SCIP_Real)ndiscretevars));

      reward = heurdata->rewardbaseline - (usednodes) * heurdata->rewardbaseline / maxeffort;
      reward = MAX(0.0, reward);
   }

   *rewardptr = reward;
   return SCIP_OKAY;
}

/** update internal bandit algorithm statistics for future draws */
static
SCIP_RETCODE updateBanditAlgorithm(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
   SCIP_Real             reward,             /**< measured reward */
   int                   neighborhoodidx     /**< the neighborhood that was chosen */
   )
{
   SCIP_BANDIT* bandit;
   assert(scip != NULL);
   assert(heurdata != NULL);
   assert(neighborhoodidx >= 0);
   assert(neighborhoodidx < heurdata->nactiveneighborhoods);

   bandit = getBandit(heurdata);

   SCIPdebugMsg(scip, "Rewarding bandit algorithm action %d with reward %.2f\n", neighborhoodidx, reward);
   SCIP_CALL( SCIPbanditUpdate(bandit, neighborhoodidx, reward) );

   return SCIP_OKAY;
}

/** set up the sub-SCIP parameters, objective cutoff, and solution limits */
static
SCIP_RETCODE setupSubScip(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP*                 subscip,            /**< sub-SCIP data structure */
   SCIP_VAR**            subvars,            /**< array of sub-SCIP variables in the order of the main SCIP */
   SOLVELIMITS*          solvelimits,        /**< pointer to solving limits data structure */
   SCIP_HEUR*            heur,               /**< this heuristic */
   SCIP_Bool             objchgd             /**< did the objective change between the source and the target SCIP? */
   )
{
   SCIP_HEURDATA* heurdata;
   SCIP_Real cutoff;
   SCIP_Real upperbound;

   heurdata = SCIPheurGetData(heur);

   /* do not abort subproblem on CTRL-C */
   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );

   /* disable output to console unless we are in debug mode */
   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );

   /* disable statistic timing inside sub SCIP */
   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );

#ifdef ALNS_SUBSCIPOUTPUT
   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
   /* enable statistic timing inside sub SCIP */
      SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", TRUE) );
#endif

   SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->nsolslim) );

   /* forbid recursive call of heuristics and separators solving subMIPs */
   if( ! heurdata->usesubscipheurs )
   {
      SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
   }

   /* disable cutting plane separation */
   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );

   /* disable expensive presolving */
   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );

   /* use best estimate node selection */
   if( SCIPfindNodesel(subscip, "estimate") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
   {
      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
   }

   /* use inference branching */
   if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") )
   {
      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
   }

   /* enable conflict analysis and restrict conflict pool */
   if( ! SCIPisParamFixed(subscip, "conflict/enable") )
   {
      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
   }

   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
   {
      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
   }

   if( ! SCIPisParamFixed(subscip, "conflict/maxstoresize") )
   {
      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
   }

   /* speed up sub-SCIP by not checking dual LP feasibility */
   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );

   /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
    * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
    * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
    * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
    * made for the original SCIP
    */
   if( SCIPfindConshdlr(subscip, "quadratic") != NULL && ! SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
   {
      SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
   }

   /* add an objective cutoff */
   if( ! SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
   {
      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
      if( ! SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
      {
         cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
                            + heurdata->minimprove * SCIPgetLowerbound(scip);
      }
      else
      {
         if( SCIPgetUpperbound(scip) >= 0 )
            cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
         else
            cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
      }
      cutoff = MIN(upperbound, cutoff);

      if( SCIPisObjIntegral(scip) )
         cutoff = SCIPfloor(scip, cutoff);

      SCIPdebugMsg(scip, "Sub-SCIP cutoff: %15.9" SCIP_REAL_FORMAT " (%15.9" SCIP_REAL_FORMAT " in original space)\n",
         cutoff, SCIPretransformObj(scip, cutoff));

      /* if the objective changed between the source and the target SCIP, encode the cutoff as a constraint */
      if( ! objchgd )
      {
         SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));

         SCIPdebugMsg(scip, "Cutoff added as Objective Limit\n");
      }
      else
      {
         SCIP_CONS* objcons;
         int nvars;
         SCIP_VAR** vars;
         int i;

         vars = SCIPgetVars(scip);
         nvars = SCIPgetNVars(scip);

         SCIP_CALL( SCIPcreateConsLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
                     TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
         for( i = 0; i < nvars; ++i)
         {
            if( ! SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
            {
               assert(subvars[i] != NULL);
               SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
            }
         }
         SCIP_CALL( SCIPaddCons(subscip, objcons) );
         SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );

         SCIPdebugMsg(scip, "Cutoff added as constraint\n");
      }
   }

   /* set solve limits for sub-SCIP */
   SCIP_CALL( setLimits(subscip, solvelimits) );

   /* change random seed of sub-SCIP */
   if( heurdata->subsciprandseeds )
   {
      SCIP_CALL( SCIPsetIntParam(subscip, "randomization/randomseedshift", (int)SCIPheurGetNCalls(heur)) );
   }

   SCIPdebugMsg(scip, "Solve Limits: %lld (%lld) nodes (stall nodes), %.1f sec., %d sols\n",
         solvelimits->nodelimit, solvelimits->stallnodes, solvelimits->timelimit, heurdata->nsolslim);

   return SCIP_OKAY;
}

/** execution method of primal heuristic */
static
SCIP_DECL_HEUREXEC(heurExecAlns)
{  /*lint --e{715}*/
   SCIP_HEURDATA* heurdata;
   SCIP_VAR** varbuf;
   SCIP_Real* valbuf;
   SCIP_VAR** vars;
   SCIP_VAR** subvars;
   NH_STATS runstats[NNEIGHBORHOODS];
   SCIP_STATUS subscipstatus[NNEIGHBORHOODS];
   SCIP* subscip = NULL;

   int nfixings;
   int nvars;
   int neighborhoodidx;
   int ntries;
   SCIP_Bool tryagain;
   NH* neighborhood;
   SOLVELIMITS solvelimits;
   SCIP_Bool success;
   SCIP_Bool run;
   SCIP_Bool allrewardsmode;
   SCIP_Real rewards[NNEIGHBORHOODS];
   int banditidx;
   int i;

   heurdata = SCIPheurGetData(heur);
   assert(heurdata != NULL);

   *result = SCIP_DIDNOTRUN;

   if( heurdata->nactiveneighborhoods == 0 )
      return SCIP_OKAY;

   /* wait for a sufficient number of nodes since last incumbent solution */
   if( SCIPgetDepth(scip) > 0 && SCIPgetBestSol(scip) != NULL
      && (SCIPgetNNodes(scip) - SCIPsolGetNodenum(SCIPgetBestSol(scip))) < heurdata->waitingnodes )
   {
      SCIPdebugMsg(scip, "Waiting nodes not satisfied\n");
      return SCIP_OKAY;
   }

   run = TRUE;
   /* check if budget allows a run of the next selected neighborhood */
   SCIP_CALL( determineLimits(scip, heur, &solvelimits, &run) );
   SCIPdebugMsg(scip, "Budget check: %" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT ") %s\n", solvelimits.nodelimit, heurdata->targetnodes, run ? "passed" : "must wait");

   if( ! run )
      return SCIP_OKAY;

   /* delay the heuristic if local reduced costs should be used for generic variable unfixing */
   if( heurdata->uselocalredcost && (nodeinfeasible || ! SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL) )
   {
      *result = SCIP_DELAYED;

      return SCIP_OKAY;
   }

   allrewardsmode = heurdata->rewardfile != NULL;

   /* apply some other rules for a fair all rewards mode; in normal execution mode, neighborhoods are iterated through */
   if( allrewardsmode )
   {
      /* most neighborhoods require an incumbent solution */
      if( SCIPgetNSols(scip) < 2 )
      {
         SCIPdebugMsg(scip, "Not enough solutions for all rewards mode\n");
         return SCIP_OKAY;
      }

      /* if the node is infeasible, or has no LP solution, which is required by some neighborhoods
       * if we are not in all rewards mode, the neighborhoods delay themselves individually
       */
      if( nodeinfeasible || ! SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
      {
         SCIPdebugMsg(scip, "Delay ALNS heuristic until a feasible node with optimally solved LP relaxation\n");
         *result = SCIP_DELAYED;
         return SCIP_OKAY;
      }
   }

   /* use the neighborhood that requested a delay or select the next neighborhood to run based on the selected bandit algorithm */
   if( heurdata->currneighborhood >= 0 )
   {
      assert(! allrewardsmode);
      banditidx = heurdata->currneighborhood;
      SCIPdebugMsg(scip, "Select delayed neighborhood %d (was delayed %d times)\n", banditidx, heurdata->ndelayedcalls);
   }
   else
   {
      SCIP_CALL( selectNeighborhood(scip, heurdata, &banditidx) );
      SCIPdebugMsg(scip, "Selected neighborhood %d with bandit algorithm\n", banditidx);
   }

   /* in all rewards mode, we simply loop over all heuristics */
   if( ! allrewardsmode )
      neighborhoodidx = banditidx;
   else
      neighborhoodidx = 0;

   assert(0 <= neighborhoodidx && neighborhoodidx < NNEIGHBORHOODS);
   assert(heurdata->nactiveneighborhoods > neighborhoodidx);

   /* allocate memory for variable fixings buffer */
   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
   SCIP_CALL( SCIPallocBufferArray(scip, &varbuf, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &valbuf, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );

   /* initialize neighborhood statistics for a run */
   ntries = 1;
   do
   {
      SCIP_HASHMAP* varmapf;
      SCIP_EVENTHDLR* eventhdlr;
      SCIP_EVENTDATA eventdata;
      char probnamesuffix[SCIP_MAXSTRLEN];
      SCIP_Real allfixingrate;
      int ndomchgs;
      int nchgobjs;
      int naddedconss;
      int v;
      SCIP_RETCODE retcode;
      SCIP_RESULT fixresult;

      tryagain = FALSE;
      neighborhood = heurdata->neighborhoods[neighborhoodidx];
      SCIPdebugMsg(scip, "Running '%s' neighborhood %d\n", neighborhood->name, neighborhoodidx);

      initRunStats(scip, &runstats[neighborhoodidx]);
      rewards[neighborhoodidx] = 0.0;

      subscipstatus[neighborhoodidx] = SCIP_STATUS_UNKNOWN;
      SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.setupclock) );

      /* determine variable fixings and objective coefficients of this neighborhood */
      SCIP_CALL( neighborhoodFixVariables(scip, heurdata, neighborhood, varbuf, valbuf, &nfixings, &fixresult) );

      SCIPdebugMsg(scip, "Fix %d/%d variables, result code %d\n", nfixings, nvars,fixresult);

      /* Fixing was not successful, either because the fixing rate was not reached (and no additional variable
       * prioritization was used), or the neighborhood requested a delay, e.g., because no LP relaxation solution exists
       * at the current node
       *
       * The ALNS heuristic keeps a delayed neighborhood active and delays itself.
       */
      if( fixresult != SCIP_SUCCESS )
      {
         SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );

         /* to determine all rewards, we cannot delay neighborhoods */
         if( allrewardsmode )
         {
            if( ntries == heurdata->nactiveneighborhoods )
               break;

            neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
            ntries++;
            tryagain = TRUE;

            continue;
         }

         /* delay the heuristic along with the selected neighborhood
          *
          * if the neighborhood has been delayed for too many consecutive calls, the delay is treated as a failure */
         if( fixresult == SCIP_DELAYED )
         {
            if( heurdata->ndelayedcalls > (SCIPheurGetFreq(heur) / 4 + 1) )
            {
               resetCurrentNeighborhood(heurdata);

               /* use SCIP_DIDNOTFIND to penalize the neighborhood with a bad reward */
               fixresult = SCIP_DIDNOTFIND;
            }
            else if( heurdata->currneighborhood == -1 )
            {
               heurdata->currneighborhood = neighborhoodidx;
               heurdata->ndelayedcalls = 1;
            }
            else
            {
               heurdata->ndelayedcalls++;
            }
         }

         if( fixresult == SCIP_DIDNOTRUN )
         {
            if( ntries < heurdata->nactiveneighborhoods )
            {
               SCIP_CALL( updateBanditAlgorithm(scip, heurdata, 0.0, neighborhoodidx) );
               SCIP_CALL( selectNeighborhood(scip, heurdata, &neighborhoodidx) );
               ntries++;
               tryagain = TRUE;

               SCIPdebugMsg(scip, "Neighborhood cannot run -> try next neighborhood %d\n", neighborhoodidx);
               continue;
            }
            else
               break;
         }

         assert(fixresult == SCIP_DIDNOTFIND || fixresult == SCIP_DELAYED);
         *result = fixresult;
         break;
      }

      *result = SCIP_DIDNOTFIND;

      neighborhood->stats.nfixings += nfixings;
      runstats[neighborhoodidx].nfixings = nfixings;

      SCIP_CALL( SCIPcreate(&subscip) );
      SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(scip), nvars) );
      (void) SCIPsnprintf(probnamesuffix, SCIP_MAXSTRLEN, "alns_%s", neighborhood->name);

      /* todo later: run global propagation for this set of fixings */
      SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapf, probnamesuffix, varbuf, valbuf, nfixings, FALSE, heurdata->copycuts, &success, NULL) );

      /* store sub-SCIP variables in array for faster access */
      for( v = 0; v < nvars; ++v )
      {
         subvars[v] = (SCIP_VAR*)SCIPhashmapGetImage(varmapf, (void *)vars[v]);
      }

      SCIPhashmapFree(&varmapf);

      /* let the neighborhood add additional constraints, or restrict domains */
      SCIP_CALL( neighborhoodChangeSubscip(scip, subscip, neighborhood, subvars, &ndomchgs, &nchgobjs, &naddedconss, &success) );

      if( ! success )
      {
         SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );

         if( ! allrewardsmode || ntries == heurdata->nactiveneighborhoods )
            break;

         neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
         ntries++;
         tryagain = TRUE;

         SCIP_CALL( SCIPfree(&subscip) );

         continue;
      }

      /* set up sub-SCIP parameters */
      SCIP_CALL( setupSubScip(scip, subscip, subvars, &solvelimits, heur, nchgobjs > 0) );

      /* copy the necessary data into the event data to create new solutions */
      eventdata.nodelimit = solvelimits.nodelimit;  /*lint !e644*/
      eventdata.lplimfac = heurdata->lplimfac;
      eventdata.heur = heur;
      eventdata.sourcescip = scip;
      eventdata.subvars = subvars;
      eventdata.runstats = &runstats[neighborhoodidx];
      eventdata.allrewardsmode = allrewardsmode;

      /* include an event handler to transfer solutions into the main SCIP */
      SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecAlns, NULL) );

      /* transform the problem before catching the events */
      SCIP_CALL( SCIPtransformProb(subscip) );
      SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_ALNS, eventhdlr, &eventdata, NULL) );

      SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );

      SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.submipclock) );

      /* set up sub-SCIP and run presolving */
      retcode = SCIPpresolve(subscip);
      if( retcode != SCIP_OKAY )
      {
         SCIPwarningMessage(scip, "Error while presolving subproblem in ALNS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
         SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.submipclock) );

         SCIPABORT();  /*lint --e{527}*/
         break;
      }

      /* was presolving successful enough regarding fixings? otherwise, terminate */
      allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);

      /* additional variables added in presolving may lead to the subSCIP having more variables than the original */
      allfixingrate = MAX(allfixingrate, 0.0);

      if( allfixingrate >= neighborhood->fixingrate.targetfixingrate / 2.0 )
      {
         /* run sub-SCIP for the given budget, and collect statistics */
         SCIP_CALL_ABORT( SCIPsolve(subscip) );
      }
      else
      {
         SCIPdebugMsg(scip, "Fixed only %.3f of all variables after presolving -> do not solve sub-SCIP\n", allfixingrate);
      }

#ifdef ALNS_SUBSCIPOUTPUT
      SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
#endif

      SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.submipclock) );

      /* update statistics based on the sub-SCIP run results */
      updateRunStats(&runstats[neighborhoodidx], subscip);
      subscipstatus[neighborhoodidx] = SCIPgetStatus(subscip);
      SCIPdebugMsg(scip, "Status of sub-SCIP run: %d\n", subscipstatus[neighborhoodidx]);

      SCIP_CALL( getReward(scip, heurdata, &runstats[neighborhoodidx], &rewards[neighborhoodidx]) );

      /* in all rewards mode, continue with the next neighborhood */
      if( allrewardsmode && ntries < heurdata->nactiveneighborhoods )
      {
         neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
         ntries++;
         tryagain = TRUE;

         SCIP_CALL( SCIPfree(&subscip) );
      }
   }
   while( tryagain && ! SCIPisStopped(scip) );

   if( subscip != NULL )
   {
      SCIP_CALL( SCIPfree(&subscip) );
   }

   SCIPfreeBufferArray(scip, &subvars);
   SCIPfreeBufferArray(scip, &valbuf);
   SCIPfreeBufferArray(scip, &varbuf);

   /* update bandit index that may have changed unless we are in all rewards mode */
   if( ! allrewardsmode )
      banditidx = neighborhoodidx;

   if( *result != SCIP_DELAYED )
   {
      /* decrease the number of neighborhoods that have not been initialized */
      if( neighborhood->stats.nruns == 0 )
         --heurdata->ninitneighborhoods;

      heurdata->usednodes += runstats[banditidx].usednodes;

      /* determine the success of this neighborhood, and update the target fixing rate for the next time */
      updateNeighborhoodStats(&runstats[banditidx], heurdata->neighborhoods[banditidx], subscipstatus[banditidx]);

      /* adjust the fixing rate for this neighborhood
       * make no adjustments in all rewards mode, because this only affects 1 of 8 heuristics
       */
      if( heurdata->adjustfixingrate && ! allrewardsmode )
      {
         SCIPdebugMsg(scip, "Update fixing rate: %.2f\n", heurdata->neighborhoods[banditidx]->fixingrate.targetfixingrate);
         updateFixingRate(heurdata->neighborhoods[banditidx], subscipstatus[banditidx], &runstats[banditidx]);
         SCIPdebugMsg(scip, "New fixing rate: %.2f\n", heurdata->neighborhoods[banditidx]->fixingrate.targetfixingrate);
      }
      /* similarly, update the minimum improvement for the ALNS heuristic */
      if( heurdata->adjustminimprove )
      {
         SCIPdebugMsg(scip, "Update Minimum Improvement: %.4f\n", heurdata->minimprove);
         updateMinimumImprovement(heurdata, subscipstatus[banditidx], &runstats[banditidx]);
         SCIPdebugMsg(scip, "--> %.4f\n", heurdata->minimprove);
      }

      /* update the target node limit based on the status of the selected algorithm */
      if( heurdata->adjusttargetnodes && SCIPheurGetNCalls(heur) >= heurdata->nactiveneighborhoods )
      {
         updateTargetNodeLimit(heurdata, &runstats[banditidx], subscipstatus[banditidx]);
      }

      /* update the bandit algorithm by the measured reward */
      SCIP_CALL( updateBanditAlgorithm(scip, heurdata, rewards[banditidx], banditidx) );

      resetCurrentNeighborhood(heurdata);
   }

   /* write single, measured rewards and the bandit index to the reward file */
   if( allrewardsmode )
   {
      for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
      {
         fprintf(heurdata->rewardfile, "%.4f,", rewards[i]);
      }
      fprintf(heurdata->rewardfile, "%d\n", banditidx);
   }

   return SCIP_OKAY;
}

/** callback to collect variable fixings of RENS */
static
DECL_VARFIXINGS(varFixingsRens)
{  /*lint --e{715}*/
   int nbinvars;
   int nintvars;
   SCIP_VAR** vars;
   int i;
   assert(scip != NULL);
   assert(varbuf != NULL);
   assert(nfixings != NULL);
   assert(valbuf != NULL);

   *result = SCIP_DELAYED;

   if( ! SCIPhasCurrentNodeLP(scip) )
      return SCIP_OKAY;
   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
      return SCIP_OKAY;

   *result = SCIP_DIDNOTRUN;

   /* get variable information */
   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );

   /* return if no binary or integer variables are present */
   if( nbinvars + nintvars == 0 )
      return SCIP_OKAY;

   /* loop over binary and integer variables; determine those that should be fixed in the sub-SCIP */
   for( i = 0; i < nbinvars + nintvars; ++i )
   {
      SCIP_VAR* var = vars[i];
      SCIP_Real lpsolval = SCIPvarGetLPSol(var);
      assert((i < nbinvars && SCIPvarIsBinary(var)) || (i >= nbinvars && SCIPvarIsIntegral(var)));

      /* fix all binary and integer variables with integer LP solution value */
      if( SCIPisFeasIntegral(scip, lpsolval) )
         tryAdd2variableBuffer(scip, var, lpsolval, varbuf, valbuf, nfixings, TRUE);
   }

   *result = SCIP_SUCCESS;

   return SCIP_OKAY;
}

/** callback for RENS subproblem changes */
static
DECL_CHANGESUBSCIP(changeSubscipRens)
{  /*lint --e{715}*/
   SCIP_VAR** vars;
   int nintvars;
   int nbinvars;
   int i;

   assert(SCIPhasCurrentNodeLP(sourcescip));
   assert(SCIPgetLPSolstat(sourcescip) == SCIP_LPSOLSTAT_OPTIMAL);

   /* get variable information */
   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );

   /* restrict bounds of integer variables with fractional solution value */
   for( i = nbinvars; i < nbinvars + nintvars; ++i )
   {
      SCIP_VAR* var = vars[i];
      SCIP_Real lpsolval = SCIPgetSolVal(sourcescip, NULL, var);

      if( subvars[i] == NULL )
         continue;

      if( ! SCIPisFeasIntegral(sourcescip, lpsolval) )
      {
         SCIP_Real newlb = SCIPfloor(sourcescip, lpsolval);
         SCIP_Real newub = newlb + 1.0;

         /* only count this as a domain change if the new lower and upper bound are a further restriction */
         if( newlb > SCIPvarGetLbGlobal(subvars[i]) + 0.5 || newub < SCIPvarGetUbGlobal(subvars[i]) - 0.5 )
         {
            SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[i], newlb) );
            SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[i], newub) );
            (*ndomchgs)++;
         }
      }
   }

   *success = TRUE;

   return SCIP_OKAY;
}

/** collect fixings by matching solution values in a collection of solutions for all binary and integer variables,
 *  or for a custom set of variables
 */
static
SCIP_RETCODE fixMatchingSolutionValues(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_SOL**            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 */
   int                   nsols,              /**< number of solutions in the array */
   SCIP_VAR**            vars,               /**< variable array for which solution values must agree */
   int                   nvars,              /**< number of variables, or -1 for all binary and integer variables */
   SCIP_VAR**            varbuf,             /**< buffer storage for variable fixings */
   SCIP_Real*            valbuf,             /**< buffer storage for fixing values */
   int*                  nfixings            /**< pointer to store the number of fixings */
   )
{
   int v;
   int nbinintvars;
   SCIP_SOL* firstsol;

   assert(scip != NULL);
   assert(sols != NULL);
   assert(nsols >= 2);
   assert(varbuf != NULL);
   assert(valbuf != NULL);
   assert(nfixings != NULL);
   assert(*nfixings == 0);

   if( nvars == -1 || vars == NULL )
   {
      int nbinvars;
      int nintvars;
      SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
      nbinintvars = nbinvars + nintvars;
      nvars = nbinintvars;
   }
   firstsol = sols[0];
   assert(nvars > 0);

   /* loop over integer and binary variables and check if their solution values match in all solutions */
   for( v = 0; v < nvars; ++v )
   {
      SCIP_Real solval;
      SCIP_VAR* var;
      int s;

      var = vars[v];
      assert((v < SCIPgetNBinVars(scip) && SCIPvarIsBinary(var)) || (v >= SCIPgetNBinVars(scip) && SCIPvarIsIntegral(var)));
      solval = SCIPgetSolVal(scip, firstsol, var);

      /* determine if solution values match in all given solutions */
      for( s = 1; s < nsols; ++s )
      {
         SCIP_Real solval2 = SCIPgetSolVal(scip, sols[s], var);
         if( ! SCIPisEQ(scip, solval, solval2) )
            break;
      }

      /* if we did not break early, all solutions agree on the solution value of this variable */
      if( s == nsols )
      {
         tryAdd2variableBuffer(scip, var, solval, varbuf, valbuf, nfixings, TRUE);
      }
   }

   return SCIP_OKAY;
}

/** callback to collect variable fixings of RINS */
static
DECL_VARFIXINGS(varFixingsRins)
{
   /*lint --e{715}*/
   int nbinvars;
   int nintvars;
   SCIP_VAR** vars;
   SCIP_SOL* incumbent;
   SCIP_SOL* sols[2];
   assert(scip != NULL);
   assert(varbuf != NULL);
   assert(nfixings != NULL);
   assert(valbuf != NULL);

   *result = SCIP_DELAYED;

   if( ! SCIPhasCurrentNodeLP(scip) )
      return SCIP_OKAY;
   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
      return SCIP_OKAY;

   *result = SCIP_DIDNOTRUN;

   incumbent = SCIPgetBestSol(scip);
   if( incumbent == NULL )
      return SCIP_OKAY;

   if( SCIPsolGetOrigin(incumbent) == SCIP_SOLORIGIN_ORIGINAL )
      return SCIP_OKAY;

   /* get variable information */
   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );

   /* return if no binary or integer variables are present */
   if( nbinvars + nintvars == 0 )
      return SCIP_OKAY;

   sols[0] = NULL;
   sols[1] = incumbent;

   SCIP_CALL( fixMatchingSolutionValues(scip, sols, 2, vars, nbinvars + nintvars, varbuf, valbuf, nfixings) );

   *result = SCIP_SUCCESS;

   return SCIP_OKAY;
}

/** initialization callback for crossover when a new problem is read */
static
DECL_NHINIT(nhInitCrossover)
{  /*lint --e{715}*/
   DATA_CROSSOVER* data;

   data = neighborhood->data.crossover;
   assert(data != NULL);

   if( data->rng != NULL )
      SCIPfreeRandom(scip, &data->rng);

   data->selsol = NULL;

   SCIP_CALL( SCIPcreateRandom(scip, &data->rng, CROSSOVERSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );

   return SCIP_OKAY;
}

/** deinitialization callback for crossover when exiting a problem */
static
DECL_NHEXIT(nhExitCrossover)
{  /*lint --e{715}*/
   DATA_CROSSOVER* data;
   data = neighborhood->data.crossover;

   assert(neighborhood != NULL);
   assert(data->rng != NULL);

   SCIPfreeRandom(scip, &data->rng);

   return SCIP_OKAY;
}

/** deinitialization callback for crossover before SCIP is freed */
static
DECL_NHFREE(nhFreeCrossover)
{  /*lint --e{715}*/
   assert(neighborhood->data.crossover != NULL);
   SCIPfreeBlockMemory(scip, &neighborhood->data.crossover);

   return SCIP_OKAY;
}

/** callback to collect variable fixings of crossover */
static
DECL_VARFIXINGS(varFixingsCrossover)
{  /*lint --e{715}*/
   DATA_CROSSOVER* data;
   SCIP_RANDNUMGEN* rng;
   SCIP_SOL** sols;
   SCIP_SOL** scipsols;
   int nsols;
   int lastdraw;
   assert(scip != NULL);
   assert(varbuf != NULL);
   assert(nfixings != NULL);
   assert(valbuf != NULL);

   data = neighborhood->data.crossover;

   assert(data != NULL);
   nsols = data->nsols;
   data->selsol = NULL;

   *result = SCIP_DIDNOTRUN;

   /* return if the pool has not enough solutions */
   if( nsols > SCIPgetNSols(scip) )
      return SCIP_OKAY;

   /* return if no binary or integer variables are present */
   if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
      return SCIP_OKAY;

   rng = data->rng;
   lastdraw = SCIPgetNSols(scip);
   SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
   scipsols = SCIPgetSols(scip);

   /* draw as many solutions from the pool as required by crossover, biased towards
    * better solutions; therefore, the sorting of the solutions by objective is implicitly used
    */
   while( nsols > 0 )
   {
      /* no need for randomization anymore, exactly nsols many solutions remain for the selection */
      if( lastdraw == nsols )
      {
         int s;

         /* fill the remaining slots 0,...,nsols - 1 by the solutions at the same places */
         for( s = 0; s < nsols; ++s )
            sols[s] = scipsols[s];

         nsols = 0;
      }
      else
      {
         int nextdraw;

         assert(nsols < lastdraw);

         /* draw from the lastdraw - nsols many solutions nsols - 1, ... lastdraw - 1 such that nsols many solution */
         nextdraw = SCIPrandomGetInt(rng, nsols - 1, lastdraw - 1);
         assert(nextdraw >= 0);

         sols[nsols - 1] = scipsols[nextdraw];
         nsols--;
         lastdraw = nextdraw;
      }
   }

   SCIP_CALL( fixMatchingSolutionValues(scip, sols, data->nsols, NULL, -1, varbuf, valbuf, nfixings) );

   /* store best selected solution as reference solution */
   data->selsol = sols[0];
   assert(data->selsol != NULL);

   *result = SCIP_SUCCESS;

   SCIPfreeBufferArray(scip, &sols);

   return SCIP_OKAY;
}

/** callback for crossover reference solution */
static
DECL_NHREFSOL(nhRefsolCrossover)
{ /*lint --e{715}*/
   DATA_CROSSOVER* data;

   data = neighborhood->data.crossover;

   if( data->selsol != NULL )
   {
      *solptr = data->selsol;
      *result = SCIP_SUCCESS;
   }
   else
   {
      *result = SCIP_DIDNOTFIND;
   }

   return SCIP_OKAY;
}

/** initialization callback for mutation when a new problem is read */
static
DECL_NHINIT(nhInitMutation)
{  /*lint --e{715}*/
   DATA_MUTATION* data;
   assert(scip != NULL);
   assert(neighborhood != NULL);

   SCIP_CALL( SCIPallocBlockMemory(scip, &neighborhood->data.mutation) );

   data = neighborhood->data.mutation;
   assert(data != NULL);

   SCIP_CALL( SCIPcreateRandom(scip, &data->rng, MUTATIONSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );

   return SCIP_OKAY;
}

/** deinitialization callback for mutation when exiting a problem */
static
DECL_NHEXIT(nhExitMutation)
{  /*lint --e{715}*/
   DATA_MUTATION* data;
   assert(scip != NULL);
   assert(neighborhood != NULL);
   data = neighborhood->data.mutation;
   assert(data != NULL);

   SCIPfreeRandom(scip, &data->rng);

   SCIPfreeBlockMemory(scip, &neighborhood->data.mutation);

   return SCIP_OKAY;
}

/** callback to collect variable fixings of mutation */
static
DECL_VARFIXINGS(varFixingsMutation)
{  /*lint --e{715}*/
   SCIP_RANDNUMGEN* rng;

   SCIP_VAR** vars;
   SCIP_VAR** varscpy;
   int i;
   int nvars;
   int nbinvars;
   int nintvars;
   int nbinintvars;
   int ntargetfixings;
   SCIP_SOL* incumbentsol;
   SCIP_Real targetfixingrate;

   assert(scip != NULL);
   assert(neighborhood != NULL);
   assert(neighborhood->data.mutation != NULL);
   assert(neighborhood->data.mutation->rng != NULL);
   rng = neighborhood->data.mutation->rng;

   *result = SCIP_DIDNOTRUN;

   /* get the problem variables */
   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );

   nbinintvars = nbinvars + nintvars;
   if( nbinintvars == 0 )
      return SCIP_OKAY;

   incumbentsol = SCIPgetBestSol(scip);
   if( incumbentsol == NULL )
      return SCIP_OKAY;

   targetfixingrate = neighborhood->fixingrate.targetfixingrate;
   ntargetfixings = (int)(targetfixingrate * nbinintvars) + 1;

   /* don't continue if number of discrete variables is too small to reach target fixing rate */
   if( nbinintvars <= ntargetfixings )
      return SCIP_OKAY;

   *result = SCIP_DIDNOTFIND;

   /* copy variables into a buffer array */
   SCIP_CALL( SCIPduplicateBufferArray(scip, &varscpy, vars, nbinintvars) );

   /* partially perturb the array until the number of target fixings is reached */
   for( i = 0; *nfixings < ntargetfixings && i < nbinintvars; ++i )
   {
      int randint = SCIPrandomGetInt(rng, i, nbinintvars - 1);
      assert(randint < nbinintvars);

      if( randint > i )
      {
         SCIPswapPointers((void**)&varscpy[i], (void**)&varscpy[randint]);
      }
      /* copy the selected variables and their solution values into the buffer */
      tryAdd2variableBuffer(scip, varscpy[i], SCIPgetSolVal(scip, incumbentsol, varscpy[i]), varbuf, valbuf, nfixings, TRUE);
   }

   assert(i == nbinintvars || *nfixings == ntargetfixings);

   /* Not reaching the number of target fixings means that there is a significant fraction (at least 1 - targetfixingrate)
    * of variables for which the incumbent solution value does not lie within the global bounds anymore. This is a nonsuccess
    * for the neighborhood (additional fixings are not possible), which is okay because the incumbent solution is
    * significantly outdated
    */
   if( *nfixings == ntargetfixings )
      *result = SCIP_SUCCESS;

   /* free the buffer array */
   SCIPfreeBufferArray(scip, &varscpy);

   return SCIP_OKAY;
}

/** add local branching constraint */
static
SCIP_RETCODE addLocalBranchingConstraint(
   SCIP*                 sourcescip,         /**< source SCIP data structure */
   SCIP*                 targetscip,         /**< target SCIP data structure */
   SCIP_VAR**            subvars,            /**< array of sub SCIP variables in same order as source SCIP variables */
   int                   distance,           /**< right hand side of the local branching constraint */
   SCIP_Bool*            success,            /**< pointer to store of a local branching constraint has been successfully added */
   int*                  naddedconss         /**< pointer to increase the number of added constraints */
   )
{
   int nbinvars;
   int i;
   SCIP_SOL* referencesol;
   SCIP_CONS* localbranchcons;
   SCIP_VAR** vars;
   SCIP_Real* consvals;
   SCIP_Real rhs;

   assert(sourcescip != NULL);
   assert(*success == FALSE);

   nbinvars = SCIPgetNBinVars(sourcescip);
   vars = SCIPgetVars(sourcescip);

   if( nbinvars <= 3 )
      return SCIP_OKAY;

   referencesol = SCIPgetBestSol(sourcescip);
   if( referencesol == NULL )
      return SCIP_OKAY;

   rhs = (SCIP_Real)distance;
   rhs = MAX(rhs, 2.0);

   SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars) );

   /* loop over binary variables and fill the local branching constraint */
   for( i = 0; i < nbinvars; ++i )
   {
      /* skip variables that are not present in sub-SCIP */
      if( subvars[i] == NULL )
         continue;

      if( SCIPisEQ(sourcescip, SCIPgetSolVal(sourcescip, referencesol, vars[i]), 0.0) )
         consvals[i] = 1.0;
      else
      {
         consvals[i] = -1.0;
         rhs -= 1.0;
      }
   }

   /* create the local branching constraint in the target scip */
   SCIP_CALL( SCIPcreateConsBasicLinear(targetscip, &localbranchcons, "localbranch", nbinvars, subvars, consvals, -SCIPinfinity(sourcescip), rhs) );
   SCIP_CALL( SCIPaddCons(targetscip, localbranchcons) );
   SCIP_CALL( SCIPreleaseCons(targetscip, &localbranchcons) );

   *naddedconss = 1;
   *success = TRUE;

   SCIPfreeBufferArray(sourcescip, &consvals);

   return SCIP_OKAY;
}

/** callback for local branching subproblem changes */
static
DECL_CHANGESUBSCIP(changeSubscipLocalbranching)
{  /*lint --e{715}*/

   SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.2 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );

   return SCIP_OKAY;
}

/** callback for proximity subproblem changes */
static
DECL_CHANGESUBSCIP(changeSubscipProximity)
{  /*lint --e{715}*/
   SCIP_SOL* referencesol;
   SCIP_VAR** vars;
   int nbinvars;
   int nintvars;
   int nvars;
   int i;

   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );

   if( nbinvars == 0 )
      return SCIP_OKAY;

   referencesol = SCIPgetBestSol(sourcescip);
   if( referencesol == NULL )
      return SCIP_OKAY;

   /* loop over binary variables, set objective coefficients based on reference solution in a local branching fashion */
   for( i = 0; i < nbinvars; ++i )
   {
      SCIP_Real newobj;

      /* skip variables not present in sub-SCIP */
      if( subvars[i] == NULL )
         continue;

      if( SCIPgetSolVal(sourcescip, referencesol, vars[i]) < 0.5 )
         newobj = -1.0;
      else
         newobj = 1.0;
      SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], newobj) );
   }

   /* loop over the remaining variables and change their objective coefficients to 0 */
   for( ; i < nvars; ++i )
   {
      /* skip variables not present in sub-SCIP */
      if( subvars[i] == NULL )
         continue;

      SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
   }

   *nchgobjs = nvars;
   *success = TRUE;

   return SCIP_OKAY;
}

/** callback for zeroobjective subproblem changes */
static
DECL_CHANGESUBSCIP(changeSubscipZeroobjective)
{  /*lint --e{715}*/
   SCIP_VAR** vars;
   int nvars;
   int i;

   assert(*success == FALSE);

   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, NULL, NULL, NULL, NULL) );

   /* do not run if no objective variables are present */
   if( SCIPgetNObjVars(sourcescip) == 0 )
      return SCIP_OKAY;

   /* loop over the variables and change their objective coefficients to 0 */
   for( i = 0; i < nvars; ++i )
   {
      /* skip variables not present in sub-SCIP */
      if( subvars[i] == NULL )
         continue;

      SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
   }

   *nchgobjs = nvars;
   *success = TRUE;

   return SCIP_OKAY;
}

/** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */
static
void computeIntegerVariableBoundsDins(
   SCIP*                 scip,               /**< SCIP data structure of the original problem */
   SCIP_VAR*             var,                /**< the variable for which bounds should be computed */
   SCIP_Real*            lbptr,              /**< pointer to store the lower bound in the DINS sub-SCIP */
   SCIP_Real*            ubptr               /**< pointer to store the upper bound in the DINS sub-SCIP */
   )
{
   SCIP_Real mipsol;
   SCIP_Real lpsol;

   SCIP_Real lbglobal;
   SCIP_Real ubglobal;
   SCIP_SOL* bestsol;

   /* get the bounds for each variable */
   lbglobal = SCIPvarGetLbGlobal(var);
   ubglobal = SCIPvarGetUbGlobal(var);

   assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
   /* get the current LP solution for each variable */
   lpsol = SCIPvarGetLPSol(var);

   /* get the current MIP solution for each variable */
   bestsol = SCIPgetBestSol(scip);
   mipsol = SCIPgetSolVal(scip, bestsol, var);

   /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
   if( REALABS(lpsol - mipsol) >= 0.5 )
   {
      SCIP_Real range;

      *lbptr = lbglobal;
      *ubptr = ubglobal;

      /* create an equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
      range = 2 * lpsol - mipsol;

      if( mipsol >= lpsol )
      {
         range = SCIPfeasCeil(scip, range);
         *lbptr = MAX(*lbptr, range);

         /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
         if( SCIPisFeasEQ(scip, mipsol, *lbptr) )
            *ubptr = *lbptr;
         else
            *ubptr = mipsol;
      }
      else
      {
         range = SCIPfeasFloor(scip, range);
         *ubptr = MIN(*ubptr, range);

         /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
         if( SCIPisFeasEQ(scip, mipsol, *ubptr) )
            *lbptr = *ubptr;
         else
            *lbptr = mipsol;
      }

      /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
      *lbptr = MAX(*lbptr, lbglobal);
      *ubptr = MIN(*ubptr, ubglobal);
   }
   else
   {
      /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
      *lbptr = MAX(mipsol, lbglobal);
      *ubptr = MIN(mipsol, ubglobal);
   }
}

/** callback to collect variable fixings of DINS */
static
DECL_VARFIXINGS(varFixingsDins)
{
   DATA_DINS* data;
   SCIP_SOL* rootlpsol;
   SCIP_SOL** sols;
   int nsols;
   int nmipsols;
   int nbinvars;
   int nintvars;
   SCIP_VAR** vars;
   int v;

   data = neighborhood->data.dins;
   assert(data != NULL);
   nmipsols = SCIPgetNSols(scip);
   nmipsols = MIN(nmipsols, data->npoolsols);

   *result = SCIP_DELAYED;

   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
      return SCIP_OKAY;

   *result = SCIP_DIDNOTRUN;

   if( nmipsols == 0 )
      return SCIP_OKAY;

   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );

   if( nbinvars + nintvars == 0 )
      return SCIP_OKAY;

   SCIP_CALL( SCIPcreateSol(scip, &rootlpsol, NULL) );

   /* save root solution LP values in solution */
   for( v = 0; v < nbinvars + nintvars; ++v )
   {
      SCIP_CALL( SCIPsetSolVal(scip, rootlpsol, vars[v], SCIPvarGetRootSol(vars[v])) );
   }

   /* add the node and the root LP solution */
   nsols = nmipsols + 2;

   SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
   sols[0] = NULL; /* node LP solution */
   sols[1] = rootlpsol;

   /* copy the remaining MIP solutions after the LP solutions */
   BMScopyMemoryArray(&sols[2], SCIPgetSols(scip), nmipsols); /*lint !e866*/

   /* 1. Binary variables are fixed if their values agree in all the solutions */
   if( nbinvars > 0 )
   {
      SCIP_CALL( fixMatchingSolutionValues(scip, sols, nsols, vars, nbinvars, varbuf, valbuf, nfixings) );
   }

   /* 2. Integer variables are fixed if they have a very low distance between the incumbent and the root LP solution */
   for( v = nbinvars; v < nintvars; ++v )
   {
      SCIP_Real lb;
      SCIP_Real ub;
      computeIntegerVariableBoundsDins(scip, vars[v], &lb, &ub);

      if( ub - lb < 0.5 )
      {
         assert(SCIPisFeasIntegral(scip, lb));
         tryAdd2variableBuffer(scip, vars[v], lb, varbuf, valbuf, nfixings, TRUE);
      }
   }

   *result = SCIP_SUCCESS;

   SCIPfreeBufferArray(scip, &sols);

   SCIP_CALL( SCIPfreeSol(scip, &rootlpsol) );

   return SCIP_OKAY;
}

/** callback for DINS subproblem changes */
static
DECL_CHANGESUBSCIP(changeSubscipDins)
{  /*lint --e{715}*/
   SCIP_VAR** vars;
   int nintvars;
   int nbinvars;
   int v;

   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );

   /* 1. loop over integer variables and tighten the bounds */
   for( v = nbinvars; v < nintvars; ++v )
   {
      SCIP_Real lb;
      SCIP_Real ub;

      /* skip variables not present in sub-SCIP */
      if( subvars[v] == NULL )
         continue;

      computeIntegerVariableBoundsDins(sourcescip, vars[v], &lb, &ub);

      SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[v], lb) );
      SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[v], ub) );
      ++(*ndomchgs);
   }

   /* 2. add local branching constraint for binary variables */
   SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.1 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );

   *success = TRUE;

   return SCIP_OKAY;
}

/** deinitialization callback for DINS before SCIP is freed */
static
DECL_NHFREE(nhFreeDins)
{
   assert(neighborhood->data.dins != NULL);

   SCIPfreeBlockMemory(scip, &neighborhood->data.dins);

   return SCIP_OKAY;
}

/** deinitialization callback for trustregion before SCIP is freed */
static
DECL_NHFREE(nhFreeTrustregion)
{
   assert(neighborhood->data.trustregion != NULL);

   SCIPfreeBlockMemory(scip, &neighborhood->data.trustregion);

   return SCIP_OKAY;
}

/** add trust region neighborhood constraint and auxiliary objective variable */
static
DECL_CHANGESUBSCIP(changeSubscipTrustregion)
{  /*lint --e{715}*/
   DATA_TRUSTREGION* data;

   data = neighborhood->data.trustregion;

   /* adding the neighborhood constraint for the trust region heuristic */
   SCIP_CALL( SCIPaddTrustregionNeighborhoodConstraint(sourcescip, targetscip, subvars, data->violpenalty) );

   /* incrementing the change in objective since an additional variable is added to the objective to penalize the
    * violation of the trust region.
    */
   ++(*nchgobjs);

   return SCIP_OKAY;
}

/** callback that returns the incumbent solution as a reference point */
static
DECL_NHREFSOL(nhRefsolIncumbent)
{  /*lint --e{715}*/
   assert(scip != NULL);

   if( SCIPgetBestSol(scip) != NULL )
   {
      *result = SCIP_SUCCESS;
      *solptr = SCIPgetBestSol(scip);
   }
   else
   {
      *result = SCIP_DIDNOTFIND;
   }

   return SCIP_OKAY;
}


/** callback function that deactivates a neighborhood on problems with no discrete variables */
static
DECL_NHDEACTIVATE(nhDeactivateDiscreteVars)
{ /*lint --e{715}*/
   assert(scip != NULL);
   assert(deactivate != NULL);

   /* deactivate if no discrete variables are present */
   *deactivate = (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0);

   return SCIP_OKAY;
}

/** callback function that deactivates a neighborhood on problems with no binary variables */
static
DECL_NHDEACTIVATE(nhDeactivateBinVars)
{ /*lint --e{715}*/
   assert(scip != NULL);
   assert(deactivate != NULL);

   /* deactivate if no discrete variables are present */
   *deactivate = (SCIPgetNBinVars(scip) == 0);

   return SCIP_OKAY;
}

/** callback function that deactivates a neighborhood on problems with no objective variables */
static
DECL_NHDEACTIVATE(nhDeactivateObjVars)
{ /*lint --e{715}*/
   assert(scip != NULL);
   assert(deactivate != NULL);

   /* deactivate if no discrete variables are present */
   *deactivate = (SCIPgetNObjVars(scip) == 0);

   return SCIP_OKAY;
}


/** include all neighborhoods */
static
SCIP_RETCODE includeNeighborhoods(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_HEURDATA*        heurdata            /**< heuristic data of the ALNS heuristic */
   )
{
   NH* rens;
   NH* rins;
   NH* mutation;
   NH* localbranching;
   NH* crossover;
   NH* proximity;
   NH* zeroobjective;
   NH* dins;
   NH* trustregion;

   heurdata->nneighborhoods = 0;

   /* include the RENS neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &rens, "rens",
         DEFAULT_MINFIXINGRATE_RENS, DEFAULT_MAXFIXINGRATE_RENS, DEFAULT_ACTIVE_RENS, DEFAULT_PRIORITY_RENS,
         varFixingsRens, changeSubscipRens, NULL, NULL, NULL, NULL, nhDeactivateDiscreteVars) );

   /* include the RINS neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &rins, "rins",
         DEFAULT_MINFIXINGRATE_RINS, DEFAULT_MAXFIXINGRATE_RINS, DEFAULT_ACTIVE_RINS, DEFAULT_PRIORITY_RINS,
         varFixingsRins, NULL, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );

   /* include the mutation neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &mutation, "mutation",
         DEFAULT_MINFIXINGRATE_MUTATION, DEFAULT_MAXFIXINGRATE_MUTATION, DEFAULT_ACTIVE_MUTATION, DEFAULT_PRIORITY_MUTATION,
         varFixingsMutation, NULL, nhInitMutation, nhExitMutation, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );

   /* include the local branching neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &localbranching, "localbranching",
         DEFAULT_MINFIXINGRATE_LOCALBRANCHING, DEFAULT_MAXFIXINGRATE_LOCALBRANCHING, DEFAULT_ACTIVE_LOCALBRANCHING, DEFAULT_PRIORITY_LOCALBRANCHING,
         NULL, changeSubscipLocalbranching, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );

   /* include the crossover neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &crossover, "crossover",
         DEFAULT_MINFIXINGRATE_CROSSOVER, DEFAULT_MAXFIXINGRATE_CROSSOVER, DEFAULT_ACTIVE_CROSSOVER, DEFAULT_PRIORITY_CROSSOVER,
         varFixingsCrossover, NULL,
         nhInitCrossover, nhExitCrossover, nhFreeCrossover, nhRefsolCrossover, nhDeactivateDiscreteVars) );

   /* allocate data for crossover to include the parameter */
   SCIP_CALL( SCIPallocBlockMemory(scip, &crossover->data.crossover) );
   crossover->data.crossover->rng = NULL;

   /* add crossover neighborhood parameters */
   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/alns/crossover/nsols", "the number of solutions that crossover should combine",
         &crossover->data.crossover->nsols, TRUE, DEFAULT_NSOLS_CROSSOVER, 2, 10, NULL, NULL) );

   /* include the Proximity neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &proximity, "proximity",
         DEFAULT_MINFIXINGRATE_PROXIMITY, DEFAULT_MAXFIXINGRATE_PROXIMITY, DEFAULT_ACTIVE_PROXIMITY, DEFAULT_PRIORITY_PROXIMITY,
         NULL, changeSubscipProximity, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );

   /* include the Zeroobjective neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &zeroobjective, "zeroobjective",
         DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE, DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE, DEFAULT_ACTIVE_ZEROOBJECTIVE, DEFAULT_PRIORITY_ZEROOBJECTIVE,
         NULL, changeSubscipZeroobjective, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateObjVars) );

   /* include the DINS neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &dins, "dins",
         DEFAULT_MINFIXINGRATE_DINS, DEFAULT_MAXFIXINGRATE_DINS, DEFAULT_ACTIVE_DINS, DEFAULT_PRIORITY_DINS,
         varFixingsDins, changeSubscipDins, NULL, NULL, nhFreeDins, nhRefsolIncumbent, nhDeactivateBinVars) );

   /* allocate data for DINS to include the parameter */
   SCIP_CALL( SCIPallocBlockMemory(scip, &dins->data.dins) );

   /* add DINS neighborhood parameters */
   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/alns/dins/npoolsols",
         "number of pool solutions where binary solution values must agree",
         &dins->data.dins->npoolsols, TRUE, DEFAULT_NPOOLSOLS_DINS, 1, 100, NULL, NULL) );

   /* include the trustregion neighborhood */
   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &trustregion, "trustregion",
         DEFAULT_MINFIXINGRATE_TRUSTREGION, DEFAULT_MAXFIXINGRATE_TRUSTREGION, DEFAULT_ACTIVE_TRUSTREGION, DEFAULT_PRIORITY_TRUSTREGION,
         NULL, changeSubscipTrustregion, NULL, NULL, nhFreeTrustregion, nhRefsolIncumbent, nhDeactivateBinVars) );

   /* allocate data for trustregion to include the parameter */
   SCIP_CALL( SCIPallocBlockMemory(scip, &trustregion->data.trustregion) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/trustregion/violpenalty",
         "the penalty for each change in the binary variables from the candidate solution",
         &trustregion->data.trustregion->violpenalty, FALSE, DEFAULT_VIOLPENALTY_TRUSTREGION, 0.0, SCIP_REAL_MAX, NULL, NULL) );

   return SCIP_OKAY;
}

/** initialization method of primal heuristic (called after problem was transformed) */
static
SCIP_DECL_HEURINIT(heurInitAlns)
{  /*lint --e{715}*/
   SCIP_HEURDATA* heurdata;
   int i;

   assert(scip != NULL);
   assert(heur != NULL);

   heurdata = SCIPheurGetData(heur);
   assert(heurdata != NULL);

   /* reactivate all neighborhoods if a new problem is read in */
   heurdata->nactiveneighborhoods = heurdata->nneighborhoods;

   /* initialize neighborhoods for new problem */
   for( i = 0; i < heurdata->nneighborhoods; ++i )
   {
      NH* neighborhood = heurdata->neighborhoods[i];

      SCIP_CALL( neighborhoodInit(scip, neighborhood) );

      SCIP_CALL( resetFixingRate(scip, &neighborhood->fixingrate) );

      SCIP_CALL( neighborhoodStatsReset(scip, &neighborhood->stats) );
   }

   /* open reward file for reading */
   if( strncasecmp(heurdata->rewardfilename, DEFAULT_REWARDFILENAME, strlen(DEFAULT_REWARDFILENAME)) != 0 )
   {
      heurdata->rewardfile = fopen(heurdata->rewardfilename, "w");

      if( heurdata->rewardfile == NULL )
      {
         SCIPerrorMessage("Error: Could not open reward file <%s>\n", heurdata->rewardfilename);
         return SCIP_FILECREATEERROR;
      }

      SCIPdebugMsg(scip, "Writing reward information to <%s>\n", heurdata->rewardfilename);
   }
   else
      heurdata->rewardfile = NULL;

   return SCIP_OKAY;
}


/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
static
SCIP_DECL_HEURINITSOL(heurInitsolAlns)
{  /*lint --e{715}*/
   SCIP_HEURDATA* heurdata;
   int i;
   SCIP_Real* priorities;
   unsigned int initseed;

   assert(scip != NULL);
   assert(heur != NULL);

   heurdata = SCIPheurGetData(heur);
   assert(heurdata != NULL);
   heurdata->nactiveneighborhoods = heurdata->nneighborhoods;

   SCIP_CALL( SCIPallocBufferArray(scip, &priorities, heurdata->nactiveneighborhoods) );

   /* init neighborhoods for new problem by resetting their statistics and fixing rate */
   for( i = heurdata->nneighborhoods - 1; i >= 0; --i )
   {
      NH* neighborhood = heurdata->neighborhoods[i];
      SCIP_Bool deactivate;

      SCIP_CALL( neighborhood->nhdeactivate(scip, &deactivate) );

      /* disable inactive neighborhoods */
      if( deactivate || ! neighborhood->active )
      {
         if( heurdata->nactiveneighborhoods - 1 > i )
         {
            assert(heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]->active);
            SCIPswapPointers((void **)&heurdata->neighborhoods[i], (void **)&heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]);
         }
         heurdata->nactiveneighborhoods--;
      }
   }

   /* collect neighborhood priorities */
   for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
      priorities[i] = heurdata->neighborhoods[i]->priority;

   initseed = (unsigned int)(heurdata->seed + SCIPgetNVars(scip));

   /* active neighborhoods might change between init calls, reset functionality must take this into account */
   if( heurdata->bandit != NULL && SCIPbanditGetNActions(heurdata->bandit) != heurdata->nactiveneighborhoods )
   {
      SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );

      heurdata->bandit = NULL;
   }

   if( heurdata->nactiveneighborhoods > 0 )
   {  /* create or reset bandit algorithm */
      if( heurdata->bandit == NULL )
      {
         SCIP_CALL( createBandit(scip, heurdata, priorities, initseed) );

         resetMinimumImprovement(heurdata);
         resetTargetNodeLimit(heurdata);
      }
      else if( heurdata->resetweights )
      {
         SCIP_CALL( SCIPresetBandit(scip, heurdata->bandit, priorities, initseed) );

         resetMinimumImprovement(heurdata);
         resetTargetNodeLimit(heurdata);
      }
   }

   heurdata->usednodes = 0;
   heurdata->ninitneighborhoods = heurdata->nactiveneighborhoods;
   resetCurrentNeighborhood(heurdata);

   SCIPfreeBufferArray(scip, &priorities);

   return SCIP_OKAY;
}


/** deinitialization method of primal heuristic (called before transformed problem is freed) */
static
SCIP_DECL_HEUREXIT(heurExitAlns)
{  /*lint --e{715}*/
   SCIP_HEURDATA* heurdata;
   int i;

   assert(scip != NULL);
   assert(heur != NULL);

   heurdata = SCIPheurGetData(heur);
   assert(heurdata != NULL);

   /* free neighborhood specific data */
   for( i = 0; i < heurdata->nneighborhoods; ++i )
   {
      NH* neighborhood = heurdata->neighborhoods[i];

      SCIP_CALL( neighborhoodExit(scip, neighborhood) );
   }

   if( heurdata->rewardfile != NULL )
   {
      fclose(heurdata->rewardfile);
      heurdata->rewardfile = NULL;
   }

   return SCIP_OKAY;
}

/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
static
SCIP_DECL_HEURFREE(heurFreeAlns)
{  /*lint --e{715}*/
   SCIP_HEURDATA* heurdata;
   int i;

   assert(scip != NULL);
   assert(heur != NULL);

   heurdata = SCIPheurGetData(heur);
   assert(heurdata != NULL);

   /* bandits are only initialized if a problem has been read */
   if( heurdata->bandit != NULL )
   {
      SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
   }

   /* free neighborhoods */
   for( i = 0; i < heurdata->nneighborhoods; ++i )
   {
      SCIP_CALL( alnsFreeNeighborhood(scip, &(heurdata->neighborhoods[i])) );
   }

   SCIPfreeBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS);

   SCIPfreeBlockMemory(scip, &heurdata);

   return SCIP_OKAY;
}

/** output method of statistics table to output file stream 'file' */
static
SCIP_DECL_TABLEOUTPUT(tableOutputNeighborhood)
{ /*lint --e{715}*/
   SCIP_HEURDATA* heurdata;

   assert(SCIPfindHeur(scip, HEUR_NAME) != NULL);
   heurdata = SCIPheurGetData(SCIPfindHeur(scip, HEUR_NAME));
   assert(heurdata != NULL);

   printNeighborhoodStatistics(scip, heurdata, file);

   return SCIP_OKAY;
}

/*
 * primal heuristic specific interface methods
 */

/** creates the alns primal heuristic and includes it in SCIP */
SCIP_RETCODE SCIPincludeHeurAlns(
   SCIP*                 scip                /**< SCIP data structure */
   )
{
   SCIP_HEURDATA* heurdata;
   SCIP_HEUR* heur;

   /* create alns primal heuristic data */
   heurdata = NULL;
   heur = NULL;

   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
   BMSclearMemory(heurdata);

   /* TODO make this a user parameter? */
   heurdata->lplimfac = LPLIMFAC;

   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS) );

   /* include primal heuristic */
   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAlns, heurdata) );

   assert(heur != NULL);

   /* include all neighborhoods */
   SCIP_CALL( includeNeighborhoods(scip, heurdata) );

   /* set non fundamental callbacks via setter functions */
   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAlns) );
   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAlns) );
   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAlns) );
   SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolAlns) );
   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitAlns) );

   /* add alns primal heuristic parameters */
   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
         "maximum number of nodes to regard in the subproblem",
         &heurdata->maxnodes,  TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );

   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
         "offset added to the nodes budget",
         &heurdata->nodesoffset, FALSE, DEFAULT_NODESOFFSET, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );

   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
         "minimum number of nodes required to start a sub-SCIP",
         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );

   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
         "number of nodes since last incumbent solution that the heuristic should wait",
         &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
         "fraction of nodes compared to the main SCIP for budget computation",
         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/startminimprove",
         "initial factor by which ALNS should at least improve the incumbent",
         &heurdata->startminimprove, TRUE, DEFAULT_STARTMINIMPROVE, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprovelow",
         "lower threshold for the minimal improvement over the incumbent",
         &heurdata->minimprovelow, TRUE, DEFAULT_MINIMPROVELOW, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprovehigh",
         "upper bound for the minimal improvement over the incumbent",
         &heurdata->minimprovehigh, TRUE, DEFAULT_MINIMPROVEHIGH, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nsolslim",
         "limit on the number of improving solutions in a sub-SCIP call",
         &heurdata->nsolslim, FALSE, DEFAULT_NSOLSLIM, -1, INT_MAX, NULL, NULL) );

   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/banditalgo",
         "the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy",
         &heurdata->banditalgo, TRUE, DEFAULT_BANDITALGO, "ueg", NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gamma",
         "weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3",
         &heurdata->exp3_gamma, TRUE, DEFAULT_GAMMA, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/beta",
         "reward offset between 0 and 1 at every observation for Exp.3",
         &heurdata->exp3_beta, TRUE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha",
            "parameter to increase the confidence width in UCB",
            &heurdata->ucb_alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.0, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedistances",
         "distances from fixed variables be used for variable prioritization",
         &heurdata->usedistances, TRUE, DEFAULT_USEDISTANCES, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useredcost",
         "should reduced cost scores be used for variable prioritization?",
         &heurdata->useredcost, TRUE, DEFAULT_USEREDCOST, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/domorefixings",
         "should the ALNS heuristic do more fixings by itself based on variable prioritization "
         "until the target fixing rate is reached?",
         &heurdata->domorefixings, TRUE, DEFAULT_DOMOREFIXINGS, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjustfixingrate",
         "should the heuristic adjust the target fixing rate based on the success?",
         &heurdata->adjustfixingrate, TRUE, DEFAULT_ADJUSTFIXINGRATE, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usesubscipheurs",
         "should the heuristic activate other sub-SCIP heuristics during its search?",
         &heurdata->usesubscipheurs, TRUE, DEFAULT_USESUBSCIPHEURS, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rewardcontrol",
         "reward control to increase the weight of the simple solution indicator and decrease the weight of the closed gap reward",
         &heurdata->rewardcontrol, TRUE, DEFAULT_REWARDCONTROL, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/targetnodefactor",
         "factor by which target node number is eventually increased",
         &heurdata->targetnodefactor, TRUE, DEFAULT_TARGETNODEFACTOR, 1.0, 1e+5, NULL, NULL) );

   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/seed",
         "initial random seed for bandit algorithms and random decisions by neighborhoods",
         &heurdata->seed, FALSE, DEFAULT_SEED, 0, INT_MAX, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjustminimprove",
         "should the factor by which the minimum improvement is bound be dynamically updated?",
         &heurdata->adjustminimprove, TRUE, DEFAULT_ADJUSTMINIMPROVE, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjusttargetnodes",
            "should the target nodes be dynamically adjusted?",
            &heurdata->adjusttargetnodes, TRUE, DEFAULT_ADJUSTTARGETNODES, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/eps",
         "increase exploration in epsilon-greedy bandit algorithm",
         &heurdata->epsgreedy_eps, TRUE, DEFAULT_EPS, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rewardbaseline",
         "the reward baseline to separate successful and failed calls",
         &heurdata->rewardbaseline, TRUE, DEFAULT_REWARDBASELINE, 0.0, 0.99, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/resetweights",
         "should the bandit algorithms be reset when a new problem is read?",
         &heurdata->resetweights, TRUE, DEFAULT_RESETWEIGHTS, NULL, NULL) );

   SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/rewardfilename", "file name to store all rewards and the selection of the bandit",
         &heurdata->rewardfilename, TRUE, DEFAULT_REWARDFILENAME, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/subsciprandseeds",
         "should random seeds of sub-SCIPs be altered to increase diversification?",
         &heurdata->subsciprandseeds, TRUE, DEFAULT_SUBSCIPRANDSEEDS, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scalebyeffort",
         "should the reward be scaled by the effort?",
         &heurdata->scalebyeffort, TRUE, DEFAULT_SCALEBYEFFORT, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
         "should cutting planes be copied to the sub-SCIP?",
         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/fixtol",
         "tolerance by which the fixing rate may be missed without generic fixing",
         &heurdata->fixtol, TRUE, DEFAULT_FIXTOL, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/unfixtol",
         "tolerance by which the fixing rate may be exceeded without generic unfixing",
         &heurdata->unfixtol, TRUE, DEFAULT_UNFIXTOL, 0.0, 1.0, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselocalredcost",
         "should local reduced costs be used for generic (un)fixing?",
         &heurdata->uselocalredcost, TRUE, DEFAULT_USELOCALREDCOST, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usepscost",
            "should pseudo cost scores be used for variable priorization?",
            &heurdata->usepscost, TRUE, DEFAULT_USEPSCOST, NULL, NULL) );

   assert(SCIPfindTable(scip, TABLE_NAME_NEIGHBORHOOD) == NULL);
   SCIP_CALL( SCIPincludeTable(scip, TABLE_NAME_NEIGHBORHOOD, TABLE_DESC_NEIGHBORHOOD, TRUE,
         NULL, NULL, NULL, NULL, NULL, NULL, tableOutputNeighborhood,
         NULL, TABLE_POSITION_NEIGHBORHOOD, TABLE_EARLIEST_STAGE_NEIGHBORHOOD) );

   return SCIP_OKAY;
}