1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   heur_alns.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  Adaptive large neighborhood search heuristic that orchestrates popular LNS heuristics
28   	 * @author Gregor Hendel
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/cons_linear.h"
35   	#include "scip/heur_alns.h"
36   	#include "scip/heuristics.h"
37   	#include "scip/pub_bandit_epsgreedy.h"
38   	#include "scip/pub_bandit_exp3.h"
39   	#include "scip/pub_bandit_exp3ix.h"
40   	#include "scip/pub_bandit.h"
41   	#include "scip/pub_bandit_ucb.h"
42   	#include "scip/pub_cons.h"
43   	#include "scip/pub_event.h"
44   	#include "scip/pub_heur.h"
45   	#include "scip/pub_message.h"
46   	#include "scip/pub_misc.h"
47   	#include "scip/pub_misc_select.h"
48   	#include "scip/pub_sol.h"
49   	#include "scip/pub_var.h"
50   	#include "scip/scip_bandit.h"
51   	#include "scip/scip_branch.h"
52   	#include "scip/scip_cons.h"
53   	#include "scip/scip_copy.h"
54   	#include "scip/scip_event.h"
55   	#include "scip/scip_general.h"
56   	#include "scip/scip_heur.h"
57   	#include "scip/scip_lp.h"
58   	#include "scip/scip_mem.h"
59   	#include "scip/scip_message.h"
60   	#include "scip/scip_nodesel.h"
61   	#include "scip/scip_numerics.h"
62   	#include "scip/scip_param.h"
63   	#include "scip/scip_prob.h"
64   	#include "scip/scip_randnumgen.h"
65   	#include "scip/scip_sol.h"
66   	#include "scip/scip_solve.h"
67   	#include "scip/scip_solvingstats.h"
68   	#include "scip/scip_table.h"
69   	#include "scip/scip_timing.h"
70   	#include "scip/scip_tree.h"
71   	#include "scip/scip_var.h"
72   	#include <string.h>
73   	
74   	#if !defined(_WIN32) && !defined(_WIN64)
75   	#include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */
76   	#endif
77   	
78   	#define HEUR_NAME             "alns"
79   	#define HEUR_DESC             "Large neighborhood search heuristic that orchestrates the popular neighborhoods Local Branching, RINS, RENS, DINS etc."
80   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
81   	#define HEUR_PRIORITY         -1100500
82   	#define HEUR_FREQ             20
83   	#define HEUR_FREQOFS          0
84   	#define HEUR_MAXDEPTH         -1
85   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_DURINGLPLOOP
86   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
87   	
88   	#define NNEIGHBORHOODS 9
89   	
90   	#define DEFAULT_SHOWNBSTATS   FALSE /**< show statistics on neighborhoods? */
91   	
92   	/*
93   	 * limit parameters for sub-SCIPs
94   	 */
95   	#define DEFAULT_NODESQUOT        0.1
96   	#define DEFAULT_NODESQUOTMIN     0.0
97   	#define DEFAULT_NODESOFFSET      500LL
98   	#define DEFAULT_NSOLSLIM         3
99   	#define DEFAULT_MINNODES         50LL
100  	#define DEFAULT_MAXNODES         5000LL
101  	#define DEFAULT_WAITINGNODES     25LL  /**< number of nodes since last incumbent solution that the heuristic should wait */
102  	#define DEFAULT_TARGETNODEFACTOR 1.05
103  	#define LRATEMIN                 0.01 /**<  lower bound for learning rate for target nodes and minimum improvement */
104  	#define LPLIMFAC                 4.0
105  	#define DEFAULT_INITDURINGROOT FALSE
106  	#define DEFAULT_MAXCALLSSAMESOL  -1   /**< number of allowed executions of the heuristic on the same incumbent solution */
107  	
108  	/*
109  	 * parameters for the minimum improvement
110  	 */
111  	#define DEFAULT_MINIMPROVELOW    0.01
112  	#define DEFAULT_MINIMPROVEHIGH   0.01
113  	#define MINIMPROVEFAC            1.5
114  	#define DEFAULT_STARTMINIMPROVE  0.01
115  	#define DEFAULT_ADJUSTMINIMPROVE FALSE
116  	#define DEFAULT_ADJUSTTARGETNODES TRUE /**< should the target nodes be dynamically adjusted? */
117  	
118  	/*
119  	 * bandit algorithm parameters
120  	 */
121  	#define DEFAULT_BESTSOLWEIGHT  1
122  	#define DEFAULT_BANDITALGO     'i'  /**< the default bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy, exp.3-(i)x */
123  	#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 */
124  	#define DEFAULT_SCALEBYEFFORT  TRUE /**< should the reward be scaled by the effort? */
125  	#define DEFAULT_RESETWEIGHTS   TRUE /**< should the bandit algorithms be reset when a new problem is read? */
126  	#define DEFAULT_SUBSCIPRANDSEEDS FALSE /**< should random seeds of sub-SCIPs be altered to increase diversification? */
127  	#define DEFAULT_REWARDBASELINE 0.5  /**< the reward baseline to separate successful and failed calls */
128  	#define DEFAULT_FIXTOL         0.1  /**< tolerance by which the fixing rate may be missed without generic fixing */
129  	#define DEFAULT_UNFIXTOL       0.1  /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
130  	#define DEFAULT_USELOCALREDCOST FALSE /**< should local reduced costs be used for generic (un)fixing? */
131  	#define DEFAULT_BETA           0.0  /**< default reward offset between 0 and 1 at every observation for exp3 */
132  	
133  	/*
134  	 * the following 3 parameters have been tuned by a simulation experiment
135  	 * as described in the paper.
136  	 */
137  	#define DEFAULT_EPS            0.4685844   /**< increase exploration in epsilon-greedy bandit algorithm */
138  	#define DEFAULT_ALPHA          0.0016      /**< parameter to increase the confidence width in UCB */
139  	#define DEFAULT_GAMMA          0.07041455  /**< default weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
140  	/*
141  	 * parameters to control variable fixing
142  	 */
143  	#define DEFAULT_USEREDCOST       TRUE  /**< should reduced cost scores be used for variable priorization? */
144  	#define DEFAULT_USEPSCOST        TRUE  /**< should pseudo cost scores be used for variable priorization? */
145  	#define DEFAULT_USEDISTANCES     TRUE  /**< should distances from fixed variables be used for variable priorization */
146  	#define DEFAULT_DOMOREFIXINGS    TRUE  /**< should the ALNS heuristic do more fixings by itself based on variable prioritization
147  	                                         *  until the target fixing rate is reached? */
148  	#define DEFAULT_ADJUSTFIXINGRATE TRUE  /**< should the heuristic adjust the target fixing rate based on the success? */
149  	#define FIXINGRATE_DECAY         0.75  /**< geometric decay for fixing rate adjustments */
150  	#define FIXINGRATE_STARTINC      0.2   /**< initial increment value for fixing rate */
151  	#define DEFAULT_USESUBSCIPHEURS  FALSE /**< should the heuristic activate other sub-SCIP heuristics during its search?  */
152  	#define DEFAULT_COPYCUTS         FALSE /**< should cutting planes be copied to the sub-SCIP? */
153  	#define DEFAULT_REWARDFILENAME   "-"   /**< file name to store all rewards and the selection of the bandit */
154  	
155  	/* individual random seeds */
156  	#define DEFAULT_SEED 113
157  	#define MUTATIONSEED 121
158  	#define CROSSOVERSEED 321
159  	
160  	/* individual neighborhood parameters */
161  	#define DEFAULT_MINFIXINGRATE_RENS 0.3
162  	#define DEFAULT_MAXFIXINGRATE_RENS 0.9
163  	#define DEFAULT_ACTIVE_RENS TRUE
164  	#define DEFAULT_PRIORITY_RENS 1.0
165  	
166  	#define DEFAULT_MINFIXINGRATE_RINS 0.3
167  	#define DEFAULT_MAXFIXINGRATE_RINS 0.9
168  	#define DEFAULT_ACTIVE_RINS TRUE
169  	#define DEFAULT_PRIORITY_RINS 1.0
170  	
171  	#define DEFAULT_MINFIXINGRATE_MUTATION 0.3
172  	#define DEFAULT_MAXFIXINGRATE_MUTATION 0.9
173  	#define DEFAULT_ACTIVE_MUTATION TRUE
174  	#define DEFAULT_PRIORITY_MUTATION 1.0
175  	
176  	#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING 0.3
177  	#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING 0.9
178  	#define DEFAULT_ACTIVE_LOCALBRANCHING TRUE
179  	#define DEFAULT_PRIORITY_LOCALBRANCHING 1.0
180  	
181  	#define DEFAULT_MINFIXINGRATE_PROXIMITY 0.3
182  	#define DEFAULT_MAXFIXINGRATE_PROXIMITY 0.9
183  	#define DEFAULT_ACTIVE_PROXIMITY TRUE
184  	#define DEFAULT_PRIORITY_PROXIMITY 1.0
185  	
186  	#define DEFAULT_MINFIXINGRATE_CROSSOVER 0.3
187  	#define DEFAULT_MAXFIXINGRATE_CROSSOVER 0.9
188  	#define DEFAULT_ACTIVE_CROSSOVER TRUE
189  	#define DEFAULT_PRIORITY_CROSSOVER 1.0
190  	
191  	#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE 0.3
192  	#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE 0.9
193  	#define DEFAULT_ACTIVE_ZEROOBJECTIVE TRUE
194  	#define DEFAULT_PRIORITY_ZEROOBJECTIVE 1.0
195  	
196  	#define DEFAULT_MINFIXINGRATE_DINS 0.3
197  	#define DEFAULT_MAXFIXINGRATE_DINS 0.9
198  	#define DEFAULT_ACTIVE_DINS TRUE
199  	#define DEFAULT_PRIORITY_DINS 1.0
200  	
201  	#define DEFAULT_MINFIXINGRATE_TRUSTREGION 0.3
202  	#define DEFAULT_MAXFIXINGRATE_TRUSTREGION 0.9
203  	#define DEFAULT_ACTIVE_TRUSTREGION FALSE
204  	#define DEFAULT_PRIORITY_TRUSTREGION 1.0
205  	
206  	
207  	#define DEFAULT_NSOLS_CROSSOVER 2 /**< parameter for the number of solutions that crossover should combine */
208  	#define DEFAULT_NPOOLSOLS_DINS  5 /**< number of pool solutions where binary solution values must agree */
209  	#define DEFAULT_VIOLPENALTY_TRUSTREGION 100.0  /**< the penalty for violating the trust region */
210  	
211  	/* event handler properties */
212  	#define EVENTHDLR_NAME         "Alns"
213  	#define EVENTHDLR_DESC         "LP event handler for " HEUR_NAME " heuristic"
214  	#define SCIP_EVENTTYPE_ALNS (SCIP_EVENTTYPE_LPSOLVED | SCIP_EVENTTYPE_SOLFOUND | SCIP_EVENTTYPE_BESTSOLFOUND)
215  	
216  	/* properties of the ALNS neighborhood statistics table */
217  	#define TABLE_NAME_NEIGHBORHOOD                  "neighborhood"
218  	#define TABLE_DESC_NEIGHBORHOOD                  "ALNS neighborhood statistics"
219  	#define TABLE_POSITION_NEIGHBORHOOD              12500                  /**< the position of the statistics table */
220  	#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD        SCIP_STAGE_TRANSFORMED /**< output of the statistics table is only printed from this stage onwards */
221  	
222  	/** reward types of ALNS */
223  	enum RewardType {
224  	   REWARDTYPE_TOTAL,                         /**< combination of the other rewards */
225  	   REWARDTYPE_BESTSOL,                       /**< 1, if a new solution was found, 0 otherwise */
226  	   REWARDTYPE_CLOSEDGAP,                           /**< 0 if no solution was found, closed gap otherwise */
227  	   REWARDTYPE_NOSOLPENALTY,                  /**< 1 if a solution was found, otherwise between 0 and 1 depending on the effort spent  */
228  	   NREWARDTYPES
229  	};
230  	
231  	/*
232  	 * Data structures
233  	 */
234  	
235  	/*
236  	 * additional neighborhood data structures
237  	 */
238  	
239  	
240  	typedef struct data_crossover DATA_CROSSOVER; /**< crossover neighborhood data structure */
241  	
242  	typedef struct data_mutation DATA_MUTATION; /**< mutation neighborhood data structure */
243  	
244  	typedef struct data_dins DATA_DINS; /**< dins neighborhood data structure */
245  	
246  	typedef struct data_trustregion DATA_TRUSTREGION; /**< trustregion neighborhood data structure */
247  	
248  	typedef struct NH_FixingRate NH_FIXINGRATE; /** fixing rate data structure */
249  	
250  	typedef struct NH_Stats NH_STATS; /**< neighborhood statistics data structure */
251  	
252  	typedef struct Nh NH;             /**< neighborhood data structure */
253  	
254  	
255  	/*
256  	 * variable priorization data structure for sorting
257  	 */
258  	typedef struct VarPrio VARPRIO;
259  	
260  	/** callback to collect variable fixings of neighborhood */
261  	 #define DECL_VARFIXINGS(x) SCIP_RETCODE x ( \
262  	   SCIP*                 scip,               /**< SCIP data structure */                     \
263  	   NH*                   neighborhood,       /**< ALNS neighborhood data structure */         \
264  	   SCIP_VAR**            varbuf,             /**< buffer array to collect variables to fix */\
265  	   SCIP_Real*            valbuf,             /**< buffer array to collect fixing values */   \
266  	   int*                  nfixings,           /**< pointer to store the number of fixings */  \
267  	   SCIP_RESULT*          result              /**< result pointer */                          \
268  	   )
269  	
270  	/** callback for subproblem changes other than variable fixings
271  	 *
272  	 *  this callback can be used to further modify the subproblem by changes other than variable fixings.
273  	 *  Typical modifications include restrictions of variable domains, the formulation of additional constraints,
274  	 *  or changed objective coefficients.
275  	 *
276  	 *  The callback should set the \p success pointer to indicate whether it was successful with its modifications or not.
277  	 */
278  	#define DECL_CHANGESUBSCIP(x) SCIP_RETCODE x (  \
279  	   SCIP*                 sourcescip,         /**< source SCIP data structure */\
280  	   SCIP*                 targetscip,         /**< target SCIP data structure */\
281  	   NH*                   neighborhood,       /**< ALNS neighborhood data structure */\
282  	   SCIP_VAR**            subvars,            /**< array of targetscip variables in the same order as the source SCIP variables */\
283  	   int*                  ndomchgs,           /**< pointer to store the number of performed domain changes */\
284  	   int*                  nchgobjs,           /**< pointer to store the number of changed objective coefficients */ \
285  	   int*                  naddedconss,        /**< pointer to store the number of additional constraints */\
286  	   SCIP_Bool*            success             /**< pointer to store if the sub-MIP was successfully adjusted */\
287  	   )
288  	
289  	/** optional initialization callback for neighborhoods when a new problem is read */
290  	#define DECL_NHINIT(x) SCIP_RETCODE x (                                          \
291  	   SCIP*                 scip,               /**< SCIP data structure */         \
292  	   NH*                   neighborhood        /**< neighborhood data structure */ \
293  	   )
294  	
295  	/** deinitialization callback for neighborhoods when exiting a problem */
296  	#define DECL_NHEXIT(x) SCIP_RETCODE x ( \
297  	   SCIP*                 scip,               /**< SCIP data structure */         \
298  	   NH*                   neighborhood        /**< neighborhood data structure */ \
299  	   )
300  	
301  	/** deinitialization callback for neighborhoods before SCIP is freed */
302  	#define DECL_NHFREE(x) SCIP_RETCODE x (      \
303  	   SCIP*                 scip,               /**< SCIP data structure */         \
304  	   NH*                   neighborhood        /**< neighborhood data structure */ \
305  	   )
306  	
307  	/** callback function to return a feasible reference solution for further fixings
308  	 *
309  	 *  The reference solution should be stored in the \p solptr.
310  	 *  The \p result pointer can be used to indicate either
311  	 *
312  	 *  - SCIP_SUCCESS or
313  	 *  - SCIP_DIDNOTFIND
314  	 */
315  	#define DECL_NHREFSOL(x) SCIP_RETCODE x (                                       \
316  	   SCIP*                 scip,               /**< SCIP data structure */  \
317  	   NH*                   neighborhood,       /**< neighborhood data structure */ \
318  	   SCIP_SOL**            solptr,             /**< pointer to store the reference solution */ \
319  	   SCIP_RESULT*          result              /**< pointer to indicate the callback success whether a reference solution is available */ \
320  	   )
321  	
322  	/** callback function to deactivate neighborhoods on problems where they are irrelevant */
323  	#define DECL_NHDEACTIVATE(x) SCIP_RETCODE x (\
324  	   SCIP*                 scip,               /**< SCIP data structure */  \
325  	   SCIP_Bool*            deactivate          /**< pointer to store whether the neighborhood should be deactivated (TRUE) for an instance */ \
326  	   )
327  	
328  	/** sub-SCIP status code enumerator */
329  	enum HistIndex
330  	{
331  	   HIDX_OPT              = 0,                /**< sub-SCIP was solved to optimality  */
332  	   HIDX_USR              = 1,                /**< sub-SCIP was user interrupted */
333  	   HIDX_NODELIM          = 2,                /**< sub-SCIP reached the node limit */
334  	   HIDX_STALLNODE        = 3,                /**< sub-SCIP reached the stall node limit */
335  	   HIDX_INFEAS           = 4,                /**< sub-SCIP was infeasible */
336  	   HIDX_SOLLIM           = 5,                /**< sub-SCIP reached the solution limit */
337  	   HIDX_OTHER            = 6                 /**< sub-SCIP reached none of the above codes */
338  	};
339  	typedef enum HistIndex HISTINDEX;
340  	#define NHISTENTRIES 7
341  	
342  	
343  	/** statistics for a neighborhood */
344  	struct NH_Stats
345  	{
346  	   SCIP_CLOCK*           setupclock;         /**< clock for sub-SCIP setup time */
347  	   SCIP_CLOCK*           submipclock;        /**< clock for the sub-SCIP solve */
348  	   SCIP_Longint          usednodes;          /**< total number of used nodes */
349  	   SCIP_Real             oldupperbound;      /**< upper bound before the sub-SCIP started */
350  	   SCIP_Real             newupperbound;      /**< new upper bound for allrewards mode to work correctly */
351  	   int                   nruns;              /**< number of runs of a neighborhood */
352  	   int                   nrunsbestsol;       /**< number of runs that produced a new incumbent */
353  	   SCIP_Longint          nsolsfound;         /**< the total number of solutions found */
354  	   SCIP_Longint          nbestsolsfound;     /**< the total number of improving solutions found */
355  	   int                   nfixings;           /**< the number of fixings in one run */
356  	   int                   statushist[NHISTENTRIES]; /**< array to count sub-SCIP statuses */
357  	};
358  	
359  	
360  	/** fixing rate data structure to control the amount of target fixings of a neighborhood */
361  	struct NH_FixingRate
362  	{
363  	   SCIP_Real             minfixingrate;      /**< the minimum fixing rate */
364  	   SCIP_Real             targetfixingrate;   /**< the current target fixing rate */
365  	   SCIP_Real             increment;          /**< the current increment by which the target fixing rate is in-/decreased */
366  	   SCIP_Real             maxfixingrate;      /**< the maximum fixing rate */
367  	};
368  	
369  	/** neighborhood data structure with callbacks, statistics, fixing rate */
370  	struct Nh
371  	{
372  	   char*                 name;               /**< the name of this neighborhood */
373  	   NH_FIXINGRATE         fixingrate;         /**< fixing rate for this neighborhood */
374  	   NH_STATS              stats;              /**< statistics for this neighborhood */
375  	   DECL_VARFIXINGS       ((*varfixings));    /**< variable fixings callback for this neighborhood */
376  	   DECL_CHANGESUBSCIP    ((*changesubscip)); /**< callback for subproblem changes other than variable fixings */
377  	   DECL_NHINIT           ((*nhinit));        /**< initialization callback when a new problem is read */
378  	   DECL_NHEXIT           ((*nhexit));        /**< deinitialization callback when exiting a problem */
379  	   DECL_NHFREE           ((*nhfree));        /**< deinitialization callback before SCIP is freed */
380  	   DECL_NHREFSOL         ((*nhrefsol));      /**< callback function to return a reference solution for further fixings, or NULL */
381  	   DECL_NHDEACTIVATE     ((*nhdeactivate));  /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if it is always active */
382  	   SCIP_Bool             active;             /**< is this neighborhood active or not? */
383  	   SCIP_Real             priority;           /**< positive call priority to initialize bandit algorithms */
384  	   union
385  	   {
386  	      DATA_MUTATION*     mutation;           /**< mutation data */
387  	      DATA_CROSSOVER*    crossover;          /**< crossover data */
388  	      DATA_DINS*         dins;               /**< dins data */
389  	      DATA_TRUSTREGION*  trustregion;        /**< trustregion data */
390  	   }                     data;               /**< data object for neighborhood specific data */
391  	};
392  	
393  	/** mutation neighborhood data structure */
394  	struct data_mutation
395  	{
396  	   SCIP_RANDNUMGEN*      rng;                /**< random number generator */
397  	};
398  	
399  	/** crossover neighborhood data structure */
400  	struct data_crossover
401  	{
402  	   int                   nsols;              /**< the number of solutions that crossover should combine */
403  	   SCIP_RANDNUMGEN*      rng;                /**< random number generator to draw from the solution pool */
404  	   SCIP_SOL*             selsol;             /**< best selected solution by crossover as reference point */
405  	};
406  	
407  	/** dins neighborhood data structure */
408  	struct data_dins
409  	{
410  	   int                   npoolsols;          /**< number of pool solutions where binary solution values must agree */
411  	};
412  	
413  	struct data_trustregion
414  	{
415  	   SCIP_Real             violpenalty;        /**< the penalty for violating the trust region */
416  	};
417  	
418  	/** primal heuristic data */
419  	struct SCIP_HeurData
420  	{
421  	   NH**                  neighborhoods;      /**< array of neighborhoods */
422  	   SCIP_BANDIT*          bandit;             /**< bandit algorithm */
423  	   SCIP_SOL*             lastcallsol;        /**< incumbent when the heuristic was last called */
424  	   char*                 rewardfilename;     /**< file name to store all rewards and the selection of the bandit */
425  	   FILE*                 rewardfile;         /**< reward file pointer, or NULL */
426  	   SCIP_Longint          nodesoffset;        /**< offset added to the nodes budget */
427  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes in a single sub-SCIP */
428  	   SCIP_Longint          targetnodes;        /**< targeted number of nodes to start a sub-SCIP */
429  	   SCIP_Longint          minnodes;           /**< minimum number of nodes required to start a sub-SCIP */
430  	   SCIP_Longint          usednodes;          /**< total number of nodes already spent in sub-SCIPs */
431  	   SCIP_Longint          waitingnodes;       /**< number of nodes since last incumbent solution that the heuristic should wait */
432  	   SCIP_Real             nodesquot;          /**< fraction of nodes compared to the main SCIP for budget computation */
433  	   SCIP_Real             nodesquotmin;       /**< lower bound on fraction of nodes compared to the main SCIP for budget computation */
434  	   SCIP_Real             startminimprove;    /**< initial factor by which ALNS should at least improve the incumbent */
435  	   SCIP_Real             minimprovelow;      /**< lower threshold for the minimal improvement over the incumbent */
436  	   SCIP_Real             minimprovehigh;     /**< upper bound for the minimal improvement over the incumbent */
437  	   SCIP_Real             minimprove;         /**< factor by which ALNS should at least improve the incumbent */
438  	   SCIP_Real             lplimfac;           /**< limit fraction of LPs per node to interrupt sub-SCIP */
439  	   SCIP_Real             exp3_gamma;         /**< weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
440  	   SCIP_Real             exp3_beta;          /**< reward offset between 0 and 1 at every observation for exp3 */
441  	   SCIP_Real             epsgreedy_eps;      /**< increase exploration in epsilon-greedy bandit algorithm */
442  	   SCIP_Real             ucb_alpha;          /**< parameter to increase the confidence width in UCB */
443  	   SCIP_Real             rewardcontrol;      /**< reward control to increase the weight of the simple solution indicator
444  	                                               *  and decrease the weight of the closed gap reward */
445  	   SCIP_Real             targetnodefactor;   /**< factor by which target node number is eventually increased */
446  	   SCIP_Real             rewardbaseline;     /**< the reward baseline to separate successful and failed calls */
447  	   SCIP_Real             fixtol;             /**< tolerance by which the fixing rate may be missed without generic fixing */
448  	   SCIP_Real             unfixtol;           /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
449  	   int                   nneighborhoods;     /**< number of neighborhoods */
450  	   int                   nactiveneighborhoods;/**< number of active neighborhoods */
451  	   int                   ninitneighborhoods; /**< neighborhoods that were used at least one time */
452  	   int                   nsolslim;           /**< limit on the number of improving solutions in a sub-SCIP call */
453  	   int                   seed;               /**< initial random seed for bandit algorithms and random decisions by neighborhoods */
454  	   int                   currneighborhood;   /**< index of currently selected neighborhood */
455  	   int                   ndelayedcalls;      /**< the number of delayed calls */
456  	   int                   maxcallssamesol;    /**< number of allowed executions of the heuristic on the same incumbent solution
457  	                                              *   (-1: no limit, 0: number of active neighborhoods) */
458  	   SCIP_Longint          firstcallthissol;   /**< counter for the number of calls on this incumbent */
459  	   char                  banditalgo;         /**< the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy */
460  	   SCIP_Bool             useredcost;         /**< should reduced cost scores be used for variable prioritization? */
461  	   SCIP_Bool             usedistances;       /**< should distances from fixed variables be used for variable prioritization */
462  	   SCIP_Bool             usepscost;          /**< should pseudo cost scores be used for variable prioritization? */
463  	   SCIP_Bool             domorefixings;      /**< should the ALNS heuristic do more fixings by itself based on variable prioritization
464  	                                               *  until the target fixing rate is reached? */
465  	   SCIP_Bool             adjustfixingrate;   /**< should the heuristic adjust the target fixing rate based on the success? */
466  	   SCIP_Bool             usesubscipheurs;    /**< should the heuristic activate other sub-SCIP heuristics during its search?  */
467  	   SCIP_Bool             adjustminimprove;   /**< should the factor by which the minimum improvement is bound be dynamically updated? */
468  	   SCIP_Bool             adjusttargetnodes;  /**< should the target nodes be dynamically adjusted? */
469  	   SCIP_Bool             resetweights;       /**< should the bandit algorithms be reset when a new problem is read? */
470  	   SCIP_Bool             subsciprandseeds;   /**< should random seeds of sub-SCIPs be altered to increase diversification? */
471  	   SCIP_Bool             scalebyeffort;      /**< should the reward be scaled by the effort? */
472  	   SCIP_Bool             copycuts;           /**< should cutting planes be copied to the sub-SCIP? */
473  	   SCIP_Bool             uselocalredcost;    /**< should local reduced costs be used for generic (un)fixing? */
474  	   SCIP_Bool             initduringroot;     /**< should the heuristic be executed multiple times during the root node? */
475  	   SCIP_Bool             shownbstats;        /**< show statistics on neighborhoods? */
476  	};
477  	
478  	/** event handler data */
479  	struct SCIP_EventData
480  	{
481  	   SCIP_VAR**            subvars;            /**< the variables of the subproblem */
482  	   SCIP*                 sourcescip;         /**< original SCIP data structure */
483  	   SCIP_HEUR*            heur;               /**< alns heuristic structure */
484  	   SCIP_Longint          nodelimit;          /**< node limit of the run */
485  	   SCIP_Real             lplimfac;           /**< limit fraction of LPs per node to interrupt sub-SCIP */
486  	   NH_STATS*             runstats;           /**< run statistics for the current neighborhood */
487  	   SCIP_Bool             allrewardsmode;     /**< true if solutions should only be checked for reward comparisons */
488  	};
489  	
490  	/** represents limits for the sub-SCIP solving process */
491  	struct SolveLimits
492  	{
493  	   SCIP_Longint          nodelimit;          /**< maximum number of solving nodes for the sub-SCIP */
494  	   SCIP_Real             memorylimit;        /**< memory limit for the sub-SCIP */
495  	   SCIP_Real             timelimit;          /**< time limit for the sub-SCIP */
496  	   SCIP_Longint          stallnodes;         /**< maximum number of nodes without (primal) stalling */
497  	};
498  	
499  	typedef struct SolveLimits SOLVELIMITS;
500  	
501  	/** data structure that can be used for variable prioritization for additional fixings */
502  	struct VarPrio
503  	{
504  	   SCIP*                 scip;               /**< SCIP data structure */
505  	   SCIP_Real*            randscores;         /**< random scores for prioritization */
506  	   int*                  distances;          /**< breadth-first distances from already fixed variables */
507  	   SCIP_Real*            redcostscores;      /**< reduced cost scores for fixing a variable to a reference value */
508  	   SCIP_Real*            pscostscores;       /**< pseudocost scores for fixing a variable to a reference value */
509  	   unsigned int          useredcost:1;       /**< should reduced cost scores be used for variable prioritization? */
510  	   unsigned int          usedistances:1;     /**< should distances from fixed variables be used for variable prioritization */
511  	   unsigned int          usepscost:1;        /**< should pseudo cost scores be used for variable prioritization? */
512  	};
513  	
514  	/*
515  	 * Local methods
516  	 */
517  	
518  	/** Reset target fixing rate */
519  	static
520  	SCIP_RETCODE resetFixingRate(
521  	   SCIP*                 scip,               /**< SCIP data structure */
522  	   NH_FIXINGRATE*        fixingrate          /**< heuristic fixing rate */
523  	   )
524  	{
525  	   assert(scip != NULL);
526  	   assert(fixingrate != NULL);
527  	   fixingrate->increment = FIXINGRATE_STARTINC;
528  	
529  	   /* always start with the most conservative value */
530  	   fixingrate->targetfixingrate = fixingrate->maxfixingrate;
531  	
532  	   return SCIP_OKAY;
533  	}
534  	
535  	/** reset the currently active neighborhood */
536  	static
537  	void resetCurrentNeighborhood(
538  	   SCIP_HEURDATA*        heurdata
539  	   )
540  	{
541  	   assert(heurdata != NULL);
542  	   heurdata->currneighborhood = -1;
543  	   heurdata->ndelayedcalls = 0;
544  	}
545  	
546  	/** update increment for fixing rate */
547  	static
548  	void updateFixingRateIncrement(
549  	   NH_FIXINGRATE*        fx                  /**< fixing rate */
550  	   )
551  	{
552  	   fx->increment *= FIXINGRATE_DECAY;
553  	   fx->increment = MAX(fx->increment, LRATEMIN);
554  	}
555  	
556  	
557  	/** increase fixing rate
558  	 *
559  	 *  decrease also the rate by which the target fixing rate is adjusted
560  	 */
561  	static
562  	void increaseFixingRate(
563  	   NH_FIXINGRATE*        fx                  /**< fixing rate */
564  	   )
565  	{
566  	   fx->targetfixingrate += fx->increment;
567  	   fx->targetfixingrate = MIN(fx->targetfixingrate, fx->maxfixingrate);
568  	}
569  	
570  	/** decrease fixing rate
571  	 *
572  	 *  decrease also the rate by which the target fixing rate is adjusted
573  	 */
574  	static
575  	void decreaseFixingRate(
576  	   NH_FIXINGRATE*        fx                  /**< fixing rate */
577  	   )
578  	{
579  	   fx->targetfixingrate -= fx->increment;
580  	   fx->targetfixingrate = MAX(fx->targetfixingrate, fx->minfixingrate);
581  	}
582  	
583  	/** update fixing rate based on the results of the current run */
584  	static
585  	void updateFixingRate(
586  	   NH*                   neighborhood,       /**< neighborhood */
587  	   SCIP_STATUS           subscipstatus,      /**< status of the sub-SCIP run */
588  	   NH_STATS*             runstats            /**< run statistics for this run */
589  	   )
590  	{
591  	   NH_FIXINGRATE* fx;
592  	
593  	   fx = &neighborhood->fixingrate;
594  	
595  	   switch (subscipstatus)
596  	   {
597  	   case SCIP_STATUS_OPTIMAL:
598  	   case SCIP_STATUS_INFEASIBLE:
599  	   case SCIP_STATUS_INFORUNBD:
600  	   case SCIP_STATUS_SOLLIMIT:
601  	   case SCIP_STATUS_BESTSOLLIMIT:
602  	      /* decrease the fixing rate (make subproblem harder) */
603  	      decreaseFixingRate(fx);
604  	      break;
605  	   case SCIP_STATUS_STALLNODELIMIT:
606  	   case SCIP_STATUS_USERINTERRUPT:
607  	   case SCIP_STATUS_TERMINATE:
608  	   case SCIP_STATUS_NODELIMIT:
609  	      /* increase the fixing rate (make the subproblem easier) only if no solution was found */
610  	      if( runstats->nbestsolsfound <= 0 )
611  	         increaseFixingRate(fx);
612  	      break;
613  	      /* fall through cases to please lint */
614  	   case SCIP_STATUS_UNKNOWN:
615  	   case SCIP_STATUS_TOTALNODELIMIT:
616  	   case SCIP_STATUS_TIMELIMIT:
617  	   case SCIP_STATUS_MEMLIMIT:
618  	   case SCIP_STATUS_GAPLIMIT:
619  	   case SCIP_STATUS_RESTARTLIMIT:
620  	   case SCIP_STATUS_UNBOUNDED:
621  	   default:
622  	      break;
623  	   }
624  	
625  	   updateFixingRateIncrement(fx);
626  	}
627  	
628  	/** increase target node limit */
629  	static
630  	void increaseTargetNodeLimit(
631  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
632  	   )
633  	{
634  	   heurdata->targetnodes = (SCIP_Longint)(heurdata->targetnodes * heurdata->targetnodefactor) + 1;
635  	
636  	   /* respect upper and lower parametrized bounds on targetnodes */
637  	   if( heurdata->targetnodes > heurdata->maxnodes )
638  	      heurdata->targetnodes = heurdata->maxnodes;
639  	}
640  	
641  	/** reset target node limit */
642  	static
643  	void resetTargetNodeLimit(
644  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
645  	   )
646  	{
647  	   heurdata->targetnodes = heurdata->minnodes;
648  	}
649  	
650  	/** update target node limit based on the current run results */
651  	static
652  	void updateTargetNodeLimit(
653  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
654  	   NH_STATS*             runstats,           /**< statistics of the run */
655  	   SCIP_STATUS           subscipstatus       /**< status of the sub-SCIP run */
656  	   )
657  	{
658  	   switch (subscipstatus)
659  	   {
660  	   case SCIP_STATUS_STALLNODELIMIT:
661  	   case SCIP_STATUS_NODELIMIT:
662  	      /* the subproblem could be explored more */
663  	      if( runstats->nbestsolsfound == 0 )
664  	         increaseTargetNodeLimit(heurdata);
665  	      break;
666  	   case SCIP_STATUS_OPTIMAL:
667  	   case SCIP_STATUS_INFEASIBLE:
668  	   case SCIP_STATUS_INFORUNBD:
669  	   case SCIP_STATUS_SOLLIMIT:
670  	   case SCIP_STATUS_BESTSOLLIMIT:
671  	      break;
672  	   case SCIP_STATUS_USERINTERRUPT:
673  	   case SCIP_STATUS_TERMINATE:
674  	   case SCIP_STATUS_UNKNOWN:
675  	   case SCIP_STATUS_TOTALNODELIMIT:
676  	   case SCIP_STATUS_TIMELIMIT:
677  	   case SCIP_STATUS_MEMLIMIT:
678  	   case SCIP_STATUS_GAPLIMIT:
679  	   case SCIP_STATUS_RESTARTLIMIT:
680  	   case SCIP_STATUS_UNBOUNDED:
681  	      break;
682  	   default:
683  	      break;
684  	   }
685  	}
686  	
687  	/** reset the minimum improvement for the sub-SCIPs */
688  	static
689  	void resetMinimumImprovement(
690  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
691  	   )
692  	{
693  	   assert(heurdata != NULL);
694  	   heurdata->minimprove = heurdata->startminimprove;
695  	}
696  	
697  	/** increase minimum improvement for the sub-SCIPs */
698  	static
699  	void increaseMinimumImprovement(
700  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
701  	   )
702  	{
703  	   assert(heurdata != NULL);
704  	
705  	   heurdata->minimprove *= MINIMPROVEFAC;
706  	   heurdata->minimprove = MIN(heurdata->minimprove, heurdata->minimprovehigh);
707  	}
708  	
709  	/** decrease the minimum improvement for the sub-SCIPs */
710  	static
711  	void decreaseMinimumImprovement(
712  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
713  	   )
714  	{
715  	   assert(heurdata != NULL);
716  	
717  	   heurdata->minimprove /= MINIMPROVEFAC;
718  	   SCIPdebugMessage("%.4f", heurdata->minimprovelow);
719  	   heurdata->minimprove = MAX(heurdata->minimprove, heurdata->minimprovelow);
720  	}
721  	
722  	/** update the minimum improvement based on the status of the sub-SCIP */
723  	static
724  	void updateMinimumImprovement(
725  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
726  	   SCIP_STATUS           subscipstatus,      /**< status of the sub-SCIP run */
727  	   NH_STATS*             runstats            /**< run statistics for this run */
728  	   )
729  	{
730  	   assert(heurdata != NULL);
731  	
732  	   /* if the sub-SCIP status was infeasible, we rather want to make the sub-SCIP easier
733  	    * with a smaller minimum improvement.
734  	    *
735  	    * If a solution limit was reached, we may, set it higher.
736  	    */
737  	   switch (subscipstatus)
738  	   {
739  	   case SCIP_STATUS_INFEASIBLE:
740  	   case SCIP_STATUS_INFORUNBD:
741  	      /* subproblem was infeasible, probably due to the minimum improvement -> decrease minimum improvement */
742  	      decreaseMinimumImprovement(heurdata);
743  	
744  	      break;
745  	   case SCIP_STATUS_SOLLIMIT:
746  	   case SCIP_STATUS_BESTSOLLIMIT:
747  	   case SCIP_STATUS_OPTIMAL:
748  	      /* subproblem could be optimally solved -> try higher minimum improvement */
749  	      increaseMinimumImprovement(heurdata);
750  	      break;
751  	   case SCIP_STATUS_NODELIMIT:
752  	   case SCIP_STATUS_STALLNODELIMIT:
753  	   case SCIP_STATUS_USERINTERRUPT:
754  	      /* subproblem was too hard, decrease minimum improvement */
755  	      if( runstats->nbestsolsfound <= 0 )
756  	         decreaseMinimumImprovement(heurdata);
757  	      break;
758  	   case SCIP_STATUS_UNKNOWN:
759  	   case SCIP_STATUS_TOTALNODELIMIT:
760  	   case SCIP_STATUS_TIMELIMIT:
761  	   case SCIP_STATUS_MEMLIMIT:
762  	   case SCIP_STATUS_GAPLIMIT:
763  	   case SCIP_STATUS_RESTARTLIMIT:
764  	   case SCIP_STATUS_UNBOUNDED:
765  	   case SCIP_STATUS_TERMINATE:
766  	   default:
767  	      break;
768  	   }
769  	}
770  	
771  	/** Reset neighborhood statistics */
772  	static
773  	SCIP_RETCODE neighborhoodStatsReset(
774  	   SCIP*                 scip,               /**< SCIP data structure */
775  	   NH_STATS*             stats               /**< neighborhood statistics */
776  	   )
777  	{
778  	   assert(scip != NULL);
779  	   assert(stats != NULL);
780  	
781  	   stats->nbestsolsfound = 0;
782  	   stats->nruns = 0;
783  	   stats->nrunsbestsol = 0;
784  	   stats->nsolsfound = 0;
785  	   stats->usednodes = 0L;
786  	   stats->nfixings = 0L;
787  	
788  	   BMSclearMemoryArray(stats->statushist, NHISTENTRIES);
789  	
790  	   SCIP_CALL( SCIPresetClock(scip, stats->setupclock) );
791  	   SCIP_CALL( SCIPresetClock(scip, stats->submipclock) );
792  	
793  	   return SCIP_OKAY;
794  	}
795  	
796  	/** create a neighborhood of the specified name and include it into the ALNS heuristic */
797  	static
798  	SCIP_RETCODE alnsIncludeNeighborhood(
799  	   SCIP*                 scip,               /**< SCIP data structure */
800  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS heuristic */
801  	   NH**                  neighborhood,       /**< pointer to store the neighborhood */
802  	   const char*           name,               /**< name for this neighborhood */
803  	   SCIP_Real             minfixingrate,      /**< default value for minfixingrate parameter of this neighborhood */
804  	   SCIP_Real             maxfixingrate,      /**< default value for maxfixingrate parameter of this neighborhood */
805  	   SCIP_Bool             active,             /**< default value for active parameter of this neighborhood */
806  	   SCIP_Real             priority,           /**< positive call priority to initialize bandit algorithms */
807  	   DECL_VARFIXINGS       ((*varfixings)),    /**< variable fixing callback for this neighborhood, or NULL */
808  	   DECL_CHANGESUBSCIP    ((*changesubscip)), /**< subscip changes callback for this neighborhood, or NULL */
809  	   DECL_NHINIT           ((*nhinit)),        /**< initialization callback for neighborhood, or NULL */
810  	   DECL_NHEXIT           ((*nhexit)),        /**< deinitialization callback for neighborhood, or NULL */
811  	   DECL_NHFREE           ((*nhfree)),        /**< deinitialization callback before SCIP is freed, or NULL */
812  	   DECL_NHREFSOL         ((*nhrefsol)),      /**< callback function to return a reference solution for further fixings, or NULL */
813  	   DECL_NHDEACTIVATE     ((*nhdeactivate))   /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if neighborhood is always active */
814  	   )
815  	{
816  	   char paramname[SCIP_MAXSTRLEN];
817  	
818  	   assert(scip != NULL);
819  	   assert(heurdata != NULL);
820  	   assert(neighborhood != NULL);
821  	   assert(name != NULL);
822  	
823  	   SCIP_CALL( SCIPallocBlockMemory(scip, neighborhood) );
824  	   assert(*neighborhood != NULL);
825  	
826  	   SCIP_ALLOC( BMSduplicateMemoryArray(&(*neighborhood)->name, name, strlen(name)+1) );
827  	
828  	   SCIP_CALL( SCIPcreateClock(scip, &(*neighborhood)->stats.setupclock) );
829  	   SCIP_CALL( SCIPcreateClock(scip, &(*neighborhood)->stats.submipclock) );
830  	
831  	   (*neighborhood)->changesubscip = changesubscip;
832  	   (*neighborhood)->varfixings = varfixings;
833  	   (*neighborhood)->nhinit = nhinit;
834  	   (*neighborhood)->nhexit = nhexit;
835  	   (*neighborhood)->nhfree = nhfree;
836  	   (*neighborhood)->nhrefsol = nhrefsol;
837  	   (*neighborhood)->nhdeactivate = nhdeactivate;
838  	
839  	   /* add parameters for this neighborhood */
840  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/minfixingrate", name);
841  	   SCIP_CALL( SCIPaddRealParam(scip, paramname, "minimum fixing rate for this neighborhood",
842  	         &(*neighborhood)->fixingrate.minfixingrate, TRUE, minfixingrate, 0.0, 1.0, NULL, NULL) );
843  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/maxfixingrate", name);
844  	   SCIP_CALL( SCIPaddRealParam(scip, paramname, "maximum fixing rate for this neighborhood",
845  	         &(*neighborhood)->fixingrate.maxfixingrate, TRUE, maxfixingrate, 0.0, 1.0, NULL, NULL) );
846  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/active", name);
847  	   SCIP_CALL( SCIPaddBoolParam(scip, paramname, "is this neighborhood active?",
848  	         &(*neighborhood)->active, TRUE, active, NULL, NULL) );
849  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/alns/%s/priority", name);
850  	   SCIP_CALL( SCIPaddRealParam(scip, paramname, "positive call priority to initialize bandit algorithms",
851  	         &(*neighborhood)->priority, TRUE, priority, 1e-2, 1.0, NULL, NULL) );
852  	
853  	   /* add the neighborhood to the ALNS heuristic */
854  	   heurdata->neighborhoods[heurdata->nneighborhoods++] = (*neighborhood);
855  	
856  	   return SCIP_OKAY;
857  	}
858  	
859  	/** release all data and free neighborhood */
860  	static
861  	SCIP_RETCODE alnsFreeNeighborhood(
862  	   SCIP*                 scip,               /**< SCIP data structure */
863  	   NH**                  neighborhood        /**< pointer to neighborhood that should be freed */
864  	   )
865  	{
866  	   NH* nhptr;
867  	   assert(scip != NULL);
868  	   assert(neighborhood != NULL);
869  	
870  	   nhptr = *neighborhood;
871  	   assert(nhptr != NULL);
872  	
873  	   BMSfreeMemoryArray(&nhptr->name);
874  	
875  	   /* release further, neighborhood specific data structures */
876  	   if( nhptr->nhfree != NULL )
877  	   {
878  	      SCIP_CALL( nhptr->nhfree(scip, nhptr) );
879  	   }
880  	
881  	   SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.setupclock) );
882  	   SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.submipclock) );
883  	
884  	   SCIPfreeBlockMemory(scip, neighborhood);
885  	   *neighborhood = NULL;
886  	
887  	   return SCIP_OKAY;
888  	}
889  	
890  	/** initialize neighborhood specific data */
891  	static
892  	SCIP_RETCODE neighborhoodInit(
893  	   SCIP*                 scip,               /**< SCIP data structure */
894  	   NH*                   neighborhood        /**< neighborhood to initialize */
895  	   )
896  	{
897  	   assert(scip != NULL);
898  	   assert(neighborhood != NULL);
899  	
900  	   /* call the init callback of the neighborhood */
901  	   if( neighborhood->nhinit != NULL )
902  	   {
903  	      SCIP_CALL( neighborhood->nhinit(scip, neighborhood) );
904  	   }
905  	
906  	   return SCIP_OKAY;
907  	}
908  	
909  	/** deinitialize neighborhood specific data */
910  	static
911  	SCIP_RETCODE neighborhoodExit(
912  	   SCIP*                 scip,               /**< SCIP data structure */
913  	   NH*                   neighborhood        /**< neighborhood to initialize */
914  	   )
915  	{
916  	   assert(scip != NULL);
917  	   assert(neighborhood != NULL);
918  	
919  	   if( neighborhood->nhexit != NULL )
920  	   {
921  	      SCIP_CALL( neighborhood->nhexit(scip, neighborhood) );
922  	   }
923  	
924  	   return SCIP_OKAY;
925  	}
926  	
927  	/** creates a new solution for the original problem by copying the solution of the subproblem */
928  	static
929  	SCIP_RETCODE transferSolution(
930  	   SCIP*                 subscip,            /**< SCIP data structure of the subproblem */
931  	   SCIP_EVENTDATA*       eventdata           /**< event handler data */
932  	   )
933  	{
934  	   SCIP*      sourcescip;         /* original SCIP data structure */
935  	   SCIP_VAR** subvars;            /* the variables of the subproblem */
936  	   SCIP_HEUR* heur;               /* alns heuristic structure */
937  	   SCIP_SOL*  subsol;             /* solution of the subproblem */
938  	   SCIP_SOL*  newsol;             /* solution to be created for the original problem */
939  	   SCIP_Bool  success;
940  	   NH_STATS*  runstats;
941  	   SCIP_SOL*  oldbestsol;
942  	
943  	   assert(subscip != NULL);
944  	
945  	   subsol = SCIPgetBestSol(subscip);
946  	   assert(subsol != NULL);
947  	
948  	   sourcescip = eventdata->sourcescip;
949  	   subvars = eventdata->subvars;
950  	   heur = eventdata->heur;
951  	   runstats = eventdata->runstats;
952  	   assert(sourcescip != NULL);
953  	   assert(sourcescip != subscip);
954  	   assert(heur != NULL);
955  	   assert(subvars != NULL);
956  	   assert(runstats != NULL);
957  	
958  	   SCIP_CALL( SCIPtranslateSubSol(sourcescip, subscip, subsol, heur, subvars, &newsol) );
959  	
960  	   oldbestsol = SCIPgetBestSol(sourcescip);
961  	
962  	   /* in the special, experimental all rewards mode, the solution is only checked for feasibility
963  	    * but not stored
964  	    */
965  	   if( eventdata->allrewardsmode )
966  	   {
967  	      SCIP_CALL( SCIPcheckSol(sourcescip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
968  	
969  	      if( success )
970  	      {
971  	         runstats->nsolsfound++;
972  	         if( SCIPgetSolTransObj(sourcescip, newsol) < SCIPgetCutoffbound(sourcescip) )
973  	            runstats->nbestsolsfound++;
974  	      }
975  	
976  	      SCIP_CALL( SCIPfreeSol(sourcescip, &newsol) );
977  	   }
978  	   else
979  	   {
980  	      /* try to add new solution to scip and free it immediately */
981  	      SCIP_CALL( SCIPtrySolFree(sourcescip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
982  	
983  	      if( success )
984  	      {
985  	         runstats->nsolsfound++;
986  	         if( SCIPgetBestSol(sourcescip) != oldbestsol )
987  	            runstats->nbestsolsfound++;
988  	      }
989  	   }
990  	
991  	   /* update new upper bound for reward later */
992  	   runstats->newupperbound = SCIPgetUpperbound(sourcescip);
993  	
994  	   return SCIP_OKAY;
995  	}
996  	
997  	
998  	/* ---------------- Callback methods of event handler ---------------- */
999  	
1000 	/** execution callback of the event handler
1001 	 *
1002 	 * transfer new solutions or interrupt the solving process manually
1003 	 */
1004 	static
1005 	SCIP_DECL_EVENTEXEC(eventExecAlns)
1006 	{
1007 	   assert(eventhdlr != NULL);
1008 	   assert(eventdata != NULL);
1009 	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1010 	   assert(event != NULL);
1011 	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_ALNS);
1012 	   assert(eventdata != NULL);
1013 	
1014 	   /* treat the different atomic events */
1015 	   switch( SCIPeventGetType(event) )
1016 	   {
1017 	   case SCIP_EVENTTYPE_SOLFOUND:
1018 	   case SCIP_EVENTTYPE_BESTSOLFOUND:
1019 	      /* try to transfer the solution to the original SCIP */
1020 	      SCIP_CALL( transferSolution(scip, eventdata) );
1021 	      break;
1022 	   case SCIP_EVENTTYPE_LPSOLVED:
1023 	      /* interrupt solution process of sub-SCIP */
1024 	      if( SCIPgetNLPs(scip) > eventdata->lplimfac * eventdata->nodelimit )
1025 	      {
1026 	         SCIPdebugMsg(scip, "interrupt after  %" SCIP_LONGINT_FORMAT " LPs\n", SCIPgetNLPs(scip));
1027 	         SCIP_CALL( SCIPinterruptSolve(scip) );
1028 	      }
1029 	      break;
1030 	   default:
1031 	      break;
1032 	   }
1033 	
1034 	   return SCIP_OKAY;
1035 	}
1036 	
1037 	/** initialize neighborhood statistics before the next run */
1038 	static
1039 	void initRunStats(
1040 	   SCIP*                 scip,               /**< SCIP data structure */
1041 	   NH_STATS*             stats               /**< run statistics */
1042 	   )
1043 	{
1044 	   stats->nbestsolsfound = 0;
1045 	   stats->nsolsfound = 0;
1046 	   stats->usednodes = 0L;
1047 	   stats->nfixings = 0;
1048 	   stats->oldupperbound = SCIPgetUpperbound(scip);
1049 	   stats->newupperbound = SCIPgetUpperbound(scip);
1050 	}
1051 	
1052 	/** update run stats after the sub SCIP was solved */
1053 	static
1054 	void updateRunStats(
1055 	   NH_STATS*             stats,              /**< run statistics */
1056 	   SCIP*                 subscip             /**< sub-SCIP instance, or NULL */
1057 	   )
1058 	{
1059 	   /* treat an untransformed subscip as if none was created */
1060 	   if( subscip != NULL && ! SCIPisTransformed(subscip) )
1061 	      subscip = NULL;
1062 	
1063 	   stats->usednodes = subscip != NULL ? SCIPgetNNodes(subscip) : 0L;
1064 	}
1065 	
1066 	/** get the histogram index for this status */
1067 	static
1068 	int getHistIndex(
1069 	   SCIP_STATUS           subscipstatus       /**< sub-SCIP status */
1070 	   )
1071 	{
1072 	   switch (subscipstatus)
1073 	   {
1074 	   case SCIP_STATUS_OPTIMAL:
1075 	      return (int)HIDX_OPT;
1076 	   case SCIP_STATUS_INFEASIBLE:
1077 	      return (int)HIDX_INFEAS;
1078 	   case SCIP_STATUS_NODELIMIT:
1079 	      return (int)HIDX_NODELIM;
1080 	   case SCIP_STATUS_STALLNODELIMIT:
1081 	      return (int)HIDX_STALLNODE;
1082 	   case SCIP_STATUS_SOLLIMIT:
1083 	   case SCIP_STATUS_BESTSOLLIMIT:
1084 	      return (int)HIDX_SOLLIM;
1085 	   case SCIP_STATUS_USERINTERRUPT:
1086 	      return (int)HIDX_USR;
1087 	   default:
1088 	      return (int)HIDX_OTHER;
1089 	   } /*lint !e788*/
1090 	}
1091 	
1092 	/** print neighborhood statistics */
1093 	static
1094 	void printNeighborhoodStatistics(
1095 	   SCIP*                 scip,               /**< SCIP data structure */
1096 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1097 	   FILE*                 file                /**< file handle, or NULL for standard out */
1098 	   )
1099 	{
1100 	   int i;
1101 	   int j;
1102 	   HISTINDEX statusses[] = {HIDX_OPT, HIDX_INFEAS, HIDX_NODELIM, HIDX_STALLNODE, HIDX_SOLLIM, HIDX_USR, HIDX_OTHER};
1103 	
1104 	   if( ! heurdata->shownbstats )
1105 	      return;
1106 	
1107 	   SCIPinfoMessage(scip, file, "Neighborhoods      : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %4s %4s %4s %4s %4s %4s %4s %4s\n",
1108 	            "Calls", "SetupTime", "SolveTime", "SolveNodes", "Sols", "Best", "Exp3", "Exp3-IX", "EpsGreedy", "UCB", "TgtFixRate",
1109 	            "Opt", "Inf", "Node", "Stal", "Sol", "Usr", "Othr", "Actv");
1110 	
1111 	   /* loop over neighborhoods and fill in statistics */
1112 	   for( i = 0; i < heurdata->nneighborhoods; ++i )
1113 	   {
1114 	      NH* neighborhood;
1115 	      SCIP_Real proba;
1116 	      SCIP_Real probaix;
1117 	      SCIP_Real ucb;
1118 	      SCIP_Real epsgreedyweight;
1119 	
1120 	      neighborhood = heurdata->neighborhoods[i];
1121 	      SCIPinfoMessage(scip, file, "  %-17s:", neighborhood->name);
1122 	      SCIPinfoMessage(scip, file, " %10d", neighborhood->stats.nruns);
1123 	      SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, neighborhood->stats.setupclock) );
1124 	      SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, neighborhood->stats.submipclock) );
1125 	      SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.usednodes );
1126 	      SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.nsolsfound);
1127 	      SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.nbestsolsfound);
1128 	
1129 	      proba = 0.0;
1130 	      probaix = 0.0;
1131 	      ucb = 1.0;
1132 	      epsgreedyweight = -1.0;
1133 	
1134 	      if( heurdata->bandit != NULL && i < heurdata->nactiveneighborhoods )
1135 	      {
1136 	         switch (heurdata->banditalgo)
1137 	         {
1138 	         case 'u':
1139 	            ucb = SCIPgetConfidenceBoundUcb(heurdata->bandit, i);
1140 	            break;
1141 	         case 'g':
1142 	            epsgreedyweight = SCIPgetWeightsEpsgreedy(heurdata->bandit)[i];
1143 	            break;
1144 	         case 'e':
1145 	            proba = SCIPgetProbabilityExp3(heurdata->bandit, i);
1146 	            break;
1147 	         case 'i':
1148 	            probaix = SCIPgetProbabilityExp3IX(heurdata->bandit, i);
1149 	            break;
1150 	         default:
1151 	            break;
1152 	         }
1153 	      }
1154 	
1155 	      SCIPinfoMessage(scip, file, " %10.5f", proba);
1156 	      SCIPinfoMessage(scip, file, " %10.5f", probaix);
1157 	      SCIPinfoMessage(scip, file, " %10.5f", epsgreedyweight);
1158 	      SCIPinfoMessage(scip, file, " %10.5f", ucb);
1159 	      SCIPinfoMessage(scip, file, " %10.3f", neighborhood->fixingrate.targetfixingrate);
1160 	
1161 	      /* loop over status histogram */
1162 	      for( j = 0; j < NHISTENTRIES; ++j )
1163 	         SCIPinfoMessage(scip, file, " %4d", neighborhood->stats.statushist[statusses[j]]);
1164 	
1165 	      SCIPinfoMessage(scip, file, " %4d", i < heurdata->nactiveneighborhoods ? 1 : 0);
1166 	      SCIPinfoMessage(scip, file, "\n");
1167 	   }
1168 	}
1169 	
1170 	/** update the statistics of the neighborhood based on the sub-SCIP run */
1171 	static
1172 	void updateNeighborhoodStats(
1173 	   NH_STATS*             runstats,           /**< run statistics */
1174 	   NH*                   neighborhood,       /**< the selected neighborhood */
1175 	   SCIP_STATUS           subscipstatus       /**< status of the sub-SCIP solve */
1176 	   )
1177 	{  /*lint --e{715}*/
1178 	   NH_STATS* stats;
1179 	   stats = &neighborhood->stats;
1180 	
1181 	   /* copy run statistics into neighborhood statistics */
1182 	   stats->nbestsolsfound += runstats->nbestsolsfound;
1183 	   stats->nsolsfound += runstats->nsolsfound;
1184 	   stats->usednodes += runstats->usednodes;
1185 	   stats->nruns += 1;
1186 	
1187 	   if( runstats->nbestsolsfound > 0 )
1188 	      stats->nrunsbestsol += DEFAULT_BESTSOLWEIGHT;
1189 	   else if( runstats->nsolsfound > 0 )
1190 	      stats->nrunsbestsol++;
1191 	
1192 	   /* update the counter for the subscip status */
1193 	   ++stats->statushist[getHistIndex(subscipstatus)];
1194 	}
1195 	
1196 	/** sort callback for variable pointers using the ALNS variable prioritization
1197 	 *
1198 	 *  the variable prioritization works hierarchically as follows. A variable
1199 	 *  a has the higher priority over b iff
1200 	 *
1201 	 *  - variable distances should be used and a has a smaller distance than b
1202 	 *  - variable reduced costs should be used and a has a smaller score than b
1203 	 *  - variable pseudo costs should be used and a has a smaller score than b
1204 	 *  - based on previously assigned random scores
1205 	 *
1206 	 *  @note: distances are context-based. For fixing more variables,
1207 	 *  distances are initialized from the already fixed variables.
1208 	 *  For unfixing variables, distances are initialized starting
1209 	 *  from the unfixed variables
1210 	 */
1211 	static
1212 	SCIP_DECL_SORTINDCOMP(sortIndCompAlns)
1213 	{  /*lint --e{715}*/
1214 	   VARPRIO* varprio;
1215 	
1216 	   varprio = (VARPRIO*)dataptr;
1217 	   assert(varprio != NULL);
1218 	   assert(varprio->randscores != NULL);
1219 	
1220 	   if( ind1 == ind2 )
1221 	      return 0;
1222 	
1223 	   /* priority is on distances, if enabled. The variable which is closer in a breadth-first search sense to
1224 	    * the already fixed variables has precedence */
1225 	   if( varprio->usedistances )
1226 	   {
1227 	      int dist1;
1228 	      int dist2;
1229 	
1230 	      dist1 = varprio->distances[ind1];
1231 	      dist2 = varprio->distances[ind2];
1232 	
1233 	      if( dist1 < 0 )
1234 	         dist1 = INT_MAX;
1235 	
1236 	      if( dist2 < 0 )
1237 	         dist2 = INT_MAX;
1238 	
1239 	      assert(varprio->distances != NULL);
1240 	      if( dist1 < dist2 )
1241 	         return -1;
1242 	      else if( dist1 > dist2 )
1243 	         return 1;
1244 	   }
1245 	
1246 	   assert(! varprio->usedistances || varprio->distances[ind1] == varprio->distances[ind2]);
1247 	
1248 	   /* if the indices tie considering distances or distances are disabled -> use reduced cost information instead */
1249 	   if( varprio->useredcost )
1250 	   {
1251 	      assert(varprio->redcostscores != NULL);
1252 	
1253 	      if( varprio->redcostscores[ind1] < varprio->redcostscores[ind2] )
1254 	         return -1;
1255 	      else if( varprio->redcostscores[ind1] > varprio->redcostscores[ind2] )
1256 	         return 1;
1257 	   }
1258 	
1259 	   /* use pseudo cost scores if reduced costs are disabled or a tie was found */
1260 	   if( varprio->usepscost )
1261 	   {
1262 	      assert(varprio->pscostscores != NULL);
1263 	
1264 	      /* prefer the variable with smaller pseudocost score */
1265 	      if( varprio->pscostscores[ind1] < varprio->pscostscores[ind2] )
1266 	         return -1;
1267 	      else if( varprio->pscostscores[ind1] > varprio->pscostscores[ind2] )
1268 	         return 1;
1269 	   }
1270 	
1271 	   if( varprio->randscores[ind1] < varprio->randscores[ind2] )
1272 	      return -1;
1273 	   else if( varprio->randscores[ind1] > varprio->randscores[ind2] )
1274 	      return 1;
1275 	
1276 	   return ind1 - ind2;
1277 	}
1278 	
1279 	/** Compute the reduced cost score for this variable in the reference solution */
1280 	static
1281 	SCIP_Real getVariableRedcostScore(
1282 	   SCIP*                 scip,               /**< SCIP data structure */
1283 	   SCIP_VAR*             var,                /**< the variable for which the score should be computed */
1284 	   SCIP_Real             refsolval,          /**< solution value in reference solution */
1285 	   SCIP_Bool             uselocalredcost     /**< should local reduced costs be used for generic (un)fixing? */
1286 	   )
1287 	{
1288 	   SCIP_Real bestbound;
1289 	   SCIP_Real redcost;
1290 	   SCIP_Real score;
1291 	   assert(scip != NULL);
1292 	   assert(var != NULL);
1293 	
1294 	   /* prefer column variables */
1295 	   if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
1296 	      return SCIPinfinity(scip);
1297 	
1298 	   if( ! uselocalredcost )
1299 	   {
1300 	      redcost = SCIPvarGetBestRootRedcost(var);
1301 	
1302 	      bestbound = SCIPvarGetBestRootSol(var);
1303 	
1304 	      /* using global reduced costs, the two factors yield a nonnegative score within tolerances */
1305 	      assert(SCIPisDualfeasZero(scip, redcost)
1306 	         || (SCIPisDualfeasNegative(scip, redcost) && ! SCIPisFeasPositive(scip, refsolval - bestbound))
1307 	         || (SCIPisDualfeasPositive(scip, redcost) && ! SCIPisFeasNegative(scip, refsolval - bestbound)));
1308 	   }
1309 	   else
1310 	   {
1311 	      /* this can be safely asserted here, since the heuristic would not reach this point, otherwise */
1312 	      assert(SCIPhasCurrentNodeLP(scip));
1313 	      assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
1314 	
1315 	      redcost = SCIPgetVarRedcost(scip, var);
1316 	
1317 	      bestbound = SCIPvarGetLPSol(var);
1318 	   }
1319 	
1320 	   assert(! SCIPisInfinity(scip, REALABS(bestbound)));
1321 	   assert(SCIPisDualfeasZero(scip, redcost) || SCIPisFeasIntegral(scip, bestbound));
1322 	
1323 	   score = redcost * (refsolval - bestbound);
1324 	
1325 	   /* max out numerical inaccuracies from global scores */
1326 	   if( ! uselocalredcost )
1327 	      score = MAX(score, 0.0);
1328 	
1329 	   return score;
1330 	}
1331 	
1332 	/** get the pseudo cost score of this variable with respect to the reference solution */
1333 	static
1334 	SCIP_Real getVariablePscostScore(
1335 	   SCIP*                 scip,               /**< SCIP data structure */
1336 	   SCIP_VAR*             var,                /**< the variable for which the score should be computed */
1337 	   SCIP_Real             refsolval,          /**< solution value in reference solution */
1338 	   SCIP_Bool             uselocallpsol       /**< should local LP solution be used? */
1339 	   )
1340 	{
1341 	   SCIP_Real lpsolval;
1342 	
1343 	   assert(scip != NULL);
1344 	   assert(var != NULL);
1345 	
1346 	   /* variables that aren't LP columns have no pseudocost score */
1347 	   if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
1348 	      return 0.0;
1349 	
1350 	   lpsolval = uselocallpsol ? SCIPvarGetLPSol(var) : SCIPvarGetRootSol(var);
1351 	
1352 	   /* the score is 0.0 if the values are equal */
1353 	   if( SCIPisEQ(scip, lpsolval, refsolval) )
1354 	      return 0.0;
1355 	   else
1356 	      return SCIPgetVarPseudocostVal(scip, var, refsolval - lpsolval);
1357 	}
1358 	
1359 	/** add variable and solution value to buffer data structure for variable fixings. The method checks if
1360 	 *  the value still lies within the variable bounds. The value stays unfixed otherwise.
1361 	 */
1362 	static
1363 	void tryAdd2variableBuffer(
1364 	   SCIP*                 scip,               /**< SCIP data structure */
1365 	   SCIP_VAR*             var,                /**< (source) SCIP variable that should be added to the buffer */
1366 	   SCIP_Real             val,                /**< fixing value for this variable */
1367 	   SCIP_VAR**            varbuf,             /**< variable buffer to store variables that should be fixed */
1368 	   SCIP_Real*            valbuf,             /**< value buffer to store fixing values */
1369 	   int*                  nfixings,           /**< pointer to number of fixed buffer variables, will be increased by 1 */
1370 	   SCIP_Bool             integer             /**< is this an integer variable? */
1371 	   )
1372 	{
1373 	   /* todo: this assert can fail when there was a dual reduction that changed a variable to
1374 	    * an integral type after the reference solution was found and the variable has a fractional
1375 	    * value in this solution, e.g., for boxQP instances (spar*)
1376 	    * implicit integer variables could also be an issue, as they can take fractional values in feasible solutions
1377 	    */
1378 	   assert(SCIPisFeasIntegral(scip, val) || ! SCIPvarIsIntegral(var));
1379 	   assert(*nfixings < SCIPgetNVars(scip));
1380 	
1381 	   /* round the value to its nearest integer */
1382 	   if( integer )
1383 	      val = SCIPfloor(scip, val + 0.5);
1384 	
1385 	   /* only add fixing if it is still valid within the global variable bounds. Invalidity
1386 	    * of this solution value may come from a dual reduction that was performed after the solution from which
1387 	    * this value originated was found
1388 	    */
1389 	   if( SCIPvarGetLbGlobal(var) <= val && val <= SCIPvarGetUbGlobal(var) )
1390 	   {
1391 	      varbuf[*nfixings] = var;
1392 	      valbuf[*nfixings] = val;
1393 	      ++(*nfixings);
1394 	   }
1395 	}
1396 	
1397 	/** query neighborhood for a reference solution for further fixings */
1398 	static
1399 	SCIP_RETCODE neighborhoodGetRefsol(
1400 	   SCIP*                 scip,               /**< SCIP data structure */
1401 	   NH*                   neighborhood,       /**< ALNS neighborhood data structure */
1402 	   SCIP_SOL**            solptr              /**< solution pointer */
1403 	   )
1404 	{
1405 	   assert(solptr != NULL);
1406 	   assert(scip != NULL);
1407 	   assert(neighborhood != NULL);
1408 	
1409 	   *solptr = NULL;
1410 	   if( neighborhood->nhrefsol != NULL )
1411 	   {
1412 	      SCIP_RESULT result;
1413 	      SCIP_CALL( neighborhood->nhrefsol(scip, neighborhood, solptr, &result) );
1414 	
1415 	      if( result == SCIP_DIDNOTFIND )
1416 	         *solptr = NULL;
1417 	      else
1418 	         assert(*solptr != NULL);
1419 	   }
1420 	
1421 	   return SCIP_OKAY;
1422 	}
1423 	
1424 	/** fix additional variables found in feasible reference solution if the ones that the neighborhood found were not enough
1425 	 *
1426 	 *  use not always the best solution for the values, but a reference solution provided by the neighborhood itself
1427 	 *
1428 	 *  @note it may happen that the target fixing rate is not completely reached. This is the case if intermediate,
1429 	 *  dual reductions render the solution values of the reference solution infeasible for
1430 	 *  the current, global variable bounds.
1431 	 */
1432 	static
1433 	SCIP_RETCODE alnsFixMoreVariables(
1434 	   SCIP*                 scip,               /**< SCIP data structure */
1435 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
1436 	   SCIP_SOL*             refsol,             /**< feasible reference solution for more variable fixings */
1437 	   SCIP_VAR**            varbuf,             /**< buffer array to store variables to fix */
1438 	   SCIP_Real*            valbuf,             /**< buffer array to store fixing values */
1439 	   int*                  nfixings,           /**< pointer to store the number of fixings */
1440 	   int                   ntargetfixings,     /**< number of required target fixings */
1441 	   SCIP_Bool*            success             /**< pointer to store whether the target fixings have been successfully reached */
1442 	   )
1443 	{
1444 	   VARPRIO varprio;
1445 	   SCIP_VAR** vars;
1446 	   SCIP_Real* redcostscores;
1447 	   SCIP_Real* pscostscores;
1448 	   SCIP_Real* solvals;
1449 	   SCIP_RANDNUMGEN* rng;
1450 	   SCIP_VAR** unfixedvars;
1451 	   SCIP_Bool* isfixed;
1452 	   int* distances;
1453 	   int* perm;
1454 	   SCIP_Real* randscores;
1455 	   int nbinvars;
1456 	   int nintvars;
1457 	   int nbinintvars;
1458 	   int nvars;
1459 	   int b;
1460 	   int nvarstoadd;
1461 	   int nunfixedvars;
1462 	
1463 	   assert(scip != NULL);
1464 	   assert(varbuf != NULL);
1465 	   assert(nfixings != NULL);
1466 	   assert(success != NULL);
1467 	   assert(heurdata != NULL);
1468 	   assert(refsol != NULL);
1469 	
1470 	   *success = FALSE;
1471 	
1472 	   /* if the user parameter forbids more fixings, return immediately */
1473 	   if( ! heurdata->domorefixings )
1474 	      return SCIP_OKAY;
1475 	
1476 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1477 	
1478 	   nbinintvars = nbinvars + nintvars;
1479 	
1480 	   if( ntargetfixings >= nbinintvars )
1481 	      return SCIP_OKAY;
1482 	
1483 	   /* determine the number of required additional fixings */
1484 	   nvarstoadd = ntargetfixings - *nfixings;
1485 	   if( nvarstoadd == 0 )
1486 	      return SCIP_OKAY;
1487 	
1488 	   varprio.usedistances = heurdata->usedistances && (*nfixings >= 1);
1489 	   varprio.useredcost = heurdata->useredcost;
1490 	   varprio.usepscost = heurdata->usepscost;
1491 	   varprio.scip = scip;
1492 	   rng = SCIPbanditGetRandnumgen(heurdata->bandit);
1493 	   assert(rng != NULL);
1494 	
1495 	   SCIP_CALL( SCIPallocBufferArray(scip, &randscores, nbinintvars) );
1496 	   SCIP_CALL( SCIPallocBufferArray(scip, &perm, nbinintvars) );
1497 	   SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1498 	   SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, nbinintvars) );
1499 	   SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nbinintvars) );
1500 	   SCIP_CALL( SCIPallocBufferArray(scip, &isfixed, nbinintvars) );
1501 	   SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
1502 	   SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, nbinintvars) );
1503 	
1504 	   /* initialize variable graph distances from already fixed variables */
1505 	   if( varprio.usedistances )
1506 	   {
1507 	      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, varbuf, *nfixings, distances, INT_MAX, INT_MAX, ntargetfixings) );
1508 	   }
1509 	   else
1510 	   {
1511 	      /* initialize all equal distances to make them irrelevant */
1512 	      BMSclearMemoryArray(distances, nbinintvars);
1513 	   }
1514 	
1515 	   BMSclearMemoryArray(isfixed, nbinintvars);
1516 	
1517 	   /* mark binary and integer variables if they are fixed */
1518 	   for( b = 0; b < *nfixings; ++b )
1519 	   {
1520 	      int probindex;
1521 	
1522 	      assert(varbuf[b] != NULL);
1523 	      probindex = SCIPvarGetProbindex(varbuf[b]);
1524 	      assert(probindex >= 0);
1525 	
1526 	      if( probindex < nbinintvars )
1527 	         isfixed[probindex] = TRUE;
1528 	   }
1529 	
1530 	   SCIP_CALL( SCIPgetSolVals(scip, refsol, nbinintvars, vars, solvals) );
1531 	
1532 	   /* assign scores to unfixed every discrete variable of the problem */
1533 	   nunfixedvars = 0;
1534 	   for( b = 0; b < nbinintvars; ++b )
1535 	   {
1536 	      SCIP_VAR* var = vars[b];
1537 	
1538 	      /* filter fixed variables */
1539 	      if( isfixed[b] )
1540 	         continue;
1541 	
1542 	      /* filter variables with a solution value outside its global bounds */
1543 	      if( solvals[b] < SCIPvarGetLbGlobal(var) - 0.5 || solvals[b] > SCIPvarGetUbGlobal(var) + 0.5 )
1544 	         continue;
1545 	
1546 	      redcostscores[nunfixedvars] = getVariableRedcostScore(scip, var, solvals[b], heurdata->uselocalredcost);
1547 	      pscostscores[nunfixedvars] = getVariablePscostScore(scip, var, solvals[b], heurdata->uselocalredcost);
1548 	
1549 	      unfixedvars[nunfixedvars] = var;
1550 	      perm[nunfixedvars] = nunfixedvars;
1551 	      randscores[nunfixedvars] = SCIPrandomGetReal(rng, 0.0, 1.0);
1552 	
1553 	      /* these assignments are based on the fact that nunfixedvars <= b */
1554 	      solvals[nunfixedvars] = solvals[b];
1555 	      distances[nunfixedvars] = distances[b];
1556 	
1557 	      SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
1558 	         SCIPvarGetName(var), distances[nunfixedvars], redcostscores[nunfixedvars],
1559 	         pscostscores[nunfixedvars], randscores[nunfixedvars]);
1560 	
1561 	      nunfixedvars++;
1562 	   }
1563 	
1564 	   /* use selection algorithm (order of the variables does not matter) for quickly completing the fixing */
1565 	   varprio.randscores = randscores;
1566 	   varprio.distances = distances;
1567 	   varprio.redcostscores = redcostscores;
1568 	   varprio.pscostscores = pscostscores;
1569 	
1570 	   nvarstoadd = MIN(nunfixedvars, nvarstoadd);
1571 	
1572 	   /* select the first nvarstoadd many variables according to the score */
1573 	   if( nvarstoadd < nunfixedvars )
1574 	      SCIPselectInd(perm, sortIndCompAlns, &varprio, nvarstoadd, nunfixedvars);
1575 	
1576 	   /* loop over the first elements of the selection defined in permutation. They represent the best variables */
1577 	   for( b = 0; b < nvarstoadd; ++b )
1578 	   {
1579 	      int permindex = perm[b];
1580 	      assert(permindex >= 0);
1581 	      assert(permindex < nunfixedvars);
1582 	
1583 	      tryAdd2variableBuffer(scip, unfixedvars[permindex], solvals[permindex], varbuf, valbuf, nfixings, TRUE);
1584 	   }
1585 	
1586 	   *success = TRUE;
1587 	
1588 	   /* free buffer arrays */
1589 	   SCIPfreeBufferArray(scip, &pscostscores);
1590 	   SCIPfreeBufferArray(scip, &unfixedvars);
1591 	   SCIPfreeBufferArray(scip, &isfixed);
1592 	   SCIPfreeBufferArray(scip, &solvals);
1593 	   SCIPfreeBufferArray(scip, &redcostscores);
1594 	   SCIPfreeBufferArray(scip, &distances);
1595 	   SCIPfreeBufferArray(scip, &perm);
1596 	   SCIPfreeBufferArray(scip, &randscores);
1597 	
1598 	   return SCIP_OKAY;
1599 	}
1600 	
1601 	/** create the bandit algorithm for the heuristic depending on the user parameter */
1602 	static
1603 	SCIP_RETCODE createBandit(
1604 	   SCIP*                 scip,               /**< SCIP data structure */
1605 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
1606 	   SCIP_Real*            priorities,         /**< call priorities for active neighborhoods */
1607 	   unsigned int          initseed            /**< initial random seed */
1608 	   )
1609 	{
1610 	   switch (heurdata->banditalgo)
1611 	   {
1612 	   case 'u':
1613 	      SCIP_CALL( SCIPcreateBanditUcb(scip, &heurdata->bandit, priorities,
1614 	            heurdata->ucb_alpha, heurdata->nactiveneighborhoods, initseed) );
1615 	      break;
1616 	
1617 	   case 'e':
1618 	      SCIP_CALL( SCIPcreateBanditExp3(scip, &heurdata->bandit, priorities,
1619 	            heurdata->exp3_gamma, heurdata->exp3_beta, heurdata->nactiveneighborhoods, initseed) );
1620 	      break;
1621 	
1622 	   case 'i':
1623 	      SCIP_CALL( SCIPcreateBanditExp3IX(scip, &heurdata->bandit, priorities,
1624 	            heurdata->nactiveneighborhoods, initseed) );
1625 	      break;
1626 	
1627 	   case 'g':
1628 	      SCIP_CALL( SCIPcreateBanditEpsgreedy(scip, &heurdata->bandit, priorities,
1629 	            heurdata->epsgreedy_eps, FALSE, FALSE, 0.9, 0, heurdata->nactiveneighborhoods, initseed) );
1630 	      break;
1631 	
1632 	   default:
1633 	      SCIPerrorMessage("Unknown bandit parameter %c\n", heurdata->banditalgo);
1634 	      return SCIP_INVALIDDATA;
1635 	   }
1636 	
1637 	   return SCIP_OKAY;
1638 	}
1639 	
1640 	/*
1641 	 * Callback methods of primal heuristic
1642 	 */
1643 	
1644 	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1645 	static
1646 	SCIP_DECL_HEURCOPY(heurCopyAlns)
1647 	{  /*lint --e{715}*/
1648 	   assert(scip != NULL);
1649 	   assert(heur != NULL);
1650 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1651 	
1652 	   /* call inclusion method of primal heuristic */
1653 	   SCIP_CALL( SCIPincludeHeurAlns(scip) );
1654 	
1655 	   return SCIP_OKAY;
1656 	}
1657 	
1658 	/** unfix some of the variables because there are too many fixed
1659 	 *
1660 	 *  a variable is ideally unfixed if it is close to other unfixed variables
1661 	 *  and fixing it has a high reduced cost impact
1662 	 */
1663 	static
1664 	SCIP_RETCODE alnsUnfixVariables(
1665 	   SCIP*                 scip,               /**< SCIP data structure */
1666 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
1667 	   SCIP_VAR**            varbuf,             /**< buffer array to store variables to fix */
1668 	   SCIP_Real*            valbuf,             /**< buffer array to store fixing values */
1669 	   int*                  nfixings,           /**< pointer to store the number of fixings */
1670 	   int                   ntargetfixings,     /**< number of required target fixings */
1671 	   SCIP_Bool*            success             /**< pointer to store whether the target fixings have been successfully reached */
1672 	   )
1673 	{
1674 	   VARPRIO varprio;
1675 	   SCIP_Real* redcostscores;
1676 	   SCIP_Real* pscostscores;
1677 	   SCIP_Real* randscores;
1678 	   SCIP_VAR** unfixedvars;
1679 	   SCIP_VAR** varbufcpy;
1680 	   SCIP_Real* valbufcpy;
1681 	   SCIP_Bool* isfixedvar;
1682 	   SCIP_VAR** vars;
1683 	   SCIP_RANDNUMGEN* rng;
1684 	   int* distances;
1685 	   int* fixeddistances;
1686 	   int* perm;
1687 	   int nvars;
1688 	   int i;
1689 	   int nbinintvars;
1690 	   int nunfixed;
1691 	
1692 	   *success = FALSE;
1693 	
1694 	   nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1695 	   if( nbinintvars == 0 )
1696 	      return SCIP_OKAY;
1697 	
1698 	   assert(*nfixings > 0);
1699 	
1700 	   nvars = SCIPgetNVars(scip);
1701 	   SCIP_CALL( SCIPallocBufferArray(scip, &isfixedvar, nvars) );
1702 	   SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
1703 	   SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1704 	   SCIP_CALL( SCIPallocBufferArray(scip, &fixeddistances, *nfixings) );
1705 	   SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, *nfixings) );
1706 	   SCIP_CALL( SCIPallocBufferArray(scip, &randscores, *nfixings) );
1707 	   SCIP_CALL( SCIPallocBufferArray(scip, &perm, *nfixings) );
1708 	   SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, *nfixings) );
1709 	
1710 	   SCIP_CALL( SCIPduplicateBufferArray(scip, &varbufcpy, varbuf, *nfixings) );
1711 	   SCIP_CALL( SCIPduplicateBufferArray(scip, &valbufcpy, valbuf, *nfixings) );
1712 	
1713 	   /*
1714 	    * collect the unfixed binary and integer variables
1715 	    */
1716 	   BMSclearMemoryArray(isfixedvar, nvars);
1717 	   /* loop over fixed variables and mark their respective positions as fixed */
1718 	   for( i = 0; i < *nfixings; ++i )
1719 	   {
1720 	      int probindex = SCIPvarGetProbindex(varbuf[i]);
1721 	
1722 	      assert(probindex >= 0);
1723 	
1724 	      isfixedvar[probindex] = TRUE;
1725 	   }
1726 	
1727 	   nunfixed = 0;
1728 	   vars = SCIPgetVars(scip);
1729 	   /* collect unfixed binary and integer variables */
1730 	   for( i = 0; i < nbinintvars; ++i )
1731 	   {
1732 	      if( ! isfixedvar[i] )
1733 	         unfixedvars[nunfixed++] = vars[i];
1734 	   }
1735 	
1736 	   varprio.usedistances = heurdata->usedistances && nunfixed > 0;
1737 	
1738 	   /* collect distances of all fixed variables from those that are not fixed */
1739 	   if( varprio.usedistances )
1740 	   {
1741 	      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, unfixedvars, nunfixed, distances, INT_MAX, INT_MAX, INT_MAX) );
1742 	
1743 	      for( i = 0; i < *nfixings; ++i )
1744 	      {
1745 	         int probindex = SCIPvarGetProbindex(varbuf[i]);
1746 	         if( probindex >= 0 )
1747 	            fixeddistances[i] = distances[probindex];
1748 	      }
1749 	   }
1750 	   else
1751 	   {
1752 	      BMSclearMemoryArray(fixeddistances, *nfixings);
1753 	   }
1754 	
1755 	   /* collect reduced cost scores of the fixings and assign random scores */
1756 	   rng = SCIPbanditGetRandnumgen(heurdata->bandit);
1757 	   for( i = 0; i < *nfixings; ++i )
1758 	   {
1759 	      SCIP_VAR* fixedvar = varbuf[i];
1760 	      SCIP_Real fixval = valbuf[i];
1761 	
1762 	      /* use negative reduced cost and pseudo cost scores to prefer variable fixings with small score */
1763 	      redcostscores[i] = - getVariableRedcostScore(scip, fixedvar, fixval, heurdata->uselocalredcost);
1764 	      pscostscores[i] = - getVariablePscostScore(scip, fixedvar, fixval, heurdata->uselocalredcost);
1765 	      randscores[i] = SCIPrandomGetReal(rng, 0.0, 1.0);
1766 	      perm[i] = i;
1767 	
1768 	      SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
1769 	            SCIPvarGetName(fixedvar), fixeddistances[i], redcostscores[i], pscostscores[i], randscores[i]);
1770 	   }
1771 	
1772 	   varprio.distances = fixeddistances;
1773 	   varprio.randscores = randscores;
1774 	   varprio.redcostscores = redcostscores;
1775 	   varprio.pscostscores = pscostscores;
1776 	   varprio.useredcost = heurdata->useredcost;
1777 	   varprio.usepscost = heurdata->usepscost;
1778 	   varprio.scip = scip;
1779 	
1780 	   /* scores are assigned in such a way that variables with a smaller score should be fixed last */
1781 	   SCIPselectDownInd(perm, sortIndCompAlns, &varprio, ntargetfixings, *nfixings);
1782 	
1783 	   /* bring the desired variables to the front of the array */
1784 	   for( i = 0; i < ntargetfixings; ++i )
1785 	   {
1786 	      valbuf[i] = valbufcpy[perm[i]];
1787 	      varbuf[i] = varbufcpy[perm[i]];
1788 	   }
1789 	
1790 	   *nfixings = ntargetfixings;
1791 	
1792 	   /* free the buffer arrays in reverse order of allocation */
1793 	   SCIPfreeBufferArray(scip, &valbufcpy);
1794 	   SCIPfreeBufferArray(scip, &varbufcpy);
1795 	   SCIPfreeBufferArray(scip, &pscostscores);
1796 	   SCIPfreeBufferArray(scip, &perm);
1797 	   SCIPfreeBufferArray(scip, &randscores);
1798 	   SCIPfreeBufferArray(scip, &redcostscores);
1799 	   SCIPfreeBufferArray(scip, &fixeddistances);
1800 	   SCIPfreeBufferArray(scip, &distances);
1801 	   SCIPfreeBufferArray(scip, &unfixedvars);
1802 	   SCIPfreeBufferArray(scip, &isfixedvar);
1803 	
1804 	   *success = TRUE;
1805 	
1806 	   return SCIP_OKAY;
1807 	}
1808 	
1809 	/** call variable fixing callback for this neighborhood and orchestrate additional variable fixings, if necessary */
1810 	static
1811 	SCIP_RETCODE neighborhoodFixVariables(
1812 	   SCIP*                 scip,               /**< SCIP data structure */
1813 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
1814 	   NH*                   neighborhood,       /**< neighborhood data structure */
1815 	   SCIP_VAR**            varbuf,             /**< buffer array to keep variables that should be fixed */
1816 	   SCIP_Real*            valbuf,             /**< buffer array to keep fixing values */
1817 	   int*                  nfixings,           /**< pointer to store the number of variable fixings */
1818 	   SCIP_RESULT*          result              /**< pointer to store the result of the fixing operation */
1819 	   )
1820 	{
1821 	   int ntargetfixings;
1822 	   int nmaxfixings;
1823 	   int nminfixings;
1824 	   int nbinintvars;
1825 	
1826 	   assert(scip != NULL);
1827 	   assert(neighborhood != NULL);
1828 	   assert(varbuf != NULL);
1829 	   assert(valbuf != NULL);
1830 	   assert(nfixings != NULL);
1831 	   assert(result != NULL);
1832 	
1833 	   *nfixings = 0;
1834 	
1835 	   *result = SCIP_DIDNOTRUN;
1836 	   ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)));
1837 	
1838 	   if( neighborhood->varfixings != NULL )
1839 	   {
1840 	      SCIP_CALL( neighborhood->varfixings(scip, neighborhood, varbuf, valbuf, nfixings, result) );
1841 	
1842 	      if( *result != SCIP_SUCCESS )
1843 	         return SCIP_OKAY;
1844 	   }
1845 	   else if( ntargetfixings == 0 )
1846 	   {
1847 	      *result = SCIP_SUCCESS;
1848 	
1849 	      return SCIP_OKAY;
1850 	   }
1851 	
1852 	   /* compute upper and lower target fixing limits using tolerance parameters */
1853 	   assert(neighborhood->varfixings == NULL || *result != SCIP_DIDNOTRUN);
1854 	   nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1855 	   ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * nbinintvars);
1856 	   nminfixings = (int)((neighborhood->fixingrate.targetfixingrate - heurdata->fixtol) * nbinintvars);
1857 	   nminfixings = MAX(nminfixings, 0);
1858 	   nmaxfixings = (int)((neighborhood->fixingrate.targetfixingrate + heurdata->unfixtol) * nbinintvars);
1859 	   nmaxfixings = MIN(nmaxfixings, nbinintvars);
1860 	
1861 	   SCIPdebugMsg(scip, "Neighborhood Fixings/Target: %d / %d <= %d <= %d\n",*nfixings, nminfixings, ntargetfixings, nmaxfixings);
1862 	
1863 	   /* if too few fixings, use a strategy to select more variable fixings: randomized, LP graph, ReducedCost based, mix */
1864 	   if( (*result == SCIP_SUCCESS || *result == SCIP_DIDNOTRUN) && (*nfixings < nminfixings) )
1865 	   {
1866 	      SCIP_Bool success;
1867 	      SCIP_SOL* refsol;
1868 	
1869 	      /* get reference solution from neighborhood */
1870 	      SCIP_CALL( neighborhoodGetRefsol(scip, neighborhood, &refsol) );
1871 	
1872 	      /* try to fix more variables based on the reference solution */
1873 	      if( refsol != NULL )
1874 	      {
1875 	         SCIP_CALL( alnsFixMoreVariables(scip, heurdata, refsol, varbuf, valbuf, nfixings, ntargetfixings, &success) );
1876 	      }
1877 	      else
1878 	         success = FALSE;
1879 	
1880 	      if( success )
1881 	         *result = SCIP_SUCCESS;
1882 	      else if( *result == SCIP_SUCCESS )
1883 	         *result = SCIP_DIDNOTFIND;
1884 	      else
1885 	         *result = SCIP_DIDNOTRUN;
1886 	
1887 	      SCIPdebugMsg(scip, "After additional fixings: %d / %d\n",*nfixings, ntargetfixings);
1888 	   }
1889 	   else if( (SCIP_Real)(*nfixings) > nmaxfixings )
1890 	   {
1891 	      SCIP_Bool success;
1892 	
1893 	      SCIP_CALL( alnsUnfixVariables(scip, heurdata, varbuf, valbuf, nfixings, ntargetfixings, &success) );
1894 	
1895 	      assert(success);
1896 	      *result = SCIP_SUCCESS;
1897 	      SCIPdebugMsg(scip, "Unfixed variables, fixed variables remaining: %d\n", ntargetfixings);
1898 	   }
1899 	   else
1900 	   {
1901 	      SCIPdebugMsg(scip, "No additional fixings performed\n");
1902 	   }
1903 	
1904 	   return SCIP_OKAY;
1905 	}
1906 	
1907 	/** change the sub-SCIP by restricting variable domains, changing objective coefficients, or adding constraints */
1908 	static
1909 	SCIP_RETCODE neighborhoodChangeSubscip(
1910 	   SCIP*                 sourcescip,         /**< source SCIP data structure */
1911 	   SCIP*                 targetscip,         /**< target SCIP data structure */
1912 	   NH*                   neighborhood,       /**< neighborhood */
1913 	   SCIP_VAR**            targetvars,         /**< array of target SCIP variables aligned with source SCIP variables */
1914 	   int*                  ndomchgs,           /**< pointer to store the number of variable domain changes */
1915 	   int*                  nchgobjs,           /**< pointer to store the number of changed objective coefficients */
1916 	   int*                  naddedconss,        /**< pointer to store the number of added constraints */
1917 	   SCIP_Bool*            success             /**< pointer to store whether the sub-SCIP has been successfully modified */
1918 	   )
1919 	{
1920 	   assert(sourcescip != NULL);
1921 	   assert(targetscip != NULL);
1922 	   assert(neighborhood != NULL);
1923 	   assert(targetvars != NULL);
1924 	   assert(ndomchgs != NULL);
1925 	   assert(nchgobjs != NULL);
1926 	   assert(naddedconss != NULL);
1927 	   assert(success != NULL);
1928 	
1929 	   *success = FALSE;
1930 	   *ndomchgs = 0;
1931 	   *nchgobjs = 0;
1932 	   *naddedconss = 0;
1933 	
1934 	   /* call the change sub-SCIP callback of the neighborhood */
1935 	   if( neighborhood->changesubscip != NULL )
1936 	   {
1937 	      SCIP_CALL( neighborhood->changesubscip(sourcescip, targetscip, neighborhood, targetvars, ndomchgs, nchgobjs, naddedconss, success) );
1938 	   }
1939 	   else
1940 	   {
1941 	      *success = TRUE;
1942 	   }
1943 	
1944 	   return SCIP_OKAY;
1945 	}
1946 	
1947 	/** set sub-SCIP solving limits */
1948 	static
1949 	SCIP_RETCODE setLimits(
1950 	   SCIP*                 subscip,            /**< SCIP data structure */
1951 	   SOLVELIMITS*          solvelimits         /**< pointer to solving limits data structure */
1952 	   )
1953 	{
1954 	   assert(subscip != NULL);
1955 	   assert(solvelimits != NULL);
1956 	
1957 	   assert(solvelimits->nodelimit >= solvelimits->stallnodes);
1958 	
1959 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
1960 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodes));
1961 	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", solvelimits->timelimit) );
1962 	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", solvelimits->memorylimit) );
1963 	
1964 	   return SCIP_OKAY;
1965 	}
1966 	
1967 	/** determine limits for a sub-SCIP */
1968 	static
1969 	SCIP_RETCODE determineLimits(
1970 	   SCIP*                 scip,               /**< SCIP data structure */
1971 	   SCIP_HEUR*            heur,               /**< this heuristic */
1972 	   SOLVELIMITS*          solvelimits,        /**< pointer to solving limits data structure */
1973 	   SCIP_Bool*            runagain            /**< can we solve another sub-SCIP with these limits */
1974 	   )
1975 	{
1976 	   SCIP_HEURDATA* heurdata;
1977 	   SCIP_Real initfactor;
1978 	   SCIP_Real nodesquot;
1979 	   SCIP_Bool avoidmemout;
1980 	
1981 	   assert(scip != NULL);
1982 	   assert(heur != NULL);
1983 	   assert(solvelimits != NULL);
1984 	   assert(runagain != NULL);
1985 	
1986 	   heurdata = SCIPheurGetData(heur);
1987 	
1988 	   /* check whether there is enough time and memory left */
1989 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &solvelimits->timelimit) );
1990 	   if( ! SCIPisInfinity(scip, solvelimits->timelimit) )
1991 	      solvelimits->timelimit -= SCIPgetSolvingTime(scip);
1992 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &solvelimits->memorylimit) );
1993 	   SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
1994 	
1995 	   /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1996 	   if( ! SCIPisInfinity(scip, solvelimits->memorylimit) )
1997 	   {
1998 	      solvelimits->memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1999 	      solvelimits->memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
2000 	   }
2001 	
2002 	   /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE)
2003 	   * to create a copy of SCIP, including external memory usage */
2004 	   if( solvelimits->timelimit <= 0.0 || (avoidmemout && solvelimits->memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0) )
2005 	      *runagain = FALSE;
2006 	
2007 	   nodesquot = heurdata->nodesquot;
2008 	
2009 	   /* if the heuristic is used to measure all rewards, it will always be penalized here */
2010 	   if( heurdata->rewardfile == NULL )
2011 	      nodesquot *= (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0);
2012 	
2013 	   nodesquot = MAX(nodesquot, heurdata->nodesquotmin);
2014 	
2015 	   /* calculate the search node limit of the heuristic  */
2016 	   solvelimits->stallnodes = (SCIP_Longint)(nodesquot * SCIPgetNNodes(scip));
2017 	   solvelimits->stallnodes += heurdata->nodesoffset;
2018 	   solvelimits->stallnodes -= heurdata->usednodes;
2019 	   solvelimits->stallnodes -= 100 * SCIPheurGetNCalls(heur);
2020 	   solvelimits->stallnodes = MIN(heurdata->maxnodes, solvelimits->stallnodes);
2021 	
2022 	   /* use a smaller budget if not all neighborhoods have been initialized yet */
2023 	   assert(heurdata->ninitneighborhoods >= 0);
2024 	   initfactor = (heurdata->nactiveneighborhoods - heurdata->ninitneighborhoods + 1.0) / (heurdata->nactiveneighborhoods + 1.0);
2025 	   solvelimits->stallnodes = (SCIP_Longint)(solvelimits->stallnodes * initfactor);
2026 	   solvelimits->nodelimit = (SCIP_Longint)(heurdata->maxnodes);
2027 	
2028 	   /* check whether we have enough nodes left to call subproblem solving */
2029 	   if( solvelimits->stallnodes < heurdata->targetnodes )
2030 	      *runagain = FALSE;
2031 	
2032 	   return SCIP_OKAY;
2033 	}
2034 	
2035 	/** return the bandit algorithm that should be used */
2036 	static
2037 	SCIP_BANDIT* getBandit(
2038 	   SCIP_HEURDATA*        heurdata            /**< heuristic data of the ALNS neighborhood */
2039 	   )
2040 	{
2041 	   assert(heurdata != NULL);
2042 	   return heurdata->bandit;
2043 	}
2044 	
2045 	/** select a neighborhood depending on the selected bandit algorithm */
2046 	static
2047 	SCIP_RETCODE selectNeighborhood(
2048 	   SCIP*                 scip,               /**< SCIP data structure */
2049 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
2050 	   int*                  neighborhoodidx     /**< pointer to store the selected neighborhood index */
2051 	   )
2052 	{
2053 	   SCIP_BANDIT* bandit;
2054 	   assert(scip != NULL);
2055 	   assert(heurdata != NULL);
2056 	   assert(neighborhoodidx != NULL);
2057 	
2058 	   *neighborhoodidx = -1;
2059 	
2060 	   bandit = getBandit(heurdata);
2061 	
2062 	   SCIP_CALL( SCIPbanditSelect(bandit, neighborhoodidx) );
2063 	   assert(*neighborhoodidx >= 0);
2064 	
2065 	   return SCIP_OKAY;
2066 	}
2067 	
2068 	/** Calculate reward based on the selected reward measure */
2069 	static
2070 	SCIP_RETCODE getReward(
2071 	   SCIP*                 scip,               /**< SCIP data structure */
2072 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
2073 	   NH_STATS*             runstats,           /**< run statistics */
2074 	   SCIP_Real*            rewardptr           /**< array to store the computed rewards, total and individual */
2075 	   )
2076 	{
2077 	   SCIP_Real reward = 0.0;
2078 	   SCIP_Real effort;
2079 	   int ndiscretevars;
2080 	
2081 	   memset(rewardptr, 0, sizeof(*rewardptr)*(int)NREWARDTYPES);
2082 	
2083 	   assert(rewardptr != NULL);
2084 	   assert(runstats->usednodes >= 0);
2085 	   assert(runstats->nfixings >= 0);
2086 	
2087 	   effort = runstats->usednodes / 100.0;
2088 	
2089 	   ndiscretevars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
2090 	   /* assume that every fixed variable linearly reduces the subproblem complexity */
2091 	   if( ndiscretevars > 0 )
2092 	   {
2093 	      effort = (1.0 - (runstats->nfixings / (SCIP_Real)ndiscretevars)) * effort;
2094 	   }
2095 	   assert(rewardptr != NULL);
2096 	
2097 	   /* a positive reward is only assigned if a new incumbent solution was found */
2098 	   if( runstats->nbestsolsfound > 0 )
2099 	   {
2100 	      SCIP_Real rewardcontrol = heurdata->rewardcontrol;
2101 	
2102 	      SCIP_Real lb;
2103 	      SCIP_Real ub;
2104 	
2105 	      /* the indicator function is simply 1.0 */
2106 	      rewardptr[REWARDTYPE_BESTSOL] = 1.0;
2107 	      rewardptr[REWARDTYPE_NOSOLPENALTY] = 1.0;
2108 	
2109 	      ub = runstats->newupperbound;
2110 	      lb = SCIPgetLowerbound(scip);
2111 	
2112 	      /* compute the closed gap reward */
2113 	      if( SCIPisEQ(scip, ub, lb) || SCIPisInfinity(scip, runstats->oldupperbound) )
2114 	         rewardptr[REWARDTYPE_CLOSEDGAP] = 1.0;
2115 	      else
2116 	      {
2117 	         rewardptr[REWARDTYPE_CLOSEDGAP] = (runstats->oldupperbound - ub) / (runstats->oldupperbound - lb);
2118 	      }
2119 	
2120 	      /* the reward is a convex combination of the best solution reward and the reward for the closed gap */
2121 	      reward = rewardcontrol * rewardptr[REWARDTYPE_BESTSOL] + (1.0 - rewardcontrol) * rewardptr[REWARDTYPE_CLOSEDGAP];
2122 	
2123 	      /* optionally, scale the reward by the involved effort */
2124 	      if( heurdata->scalebyeffort )
2125 	         reward /= (effort + 1.0);
2126 	
2127 	      /* add the baseline and rescale the reward into the interval [baseline, 1.0] */
2128 	      reward = heurdata->rewardbaseline + (1.0 - heurdata->rewardbaseline) * reward;
2129 	   }
2130 	   else
2131 	   {
2132 	      /* linearly decrease the reward based on the number of nodes spent */
2133 	      SCIP_Real maxeffort = heurdata->targetnodes;
2134 	      SCIP_Real usednodes = runstats->usednodes;
2135 	
2136 	      if( ndiscretevars > 0 )
2137 	         usednodes *= (1.0 - (runstats->nfixings / (SCIP_Real)ndiscretevars));
2138 	
2139 	      rewardptr[REWARDTYPE_NOSOLPENALTY] = 1 - (usednodes / maxeffort);
2140 	      rewardptr[REWARDTYPE_NOSOLPENALTY] = MAX(0.0, rewardptr[REWARDTYPE_NOSOLPENALTY]);
2141 	      reward = heurdata->rewardbaseline * rewardptr[REWARDTYPE_NOSOLPENALTY];
2142 	   }
2143 	
2144 	   rewardptr[REWARDTYPE_TOTAL] = reward;
2145 	
2146 	   return SCIP_OKAY;
2147 	}
2148 	
2149 	/** update internal bandit algorithm statistics for future draws */
2150 	static
2151 	SCIP_RETCODE updateBanditAlgorithm(
2152 	   SCIP*                 scip,               /**< SCIP data structure */
2153 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data of the ALNS neighborhood */
2154 	   SCIP_Real             reward,             /**< measured reward */
2155 	   int                   neighborhoodidx     /**< the neighborhood that was chosen */
2156 	   )
2157 	{
2158 	   SCIP_BANDIT* bandit;
2159 	   assert(scip != NULL);
2160 	   assert(heurdata != NULL);
2161 	   assert(neighborhoodidx >= 0);
2162 	   assert(neighborhoodidx < heurdata->nactiveneighborhoods);
2163 	
2164 	   bandit = getBandit(heurdata);
2165 	
2166 	   SCIPdebugMsg(scip, "Rewarding bandit algorithm action %d with reward %.2f\n", neighborhoodidx, reward);
2167 	   SCIP_CALL( SCIPbanditUpdate(bandit, neighborhoodidx, reward) );
2168 	
2169 	   return SCIP_OKAY;
2170 	}
2171 	
2172 	/** set up the sub-SCIP parameters, objective cutoff, and solution limits */
2173 	static
2174 	SCIP_RETCODE setupSubScip(
2175 	   SCIP*                 scip,               /**< SCIP data structure */
2176 	   SCIP*                 subscip,            /**< sub-SCIP data structure */
2177 	   SCIP_VAR**            subvars,            /**< array of sub-SCIP variables in the order of the main SCIP */
2178 	   SOLVELIMITS*          solvelimits,        /**< pointer to solving limits data structure */
2179 	   SCIP_HEUR*            heur,               /**< this heuristic */
2180 	   SCIP_Bool             objchgd             /**< did the objective change between the source and the target SCIP? */
2181 	   )
2182 	{
2183 	   SCIP_HEURDATA* heurdata;
2184 	   SCIP_Real cutoff;
2185 	   SCIP_Real upperbound;
2186 	
2187 	   heurdata = SCIPheurGetData(heur);
2188 	
2189 	   /* do not abort subproblem on CTRL-C */
2190 	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2191 	
2192 	   /* disable output to console unless we are in debug mode */
2193 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2194 	
2195 	   /* disable statistic timing inside sub SCIP */
2196 	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2197 	
2198 	#ifdef ALNS_SUBSCIPOUTPUT
2199 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2200 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
2201 	   /* enable statistic timing inside sub SCIP */
2202 	      SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", TRUE) );
2203 	#endif
2204 	
2205 	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->nsolslim) );
2206 	
2207 	   /* forbid recursive call of heuristics and separators solving subMIPs */
2208 	   if( ! heurdata->usesubscipheurs )
2209 	   {
2210 	      SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
2211 	   }
2212 	
2213 	   /* disable cutting plane separation */
2214 	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
2215 	
2216 	   /* disable expensive presolving */
2217 	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2218 	
2219 	   /* use best estimate node selection */
2220 	   if( SCIPfindNodesel(subscip, "estimate") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
2221 	   {
2222 	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
2223 	   }
2224 	
2225 	   /* use inference branching */
2226 	   if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") )
2227 	   {
2228 	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
2229 	   }
2230 	
2231 	   /* enable conflict analysis and restrict conflict pool */
2232 	   if( ! SCIPisParamFixed(subscip, "conflict/enable") )
2233 	   {
2234 	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
2235 	   }
2236 	
2237 	   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
2238 	   {
2239 	      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
2240 	   }
2241 	
2242 	   if( ! SCIPisParamFixed(subscip, "conflict/maxstoresize") )
2243 	   {
2244 	      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
2245 	   }
2246 	
2247 	   /* speed up sub-SCIP by not checking dual LP feasibility */
2248 	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
2249 	
2250 	   /* add an objective cutoff */
2251 	   if( ! SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
2252 	   {
2253 	      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
2254 	      if( ! SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
2255 	      {
2256 	         cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
2257 	                            + heurdata->minimprove * SCIPgetLowerbound(scip);
2258 	      }
2259 	      else
2260 	      {
2261 	         if( SCIPgetUpperbound(scip) >= 0 )
2262 	            cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
2263 	         else
2264 	            cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
2265 	      }
2266 	      cutoff = MIN(upperbound, cutoff);
2267 	
2268 	      if( SCIPisObjIntegral(scip) )
2269 	         cutoff = SCIPfloor(scip, cutoff);
2270 	
2271 	      SCIPdebugMsg(scip, "Sub-SCIP cutoff: %15.9" SCIP_REAL_FORMAT " (%15.9" SCIP_REAL_FORMAT " in original space)\n",
2272 	         cutoff, SCIPretransformObj(scip, cutoff));
2273 	
2274 	      /* if the objective changed between the source and the target SCIP, encode the cutoff as a constraint */
2275 	      if( ! objchgd )
2276 	      {
2277 	         SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
2278 	
2279 	         SCIPdebugMsg(scip, "Cutoff added as Objective Limit\n");
2280 	      }
2281 	      else
2282 	      {
2283 	         SCIP_CONS* objcons;
2284 	         int nvars;
2285 	         SCIP_VAR** vars;
2286 	         int i;
2287 	
2288 	         vars = SCIPgetVars(scip);
2289 	         nvars = SCIPgetNVars(scip);
2290 	
2291 	         SCIP_CALL( SCIPcreateConsLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
2292 	                     TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2293 	         for( i = 0; i < nvars; ++i)
2294 	         {
2295 	            if( ! SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
2296 	            {
2297 	               assert(subvars[i] != NULL);
2298 	               SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
2299 	            }
2300 	         }
2301 	         SCIP_CALL( SCIPaddCons(subscip, objcons) );
2302 	         SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );
2303 	
2304 	         SCIPdebugMsg(scip, "Cutoff added as constraint\n");
2305 	      }
2306 	   }
2307 	
2308 	   /* set solve limits for sub-SCIP */
2309 	   SCIP_CALL( setLimits(subscip, solvelimits) );
2310 	
2311 	   /* change random seed of sub-SCIP */
2312 	   if( heurdata->subsciprandseeds )
2313 	   {
2314 	      SCIP_CALL( SCIPsetIntParam(subscip, "randomization/randomseedshift", (int)SCIPheurGetNCalls(heur)) );
2315 	   }
2316 	
2317 	   SCIPdebugMsg(scip, "Solve Limits: %lld (%lld) nodes (stall nodes), %.1f sec., %d sols\n",
2318 	         solvelimits->nodelimit, solvelimits->stallnodes, solvelimits->timelimit, heurdata->nsolslim);
2319 	
2320 	   return SCIP_OKAY;
2321 	}
2322 	
2323 	/** execution method of primal heuristic */
2324 	static
2325 	SCIP_DECL_HEUREXEC(heurExecAlns)
2326 	{  /*lint --e{715}*/
2327 	   SCIP_HEURDATA* heurdata;
2328 	   SCIP_VAR** varbuf;
2329 	   SCIP_Real* valbuf;
2330 	   SCIP_VAR** vars;
2331 	   SCIP_VAR** subvars;
2332 	   NH_STATS runstats[NNEIGHBORHOODS];
2333 	   SCIP_STATUS subscipstatus[NNEIGHBORHOODS];
2334 	   SCIP* subscip = NULL;
2335 	
2336 	   int nfixings;
2337 	   int nvars;
2338 	   int neighborhoodidx;
2339 	   int ntries;
2340 	   SCIP_Bool tryagain;
2341 	   NH* neighborhood;
2342 	   SOLVELIMITS solvelimits;
2343 	   SCIP_Bool success;
2344 	   SCIP_Bool run;
2345 	   SCIP_Bool allrewardsmode;
2346 	   SCIP_Real rewards[NNEIGHBORHOODS][NREWARDTYPES] = {{0}};
2347 	   int banditidx;
2348 	
2349 	   int i;
2350 	
2351 	   heurdata = SCIPheurGetData(heur);
2352 	   assert(heurdata != NULL);
2353 	
2354 	   *result = SCIP_DIDNOTRUN;
2355 	
2356 	   if( heurdata->nactiveneighborhoods == 0 )
2357 	      return SCIP_OKAY;
2358 	
2359 	   /* we only allow to run multiple times at a node during the root */
2360 	   if( (heurtiming & SCIP_HEURTIMING_DURINGLPLOOP) && (SCIPgetDepth(scip) > 0 || !heurdata->initduringroot) )
2361 	      return SCIP_OKAY;
2362 	
2363 	   /* update internal incumbent solution */
2364 	   if( SCIPgetBestSol(scip) != heurdata->lastcallsol )
2365 	   {
2366 	      heurdata->lastcallsol = SCIPgetBestSol(scip);
2367 	      heurdata->firstcallthissol = SCIPheurGetNCalls(heur);
2368 	   }
2369 	
2370 	   /* do not run more than a user-defined number of times on each incumbent (-1: no limit) */
2371 	   if( heurdata->maxcallssamesol != -1 )
2372 	   {
2373 	      SCIP_Longint samesollimit = (heurdata->maxcallssamesol > 0) ?
2374 	         heurdata->maxcallssamesol :
2375 	         heurdata->nactiveneighborhoods;
2376 	
2377 	      if( SCIPheurGetNCalls(heur) - heurdata->firstcallthissol >= samesollimit )
2378 	      {
2379 	         SCIPdebugMsg(scip, "Heuristic already called %" SCIP_LONGINT_FORMAT " times on current incumbent\n", SCIPheurGetNCalls(heur) - heurdata->firstcallthissol);
2380 	         return SCIP_OKAY;
2381 	      }
2382 	   }
2383 	
2384 	   /* wait for a sufficient number of nodes since last incumbent solution */
2385 	   if( SCIPgetDepth(scip) > 0 && SCIPgetBestSol(scip) != NULL
2386 	      && (SCIPgetNNodes(scip) - SCIPsolGetNodenum(SCIPgetBestSol(scip))) < heurdata->waitingnodes )
2387 	   {
2388 	      SCIPdebugMsg(scip, "Waiting nodes not satisfied\n");
2389 	      return SCIP_OKAY;
2390 	   }
2391 	
2392 	   run = TRUE;
2393 	   /* check if budget allows a run of the next selected neighborhood */
2394 	   SCIP_CALL( determineLimits(scip, heur, &solvelimits, &run) );
2395 	   SCIPdebugMsg(scip, "Budget check: %" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT ") %s\n", solvelimits.nodelimit, heurdata->targetnodes, run ? "passed" : "must wait");
2396 	
2397 	   if( ! run )
2398 	      return SCIP_OKAY;
2399 	
2400 	   /* delay the heuristic if local reduced costs should be used for generic variable unfixing */
2401 	   if( heurdata->uselocalredcost && (nodeinfeasible || ! SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL) )
2402 	   {
2403 	      *result = SCIP_DELAYED;
2404 	
2405 	      return SCIP_OKAY;
2406 	   }
2407 	
2408 	   allrewardsmode = heurdata->rewardfile != NULL;
2409 	
2410 	   /* apply some other rules for a fair all rewards mode; in normal execution mode, neighborhoods are iterated through */
2411 	   if( allrewardsmode )
2412 	   {
2413 	      /* most neighborhoods require an incumbent solution */
2414 	      if( SCIPgetNSols(scip) < 2 )
2415 	      {
2416 	         SCIPdebugMsg(scip, "Not enough solutions for all rewards mode\n");
2417 	         return SCIP_OKAY;
2418 	      }
2419 	
2420 	      /* if the node is infeasible, or has no LP solution, which is required by some neighborhoods
2421 	       * if we are not in all rewards mode, the neighborhoods delay themselves individually
2422 	       */
2423 	      if( nodeinfeasible || ! SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2424 	      {
2425 	         SCIPdebugMsg(scip, "Delay ALNS heuristic until a feasible node with optimally solved LP relaxation\n");
2426 	         *result = SCIP_DELAYED;
2427 	         return SCIP_OKAY;
2428 	      }
2429 	   }
2430 	
2431 	   /* use the neighborhood that requested a delay or select the next neighborhood to run based on the selected bandit algorithm */
2432 	   if( heurdata->currneighborhood >= 0 )
2433 	   {
2434 	      assert(! allrewardsmode);
2435 	      banditidx = heurdata->currneighborhood;
2436 	      SCIPdebugMsg(scip, "Select delayed neighborhood %d (was delayed %d times)\n", banditidx, heurdata->ndelayedcalls);
2437 	   }
2438 	   else
2439 	   {
2440 	      SCIP_CALL( selectNeighborhood(scip, heurdata, &banditidx) );
2441 	      SCIPdebugMsg(scip, "Selected neighborhood %d with bandit algorithm\n", banditidx);
2442 	   }
2443 	
2444 	   /* in all rewards mode, we simply loop over all heuristics */
2445 	   if( ! allrewardsmode )
2446 	      neighborhoodidx = banditidx;
2447 	   else
2448 	      neighborhoodidx = 0;
2449 	
2450 	   assert(0 <= neighborhoodidx && neighborhoodidx < NNEIGHBORHOODS);
2451 	   assert(heurdata->nactiveneighborhoods > neighborhoodidx);
2452 	
2453 	   /* allocate memory for variable fixings buffer */
2454 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2455 	   SCIP_CALL( SCIPallocBufferArray(scip, &varbuf, nvars) );
2456 	   SCIP_CALL( SCIPallocBufferArray(scip, &valbuf, nvars) );
2457 	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
2458 	
2459 	   /* initialize neighborhood statistics for a run */
2460 	   ntries = 1;
2461 	   do
2462 	   {
2463 	      SCIP_HASHMAP* varmapf;
2464 	      SCIP_EVENTHDLR* eventhdlr;
2465 	      SCIP_EVENTDATA eventdata;
2466 	      char probnamesuffix[SCIP_MAXSTRLEN];
2467 	      SCIP_Real allfixingrate;
2468 	      int ndomchgs;
2469 	      int nchgobjs;
2470 	      int naddedconss;
2471 	      int v;
2472 	      SCIP_RETCODE retcode;
2473 	      SCIP_RESULT fixresult;
2474 	
2475 	      tryagain = FALSE;
2476 	      neighborhood = heurdata->neighborhoods[neighborhoodidx];
2477 	      SCIPdebugMsg(scip, "Running '%s' neighborhood %d\n", neighborhood->name, neighborhoodidx);
2478 	
2479 	      initRunStats(scip, &runstats[neighborhoodidx]);
2480 	      rewards[neighborhoodidx][REWARDTYPE_TOTAL] = 0.0;
2481 	
2482 	      subscipstatus[neighborhoodidx] = SCIP_STATUS_UNKNOWN;
2483 	      SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.setupclock) );
2484 	
2485 	      /* determine variable fixings and objective coefficients of this neighborhood */
2486 	      SCIP_CALL( neighborhoodFixVariables(scip, heurdata, neighborhood, varbuf, valbuf, &nfixings, &fixresult) );
2487 	
2488 	      SCIPdebugMsg(scip, "Fix %d/%d variables, result code %d\n", nfixings, nvars,fixresult);
2489 	
2490 	      /* Fixing was not successful, either because the fixing rate was not reached (and no additional variable
2491 	       * prioritization was used), or the neighborhood requested a delay, e.g., because no LP relaxation solution exists
2492 	       * at the current node
2493 	       *
2494 	       * The ALNS heuristic keeps a delayed neighborhood active and delays itself.
2495 	       */
2496 	      if( fixresult != SCIP_SUCCESS )
2497 	      {
2498 	         SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2499 	
2500 	         /* to determine all rewards, we cannot delay neighborhoods */
2501 	         if( allrewardsmode )
2502 	         {
2503 	            if( ntries == heurdata->nactiveneighborhoods )
2504 	               break;
2505 	
2506 	            neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
2507 	            ntries++;
2508 	            tryagain = TRUE;
2509 	
2510 	            continue;
2511 	         }
2512 	
2513 	         /* delay the heuristic along with the selected neighborhood
2514 	          *
2515 	          * if the neighborhood has been delayed for too many consecutive calls, the delay is treated as a failure */
2516 	         if( fixresult == SCIP_DELAYED )
2517 	         {
2518 	            if( heurdata->ndelayedcalls > (SCIPheurGetFreq(heur) / 4 + 1) )
2519 	            {
2520 	               resetCurrentNeighborhood(heurdata);
2521 	
2522 	               /* use SCIP_DIDNOTFIND to penalize the neighborhood with a bad reward */
2523 	               fixresult = SCIP_DIDNOTFIND;
2524 	            }
2525 	            else if( heurdata->currneighborhood == -1 )
2526 	            {
2527 	               heurdata->currneighborhood = neighborhoodidx;
2528 	               heurdata->ndelayedcalls = 1;
2529 	            }
2530 	            else
2531 	            {
2532 	               heurdata->ndelayedcalls++;
2533 	            }
2534 	         }
2535 	
2536 	         if( fixresult == SCIP_DIDNOTRUN )
2537 	         {
2538 	            if( ntries < heurdata->nactiveneighborhoods )
2539 	            {
2540 	               SCIP_CALL( updateBanditAlgorithm(scip, heurdata, 0.0, neighborhoodidx) );
2541 	               SCIP_CALL( selectNeighborhood(scip, heurdata, &neighborhoodidx) );
2542 	               ntries++;
2543 	               tryagain = TRUE;
2544 	
2545 	               SCIPdebugMsg(scip, "Neighborhood cannot run -> try next neighborhood %d\n", neighborhoodidx);
2546 	               continue;
2547 	            }
2548 	            else
2549 	               break;
2550 	         }
2551 	
2552 	         assert(fixresult == SCIP_DIDNOTFIND || fixresult == SCIP_DELAYED);
2553 	         *result = fixresult;
2554 	         break;
2555 	      }
2556 	
2557 	      *result = SCIP_DIDNOTFIND;
2558 	
2559 	      neighborhood->stats.nfixings += nfixings;
2560 	      runstats[neighborhoodidx].nfixings = nfixings;
2561 	
2562 	      SCIP_CALL( SCIPcreate(&subscip) );
2563 	      SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(scip), nvars) );
2564 	      (void) SCIPsnprintf(probnamesuffix, SCIP_MAXSTRLEN, "alns_%s", neighborhood->name);
2565 	
2566 	      /* todo later: run global propagation for this set of fixings */
2567 	      SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapf, probnamesuffix, varbuf, valbuf, nfixings, FALSE, heurdata->copycuts, &success, NULL) );
2568 	
2569 	      /* store sub-SCIP variables in array for faster access */
2570 	      for( v = 0; v < nvars; ++v )
2571 	      {
2572 	         subvars[v] = (SCIP_VAR*)SCIPhashmapGetImage(varmapf, (void *)vars[v]);
2573 	      }
2574 	
2575 	      SCIPhashmapFree(&varmapf);
2576 	
2577 	      /* let the neighborhood add additional constraints, or restrict domains */
2578 	      SCIP_CALL( neighborhoodChangeSubscip(scip, subscip, neighborhood, subvars, &ndomchgs, &nchgobjs, &naddedconss, &success) );
2579 	
2580 	      if( ! success )
2581 	      {
2582 	         SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2583 	
2584 	         if( ! allrewardsmode || ntries == heurdata->nactiveneighborhoods )
2585 	            break;
2586 	
2587 	         neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
2588 	         ntries++;
2589 	         tryagain = TRUE;
2590 	
2591 	         SCIP_CALL( SCIPfree(&subscip) );
2592 	
2593 	         continue;
2594 	      }
2595 	
2596 	      /* set up sub-SCIP parameters */
2597 	      SCIP_CALL( setupSubScip(scip, subscip, subvars, &solvelimits, heur, nchgobjs > 0) );
2598 	
2599 	      /* copy the necessary data into the event data to create new solutions */
2600 	      eventdata.nodelimit = solvelimits.nodelimit;  /*lint !e644*/
2601 	      eventdata.lplimfac = heurdata->lplimfac;
2602 	      eventdata.heur = heur;
2603 	      eventdata.sourcescip = scip;
2604 	      eventdata.subvars = subvars;
2605 	      eventdata.runstats = &runstats[neighborhoodidx];
2606 	      eventdata.allrewardsmode = allrewardsmode;
2607 	
2608 	      /* include an event handler to transfer solutions into the main SCIP */
2609 	      SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecAlns, NULL) );
2610 	
2611 	      /* transform the problem before catching the events */
2612 	      SCIP_CALL( SCIPtransformProb(subscip) );
2613 	      SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_ALNS, eventhdlr, &eventdata, NULL) );
2614 	
2615 	      SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2616 	
2617 	      SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.submipclock) );
2618 	
2619 	      /* set up sub-SCIP and run presolving */
2620 	      retcode = SCIPpresolve(subscip);
2621 	      if( retcode != SCIP_OKAY )
2622 	      {
2623 	         SCIPwarningMessage(scip, "Error while presolving subproblem in ALNS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
2624 	         SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.submipclock) );
2625 	
2626 	         SCIPABORT();  /*lint --e{527}*/
2627 	         break;
2628 	      }
2629 	
2630 	      /* was presolving successful enough regarding fixings? otherwise, terminate */
2631 	      allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
2632 	
2633 	      /* additional variables added in presolving may lead to the subSCIP having more variables than the original */
2634 	      allfixingrate = MAX(allfixingrate, 0.0);
2635 	
2636 	      if( allfixingrate >= neighborhood->fixingrate.targetfixingrate / 2.0 )
2637 	      {
2638 	         /* run sub-SCIP for the given budget, and collect statistics */
2639 	         SCIP_CALL_ABORT( SCIPsolve(subscip) );
2640 	      }
2641 	      else
2642 	      {
2643 	         SCIPdebugMsg(scip, "Fixed only %.3f of all variables after presolving -> do not solve sub-SCIP\n", allfixingrate);
2644 	      }
2645 	
2646 	#ifdef ALNS_SUBSCIPOUTPUT
2647 	      SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2648 	#endif
2649 	
2650 	      SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.submipclock) );
2651 	
2652 	      /* update statistics based on the sub-SCIP run results */
2653 	      updateRunStats(&runstats[neighborhoodidx], subscip);
2654 	      subscipstatus[neighborhoodidx] = SCIPgetStatus(subscip);
2655 	      SCIPdebugMsg(scip, "Status of sub-SCIP run: %d\n", subscipstatus[neighborhoodidx]);
2656 	
2657 	      SCIP_CALL( getReward(scip, heurdata, &runstats[neighborhoodidx], rewards[neighborhoodidx]) );
2658 	
2659 	      /* in all rewards mode, continue with the next neighborhood */
2660 	      if( allrewardsmode && ntries < heurdata->nactiveneighborhoods )
2661 	      {
2662 	         neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
2663 	         ntries++;
2664 	         tryagain = TRUE;
2665 	
2666 	         SCIP_CALL( SCIPfree(&subscip) );
2667 	      }
2668 	   }
2669 	   while( tryagain && ! SCIPisStopped(scip) );
2670 	
2671 	   if( subscip != NULL )
2672 	   {
2673 	      SCIP_CALL( SCIPfree(&subscip) );
2674 	   }
2675 	
2676 	   SCIPfreeBufferArray(scip, &subvars);
2677 	   SCIPfreeBufferArray(scip, &valbuf);
2678 	   SCIPfreeBufferArray(scip, &varbuf);
2679 	
2680 	   /* update bandit index that may have changed unless we are in all rewards mode */
2681 	   if( ! allrewardsmode )
2682 	      banditidx = neighborhoodidx;
2683 	
2684 	   if( *result != SCIP_DELAYED )
2685 	   {
2686 	      /* decrease the number of neighborhoods that have not been initialized */
2687 	      if( neighborhood->stats.nruns == 0 )
2688 	         --heurdata->ninitneighborhoods;
2689 	
2690 	      heurdata->usednodes += runstats[banditidx].usednodes;
2691 	
2692 	      /* determine the success of this neighborhood, and update the target fixing rate for the next time */
2693 	      updateNeighborhoodStats(&runstats[banditidx], heurdata->neighborhoods[banditidx], subscipstatus[banditidx]);
2694 	
2695 	      /* adjust the fixing rate for this neighborhood
2696 	       * make no adjustments in all rewards mode, because this only affects 1 of 8 heuristics
2697 	       */
2698 	      if( heurdata->adjustfixingrate && ! allrewardsmode )
2699 	      {
2700 	         SCIPdebugMsg(scip, "Update fixing rate: %.2f\n", heurdata->neighborhoods[banditidx]->fixingrate.targetfixingrate);
2701 	         updateFixingRate(heurdata->neighborhoods[banditidx], subscipstatus[banditidx], &runstats[banditidx]);
2702 	         SCIPdebugMsg(scip, "New fixing rate: %.2f\n", heurdata->neighborhoods[banditidx]->fixingrate.targetfixingrate);
2703 	      }
2704 	      /* similarly, update the minimum improvement for the ALNS heuristic */
2705 	      if( heurdata->adjustminimprove )
2706 	      {
2707 	         SCIPdebugMsg(scip, "Update Minimum Improvement: %.4f\n", heurdata->minimprove);
2708 	         updateMinimumImprovement(heurdata, subscipstatus[banditidx], &runstats[banditidx]);
2709 	         SCIPdebugMsg(scip, "--> %.4f\n", heurdata->minimprove);
2710 	      }
2711 	
2712 	      /* update the target node limit based on the status of the selected algorithm */
2713 	      if( heurdata->adjusttargetnodes && SCIPheurGetNCalls(heur) >= heurdata->nactiveneighborhoods )
2714 	      {
2715 	         updateTargetNodeLimit(heurdata, &runstats[banditidx], subscipstatus[banditidx]);
2716 	      }
2717 	
2718 	      /* update the bandit algorithm by the measured reward */
2719 	      SCIP_CALL( updateBanditAlgorithm(scip, heurdata, rewards[banditidx][REWARDTYPE_TOTAL], banditidx) );
2720 	
2721 	      resetCurrentNeighborhood(heurdata);
2722 	   }
2723 	
2724 	   /* write single, measured rewards and the bandit index to the reward file */
2725 	   if( allrewardsmode )
2726 	   {
2727 	      int j;
2728 	      for( j = 0; j < (int)NREWARDTYPES; j++ )
2729 	         for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
2730 	            fprintf(heurdata->rewardfile, "%.4f,", rewards[i][j]);
2731 	
2732 	      fprintf(heurdata->rewardfile, "%d\n", banditidx);
2733 	   }
2734 	
2735 	   return SCIP_OKAY;
2736 	}
2737 	
2738 	/** callback to collect variable fixings of RENS */
2739 	static
2740 	DECL_VARFIXINGS(varFixingsRens)
2741 	{  /*lint --e{715}*/
2742 	   int nbinvars;
2743 	   int nintvars;
2744 	   SCIP_VAR** vars;
2745 	   int i;
2746 	   int *fracidx = NULL;
2747 	   SCIP_Real* frac = NULL;
2748 	   int nfracs;
2749 	
2750 	   assert(scip != NULL);
2751 	   assert(varbuf != NULL);
2752 	   assert(nfixings != NULL);
2753 	   assert(valbuf != NULL);
2754 	
2755 	   *result = SCIP_DELAYED;
2756 	
2757 	   if( ! SCIPhasCurrentNodeLP(scip) )
2758 	      return SCIP_OKAY;
2759 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2760 	      return SCIP_OKAY;
2761 	
2762 	   *result = SCIP_DIDNOTRUN;
2763 	
2764 	   /* get variable information */
2765 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2766 	
2767 	   /* return if no binary or integer variables are present */
2768 	   if( nbinvars + nintvars == 0 )
2769 	      return SCIP_OKAY;
2770 	
2771 	   SCIP_CALL( SCIPallocBufferArray(scip, &fracidx, nbinvars + nintvars) );
2772 	   SCIP_CALL( SCIPallocBufferArray(scip, &frac, nbinvars + nintvars) );
2773 	
2774 	   /* loop over binary and integer variables; determine those that should be fixed in the sub-SCIP */
2775 	   for( nfracs = 0, i = 0; i < nbinvars + nintvars; ++i )
2776 	   {
2777 	      SCIP_VAR* var = vars[i];
2778 	      SCIP_Real lpsolval = SCIPvarGetLPSol(var);
2779 	      assert((i < nbinvars && SCIPvarIsBinary(var)) || (i >= nbinvars && SCIPvarIsIntegral(var)));
2780 	
2781 	      /* fix all binary and integer variables with integer LP solution value */
2782 	      if( SCIPisFeasIntegral(scip, lpsolval) )
2783 	      {
2784 	         tryAdd2variableBuffer(scip, var, lpsolval, varbuf, valbuf, nfixings, TRUE);
2785 	      }
2786 	      else
2787 	      {
2788 	         frac[nfracs] = SCIPfrac(scip, lpsolval);
2789 	         frac[nfracs] = MIN(frac[nfracs], 1.0 - frac[nfracs]);
2790 	         fracidx[nfracs++] = i;
2791 	      }
2792 	   }
2793 	
2794 	   /* do some additional fixing */
2795 	   if( *nfixings < neighborhood->fixingrate.targetfixingrate * (nbinvars + nintvars) && nfracs > 0 )
2796 	   {
2797 	      SCIPsortDownRealInt(frac, fracidx, nfracs);
2798 	
2799 	      /* prefer variables that are almost integer */
2800 	      for( i = 0; i < nfracs && *nfixings < neighborhood->fixingrate.targetfixingrate * (nbinvars + nintvars); i++ )
2801 	      {
2802 	         tryAdd2variableBuffer(scip, vars[fracidx[i]], SCIPround(scip, SCIPvarGetLPSol(vars[fracidx[i]])), varbuf, valbuf, nfixings, TRUE);
2803 	      }
2804 	   }
2805 	
2806 	   SCIPfreeBufferArray(scip, &frac);
2807 	   SCIPfreeBufferArray(scip, &fracidx);
2808 	
2809 	   *result = SCIP_SUCCESS;
2810 	
2811 	   return SCIP_OKAY;
2812 	}
2813 	
2814 	/** callback for RENS subproblem changes */
2815 	static
2816 	DECL_CHANGESUBSCIP(changeSubscipRens)
2817 	{  /*lint --e{715}*/
2818 	   SCIP_VAR** vars;
2819 	   int nintvars;
2820 	   int nbinvars;
2821 	   int i;
2822 	
2823 	   assert(SCIPhasCurrentNodeLP(sourcescip));
2824 	   assert(SCIPgetLPSolstat(sourcescip) == SCIP_LPSOLSTAT_OPTIMAL);
2825 	
2826 	   /* get variable information */
2827 	   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2828 	
2829 	   /* restrict bounds of integer variables with fractional solution value */
2830 	   for( i = nbinvars; i < nbinvars + nintvars; ++i )
2831 	   {
2832 	      SCIP_VAR* var = vars[i];
2833 	      SCIP_Real lpsolval = SCIPgetSolVal(sourcescip, NULL, var);
2834 	
2835 	      if( subvars[i] == NULL )
2836 	         continue;
2837 	
2838 	      if( ! SCIPisFeasIntegral(sourcescip, lpsolval) )
2839 	      {
2840 	         SCIP_Real newlb = SCIPfloor(sourcescip, lpsolval);
2841 	         SCIP_Real newub = newlb + 1.0;
2842 	
2843 	         /* only count this as a domain change if the new lower and upper bound are a further restriction */
2844 	         if( newlb > SCIPvarGetLbGlobal(subvars[i]) + 0.5 || newub < SCIPvarGetUbGlobal(subvars[i]) - 0.5 )
2845 	         {
2846 	            SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[i], newlb) );
2847 	            SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[i], newub) );
2848 	            (*ndomchgs)++;
2849 	         }
2850 	      }
2851 	   }
2852 	
2853 	   *success = TRUE;
2854 	
2855 	   return SCIP_OKAY;
2856 	}
2857 	
2858 	/** collect fixings by matching solution values in a collection of solutions for all binary and integer variables,
2859 	 *  or for a custom set of variables
2860 	 */
2861 	static
2862 	SCIP_RETCODE fixMatchingSolutionValues(
2863 	   SCIP*                 scip,               /**< SCIP data structure */
2864 	   SCIP_SOL**            sols,               /**< array of 2 or more solutions. It is okay for the array to contain one element
2865 	                                              *   equal to NULL to represent the current LP solution */
2866 	   int                   nsols,              /**< number of solutions in the array */
2867 	   SCIP_VAR**            vars,               /**< variable array for which solution values must agree */
2868 	   int                   nvars,              /**< number of variables, or -1 for all binary and integer variables */
2869 	   SCIP_VAR**            varbuf,             /**< buffer storage for variable fixings */
2870 	   SCIP_Real*            valbuf,             /**< buffer storage for fixing values */
2871 	   int*                  nfixings            /**< pointer to store the number of fixings */
2872 	   )
2873 	{
2874 	   int v;
2875 	   int nbinintvars;
2876 	   SCIP_SOL* firstsol;
2877 	
2878 	   assert(scip != NULL);
2879 	   assert(sols != NULL);
2880 	   assert(nsols >= 2);
2881 	   assert(varbuf != NULL);
2882 	   assert(valbuf != NULL);
2883 	   assert(nfixings != NULL);
2884 	   assert(*nfixings == 0);
2885 	
2886 	   if( nvars == -1 || vars == NULL )
2887 	   {
2888 	      int nbinvars;
2889 	      int nintvars;
2890 	      SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2891 	      nbinintvars = nbinvars + nintvars;
2892 	      nvars = nbinintvars;
2893 	   }
2894 	   firstsol = sols[0];
2895 	   assert(nvars > 0);
2896 	
2897 	   /* loop over integer and binary variables and check if their solution values match in all solutions */
2898 	   for( v = 0; v < nvars; ++v )
2899 	   {
2900 	      SCIP_Real solval;
2901 	      SCIP_VAR* var;
2902 	      int s;
2903 	
2904 	      var = vars[v];
2905 	      assert((v < SCIPgetNBinVars(scip) && SCIPvarIsBinary(var)) || (v >= SCIPgetNBinVars(scip) && SCIPvarIsIntegral(var)));
2906 	      solval = SCIPgetSolVal(scip, firstsol, var);
2907 	
2908 	      /* determine if solution values match in all given solutions */
2909 	      for( s = 1; s < nsols; ++s )
2910 	      {
2911 	         SCIP_Real solval2 = SCIPgetSolVal(scip, sols[s], var);
2912 	         if( ! SCIPisEQ(scip, solval, solval2) )
2913 	            break;
2914 	      }
2915 	
2916 	      /* if we did not break early, all solutions agree on the solution value of this variable */
2917 	      if( s == nsols )
2918 	      {
2919 	         tryAdd2variableBuffer(scip, var, solval, varbuf, valbuf, nfixings, TRUE);
2920 	      }
2921 	   }
2922 	
2923 	   return SCIP_OKAY;
2924 	}
2925 	
2926 	/** callback to collect variable fixings of RINS */
2927 	static
2928 	DECL_VARFIXINGS(varFixingsRins)
2929 	{
2930 	   /*lint --e{715}*/
2931 	   int nbinvars;
2932 	   int nintvars;
2933 	   SCIP_VAR** vars;
2934 	   SCIP_SOL* incumbent;
2935 	   SCIP_SOL* sols[2];
2936 	   assert(scip != NULL);
2937 	   assert(varbuf != NULL);
2938 	   assert(nfixings != NULL);
2939 	   assert(valbuf != NULL);
2940 	
2941 	   *result = SCIP_DELAYED;
2942 	
2943 	   if( ! SCIPhasCurrentNodeLP(scip) )
2944 	      return SCIP_OKAY;
2945 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2946 	      return SCIP_OKAY;
2947 	
2948 	   *result = SCIP_DIDNOTRUN;
2949 	
2950 	   incumbent = SCIPgetBestSol(scip);
2951 	   if( incumbent == NULL )
2952 	      return SCIP_OKAY;
2953 	
2954 	   if( SCIPsolGetOrigin(incumbent) == SCIP_SOLORIGIN_ORIGINAL )
2955 	      return SCIP_OKAY;
2956 	
2957 	   /* get variable information */
2958 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2959 	
2960 	   /* return if no binary or integer variables are present */
2961 	   if( nbinvars + nintvars == 0 )
2962 	      return SCIP_OKAY;
2963 	
2964 	   sols[0] = NULL;
2965 	   sols[1] = incumbent;
2966 	
2967 	   SCIP_CALL( fixMatchingSolutionValues(scip, sols, 2, vars, nbinvars + nintvars, varbuf, valbuf, nfixings) );
2968 	
2969 	   *result = SCIP_SUCCESS;
2970 	
2971 	   return SCIP_OKAY;
2972 	}
2973 	
2974 	/** initialization callback for crossover when a new problem is read */
2975 	static
2976 	DECL_NHINIT(nhInitCrossover)
2977 	{  /*lint --e{715}*/
2978 	   DATA_CROSSOVER* data;
2979 	
2980 	   data = neighborhood->data.crossover;
2981 	   assert(data != NULL);
2982 	
2983 	   if( data->rng != NULL )
2984 	      SCIPfreeRandom(scip, &data->rng);
2985 	
2986 	   data->selsol = NULL;
2987 	
2988 	   SCIP_CALL( SCIPcreateRandom(scip, &data->rng, CROSSOVERSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );
2989 	
2990 	   return SCIP_OKAY;
2991 	}
2992 	
2993 	/** deinitialization callback for crossover when exiting a problem */
2994 	static
2995 	DECL_NHEXIT(nhExitCrossover)
2996 	{  /*lint --e{715}*/
2997 	   DATA_CROSSOVER* data;
2998 	   data = neighborhood->data.crossover;
2999 	
3000 	   assert(neighborhood != NULL);
3001 	   assert(data->rng != NULL);
3002 	
3003 	   SCIPfreeRandom(scip, &data->rng);
3004 	
3005 	   return SCIP_OKAY;
3006 	}
3007 	
3008 	/** deinitialization callback for crossover before SCIP is freed */
3009 	static
3010 	DECL_NHFREE(nhFreeCrossover)
3011 	{  /*lint --e{715}*/
3012 	   assert(neighborhood->data.crossover != NULL);
3013 	   SCIPfreeBlockMemory(scip, &neighborhood->data.crossover);
3014 	
3015 	   return SCIP_OKAY;
3016 	}
3017 	
3018 	/** callback to collect variable fixings of crossover */
3019 	static
3020 	DECL_VARFIXINGS(varFixingsCrossover)
3021 	{  /*lint --e{715}*/
3022 	   DATA_CROSSOVER* data;
3023 	   SCIP_RANDNUMGEN* rng;
3024 	   SCIP_SOL** sols;
3025 	   SCIP_SOL** scipsols;
3026 	   int nsols;
3027 	   int lastdraw;
3028 	   assert(scip != NULL);
3029 	   assert(varbuf != NULL);
3030 	   assert(nfixings != NULL);
3031 	   assert(valbuf != NULL);
3032 	
3033 	   data = neighborhood->data.crossover;
3034 	
3035 	   assert(data != NULL);
3036 	   nsols = data->nsols;
3037 	   data->selsol = NULL;
3038 	
3039 	   *result = SCIP_DIDNOTRUN;
3040 	
3041 	   /* return if the pool has not enough solutions */
3042 	   if( nsols > SCIPgetNSols(scip) )
3043 	      return SCIP_OKAY;
3044 	
3045 	   /* return if no binary or integer variables are present */
3046 	   if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
3047 	      return SCIP_OKAY;
3048 	
3049 	   rng = data->rng;
3050 	   lastdraw = SCIPgetNSols(scip);
3051 	   SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
3052 	   scipsols = SCIPgetSols(scip);
3053 	
3054 	   /* draw as many solutions from the pool as required by crossover, biased towards
3055 	    * better solutions; therefore, the sorting of the solutions by objective is implicitly used
3056 	    */
3057 	   while( nsols > 0 )
3058 	   {
3059 	      /* no need for randomization anymore, exactly nsols many solutions remain for the selection */
3060 	      if( lastdraw == nsols )
3061 	      {
3062 	         int s;
3063 	
3064 	         /* fill the remaining slots 0,...,nsols - 1 by the solutions at the same places */
3065 	         for( s = 0; s < nsols; ++s )
3066 	            sols[s] = scipsols[s];
3067 	
3068 	         nsols = 0;
3069 	      }
3070 	      else
3071 	      {
3072 	         int nextdraw;
3073 	
3074 	         assert(nsols < lastdraw);
3075 	
3076 	         /* draw from the lastdraw - nsols many solutions nsols - 1, ... lastdraw - 1 such that nsols many solution */
3077 	         nextdraw = SCIPrandomGetInt(rng, nsols - 1, lastdraw - 1);
3078 	         assert(nextdraw >= 0);
3079 	
3080 	         sols[nsols - 1] = scipsols[nextdraw];
3081 	         nsols--;
3082 	         lastdraw = nextdraw;
3083 	      }
3084 	   }
3085 	
3086 	   SCIP_CALL( fixMatchingSolutionValues(scip, sols, data->nsols, NULL, -1, varbuf, valbuf, nfixings) );
3087 	
3088 	   /* store best selected solution as reference solution */
3089 	   data->selsol = sols[0];
3090 	   assert(data->selsol != NULL);
3091 	
3092 	   *result = SCIP_SUCCESS;
3093 	
3094 	   SCIPfreeBufferArray(scip, &sols);
3095 	
3096 	   return SCIP_OKAY;
3097 	}
3098 	
3099 	/** callback for crossover reference solution */
3100 	static
3101 	DECL_NHREFSOL(nhRefsolCrossover)
3102 	{ /*lint --e{715}*/
3103 	   DATA_CROSSOVER* data;
3104 	
3105 	   data = neighborhood->data.crossover;
3106 	
3107 	   if( data->selsol != NULL )
3108 	   {
3109 	      *solptr = data->selsol;
3110 	      *result = SCIP_SUCCESS;
3111 	   }
3112 	   else
3113 	   {
3114 	      *result = SCIP_DIDNOTFIND;
3115 	   }
3116 	
3117 	   return SCIP_OKAY;
3118 	}
3119 	
3120 	/** initialization callback for mutation when a new problem is read */
3121 	static
3122 	DECL_NHINIT(nhInitMutation)
3123 	{  /*lint --e{715}*/
3124 	   DATA_MUTATION* data;
3125 	   assert(scip != NULL);
3126 	   assert(neighborhood != NULL);
3127 	
3128 	   SCIP_CALL( SCIPallocBlockMemory(scip, &neighborhood->data.mutation) );
3129 	
3130 	   data = neighborhood->data.mutation;
3131 	   assert(data != NULL);
3132 	
3133 	   SCIP_CALL( SCIPcreateRandom(scip, &data->rng, MUTATIONSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );
3134 	
3135 	   return SCIP_OKAY;
3136 	}
3137 	
3138 	/** deinitialization callback for mutation when exiting a problem */
3139 	static
3140 	DECL_NHEXIT(nhExitMutation)
3141 	{  /*lint --e{715}*/
3142 	   DATA_MUTATION* data;
3143 	   assert(scip != NULL);
3144 	   assert(neighborhood != NULL);
3145 	   data = neighborhood->data.mutation;
3146 	   assert(data != NULL);
3147 	
3148 	   SCIPfreeRandom(scip, &data->rng);
3149 	
3150 	   SCIPfreeBlockMemory(scip, &neighborhood->data.mutation);
3151 	
3152 	   return SCIP_OKAY;
3153 	}
3154 	
3155 	/** callback to collect variable fixings of mutation */
3156 	static
3157 	DECL_VARFIXINGS(varFixingsMutation)
3158 	{  /*lint --e{715}*/
3159 	   SCIP_RANDNUMGEN* rng;
3160 	
3161 	   SCIP_VAR** vars;
3162 	   SCIP_VAR** varscpy;
3163 	   int i;
3164 	   int nvars;
3165 	   int nbinvars;
3166 	   int nintvars;
3167 	   int nbinintvars;
3168 	   int ntargetfixings;
3169 	   SCIP_SOL* incumbentsol;
3170 	   SCIP_Real targetfixingrate;
3171 	
3172 	   assert(scip != NULL);
3173 	   assert(neighborhood != NULL);
3174 	   assert(neighborhood->data.mutation != NULL);
3175 	   assert(neighborhood->data.mutation->rng != NULL);
3176 	   rng = neighborhood->data.mutation->rng;
3177 	
3178 	   *result = SCIP_DIDNOTRUN;
3179 	
3180 	   /* get the problem variables */
3181 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
3182 	
3183 	   nbinintvars = nbinvars + nintvars;
3184 	   if( nbinintvars == 0 )
3185 	      return SCIP_OKAY;
3186 	
3187 	   incumbentsol = SCIPgetBestSol(scip);
3188 	   if( incumbentsol == NULL )
3189 	      return SCIP_OKAY;
3190 	
3191 	   targetfixingrate = neighborhood->fixingrate.targetfixingrate;
3192 	   ntargetfixings = (int)(targetfixingrate * nbinintvars) + 1;
3193 	
3194 	   /* don't continue if number of discrete variables is too small to reach target fixing rate */
3195 	   if( nbinintvars <= ntargetfixings )
3196 	      return SCIP_OKAY;
3197 	
3198 	   *result = SCIP_DIDNOTFIND;
3199 	
3200 	   /* copy variables into a buffer array */
3201 	   SCIP_CALL( SCIPduplicateBufferArray(scip, &varscpy, vars, nbinintvars) );
3202 	
3203 	   /* partially perturb the array until the number of target fixings is reached */
3204 	   for( i = 0; *nfixings < ntargetfixings && i < nbinintvars; ++i )
3205 	   {
3206 	      int randint = SCIPrandomGetInt(rng, i, nbinintvars - 1);
3207 	      assert(randint < nbinintvars);
3208 	
3209 	      if( randint > i )
3210 	      {
3211 	         SCIPswapPointers((void**)&varscpy[i], (void**)&varscpy[randint]);
3212 	      }
3213 	      /* copy the selected variables and their solution values into the buffer */
3214 	      tryAdd2variableBuffer(scip, varscpy[i], SCIPgetSolVal(scip, incumbentsol, varscpy[i]), varbuf, valbuf, nfixings, TRUE);
3215 	   }
3216 	
3217 	   assert(i == nbinintvars || *nfixings == ntargetfixings);
3218 	
3219 	   /* Not reaching the number of target fixings means that there is a significant fraction (at least 1 - targetfixingrate)
3220 	    * of variables for which the incumbent solution value does not lie within the global bounds anymore. This is a nonsuccess
3221 	    * for the neighborhood (additional fixings are not possible), which is okay because the incumbent solution is
3222 	    * significantly outdated
3223 	    */
3224 	   if( *nfixings == ntargetfixings )
3225 	      *result = SCIP_SUCCESS;
3226 	
3227 	   /* free the buffer array */
3228 	   SCIPfreeBufferArray(scip, &varscpy);
3229 	
3230 	   return SCIP_OKAY;
3231 	}
3232 	
3233 	/** add local branching constraint */
3234 	static
3235 	SCIP_RETCODE addLocalBranchingConstraint(
3236 	   SCIP*                 sourcescip,         /**< source SCIP data structure */
3237 	   SCIP*                 targetscip,         /**< target SCIP data structure */
3238 	   SCIP_VAR**            subvars,            /**< array of sub SCIP variables in same order as source SCIP variables */
3239 	   int                   distance,           /**< right hand side of the local branching constraint */
3240 	   SCIP_Bool*            success,            /**< pointer to store of a local branching constraint has been successfully added */
3241 	   int*                  naddedconss         /**< pointer to increase the number of added constraints */
3242 	   )
3243 	{
3244 	   int nbinvars;
3245 	   int i;
3246 	   SCIP_SOL* referencesol;
3247 	   SCIP_CONS* localbranchcons;
3248 	   SCIP_VAR** vars;
3249 	   SCIP_Real* consvals;
3250 	   SCIP_Real rhs;
3251 	
3252 	   assert(sourcescip != NULL);
3253 	   assert(*success == FALSE);
3254 	
3255 	   nbinvars = SCIPgetNBinVars(sourcescip);
3256 	   vars = SCIPgetVars(sourcescip);
3257 	
3258 	   if( nbinvars <= 3 )
3259 	      return SCIP_OKAY;
3260 	
3261 	   referencesol = SCIPgetBestSol(sourcescip);
3262 	   if( referencesol == NULL )
3263 	      return SCIP_OKAY;
3264 	
3265 	   rhs = (SCIP_Real)distance;
3266 	   rhs = MAX(rhs, 2.0);
3267 	
3268 	   SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars) );
3269 	
3270 	   /* loop over binary variables and fill the local branching constraint */
3271 	   for( i = 0; i < nbinvars; ++i )
3272 	   {
3273 	      /* skip variables that are not present in sub-SCIP */
3274 	      if( subvars[i] == NULL )
3275 	         continue;
3276 	
3277 	      if( SCIPisEQ(sourcescip, SCIPgetSolVal(sourcescip, referencesol, vars[i]), 0.0) )
3278 	         consvals[i] = 1.0;
3279 	      else
3280 	      {
3281 	         consvals[i] = -1.0;
3282 	         rhs -= 1.0;
3283 	      }
3284 	   }
3285 	
3286 	   /* create the local branching constraint in the target scip */
3287 	   SCIP_CALL( SCIPcreateConsBasicLinear(targetscip, &localbranchcons, "localbranch", nbinvars, subvars, consvals, -SCIPinfinity(sourcescip), rhs) );
3288 	   SCIP_CALL( SCIPaddCons(targetscip, localbranchcons) );
3289 	   SCIP_CALL( SCIPreleaseCons(targetscip, &localbranchcons) );
3290 	
3291 	   *naddedconss = 1;
3292 	   *success = TRUE;
3293 	
3294 	   SCIPfreeBufferArray(sourcescip, &consvals);
3295 	
3296 	   return SCIP_OKAY;
3297 	}
3298 	
3299 	/** callback for local branching subproblem changes */
3300 	static
3301 	DECL_CHANGESUBSCIP(changeSubscipLocalbranching)
3302 	{  /*lint --e{715}*/
3303 	
3304 	   SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.2 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );
3305 	
3306 	   return SCIP_OKAY;
3307 	}
3308 	
3309 	/** callback for proximity subproblem changes */
3310 	static
3311 	DECL_CHANGESUBSCIP(changeSubscipProximity)
3312 	{  /*lint --e{715}*/
3313 	   SCIP_SOL* referencesol;
3314 	   SCIP_VAR** vars;
3315 	   int nbinvars;
3316 	   int nintvars;
3317 	   int nvars;
3318 	   int i;
3319 	
3320 	   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
3321 	
3322 	   if( nbinvars == 0 )
3323 	      return SCIP_OKAY;
3324 	
3325 	   referencesol = SCIPgetBestSol(sourcescip);
3326 	   if( referencesol == NULL )
3327 	      return SCIP_OKAY;
3328 	
3329 	   /* loop over binary variables, set objective coefficients based on reference solution in a local branching fashion */
3330 	   for( i = 0; i < nbinvars; ++i )
3331 	   {
3332 	      SCIP_Real newobj;
3333 	
3334 	      /* skip variables not present in sub-SCIP */
3335 	      if( subvars[i] == NULL )
3336 	         continue;
3337 	
3338 	      if( SCIPgetSolVal(sourcescip, referencesol, vars[i]) < 0.5 )
3339 	         newobj = -1.0;
3340 	      else
3341 	         newobj = 1.0;
3342 	      SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], newobj) );
3343 	   }
3344 	
3345 	   /* loop over the remaining variables and change their objective coefficients to 0 */
3346 	   for( ; i < nvars; ++i )
3347 	   {
3348 	      /* skip variables not present in sub-SCIP */
3349 	      if( subvars[i] == NULL )
3350 	         continue;
3351 	
3352 	      SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
3353 	   }
3354 	
3355 	   *nchgobjs = nvars;
3356 	   *success = TRUE;
3357 	
3358 	   return SCIP_OKAY;
3359 	}
3360 	
3361 	/** callback for zeroobjective subproblem changes */
3362 	static
3363 	DECL_CHANGESUBSCIP(changeSubscipZeroobjective)
3364 	{  /*lint --e{715}*/
3365 	   SCIP_CONSHDLR* conshdlrnl;
3366 	   SCIP_VAR** vars;
3367 	   int nvars;
3368 	   int i;
3369 	
3370 	   assert(*success == FALSE);
3371 	
3372 	   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3373 	
3374 	   /* do not run if no objective variables are present */
3375 	   if( SCIPgetNObjVars(sourcescip) == 0 )
3376 	      return SCIP_OKAY;
3377 	
3378 	   /* zeroobj may trigger fixing objvar in nonlinear constraint to infinity,
3379 	    * which expr_var.c:simplify cannot handle at the moment; also #3273
3380 	    */
3381 	   conshdlrnl = SCIPfindConshdlr(sourcescip, "nonlinear");
3382 	   if( conshdlrnl != NULL && SCIPconshdlrGetNActiveConss(conshdlrnl) > 0 )
3383 	      return SCIP_OKAY;
3384 	
3385 	   /* loop over the variables and change their objective coefficients to 0 */
3386 	   for( i = 0; i < nvars; ++i )
3387 	   {
3388 	      /* skip variables not present in sub-SCIP */
3389 	      if( subvars[i] == NULL )
3390 	         continue;
3391 	
3392 	      SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
3393 	   }
3394 	
3395 	   *nchgobjs = nvars;
3396 	   *success = TRUE;
3397 	
3398 	   return SCIP_OKAY;
3399 	}
3400 	
3401 	/** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */
3402 	static
3403 	void computeIntegerVariableBoundsDins(
3404 	   SCIP*                 scip,               /**< SCIP data structure of the original problem */
3405 	   SCIP_VAR*             var,                /**< the variable for which bounds should be computed */
3406 	   SCIP_Real*            lbptr,              /**< pointer to store the lower bound in the DINS sub-SCIP */
3407 	   SCIP_Real*            ubptr               /**< pointer to store the upper bound in the DINS sub-SCIP */
3408 	   )
3409 	{
3410 	   SCIP_Real mipsol;
3411 	   SCIP_Real lpsol;
3412 	
3413 	   SCIP_Real lbglobal;
3414 	   SCIP_Real ubglobal;
3415 	   SCIP_SOL* bestsol;
3416 	
3417 	   /* get the bounds for each variable */
3418 	   lbglobal = SCIPvarGetLbGlobal(var);
3419 	   ubglobal = SCIPvarGetUbGlobal(var);
3420 	
3421 	   assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
3422 	   /* get the current LP solution for each variable */
3423 	   lpsol = SCIPvarGetLPSol(var);
3424 	
3425 	   /* get the current MIP solution for each variable */
3426 	   bestsol = SCIPgetBestSol(scip);
3427 	   mipsol = SCIPgetSolVal(scip, bestsol, var);
3428 	
3429 	   /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
3430 	   if( REALABS(lpsol - mipsol) >= 0.5 )
3431 	   {
3432 	      SCIP_Real range;
3433 	
3434 	      *lbptr = lbglobal;
3435 	      *ubptr = ubglobal;
3436 	
3437 	      /* create an equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
3438 	      range = 2 * lpsol - mipsol;
3439 	
3440 	      if( mipsol >= lpsol )
3441 	      {
3442 	         range = SCIPfeasCeil(scip, range);
3443 	         *lbptr = MAX(*lbptr, range);
3444 	
3445 	         /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
3446 	         if( SCIPisFeasEQ(scip, mipsol, *lbptr) )
3447 	            *ubptr = *lbptr;
3448 	         else
3449 	            *ubptr = mipsol;
3450 	      }
3451 	      else
3452 	      {
3453 	         range = SCIPfeasFloor(scip, range);
3454 	         *ubptr = MIN(*ubptr, range);
3455 	
3456 	         /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
3457 	         if( SCIPisFeasEQ(scip, mipsol, *ubptr) )
3458 	            *lbptr = *ubptr;
3459 	         else
3460 	            *lbptr = mipsol;
3461 	      }
3462 	
3463 	      /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
3464 	      *lbptr = MAX(*lbptr, lbglobal);
3465 	      *ubptr = MIN(*ubptr, ubglobal);
3466 	   }
3467 	   else
3468 	   {
3469 	      /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
3470 	      *lbptr = MAX(mipsol, lbglobal);
3471 	      *ubptr = MIN(mipsol, ubglobal);
3472 	   }
3473 	}
3474 	
3475 	/** callback to collect variable fixings of DINS */
3476 	static
3477 	DECL_VARFIXINGS(varFixingsDins)
3478 	{
3479 	   DATA_DINS* data;
3480 	   SCIP_SOL* rootlpsol;
3481 	   SCIP_SOL** sols;
3482 	   int nsols;
3483 	   int nmipsols;
3484 	   int nbinvars;
3485 	   int nintvars;
3486 	   SCIP_VAR** vars;
3487 	   int v;
3488 	
3489 	   data = neighborhood->data.dins;
3490 	   assert(data != NULL);
3491 	   nmipsols = SCIPgetNSols(scip);
3492 	   nmipsols = MIN(nmipsols, data->npoolsols);
3493 	
3494 	   *result = SCIP_DELAYED;
3495 	
3496 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
3497 	      return SCIP_OKAY;
3498 	
3499 	   *result = SCIP_DIDNOTRUN;
3500 	
3501 	   if( nmipsols == 0 )
3502 	      return SCIP_OKAY;
3503 	
3504 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3505 	
3506 	   if( nbinvars + nintvars == 0 )
3507 	      return SCIP_OKAY;
3508 	
3509 	   SCIP_CALL( SCIPcreateSol(scip, &rootlpsol, NULL) );
3510 	
3511 	   /* save root solution LP values in solution */
3512 	   for( v = 0; v < nbinvars + nintvars; ++v )
3513 	   {
3514 	      SCIP_CALL( SCIPsetSolVal(scip, rootlpsol, vars[v], SCIPvarGetRootSol(vars[v])) );
3515 	   }
3516 	
3517 	   /* add the node and the root LP solution */
3518 	   nsols = nmipsols + 2;
3519 	
3520 	   SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
3521 	   sols[0] = NULL; /* node LP solution */
3522 	   sols[1] = rootlpsol;
3523 	
3524 	   /* copy the remaining MIP solutions after the LP solutions */
3525 	   BMScopyMemoryArray(&sols[2], SCIPgetSols(scip), nmipsols); /*lint !e866*/
3526 	
3527 	   /* 1. Binary variables are fixed if their values agree in all the solutions */
3528 	   if( nbinvars > 0 )
3529 	   {
3530 	      SCIP_CALL( fixMatchingSolutionValues(scip, sols, nsols, vars, nbinvars, varbuf, valbuf, nfixings) );
3531 	   }
3532 	
3533 	   /* 2. Integer variables are fixed if they have a very low distance between the incumbent and the root LP solution */
3534 	   for( v = nbinvars; v < nintvars; ++v )
3535 	   {
3536 	      SCIP_Real lb;
3537 	      SCIP_Real ub;
3538 	      computeIntegerVariableBoundsDins(scip, vars[v], &lb, &ub);
3539 	
3540 	      if( ub - lb < 0.5 )
3541 	      {
3542 	         assert(SCIPisFeasIntegral(scip, lb));
3543 	         tryAdd2variableBuffer(scip, vars[v], lb, varbuf, valbuf, nfixings, TRUE);
3544 	      }
3545 	   }
3546 	
3547 	   *result = SCIP_SUCCESS;
3548 	
3549 	   SCIPfreeBufferArray(scip, &sols);
3550 	
3551 	   SCIP_CALL( SCIPfreeSol(scip, &rootlpsol) );
3552 	
3553 	   return SCIP_OKAY;
3554 	}
3555 	
3556 	/** callback for DINS subproblem changes */
3557 	static
3558 	DECL_CHANGESUBSCIP(changeSubscipDins)
3559 	{  /*lint --e{715}*/
3560 	   SCIP_VAR** vars;
3561 	   int nintvars;
3562 	   int nbinvars;
3563 	   int v;
3564 	
3565 	   SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3566 	
3567 	   /* 1. loop over integer variables and tighten the bounds */
3568 	   for( v = nbinvars; v < nintvars; ++v )
3569 	   {
3570 	      SCIP_Real lb;
3571 	      SCIP_Real ub;
3572 	
3573 	      /* skip variables not present in sub-SCIP */
3574 	      if( subvars[v] == NULL )
3575 	         continue;
3576 	
3577 	      computeIntegerVariableBoundsDins(sourcescip, vars[v], &lb, &ub);
3578 	
3579 	      SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[v], lb) );
3580 	      SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[v], ub) );
3581 	      ++(*ndomchgs);
3582 	   }
3583 	
3584 	   /* 2. add local branching constraint for binary variables */
3585 	   SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.1 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );
3586 	
3587 	   *success = TRUE;
3588 	
3589 	   return SCIP_OKAY;
3590 	}
3591 	
3592 	/** deinitialization callback for DINS before SCIP is freed */
3593 	static
3594 	DECL_NHFREE(nhFreeDins)
3595 	{
3596 	   assert(neighborhood->data.dins != NULL);
3597 	
3598 	   SCIPfreeBlockMemory(scip, &neighborhood->data.dins);
3599 	
3600 	   return SCIP_OKAY;
3601 	}
3602 	
3603 	/** deinitialization callback for trustregion before SCIP is freed */
3604 	static
3605 	DECL_NHFREE(nhFreeTrustregion)
3606 	{
3607 	   assert(neighborhood->data.trustregion != NULL);
3608 	
3609 	   SCIPfreeBlockMemory(scip, &neighborhood->data.trustregion);
3610 	
3611 	   return SCIP_OKAY;
3612 	}
3613 	
3614 	/** add trust region neighborhood constraint and auxiliary objective variable */
3615 	static
3616 	DECL_CHANGESUBSCIP(changeSubscipTrustregion)
3617 	{  /*lint --e{715}*/
3618 	   DATA_TRUSTREGION* data;
3619 	
3620 	   assert(success != NULL);
3621 	
3622 	   if( !SCIPgetBestSol(sourcescip) )
3623 	   {
3624 	      SCIPdebugMsg(sourcescip, "changeSubscipTrustregion unsuccessful, because it was called without incumbent being present\n");
3625 	      *success = FALSE;
3626 	
3627 	      return SCIP_OKAY;
3628 	   }
3629 	
3630 	   data = neighborhood->data.trustregion;
3631 	
3632 	   /* adding the neighborhood constraint for the trust region heuristic */
3633 	   SCIP_CALL( SCIPaddTrustregionNeighborhoodConstraint(sourcescip, targetscip, subvars, data->violpenalty) );
3634 	
3635 	   /* incrementing the change in objective since an additional variable is added to the objective to penalize the
3636 	    * violation of the trust region.
3637 	    */
3638 	   ++(*nchgobjs);
3639 	
3640 	   return SCIP_OKAY;
3641 	}
3642 	
3643 	/** callback that returns the incumbent solution as a reference point */
3644 	static
3645 	DECL_NHREFSOL(nhRefsolIncumbent)
3646 	{  /*lint --e{715}*/
3647 	   assert(scip != NULL);
3648 	
3649 	   if( SCIPgetBestSol(scip) != NULL )
3650 	   {
3651 	      *result = SCIP_SUCCESS;
3652 	      *solptr = SCIPgetBestSol(scip);
3653 	   }
3654 	   else
3655 	   {
3656 	      *result = SCIP_DIDNOTFIND;
3657 	   }
3658 	
3659 	   return SCIP_OKAY;
3660 	}
3661 	
3662 	
3663 	/** callback function that deactivates a neighborhood on problems with no discrete variables */
3664 	static
3665 	DECL_NHDEACTIVATE(nhDeactivateDiscreteVars)
3666 	{ /*lint --e{715}*/
3667 	   assert(scip != NULL);
3668 	   assert(deactivate != NULL);
3669 	
3670 	   /* deactivate if no discrete variables are present */
3671 	   *deactivate = (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0);
3672 	
3673 	   return SCIP_OKAY;
3674 	}
3675 	
3676 	/** callback function that deactivates a neighborhood on problems with no binary variables */
3677 	static
3678 	DECL_NHDEACTIVATE(nhDeactivateBinVars)
3679 	{ /*lint --e{715}*/
3680 	   assert(scip != NULL);
3681 	   assert(deactivate != NULL);
3682 	
3683 	   /* deactivate if no discrete variables are present */
3684 	   *deactivate = (SCIPgetNBinVars(scip) == 0);
3685 	
3686 	   return SCIP_OKAY;
3687 	}
3688 	
3689 	/** callback function that deactivates a neighborhood on problems with no objective variables */
3690 	static
3691 	DECL_NHDEACTIVATE(nhDeactivateObjVars)
3692 	{ /*lint --e{715}*/
3693 	   assert(scip != NULL);
3694 	   assert(deactivate != NULL);
3695 	
3696 	   /* deactivate if no discrete variables are present */
3697 	   *deactivate = (SCIPgetNObjVars(scip) == 0);
3698 	
3699 	   return SCIP_OKAY;
3700 	}
3701 	
3702 	
3703 	/** include all neighborhoods */
3704 	static
3705 	SCIP_RETCODE includeNeighborhoods(
3706 	   SCIP*                 scip,               /**< SCIP data structure */
3707 	   SCIP_HEURDATA*        heurdata            /**< heuristic data of the ALNS heuristic */
3708 	   )
3709 	{
3710 	   NH* rens;
3711 	   NH* rins;
3712 	   NH* mutation;
3713 	   NH* localbranching;
3714 	   NH* crossover;
3715 	   NH* proximity;
3716 	   NH* zeroobjective;
3717 	   NH* dins;
3718 	   NH* trustregion;
3719 	
3720 	   heurdata->nneighborhoods = 0;
3721 	
3722 	   /* include the RENS neighborhood */
3723 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &rens, "rens",
3724 	         DEFAULT_MINFIXINGRATE_RENS, DEFAULT_MAXFIXINGRATE_RENS, DEFAULT_ACTIVE_RENS, DEFAULT_PRIORITY_RENS,
3725 	         varFixingsRens, changeSubscipRens, NULL, NULL, NULL, NULL, nhDeactivateDiscreteVars) );
3726 	
3727 	   /* include the RINS neighborhood */
3728 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &rins, "rins",
3729 	         DEFAULT_MINFIXINGRATE_RINS, DEFAULT_MAXFIXINGRATE_RINS, DEFAULT_ACTIVE_RINS, DEFAULT_PRIORITY_RINS,
3730 	         varFixingsRins, NULL, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );
3731 	
3732 	   /* include the mutation neighborhood */
3733 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &mutation, "mutation",
3734 	         DEFAULT_MINFIXINGRATE_MUTATION, DEFAULT_MAXFIXINGRATE_MUTATION, DEFAULT_ACTIVE_MUTATION, DEFAULT_PRIORITY_MUTATION,
3735 	         varFixingsMutation, NULL, nhInitMutation, nhExitMutation, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );
3736 	
3737 	   /* include the local branching neighborhood */
3738 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &localbranching, "localbranching",
3739 	         DEFAULT_MINFIXINGRATE_LOCALBRANCHING, DEFAULT_MAXFIXINGRATE_LOCALBRANCHING, DEFAULT_ACTIVE_LOCALBRANCHING, DEFAULT_PRIORITY_LOCALBRANCHING,
3740 	         NULL, changeSubscipLocalbranching, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );
3741 	
3742 	   /* include the crossover neighborhood */
3743 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &crossover, "crossover",
3744 	         DEFAULT_MINFIXINGRATE_CROSSOVER, DEFAULT_MAXFIXINGRATE_CROSSOVER, DEFAULT_ACTIVE_CROSSOVER, DEFAULT_PRIORITY_CROSSOVER,
3745 	         varFixingsCrossover, NULL,
3746 	         nhInitCrossover, nhExitCrossover, nhFreeCrossover, nhRefsolCrossover, nhDeactivateDiscreteVars) );
3747 	
3748 	   /* allocate data for crossover to include the parameter */
3749 	   SCIP_CALL( SCIPallocBlockMemory(scip, &crossover->data.crossover) );
3750 	   crossover->data.crossover->rng = NULL;
3751 	
3752 	   /* add crossover neighborhood parameters */
3753 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/alns/crossover/nsols", "the number of solutions that crossover should combine",
3754 	         &crossover->data.crossover->nsols, TRUE, DEFAULT_NSOLS_CROSSOVER, 2, 10, NULL, NULL) );
3755 	
3756 	   /* include the Proximity neighborhood */
3757 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &proximity, "proximity",
3758 	         DEFAULT_MINFIXINGRATE_PROXIMITY, DEFAULT_MAXFIXINGRATE_PROXIMITY, DEFAULT_ACTIVE_PROXIMITY, DEFAULT_PRIORITY_PROXIMITY,
3759 	         NULL, changeSubscipProximity, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );
3760 	
3761 	   /* include the Zeroobjective neighborhood */
3762 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &zeroobjective, "zeroobjective",
3763 	         DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE, DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE, DEFAULT_ACTIVE_ZEROOBJECTIVE, DEFAULT_PRIORITY_ZEROOBJECTIVE,
3764 	         NULL, changeSubscipZeroobjective, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateObjVars) );
3765 	
3766 	   /* include the DINS neighborhood */
3767 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &dins, "dins",
3768 	         DEFAULT_MINFIXINGRATE_DINS, DEFAULT_MAXFIXINGRATE_DINS, DEFAULT_ACTIVE_DINS, DEFAULT_PRIORITY_DINS,
3769 	         varFixingsDins, changeSubscipDins, NULL, NULL, nhFreeDins, nhRefsolIncumbent, nhDeactivateBinVars) );
3770 	
3771 	   /* allocate data for DINS to include the parameter */
3772 	   SCIP_CALL( SCIPallocBlockMemory(scip, &dins->data.dins) );
3773 	
3774 	   /* add DINS neighborhood parameters */
3775 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/alns/dins/npoolsols",
3776 	         "number of pool solutions where binary solution values must agree",
3777 	         &dins->data.dins->npoolsols, TRUE, DEFAULT_NPOOLSOLS_DINS, 1, 100, NULL, NULL) );
3778 	
3779 	   /* include the trustregion neighborhood */
3780 	   SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &trustregion, "trustregion",
3781 	         DEFAULT_MINFIXINGRATE_TRUSTREGION, DEFAULT_MAXFIXINGRATE_TRUSTREGION, DEFAULT_ACTIVE_TRUSTREGION, DEFAULT_PRIORITY_TRUSTREGION,
3782 	         NULL, changeSubscipTrustregion, NULL, NULL, nhFreeTrustregion, nhRefsolIncumbent, nhDeactivateBinVars) );
3783 	
3784 	   /* allocate data for trustregion to include the parameter */
3785 	   SCIP_CALL( SCIPallocBlockMemory(scip, &trustregion->data.trustregion) );
3786 	
3787 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/trustregion/violpenalty",
3788 	         "the penalty for each change in the binary variables from the candidate solution",
3789 	         &trustregion->data.trustregion->violpenalty, FALSE, DEFAULT_VIOLPENALTY_TRUSTREGION, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3790 	
3791 	   return SCIP_OKAY;
3792 	}
3793 	
3794 	/** initialization method of primal heuristic (called after problem was transformed) */
3795 	static
3796 	SCIP_DECL_HEURINIT(heurInitAlns)
3797 	{  /*lint --e{715}*/
3798 	   SCIP_HEURDATA* heurdata;
3799 	   int i;
3800 	
3801 	   assert(scip != NULL);
3802 	   assert(heur != NULL);
3803 	
3804 	   heurdata = SCIPheurGetData(heur);
3805 	   assert(heurdata != NULL);
3806 	
3807 	   /* reactivate all neighborhoods if a new problem is read in */
3808 	   heurdata->nactiveneighborhoods = heurdata->nneighborhoods;
3809 	
3810 	   /* initialize neighborhoods for new problem */
3811 	   for( i = 0; i < heurdata->nneighborhoods; ++i )
3812 	   {
3813 	      NH* neighborhood = heurdata->neighborhoods[i];
3814 	
3815 	      SCIP_CALL( neighborhoodInit(scip, neighborhood) );
3816 	
3817 	      SCIP_CALL( resetFixingRate(scip, &neighborhood->fixingrate) );
3818 	
3819 	      SCIP_CALL( neighborhoodStatsReset(scip, &neighborhood->stats) );
3820 	   }
3821 	
3822 	   /* open reward file for reading */
3823 	   if( strncasecmp(heurdata->rewardfilename, DEFAULT_REWARDFILENAME, strlen(DEFAULT_REWARDFILENAME)) != 0 )
3824 	   {
3825 	      heurdata->rewardfile = fopen(heurdata->rewardfilename, "w");
3826 	
3827 	      if( heurdata->rewardfile == NULL )
3828 	      {
3829 	         SCIPerrorMessage("Error: Could not open reward file <%s>\n", heurdata->rewardfilename);
3830 	         return SCIP_FILECREATEERROR;
3831 	      }
3832 	
3833 	      SCIPdebugMsg(scip, "Writing reward information to <%s>\n", heurdata->rewardfilename);
3834 	   }
3835 	   else
3836 	      heurdata->rewardfile = NULL;
3837 	
3838 	   return SCIP_OKAY;
3839 	}
3840 	
3841 	
3842 	/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
3843 	static
3844 	SCIP_DECL_HEURINITSOL(heurInitsolAlns)
3845 	{  /*lint --e{715}*/
3846 	   SCIP_HEURDATA* heurdata;
3847 	   int i;
3848 	   SCIP_Real* priorities;
3849 	   unsigned int initseed;
3850 	
3851 	   assert(scip != NULL);
3852 	   assert(heur != NULL);
3853 	
3854 	   heurdata = SCIPheurGetData(heur);
3855 	   assert(heurdata != NULL);
3856 	   heurdata->nactiveneighborhoods = heurdata->nneighborhoods;
3857 	
3858 	   SCIP_CALL( SCIPallocBufferArray(scip, &priorities, heurdata->nactiveneighborhoods) );
3859 	
3860 	   /* init neighborhoods for new problem by resetting their statistics and fixing rate */
3861 	   for( i = heurdata->nneighborhoods - 1; i >= 0; --i )
3862 	   {
3863 	      NH* neighborhood = heurdata->neighborhoods[i];
3864 	      SCIP_Bool deactivate;
3865 	
3866 	      SCIP_CALL( neighborhood->nhdeactivate(scip, &deactivate) );
3867 	
3868 	      /* disable inactive neighborhoods */
3869 	      if( deactivate || ! neighborhood->active )
3870 	      {
3871 	         if( heurdata->nactiveneighborhoods - 1 > i )
3872 	         {
3873 	            assert(heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]->active);
3874 	            SCIPswapPointers((void **)&heurdata->neighborhoods[i], (void **)&heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]);
3875 	         }
3876 	         heurdata->nactiveneighborhoods--;
3877 	      }
3878 	   }
3879 	
3880 	   /* collect neighborhood priorities */
3881 	   for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
3882 	      priorities[i] = heurdata->neighborhoods[i]->priority;
3883 	
3884 	   initseed = (unsigned int)(heurdata->seed + SCIPgetNVars(scip));
3885 	
3886 	   /* active neighborhoods might change between init calls, reset functionality must take this into account */
3887 	   if( heurdata->bandit != NULL && SCIPbanditGetNActions(heurdata->bandit) != heurdata->nactiveneighborhoods )
3888 	   {
3889 	      SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
3890 	
3891 	      heurdata->bandit = NULL;
3892 	   }
3893 	
3894 	   if( heurdata->nactiveneighborhoods > 0 )
3895 	   {  /* create or reset bandit algorithm */
3896 	      if( heurdata->bandit == NULL )
3897 	      {
3898 	         SCIP_CALL( createBandit(scip, heurdata, priorities, initseed) );
3899 	
3900 	         resetMinimumImprovement(heurdata);
3901 	         resetTargetNodeLimit(heurdata);
3902 	      }
3903 	      else if( heurdata->resetweights )
3904 	      {
3905 	         SCIP_CALL( SCIPresetBandit(scip, heurdata->bandit, priorities, initseed) );
3906 	
3907 	         resetMinimumImprovement(heurdata);
3908 	         resetTargetNodeLimit(heurdata);
3909 	      }
3910 	   }
3911 	
3912 	   heurdata->usednodes = 0;
3913 	   heurdata->ninitneighborhoods = heurdata->nactiveneighborhoods;
3914 	
3915 	   heurdata->lastcallsol = NULL;
3916 	   heurdata->firstcallthissol = 0;
3917 	
3918 	   resetCurrentNeighborhood(heurdata);
3919 	
3920 	   SCIPfreeBufferArray(scip, &priorities);
3921 	
3922 	   return SCIP_OKAY;
3923 	}
3924 	
3925 	
3926 	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
3927 	static
3928 	SCIP_DECL_HEUREXIT(heurExitAlns)
3929 	{  /*lint --e{715}*/
3930 	   SCIP_HEURDATA* heurdata;
3931 	   int i;
3932 	
3933 	   assert(scip != NULL);
3934 	   assert(heur != NULL);
3935 	
3936 	   heurdata = SCIPheurGetData(heur);
3937 	   assert(heurdata != NULL);
3938 	
3939 	   /* free neighborhood specific data */
3940 	   for( i = 0; i < heurdata->nneighborhoods; ++i )
3941 	   {
3942 	      NH* neighborhood = heurdata->neighborhoods[i];
3943 	
3944 	      SCIP_CALL( neighborhoodExit(scip, neighborhood) );
3945 	   }
3946 	
3947 	   if( heurdata->rewardfile != NULL )
3948 	   {
3949 	      fclose(heurdata->rewardfile);
3950 	      heurdata->rewardfile = NULL;
3951 	   }
3952 	
3953 	   return SCIP_OKAY;
3954 	}
3955 	
3956 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
3957 	static
3958 	SCIP_DECL_HEURFREE(heurFreeAlns)
3959 	{  /*lint --e{715}*/
3960 	   SCIP_HEURDATA* heurdata;
3961 	   int i;
3962 	
3963 	   assert(scip != NULL);
3964 	   assert(heur != NULL);
3965 	
3966 	   heurdata = SCIPheurGetData(heur);
3967 	   assert(heurdata != NULL);
3968 	
3969 	   /* bandits are only initialized if a problem has been read */
3970 	   if( heurdata->bandit != NULL )
3971 	   {
3972 	      SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
3973 	   }
3974 	
3975 	   /* free neighborhoods */
3976 	   for( i = 0; i < heurdata->nneighborhoods; ++i )
3977 	   {
3978 	      SCIP_CALL( alnsFreeNeighborhood(scip, &(heurdata->neighborhoods[i])) );
3979 	   }
3980 	
3981 	   SCIPfreeBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS);
3982 	
3983 	   SCIPfreeBlockMemory(scip, &heurdata);
3984 	
3985 	   return SCIP_OKAY;
3986 	}
3987 	
3988 	/** output method of statistics table to output file stream 'file' */
3989 	static
3990 	SCIP_DECL_TABLEOUTPUT(tableOutputNeighborhood)
3991 	{ /*lint --e{715}*/
3992 	   SCIP_HEURDATA* heurdata;
3993 	
3994 	   assert(SCIPfindHeur(scip, HEUR_NAME) != NULL);
3995 	   heurdata = SCIPheurGetData(SCIPfindHeur(scip, HEUR_NAME));
3996 	   assert(heurdata != NULL);
3997 	
3998 	   printNeighborhoodStatistics(scip, heurdata, file);
3999 	
4000 	   return SCIP_OKAY;
4001 	}
4002 	
4003 	/*
4004 	 * primal heuristic specific interface methods
4005 	 */
4006 	
4007 	/** creates the alns primal heuristic and includes it in SCIP */
4008 	SCIP_RETCODE SCIPincludeHeurAlns(
4009 	   SCIP*                 scip                /**< SCIP data structure */
4010 	   )
4011 	{
4012 	   SCIP_HEURDATA* heurdata;
4013 	   SCIP_HEUR* heur;
4014 	
4015 	   /* create alns primal heuristic data */
4016 	   heurdata = NULL;
4017 	   heur = NULL;
4018 	
4019 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
4020 	   BMSclearMemory(heurdata);
4021 	
4022 	   /* TODO make this a user parameter? */
4023 	   heurdata->lplimfac = LPLIMFAC;
4024 	
4025 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS) );
4026 	
4027 	   /* include primal heuristic */
4028 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
4029 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
4030 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAlns, heurdata) );
4031 	
4032 	   assert(heur != NULL);
4033 	
4034 	   /* include all neighborhoods */
4035 	   SCIP_CALL( includeNeighborhoods(scip, heurdata) );
4036 	
4037 	   /* set non fundamental callbacks via setter functions */
4038 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAlns) );
4039 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAlns) );
4040 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAlns) );
4041 	   SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolAlns) );
4042 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitAlns) );
4043 	
4044 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/shownbstats",
4045 	         "show statistics on neighborhoods?",
4046 	         &heurdata->shownbstats, TRUE, DEFAULT_SHOWNBSTATS, NULL, NULL) );
4047 	
4048 	   /* add alns primal heuristic parameters */
4049 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
4050 	         "maximum number of nodes to regard in the subproblem",
4051 	         &heurdata->maxnodes,  TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4052 	
4053 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
4054 	         "offset added to the nodes budget",
4055 	         &heurdata->nodesoffset, FALSE, DEFAULT_NODESOFFSET, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4056 	
4057 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
4058 	         "minimum number of nodes required to start a sub-SCIP",
4059 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4060 	
4061 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
4062 	         "number of nodes since last incumbent solution that the heuristic should wait",
4063 	         &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4064 	
4065 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
4066 	         "fraction of nodes compared to the main SCIP for budget computation",
4067 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
4068 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquotmin",
4069 	         "lower bound fraction of nodes compared to the main SCIP for budget computation",
4070 	         &heurdata->nodesquotmin, FALSE, DEFAULT_NODESQUOTMIN, 0.0, 1.0, NULL, NULL) );
4071 	
4072 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/startminimprove",
4073 	         "initial factor by which ALNS should at least improve the incumbent",
4074 	         &heurdata->startminimprove, TRUE, DEFAULT_STARTMINIMPROVE, 0.0, 1.0, NULL, NULL) );
4075 	
4076 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprovelow",
4077 	         "lower threshold for the minimal improvement over the incumbent",
4078 	         &heurdata->minimprovelow, TRUE, DEFAULT_MINIMPROVELOW, 0.0, 1.0, NULL, NULL) );
4079 	
4080 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprovehigh",
4081 	         "upper bound for the minimal improvement over the incumbent",
4082 	         &heurdata->minimprovehigh, TRUE, DEFAULT_MINIMPROVEHIGH, 0.0, 1.0, NULL, NULL) );
4083 	
4084 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nsolslim",
4085 	         "limit on the number of improving solutions in a sub-SCIP call",
4086 	         &heurdata->nsolslim, FALSE, DEFAULT_NSOLSLIM, -1, INT_MAX, NULL, NULL) );
4087 	
4088 	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/banditalgo",
4089 	         "the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy, exp.3-(i)x",
4090 	         &heurdata->banditalgo, TRUE, DEFAULT_BANDITALGO, "uegib", NULL, NULL) );
4091 	
4092 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gamma",
4093 	         "weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3",
4094 	         &heurdata->exp3_gamma, TRUE, DEFAULT_GAMMA, 0.0, 1.0, NULL, NULL) );
4095 	
4096 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/beta",
4097 	         "reward offset between 0 and 1 at every observation for Exp.3",
4098 	         &heurdata->exp3_beta, TRUE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL) );
4099 	
4100 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha",
4101 	         "parameter to increase the confidence width in UCB",
4102 	         &heurdata->ucb_alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.0, NULL, NULL) );
4103 	
4104 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedistances",
4105 	         "distances from fixed variables be used for variable prioritization",
4106 	         &heurdata->usedistances, TRUE, DEFAULT_USEDISTANCES, NULL, NULL) );
4107 	
4108 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useredcost",
4109 	         "should reduced cost scores be used for variable prioritization?",
4110 	         &heurdata->useredcost, TRUE, DEFAULT_USEREDCOST, NULL, NULL) );
4111 	
4112 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/domorefixings",
4113 	         "should the ALNS heuristic do more fixings by itself based on variable prioritization "
4114 	         "until the target fixing rate is reached?",
4115 	         &heurdata->domorefixings, TRUE, DEFAULT_DOMOREFIXINGS, NULL, NULL) );
4116 	
4117 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjustfixingrate",
4118 	         "should the heuristic adjust the target fixing rate based on the success?",
4119 	         &heurdata->adjustfixingrate, TRUE, DEFAULT_ADJUSTFIXINGRATE, NULL, NULL) );
4120 	
4121 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usesubscipheurs",
4122 	         "should the heuristic activate other sub-SCIP heuristics during its search?",
4123 	         &heurdata->usesubscipheurs, TRUE, DEFAULT_USESUBSCIPHEURS, NULL, NULL) );
4124 	
4125 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rewardcontrol",
4126 	         "reward control to increase the weight of the simple solution indicator and decrease the weight of the closed gap reward",
4127 	         &heurdata->rewardcontrol, TRUE, DEFAULT_REWARDCONTROL, 0.0, 1.0, NULL, NULL) );
4128 	
4129 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/targetnodefactor",
4130 	         "factor by which target node number is eventually increased",
4131 	         &heurdata->targetnodefactor, TRUE, DEFAULT_TARGETNODEFACTOR, 1.0, 1e+5, NULL, NULL) );
4132 	
4133 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/seed",
4134 	         "initial random seed for bandit algorithms and random decisions by neighborhoods",
4135 	         &heurdata->seed, FALSE, DEFAULT_SEED, 0, INT_MAX, NULL, NULL) );
4136 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcallssamesol",
4137 	         "number of allowed executions of the heuristic on the same incumbent solution (-1: no limit, 0: number of active neighborhoods)",
4138 	         &heurdata->maxcallssamesol, TRUE, DEFAULT_MAXCALLSSAMESOL, -1, 100, NULL, NULL) );
4139 	
4140 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjustminimprove",
4141 	         "should the factor by which the minimum improvement is bound be dynamically updated?",
4142 	         &heurdata->adjustminimprove, TRUE, DEFAULT_ADJUSTMINIMPROVE, NULL, NULL) );
4143 	
4144 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjusttargetnodes",
4145 	         "should the target nodes be dynamically adjusted?",
4146 	         &heurdata->adjusttargetnodes, TRUE, DEFAULT_ADJUSTTARGETNODES, NULL, NULL) );
4147 	
4148 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/eps",
4149 	         "increase exploration in epsilon-greedy bandit algorithm",
4150 	         &heurdata->epsgreedy_eps, TRUE, DEFAULT_EPS, 0.0, 1.0, NULL, NULL) );
4151 	
4152 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rewardbaseline",
4153 	         "the reward baseline to separate successful and failed calls",
4154 	         &heurdata->rewardbaseline, TRUE, DEFAULT_REWARDBASELINE, 0.0, 0.99, NULL, NULL) );
4155 	
4156 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/resetweights",
4157 	         "should the bandit algorithms be reset when a new problem is read?",
4158 	         &heurdata->resetweights, TRUE, DEFAULT_RESETWEIGHTS, NULL, NULL) );
4159 	
4160 	   SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/rewardfilename", "file name to store all rewards and the selection of the bandit",
4161 	         &heurdata->rewardfilename, TRUE, DEFAULT_REWARDFILENAME, NULL, NULL) );
4162 	
4163 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/subsciprandseeds",
4164 	         "should random seeds of sub-SCIPs be altered to increase diversification?",
4165 	         &heurdata->subsciprandseeds, TRUE, DEFAULT_SUBSCIPRANDSEEDS, NULL, NULL) );
4166 	
4167 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scalebyeffort",
4168 	         "should the reward be scaled by the effort?",
4169 	         &heurdata->scalebyeffort, TRUE, DEFAULT_SCALEBYEFFORT, NULL, NULL) );
4170 	
4171 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
4172 	         "should cutting planes be copied to the sub-SCIP?",
4173 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
4174 	
4175 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/fixtol",
4176 	         "tolerance by which the fixing rate may be missed without generic fixing",
4177 	         &heurdata->fixtol, TRUE, DEFAULT_FIXTOL, 0.0, 1.0, NULL, NULL) );
4178 	
4179 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/unfixtol",
4180 	         "tolerance by which the fixing rate may be exceeded without generic unfixing",
4181 	         &heurdata->unfixtol, TRUE, DEFAULT_UNFIXTOL, 0.0, 1.0, NULL, NULL) );
4182 	
4183 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselocalredcost",
4184 	         "should local reduced costs be used for generic (un)fixing?",
4185 	         &heurdata->uselocalredcost, TRUE, DEFAULT_USELOCALREDCOST, NULL, NULL) );
4186 	
4187 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usepscost",
4188 	         "should pseudo cost scores be used for variable priorization?",
4189 	         &heurdata->usepscost, TRUE, DEFAULT_USEPSCOST, NULL, NULL) );
4190 	
4191 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/initduringroot",
4192 	         "should the heuristic be executed multiple times during the root node?",
4193 	         &heurdata->initduringroot, TRUE, DEFAULT_INITDURINGROOT, NULL, NULL) );
4194 	
4195 	   assert(SCIPfindTable(scip, TABLE_NAME_NEIGHBORHOOD) == NULL);
4196 	   SCIP_CALL( SCIPincludeTable(scip, TABLE_NAME_NEIGHBORHOOD, TABLE_DESC_NEIGHBORHOOD, TRUE,
4197 	         NULL, NULL, NULL, NULL, NULL, NULL, tableOutputNeighborhood,
4198 	         NULL, TABLE_POSITION_NEIGHBORHOOD, TABLE_EARLIEST_STAGE_NEIGHBORHOOD) );
4199 	
4200 	   return SCIP_OKAY;
4201 	}
4202